/*
 Copyright (C) 2010 Kuri-Applications

 KeyList.h - declarations of CMyKeyList and CMyStringKeyList[A/W]
 */

#ifndef __KEYLIST_H__
#define __KEYLIST_H__

#pragma once

#define IsAddress(var, size) (HIWORD(var) != 0)

typedef void* _INDEX;

template<class TYPE, class KEY, KEY DefKey = NULL>
class CMyKeyList
{
protected:
	struct CMyKeyListItem
	{
		_INDEX unused;
		CMyKeyListItem* pNext;
		KEY key;
		TYPE value;
	};

	void Construct()
	{
		m_nCount = 0;
		m_pFirst = NULL;
		memset(&m_empty, 0, sizeof(m_empty));
		m_empty.pNext = NULL;
	}

public:
	CMyKeyList()
		{ Construct(); }

	int GetCount() const
		{ return m_nCount; }

	BOOL IsEmpty() const
		{ return m_nCount == 0; }

	void Remove(int nIndex)
	{
		CMyKeyListItem* pItem = m_pFirst;
		CMyKeyListItem* pPrev = NULL;
		for (int n = 0; n < m_nCount && pItem != NULL; n++)
		{
			if (n == nIndex)
				break;
			pPrev = pItem;
			pItem = pItem->pNext;
		}
		if (pItem == NULL)
			return;
		if (pPrev != NULL)
			pPrev->pNext = pItem->pNext;
		if (m_pFirst == pItem)
			m_pFirst = pItem->pNext;
		m_nCount--;
		DeleteItem(pItem);
	}

	void Remove(KEY key)
	{
		int n = IndexFromKey(key);
		if (n == -1)
			return;
		Remove((_INDEX) IntToPtr(n));
	}

	void Remove(_INDEX aIndex)
	{
		CMyKeyListItem* pItem = NULL;
		CMyKeyListItem* pPrev = NULL;
		if (IsAddress(aIndex, sizeof(_INDEX)))
		{
			pItem = m_pFirst;
			for (int n = 0; n < m_nCount; n++)
			{
				if (pItem == (CMyKeyListItem*) aIndex)
					break;
				pPrev = pItem;
				pItem = pItem->pNext;
			}
			pItem = (CMyKeyListItem*) aIndex;
		}
		else
		{
			int nIndex = (int) PtrToInt(aIndex);
			pItem = m_pFirst;
			for (int n = 0; n < m_nCount && pItem != NULL; n++)
			{
				if (n == nIndex)
					break;
				pPrev = pItem;
				pItem = pItem->pNext;
			}
		}
		if (pItem == NULL)
			return;
		if (pPrev != NULL)
			pPrev->pNext = pItem->pNext;
		if (m_pFirst == pItem)
			m_pFirst = pItem->pNext;
		m_nCount--;
		DeleteItem(pItem);
	}

	void RemoveAll()
	{
		CMyKeyListItem* pItem = m_pFirst;
		CMyKeyListItem* pDel;
		while (pItem != NULL)
		{
			pDel = pItem;
			pItem = pItem->pNext;
			DeleteItem(pDel);
		}
		m_pFirst = NULL;
		m_nCount = 0;
	}

	_INDEX Add(TYPE value, KEY key = DefKey)
	{
		if (m_nCount == 65535)
			return NULL;
		CMyKeyListItem* pItem = CreateItem(value, key);
		if (m_pFirst == NULL)
			m_pFirst = pItem;
		else
		{
			CMyKeyListItem* pLast = GetLastItem();
			pLast->pNext = pItem;
		}
		m_nCount++;
		return (_INDEX) pItem;
	}

	TYPE GetItem(KEY key) const
	{
		int n = IndexFromKey(key);
		if (n == -1)
			return m_empty.value;
		return GetItem((_INDEX) IntToPtr(n));
	}

	TYPE GetItem(int nIndex) const
	{
		CMyKeyListItem* pItem = m_pFirst;
		for (int n = 0; n < m_nCount && pItem != NULL; n++)
		{
			if (n == nIndex)
				return pItem->value;
			pItem = pItem->pNext;
		}

		return m_empty.value;
	}

	TYPE GetItem(_INDEX ind) const
	{
		if (IsAddress(ind, sizeof(_INDEX)))
		{
			CMyKeyListItem* pItem = (CMyKeyListItem*) ind;
			return pItem->value;
		}
		else
		{
			int nIndex = (int) PtrToInt(ind);
			CMyKeyListItem* pItem = m_pFirst;
			for (int n = 0; n < m_nCount && pItem != NULL; n++)
			{
				if (n == nIndex)
					return pItem->value;
				pItem = pItem->pNext;
			}

			return m_empty.value;
		}
	}

	TYPE& GetItemVar(KEY key)
	{
		int n = IndexFromKey(key);
		if (n == -1)
			return m_empty.value;
		return GetItemVar((_INDEX) n);
	}

	TYPE& GetItemVar(int nIndex)
	{
		CMyKeyListItem* pItem = m_pFirst;
		for (int n = 0; n < m_nCount && pItem != NULL; n++)
		{
			if (n == nIndex)
				return pItem->value;
			pItem = pItem->pNext;
		}

		return m_empty.value;
	}

	TYPE& GetItemVar(_INDEX ind)
	{
		if (IsAddress(ind, sizeof(_INDEX)))
		{
			CMyKeyListItem* pItem = (CMyKeyListItem*) ind;
			return pItem->value;
		}
		else
		{
			int nIndex = (int) ind;
			CMyKeyListItem* pItem = m_pFirst;
			for (int n = 0; n < m_nCount && pItem != NULL; n++)
			{
				if (n == nIndex)
					return pItem->value;
				pItem = pItem->pNext;
			}

			return m_empty.value;
		}
	}

	KEY IndexToKey(int nIndex) const
	{
		CMyKeyListItem* pItem = GetItemData(nIndex);
		if (pItem == NULL)
			return DefKey;
		return pItem->key;
	}

	KEY IndexToKey(_INDEX aIndex) const
	{
		if (IsAddress(aIndex, sizeof(_INDEX)))
			return ((CMyKeyListItem*) aIndex)->key;
		return IndexToKey((int) PtrToInt(aIndex));
	}

	int IndexFromKey(KEY key) const
	{
		CMyKeyListItem* pItem = m_pFirst;
		int n = 0;
		while (pItem != NULL)
		{
			if (CompareKey(key, pItem->key))
				return n;
			n++;
			pItem = pItem->pNext;
		}
		return -1;
	}

	BOOL IsItemKey(KEY key) const
	{
		CMyKeyListItem* pItem = m_pFirst;
		while (pItem != NULL)
		{
			if (CompareKey(key, pItem->key))
				return TRUE;
			pItem = pItem->pNext;
		}
		return FALSE;
	}

	_INDEX InsertItem(int nIndex, TYPE value, KEY key = DefKey)
	{
		if (nIndex > m_nCount || m_nCount == 65535)
			return NULL;
		CMyKeyListItem* pItem = CreateItem(value, key);
		CMyKeyListItem* pBefore = NULL;
		if (nIndex == m_nCount)
		{
			if (m_nCount == 0)
				m_pFirst = pItem;
			else
			{
				pBefore = GetLastItem();
				pBefore->pNext = pItem;
			}
		}
		else
		{
			pBefore = GetItemData(nIndex);
			if (pBefore != NULL)
			{
				CMyKeyListItem* pPrev = GetPrevItem(pBefore);
				if (pPrev != NULL)
					pPrev->pNext = pItem;
				pItem->pNext = pBefore;
			}
			else
				return NULL;
		}
		m_nCount++;
		return (_INDEX) pItem;
	}

	BOOL SetItem(int nIndex, TYPE value, KEY NewKey = DefKey)
	{
		CMyKeyListItem* pItem = GetItemData(nIndex);
		if (pItem == NULL)
			return FALSE;
		pItem->value = value;
		if (NewKey != DefKey)
		{
			DestructKey(&pItem->key);
			pItem->key = CreateCopyKey(NewKey);
		}
		return TRUE;
	}

	BOOL SetItem(KEY key, TYPE value, KEY NewKey = DefKey)
	{
		int n = IndexFromKey(key);
		if (n == -1)
			return FALSE;
		return SetItem((_INDEX) IntToPtr(n), value, NewKey);
	}

	BOOL SetItem(_INDEX ind, TYPE value, KEY NewKey = DefKey)
	{
		if (IsAddress(ind, sizeof(_INDEX)))
		{
			CMyKeyListItem* pItem = (CMyKeyListItem*) ind;
			pItem->value = value;
			if (NewKey != DefKey)
			{
				DestructKey(&pItem->key);
				pItem->key = CreateCopyKey(NewKey);
			}
			return TRUE;
		}
		else
		{
			int nIndex = (int) ind;
			CMyKeyListItem* pItem = GetItemData(nIndex);
			if (pItem == NULL)
				return FALSE;
			pItem->value = value;
			if (NewKey != DefKey)
			{
				DestructKey(&pItem->key);
				pItem->key = CreateCopyKey(NewKey);
			}
			return TRUE;
		}
	}

	BOOL SetItemEx(KEY key, TYPE value)
	{
		if (IsItemKey(key))
			return SetItem(key, value);
		else
			return Add(value, key) != NULL;
	}

	_INDEX Find(TYPE value, _INDEX start = NULL)
	{
		CMyKeyListItem* pItem;
		if (start == NULL)
			pItem = m_pFirst;
		else if (IsAddress(start, sizeof(_INDEX)))
			pItem = (CMyKeyListItem*) start;
		else
			pItem = GetItemData((int) start);
		while (pItem != NULL)
		{
			if (pItem->value == value)
				return (_INDEX) pItem;
		}
		return NULL;
	}

	_INDEX PositionFromKey(KEY key)
	{
		CMyKeyListItem* pItem = m_pFirst;
		while (pItem != NULL)
		{
			if (CompareKey(pItem->key, key))
				return (_INDEX) pItem;
			pItem = pItem->pNext;
		}
		return NULL;
	}

	_INDEX GetFirstItemPosition() const
	{
		return (_INDEX) m_pFirst;
	}

	int GetNextItem(_INDEX& rIndex, TYPE& rValue, KEY& rKey) const
	{
		CMyKeyListItem* pItem = (CMyKeyListItem*) rIndex;
		if (pItem == NULL)
			return -1;
		rIndex = (_INDEX) pItem->pNext;
		rValue = pItem->value;
		rKey = CreateCopyKey(pItem->key);
		if (rIndex == NULL)
			return 0;
		return 1;
	}

	TYPE GetNextItem(_INDEX& rIndex, KEY* pKey = NULL) const
	{
		CMyKeyListItem* pItem = (CMyKeyListItem*) rIndex;
		if (pItem == NULL)
			return m_empty.value;
		rIndex = (_INDEX) pItem->pNext;
		if (pKey != NULL)
			*pKey = CreateCopyKey(pItem->key);
		return pItem->value;
	}

	int GetUpperBound() const
	{
		return m_nCount;
	}

public:
	void SetEmptyItem(TYPE value, KEY key = DefKey)
	{
		DestructKey(&m_empty.key);
		m_empty.value = value;
		m_empty.key = CreateCopyKey(key);
	}

	TYPE operator [] (int nIndex) const
		{ return GetItem(nIndex); }
	TYPE operator [] (_INDEX aIndex) const
		{ return GetItem(aIndex); }
	TYPE operator [] (KEY key) const
		{ return GetItem(key); }
	TYPE& operator [] (int nIndex)
		{ return GetItemVar(nIndex); }
	TYPE& operator [] (_INDEX aIndex)
		{ return GetItemVar(aIndex); }
	TYPE& operator [] (KEY key)
		{ return GetItemVar(key); }

protected:
	int m_nCount;
	CMyKeyListItem* m_pFirst;
	CMyKeyListItem m_empty;

	CMyKeyListItem* GetLastItem() const
	{
		CMyKeyListItem* pItem = m_pFirst;
		int n = 0;
		if (pItem == NULL)
			return NULL;
		CMyKeyListItem* pNext = pItem->pNext;
		n = 1;
		while (pNext != NULL)
		{
			pItem = pNext;
			pNext = pItem->pNext;
			n++;
		}
		if (m_nCount != n)
		{
			CMyKeyList<TYPE, KEY, DefKey>* pThis = const_cast<CMyKeyList<TYPE, KEY, DefKey>*>(this);
			pThis->m_nCount = n;
		}
		return pItem;
	}

	CMyKeyListItem* GetPrevItem(CMyKeyListItem* pItem) const
	{
		CMyKeyListItem* p = m_pFirst;
		CMyKeyListItem* pPrev = NULL;
		while (p != pItem)
		{
			pPrev = p;
			p = p->pNext;
		}
		return pPrev;
	}

	CMyKeyListItem* GetItemData(int nIndex) const
	{
		CMyKeyListItem* pItem = m_pFirst;
		for (int n = 0; n < m_nCount && pItem != NULL; n++)
		{
			if (n == nIndex)
				return pItem;
			pItem = pItem->pNext;
		}
		return NULL;
	}

	virtual KEY CreateCopyKey(KEY key) const
	{
		return key;
	}

	virtual void DestructKey(KEY* pKey) const
	{
		*pKey = DefKey;
	}

	virtual BOOL CompareKey(KEY key1, KEY key2) const
	{
		return key1 == key2;
	}

	virtual CMyKeyListItem* CreateItem(TYPE value, KEY key) const
	{
		CMyKeyListItem* pItem = (CMyKeyListItem*) malloc(sizeof(CMyKeyListItem));
		memset(pItem, 0, sizeof(CMyKeyListItem));
		new (pItem) CMyKeyListItem;
		pItem->value = value;
		pItem->key = CreateCopyKey(key);
		return pItem;
	}

	virtual void DeleteItem(CMyKeyListItem* pItem) const
	{
		DestructKey(&pItem->key);
		pItem->~CMyKeyListItem();
		free((void*) pItem);
	}

public:
	~CMyKeyList()
	{
		RemoveAll();
		//Assert(m_nCount == 0);
	}
};

template <class TYPE> class CMyStringKeyListA : public CMyKeyList<TYPE, LPCSTR, NULL>
{
protected:
	virtual LPCSTR CreateCopyKey(LPCSTR key) const
	{
		return _strdup(key);
	}
	virtual void DestructKey(LPCSTR* pKey) const
	{
		free((LPSTR) *pKey);
		*pKey = NULL;
	}
	virtual BOOL CompareKey(LPCSTR key1, LPCSTR key2) const
	{
		return _stricmp(key1, key2) == 0;
	}
};

template <class TYPE> class CMyStringKeyListW : public CMyKeyList<TYPE, LPCWSTR, NULL>
{
protected:
	virtual LPCWSTR CreateCopyKey(LPCWSTR key) const
	{
		return _wcsdup(key);
	}
	virtual void DestructKey(LPCWSTR* pKey) const
	{
		free((LPWSTR) *pKey);
		*pKey = NULL;
	}
	virtual BOOL CompareKey(LPCWSTR key1, LPCWSTR key2) const
	{
		return _wcsicmp(key1, key2) == 0;
	}
};

#endif // __KEYLIST_H__
