/*******************************************************************************
The content of this file includes portions of the AUDIOKINETIC Wwise Technology
released in source code form as part of the SDK installer package.

Commercial License Usage

Licensees holding valid commercial licenses to the AUDIOKINETIC Wwise Technology
may use this file in accordance with the end user license agreement provided 
with the software or, alternatively, in accordance with the terms contained in a
written agreement between you and Audiokinetic Inc.

Apache License Usage

Alternatively, this file may be used under the Apache License, Version 2.0 (the 
"Apache License"); you may not use this file except in compliance with the 
Apache License. You may obtain a copy of the Apache License at 
http://www.apache.org/licenses/LICENSE-2.0.

Unless required by applicable law or agreed to in writing, software distributed
under the Apache License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES
OR CONDITIONS OF ANY KIND, either express or implied. See the Apache License for
the specific language governing permissions and limitations under the License.

  Copyright (c) 2023 Audiokinetic Inc.
*******************************************************************************/

#ifndef _AKHASHLIST_H
#define _AKHASHLIST_H

#include <AK/Tools/Common/AkKeyDef.h>// for MapStruct
#include <AK/Tools/Common/AkObject.h>
#include <AK/Tools/Common/AkArray.h>

// NOTE: when using this template, a hashing function of the following form must be available: 
//
// AkHashType AkHash( T_KEY );

typedef AkUInt32 AkHashType;

template < class T_KEY >
AkForceInline AkHashType AkHash(T_KEY in_key) { return (AkHashType)in_key; }

#define AK_HASH_SIZE_VERY_SMALL 11
static const AkHashType kHashSizes[] = { 29, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741 };
static const size_t kNumHashSizes = sizeof(kHashSizes) / sizeof(kHashSizes[0]);
static const AkReal32 kHashTableGrowthFactor = 0.9f; 

template < class T_KEY, class T_ITEM, typename T_ALLOC = ArrayPoolDefault >
class AkHashList: public T_ALLOC
{
public:
	
    struct Item
	{
		Item * pNextItem;               // our next one
		MapStruct<T_KEY, T_ITEM> Assoc;	// key-item association
	};

	typedef AkArray<Item*, Item*, T_ALLOC, AkGrowByPolicy_NoGrow > HashTableArray;

	struct Iterator
	{
		typename AkHashList<T_KEY,T_ITEM,T_ALLOC>::HashTableArray* pTable;
		AkHashType uiTable;
		Item* pItem;

		inline Iterator& operator++()
		{
			AKASSERT( pItem );
			pItem = pItem->pNextItem;
			
			while ( ( pItem == NULL ) && ( ++uiTable < pTable->Length() ) )
				pItem = (*pTable)[ uiTable ];

			return *this;
		}

		inline MapStruct<T_KEY, T_ITEM>& operator*()
		{
			AKASSERT( pItem );
			return pItem->Assoc;
		}

		inline MapStruct<T_KEY, T_ITEM>* operator->()
		{
			AKASSERT(pItem);
			return &pItem->Assoc;
		}

		bool operator ==(const Iterator& in_rOp) const
		{
			return pItem == in_rOp.pItem;
		}

		bool operator !=( const Iterator& in_rOp ) const
		{
			return !operator==(in_rOp);
		}
	};

	struct ConstIterator
	{
		const typename AkHashList<T_KEY, T_ITEM, T_ALLOC>::HashTableArray* pTable;
		AkHashType uiTable;
		Item* pItem;

		inline ConstIterator& operator++()
		{
			AKASSERT(pItem);
			pItem = pItem->pNextItem;

			while ((pItem == NULL) && (++uiTable < pTable->Length()))
				pItem = (*pTable)[uiTable];

			return *this;
		}

		inline const MapStruct<T_KEY, T_ITEM>& operator*()
		{
			AKASSERT(pItem);
			return pItem->Assoc;
		}

		inline MapStruct<T_KEY, T_ITEM>* operator->() const
		{
			AKASSERT(pItem);
			return &pItem->Assoc;
		}

		bool operator ==(const ConstIterator& in_rOp) const
		{
			return pItem == in_rOp.pItem;
		}

		bool operator !=(const ConstIterator& in_rOp) const
		{
			return !operator==(in_rOp);
		}
	};

	// The IteratorEx iterator is intended for usage when a possible erase may occurs
	// when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
	struct IteratorEx : public Iterator
	{
		Item* pPrevItem;

		IteratorEx& operator++()
		{
			AKASSERT( this->pItem );
			
			pPrevItem = this->pItem;
			this->pItem = this->pItem->pNextItem;
			
			while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
			{
				pPrevItem = NULL;
				this->pItem = (*this->pTable)[ this->uiTable ];
			}

			return *this;
		}
	};

	struct ConstIteratorEx : public ConstIterator
	{
		Item* pPrevItem;

		ConstIteratorEx& operator++()
		{
			AKASSERT(this->pItem);

			pPrevItem = this->pItem;
			this->pItem = this->pItem->pNextItem;

			while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
			{
				pPrevItem = NULL;
				this->pItem = (*this->pTable)[this->uiTable];
			}

			return *this;
		}
	};

	Iterator Begin()
	{
		Iterator returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = 0;
			returnedIt.pItem = m_table[0];

			while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
				returnedIt.pItem = m_table[returnedIt.uiTable];
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
		}

		return returnedIt;
	}

	ConstIterator Begin() const
	{
		ConstIterator returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = 0;
			returnedIt.pItem = m_table[0];

			while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
				returnedIt.pItem = m_table[returnedIt.uiTable];
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
		}

		return returnedIt;
	}

	IteratorEx BeginEx()
	{
		IteratorEx returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = 0;
			returnedIt.pItem = *(m_table.Begin());
			returnedIt.pPrevItem = NULL;

			while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
				returnedIt.pItem = m_table[returnedIt.uiTable];
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
		}

		return returnedIt;
	}

	ConstIteratorEx BeginEx() const
	{
		ConstIteratorEx returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = 0;
			returnedIt.pItem = *(m_table.Begin());
			returnedIt.pPrevItem = NULL;

			while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
				returnedIt.pItem = m_table[returnedIt.uiTable];
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
		}

		return returnedIt;
	}

	inline Iterator End()
	{
		Iterator returnedIt;
		returnedIt.pItem = NULL;
		return returnedIt;
	}

	inline ConstIterator End() const
	{
		ConstIterator returnedIt;
		returnedIt.pItem = NULL;
		return returnedIt;
	}

	inline IteratorEx EndEx()
	{
		IteratorEx returnedIt;
		returnedIt.pItem = NULL;
		return returnedIt;
	}

	inline ConstIterator EndEx() const
	{
		ConstIteratorEx returnedIt;
		returnedIt.pItem = NULL;
		return returnedIt;
	}

	IteratorEx FindEx( T_KEY in_Key )
	{
		IteratorEx returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = AkHash(in_Key) % HashSize();
			returnedIt.pItem = m_table.Length() > 0 ? m_table[returnedIt.uiTable] : NULL;
			returnedIt.pPrevItem = NULL;

			while (returnedIt.pItem != NULL)
			{
				if (returnedIt.pItem->Assoc.key == in_Key)
					break;

				returnedIt.pPrevItem = returnedIt.pItem;
				returnedIt.pItem = returnedIt.pItem->pNextItem;
			}
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
			returnedIt.pPrevItem = NULL;
		}

		return returnedIt;
	}

	ConstIteratorEx FindEx(T_KEY in_Key) const
	{
		ConstIteratorEx returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = AkHash(in_Key) % HashSize();
			returnedIt.pItem = m_table.Length() > 0 ? m_table[returnedIt.uiTable] : NULL;
			returnedIt.pPrevItem = NULL;

			while (returnedIt.pItem != NULL)
			{
				if (returnedIt.pItem->Assoc.key == in_Key)
					break;

				returnedIt.pPrevItem = returnedIt.pItem;
				returnedIt.pItem = returnedIt.pItem->pNextItem;
			}
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
			returnedIt.pPrevItem = NULL;
		}

		return returnedIt;
	}

	AkHashList(): m_uiSize( 0 )
	{
	}

	~AkHashList()
	{
		AKASSERT(m_uiSize == 0);
		m_table.Term();
	}

	void Term()
	{
		RemoveAll();
		m_table.Term();
	}

	void RemoveAll()
	{
		for (AkHashType i = 0; i < HashSize(); ++i)
		{
			Item * pItem = m_table[ i ];
			while ( pItem != NULL )
			{
				Item * pNextItem = pItem->pNextItem;
				pItem->Assoc.item.~T_ITEM();
				T_ALLOC::Free( pItem );
				pItem = pNextItem;
			}
			
			m_table[ i ] = NULL;
		}

		m_uiSize = 0;
	}

	T_ITEM * Exists( T_KEY in_Key )
	{
		if (HashSize() > 0)
		{
			AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
			return ExistsInList(in_Key, uiTable);
		}
		return NULL;
	}

	// Set using an externally preallocated Item -- Hash list takes ownership of the Item.
	T_ITEM * Set( Item * in_pItem )
	{
		if (CheckSize())
		{
			AkHashType uiTable = AkHash(in_pItem->Assoc.key) % HashSize();

			AKASSERT(!ExistsInList(in_pItem->Assoc.key, uiTable)); // Item must not exist in list !

			// Add new entry

			in_pItem->pNextItem = m_table[uiTable];
			m_table[uiTable] = in_pItem;

			++m_uiSize;

			return &(in_pItem->Assoc.item);
		}

		return NULL;
	}

	T_ITEM * Set( T_KEY in_Key )
	{
		if ( CheckSize() )
		{
			AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
			T_ITEM * pItem = ExistsInList(in_Key, uiTable);
			if (pItem)
				return pItem;

			return CreateEntry(in_Key, uiTable);
		}

		return NULL;
	}

	T_ITEM * Set( T_KEY in_Key, bool& out_bWasAlreadyThere )
	{
		if (CheckSize())
		{
			AkHashType uiTable = AkHash(in_Key) % HashSize();
			T_ITEM * pItem = ExistsInList(in_Key, uiTable);
			if (pItem)
			{
				out_bWasAlreadyThere = true;
				return pItem;
			}
			else
			{
				out_bWasAlreadyThere = false;
			}

			return CreateEntry(in_Key, uiTable);
		}

		return NULL;
	}

	void Unset( T_KEY in_Key )
	{
		if (HashSize() > 0)
		{
			AkHashType uiTable = AkHash(in_Key) % HashSize();
			Item * pItem = m_table[uiTable];
			Item * pPrevItem = NULL;
			while (pItem != NULL)
			{
				if (pItem->Assoc.key == in_Key)
					break;

				pPrevItem = pItem;
				pItem = pItem->pNextItem;
			}

			if (pItem)
				RemoveItem(uiTable, pItem, pPrevItem);
		}
	}

	IteratorEx Erase( const IteratorEx& in_rIter )
	{
		IteratorEx returnedIt;
		returnedIt.pTable = in_rIter.pTable;
		returnedIt.uiTable = in_rIter.uiTable;
		returnedIt.pItem = in_rIter.pItem->pNextItem;
		returnedIt.pPrevItem = in_rIter.pPrevItem;
		
		while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
		{
			returnedIt.pPrevItem = NULL;
			returnedIt.pItem = (*returnedIt.pTable)[returnedIt.uiTable];
		}
		
		RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );

		return returnedIt;
	}

	void RemoveItem( AkHashType in_uiTable, Item* in_pItem, Item* in_pPrevItem )
	{
		if( in_pPrevItem ) 
			in_pPrevItem->pNextItem = in_pItem->pNextItem;
		else
			m_table[ in_uiTable ] = in_pItem->pNextItem;

		in_pItem->Assoc.item.~T_ITEM();
		T_ALLOC::Free(in_pItem);

		--m_uiSize;
	}

	AkUInt32 Length() const
	{
		return m_uiSize;
	}

	AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
	{
		if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
			return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));

		return AK_Success;
	}

	AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
	{
		AKRESULT res = AK_Fail;

		AkUInt32 uNewSize = 0;
		for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
		{
			if (kHashSizes[i] > in_uExpectedNumberOfEntires)
			{
				uNewSize = kHashSizes[i];
				break;
			}
		}

		if (uNewSize > 0)
		{
			HashTableArray oldArray;
			oldArray.Transfer(m_table);

			if ( m_table.GrowArray(uNewSize) )
			{
				for (AkUInt32 i = 0; i < uNewSize; i++)
					m_table.AddLast(NULL);

				for (AkUInt32 i = 0; i < oldArray.Length(); i++)
				{
					Item * pItem = oldArray[i];
					while (pItem != NULL)
					{
						Item * pNextItem = pItem->pNextItem;
						{
							AkHashType uiTable = AkHash(pItem->Assoc.key) % HashSize();
							pItem->pNextItem = m_table[uiTable];
							m_table[uiTable] = pItem;
						}
						pItem = pNextItem;
					}
				}

				oldArray.Term();

				res = AK_Success;
			}
			else
			{
				//Backpedal..
				m_table.Transfer(oldArray);
			}
		}

		return res;
	}

	inline AkUInt32 HashSize() const
	{
		return m_table.Length();
	}

	inline bool CheckSize() 
	{
		if ( HashSize() == 0 || (AkReal32)m_uiSize / (AkReal32)HashSize() > kHashTableGrowthFactor )
			Resize(HashSize());

		return (HashSize() > 0);
	}

	void Transfer(AkHashList< T_KEY, T_ITEM, T_ALLOC >& in_source)
	{
		Term();

		m_table.Transfer(in_source.m_table);
		m_uiSize = in_source.m_uiSize;

		in_source.m_uiSize = 0;
	}

protected:
	T_ITEM * ExistsInList( T_KEY in_Key, AkUIntPtr in_uiTable )
	{
		AKASSERT(HashSize() > 0);
		
		Item * pItem = m_table[(AkUInt32)in_uiTable];
		while (pItem != NULL)
		{
			if (pItem->Assoc.key == in_Key)
				return &(pItem->Assoc.item); // found

			pItem = pItem->pNextItem;
		}

		return NULL; // not found
	}

	T_ITEM * CreateEntry( T_KEY in_Key, AkUIntPtr in_uiTable )
	{
		Item * pNewItem = (Item *)T_ALLOC::Alloc(sizeof(Item));
		if ( pNewItem == NULL )
			return NULL;

		pNewItem->pNextItem = m_table[ (AkUInt32)in_uiTable ];
		pNewItem->Assoc.key = in_Key;

		AkPlacementNew( &(pNewItem->Assoc.item) ) T_ITEM; 

		m_table[(AkUInt32)in_uiTable] = pNewItem;

		++m_uiSize;

		return &(pNewItem->Assoc.item);
	}

	HashTableArray m_table;
	AkUInt32 m_uiSize;
};

// this one lets you define the structure
// only requirement is that T_MAPSTRUCT must have members pNextItem and key.
// client is responsible for allocation/deallocation of T_MAPSTRUCTS.
template <class T_KEY, class T_MAPSTRUCT>
struct AkHashListBareMemberPolicy
{
	static const T_KEY& Key(const T_MAPSTRUCT* in_pItem) {return in_pItem->key;}
	static T_MAPSTRUCT*& Next(T_MAPSTRUCT* in_pItem) { return (*in_pItem).pNextItem; }
};

template <class T_KEY, class T_MAPSTRUCT>
struct AkHashListBareFuncPolicy
{
	static const T_KEY& Key(const T_MAPSTRUCT* in_pItem) { return in_pItem->Key(); }
	static T_MAPSTRUCT*& Next(T_MAPSTRUCT* in_pItem) { return (*in_pItem).pNextItem; }
};

template <class T_KEY, class T_MAPSTRUCT>
using AkDefaultHashListBarePolicy = AkHashListBareMemberPolicy<T_KEY, T_MAPSTRUCT>;

template <class T_KEY, class T_MAPSTRUCT, typename T_ALLOC = ArrayPoolDefault, class KEY_POLICY = AkDefaultHashListBarePolicy<T_KEY, T_MAPSTRUCT>, class LIST_POLICY = AkDefaultHashListBarePolicy<T_KEY, T_MAPSTRUCT>>
class AkHashListBare
{
	typedef AkArray<T_MAPSTRUCT*, T_MAPSTRUCT*, T_ALLOC, AkGrowByPolicy_NoGrow > HashTableArray;
public:
	struct Iterator
	{
		typename AkHashListBare<T_KEY,T_MAPSTRUCT,T_ALLOC,KEY_POLICY,LIST_POLICY>::HashTableArray* pTable;
		AkHashType uiTable;
		T_MAPSTRUCT* pItem;

		inline Iterator& operator++()
		{
			AKASSERT( pItem );
			pItem = LIST_POLICY::Next(pItem);
			
			while ((pItem == NULL) && (++uiTable < pTable->Length()))
				pItem = (*pTable)[ uiTable ];

			return *this;
		}

		inline T_MAPSTRUCT * operator*()
		{
			AKASSERT( pItem );
			return pItem;
		}

		inline T_MAPSTRUCT* operator->()
		{
			AKASSERT(pItem);
			return pItem;
		}

		bool operator !=( const Iterator& in_rOp ) const
		{
			return ( pItem != in_rOp.pItem );
		}		

		bool operator ==(const Iterator& in_rOp) const
		{
			return (pItem == in_rOp.pItem);
		}
	};

	struct ConstIterator
	{
		const typename AkHashListBare<T_KEY, T_MAPSTRUCT, T_ALLOC, KEY_POLICY>::HashTableArray* pTable;
		AkHashType uiTable;
		T_MAPSTRUCT* pItem;

		inline ConstIterator& operator++()
		{
			AKASSERT(pItem);
			pItem = pItem->pNextItem;

			while ((pItem == NULL) && (++uiTable < pTable->Length()))
				pItem = (*pTable)[uiTable];

			return *this;
		}

		inline const T_MAPSTRUCT* operator*()
		{
			AKASSERT(pItem);
			return pItem;
		}

		inline const T_MAPSTRUCT* operator->() const
		{
			AKASSERT(pItem);
			return pItem;
		}

		bool operator !=(const ConstIterator& in_rOp) const
		{
			return (pItem != in_rOp.pItem);
		}

		bool operator ==(const ConstIterator& in_rOp) const
		{
			return (pItem == in_rOp.pItem);
		}
	};

	// The IteratorEx iterator is intended for usage when a possible erase may occurs
	// when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
	struct IteratorEx : public Iterator
	{
		T_MAPSTRUCT* pPrevItem;

		IteratorEx& operator++()
		{
			AKASSERT(this->pItem);

			pPrevItem = this->pItem;
			this->pItem = this->pItem->pNextItem;

			while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
			{
				pPrevItem = NULL;
				this->pItem = (*this->pTable)[this->uiTable];
			}

			return *this;
		}
	};

	struct ConstIteratorEx : public ConstIterator
	{
		T_MAPSTRUCT* pPrevItem;

		ConstIteratorEx& operator++()
		{
			AKASSERT( this->pItem );
			
			pPrevItem = this->pItem;
			this->pItem = LIST_POLICY::Next(this->pItem);
			
			while ( ( this->pItem == NULL ) && ( ++this->uiTable < this->pTable->Length() ) )
			{
				pPrevItem = NULL;
				this->pItem = (*this->pTable)[ this->uiTable ];
			}

			return *this;
		}
	};

	Iterator Begin()
	{
		Iterator returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = 0;
			returnedIt.pItem = m_table[0];

			while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
				returnedIt.pItem = m_table[returnedIt.uiTable];
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
		}

		return returnedIt;
	}

	ConstIterator Begin() const
	{
		ConstIterator returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = 0;
			returnedIt.pItem = m_table[0];

			while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
				returnedIt.pItem = m_table[returnedIt.uiTable];
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
		}

		return returnedIt;
	}

	IteratorEx BeginEx()
	{
		IteratorEx returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = 0;
			returnedIt.pItem = m_table[0];
			returnedIt.pPrevItem = NULL;
		
			while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
				returnedIt.pItem = m_table[ returnedIt.uiTable ];
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
			returnedIt.pPrevItem = NULL;
		}

		return returnedIt;
	}

	ConstIteratorEx BeginEx() const
	{
		ConstIteratorEx returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = 0;
			returnedIt.pItem = m_table[0];
			returnedIt.pPrevItem = NULL;

			while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
				returnedIt.pItem = m_table[returnedIt.uiTable];
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
			returnedIt.pPrevItem = NULL;
		}

		return returnedIt;
	}

	inline Iterator End()
	{
		Iterator returnedIt;
		returnedIt.pItem = NULL;
		return returnedIt;
	}

	inline ConstIterator End() const
	{
		ConstIterator returnedIt;
		returnedIt.pItem = NULL;
		return returnedIt;
	}

	IteratorEx FindEx( T_KEY in_Key )
	{
		IteratorEx returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = AkHash(in_Key) % HashSize();
			returnedIt.pItem = m_table[returnedIt.uiTable];
			returnedIt.pPrevItem = NULL;

			while (returnedIt.pItem != NULL)
			{
				if (KEY_POLICY::Key(returnedIt.pItem) == in_Key)
					break;

				returnedIt.pPrevItem = returnedIt.pItem;
				returnedIt.pItem = LIST_POLICY::Next(returnedIt.pItem);
			}
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
			returnedIt.pPrevItem = NULL;
		}

		return returnedIt;
	}

	ConstIteratorEx FindEx(T_KEY in_Key) const
	{
		ConstIteratorEx returnedIt;

		if (HashSize() > 0)
		{
			returnedIt.pTable = &m_table;
			returnedIt.uiTable = AkHash(in_Key) % HashSize();
			returnedIt.pItem = m_table[returnedIt.uiTable];
			returnedIt.pPrevItem = NULL;

			while (returnedIt.pItem != NULL)
			{
				if (KEY_POLICY::Key(returnedIt.pItem) == in_Key)
					break;

				returnedIt.pPrevItem = returnedIt.pItem;
				returnedIt.pItem = returnedIt.pItem->pNextItem;
			}
		}
		else
		{
			returnedIt.pTable = NULL;
			returnedIt.uiTable = 0;
			returnedIt.pItem = NULL;
			returnedIt.pPrevItem = NULL;
		}

		return returnedIt;
	}

	AkHashListBare()
		: m_uiSize( 0 )
	{
	}

	~AkHashListBare()
	{
	}

	//If you set 0 as the starting size, you *must* check all returns of Set() calls.
	//If you initialize with anything else, you can ignore return codes of Set(), they will always succeed.
	bool Init(AkUInt32 in_iStartingSize)
	{
		m_uiSize = 0;

		if(!m_table.Resize(in_iStartingSize))
			return false;

		for ( AkHashType i = 0; i < HashSize(); ++i )
			m_table[ i ] = NULL;
		
		return true;
	}

	void Term()
	{
		AKASSERT( m_uiSize == 0 );
		m_table.Term();
	}
/*
	void RemoveAll()
	{
		for ( AkHashType i = 0; i < HashSize(); ++i )
		{
			T_MAPSTRUCT * pItem = m_table[ i ];
			while ( pItem != NULL )
			{
				T_MAPSTRUCT * pNextItem = LIST_POLICY::Next(pItem);
				pItem->~T_MAPSTRUCT();
				T_ALLOD::Free( pItem );
				pItem = pNextItem;
			}
			
			m_table[ i ] = NULL;
		}

		m_uiSize = 0;
	}
*/
	T_MAPSTRUCT * Exists( T_KEY in_Key ) const
	{
		if (HashSize() > 0)
		{
			AkHashType uiTable = AkHash(in_Key) % HashSize();
			return ExistsInList(in_Key, uiTable);
		}
		return NULL;
	}

	// Set using an externally preallocated T_MAPSTRUCT -- Hash list takes ownership of the T_MAPSTRUCT.
	bool Set( T_MAPSTRUCT * in_pItem, bool& out_exists )
	{
		out_exists = false;
		if (CheckSize())
		{
			AkHashType uiTable = AkHash(KEY_POLICY::Key(in_pItem)) % HashSize();
			if (ExistsInList(KEY_POLICY::Key(in_pItem), uiTable))
			{
				out_exists = true;
				return false;
			}

			_Set(in_pItem, uiTable);
			return true;
		}
		//This can only happen if the initial size of the map was 0.
		return false;
	}

	bool Set( T_MAPSTRUCT * in_pItem )
	{
		if (CheckSize())
		{
			AkHashType uiTable = AkHash(KEY_POLICY::Key(in_pItem)) % HashSize();
			AKASSERT(!ExistsInList(KEY_POLICY::Key(in_pItem), uiTable)); // T_MAPSTRUCT must not exist in list !
			_Set(in_pItem, uiTable);
			return true;
		}
		//This can only happen if the initial size of the map was 0.
		return false;
	}

private:
	void _Set( T_MAPSTRUCT * in_pItem, AkHashType in_uiTable )
	{
		LIST_POLICY::Next(in_pItem) = m_table[in_uiTable];
		m_table[in_uiTable] = in_pItem;
		++m_uiSize;
	}

public:
	T_MAPSTRUCT * Unset( const T_KEY &in_Key )
	{
		T_MAPSTRUCT * pItem = NULL;

		if (HashSize() > 0)
		{
			AkHashType uiTable = AkHash(in_Key) % HashSize();
			pItem = m_table[uiTable];
			T_MAPSTRUCT * pPrevItem = NULL;
			while (pItem != NULL)
			{
				if (KEY_POLICY::Key(pItem) == in_Key)
					break;

				pPrevItem = pItem;
				pItem = LIST_POLICY::Next(pItem);
			}

			if (pItem)
				RemoveItem(uiTable, pItem, pPrevItem);
		}

		return pItem;
	}

	IteratorEx Erase( const IteratorEx& in_rIter )
	{
		IteratorEx returnedIt;
		returnedIt.pTable = in_rIter.pTable;
		returnedIt.uiTable = in_rIter.uiTable;
		returnedIt.pItem = LIST_POLICY::Next(in_rIter.pItem);
		returnedIt.pPrevItem = in_rIter.pPrevItem;
		
		while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < returnedIt.pTable->Length()))
		{
			returnedIt.pPrevItem = NULL;
			returnedIt.pItem = (*returnedIt.pTable)[ returnedIt.uiTable ];
		}
		
		RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );

		return returnedIt;
	}

	AkUInt32 Length() const
	{
		return m_uiSize;
	}

	AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
	{
		if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
			return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));

		return AK_Success;
	}

	AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
	{
		AKRESULT res = AK_Fail;

		AkHashType uNewSize = 0;
		for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
		{
			if (kHashSizes[i] > in_uExpectedNumberOfEntires)
			{
				uNewSize = kHashSizes[i];
				break;
			}
		}

		if (uNewSize > 0)
		{
			HashTableArray oldArray;
			oldArray.Transfer(m_table);

			if (m_table.GrowArray(uNewSize))
			{
				for (AkUInt32 i = 0; i < uNewSize; i++)
					m_table.AddLast(NULL);

				for (AkUInt32 i = 0; i < oldArray.Length(); i++)
				{
					T_MAPSTRUCT* pItem = oldArray[i];
					while (pItem != NULL)
					{
						T_MAPSTRUCT* pNextItem = LIST_POLICY::Next(pItem);
						{
							AkHashType uiTable = AkHash(KEY_POLICY::Key(pItem)) % uNewSize;
							LIST_POLICY::Next(pItem) = m_table[uiTable];
							m_table[uiTable] = pItem;
						}
						pItem = pNextItem;
					}
				}

				oldArray.Term();

				res = AK_Success;
			}
			else
			{
				//Backpedal..
				m_table.Transfer(oldArray);
			}
		}

		return res;
	}

	inline AkHashType HashSize() const
	{
		return m_table.Length();
	}


	inline bool CheckSize()
	{
		if ( (HashSize() == 0) || (AkReal32)m_uiSize / (AkReal32)HashSize() > kHashTableGrowthFactor )
			Resize(HashSize());

		return (HashSize() > 0);
	}

protected:
	void RemoveItem( AkHashType in_uiTable, T_MAPSTRUCT* in_pItem, T_MAPSTRUCT* in_pPrevItem )
	{
		if( in_pPrevItem ) 
			LIST_POLICY::Next(in_pPrevItem) = LIST_POLICY::Next(in_pItem);
		else
			m_table[ in_uiTable ] = LIST_POLICY::Next(in_pItem);

		--m_uiSize;
	}

	T_MAPSTRUCT * ExistsInList( T_KEY in_Key, AkHashType in_uiTable ) const
	{
		T_MAPSTRUCT * pItem = m_table[in_uiTable];
		while (pItem != NULL)
		{
			if (KEY_POLICY::Key(pItem) == in_Key)
				return pItem; // found
			
			pItem = LIST_POLICY::Next(pItem);
		}

		return NULL; // not found
	}

	HashTableArray m_table;

	AkUInt32 m_uiSize;
};


#endif // _AKHASHLIST_H