/******************************************************************************
  HashTable.inl
  This file contains the hash table function definitions.

 Copyright (c) 2004-2015 Ryan Juckett
  http://www.ryanjuckett.com/

  This software is provided 'as-is', without any express or implied
  warranty. In no event will the authors be held liable for any damages
  arising from the use of this software.

  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:

  1. The origin of this software must not be misrepresented; you must not
     claim that you wrote the original software. If you use this software
     in a product, an acknowledgment in the product documentation would be
     appreciated but is not required.

  2. Altered source versions must be plainly marked as such, and must not be
     misrepresented as being the original software.

  3. This notice may not be removed or altered from any source
     distribution.
******************************************************************************/


namespace RJ
{
	namespace Containers
	{
		//******************************************************************************
		// tHashTableSlot
		//******************************************************************************
		template <typename t_Element>
		inline tHashTableSlot<t_Element>::tHashTableSlot()
			: m_endNodeLink(tNode::GetNodeFromLink(&m_endNodeLink), tNode::GetNodeFromLink(&m_endNodeLink))
		{ }

		//******************************************************************************
		//******************************************************************************
		template <typename t_Element>
		tB tHashTableSlot<t_Element>::IsEqual(const tThis & rhs) const
		{
			if( this == &rhs )
				return true;

			const tNode* pLhsCur = GetBegin();
			const tNode* pRhsCur = rhs.GetBegin();

			const tNode* pLhsEnd = GetEnd();
			const tNode* pRhsEnd = rhs.GetEnd();
			
			while(		pLhsCur != pLhsEnd
					&&	pRhsCur != pRhsEnd
					&&	pLhsCur->m_element == pRhsCur->m_element )
			{
				pLhsCur = pLhsCur->Next();
				pRhsCur = pRhsCur->Next();
			}

			return (pLhsCur == pLhsEnd) && (pRhsCur == pRhsEnd);
		}
		
		//******************************************************************************
		// Splice a range of nodes from another list into this list.
		// Returns false on failure.
		//******************************************************************************
		template <typename t_Element>
		tB tHashTableSlot<t_Element>::SpliceRange
		(
			tNode*	pSplice,
			tThis*	pRhs,
			tNode*	pBegin,
			tNode*	pEnd
		)
		{
			// do nothing if there is no need to splice
			if( pBegin == pEnd || (this == pRhs && pBegin == pSplice) )
				return true;
			
			RJ_ASSERT( !pRhs->IsEmpty() );
			RJ_ASSERT( pBegin != pRhs->GetEnd() );

			RJ_ASSERT( pBegin	!= NULL && pBegin->Prev()	!= NULL );
			RJ_ASSERT( pEnd		!= NULL && pEnd->Prev()	!= NULL );
			RJ_ASSERT( pSplice	!= NULL && pSplice->Prev()	!= NULL );
					
			pBegin->Prev()->Next()	= pEnd;
			pEnd->Prev()->Next()	= pSplice;
			pSplice->Prev()->Next()	= pBegin;
					
			tNode * pNode = pSplice->Prev();
					
			pSplice->Prev()	= pEnd->Prev();
			pEnd->Prev()	= pBegin->Prev();
			pBegin->Prev()	= pNode;

			return true;
		}

		//******************************************************************************
		// Splice a single node from another list into this list.
		// Returns false on failure.
		//******************************************************************************
		template <typename t_Element>
		inline tB tHashTableSlot<t_Element>::Splice(tNode* pSplice, tThis* pRhs, tNode* pBegin)
		{
			tNode* pEnd = pBegin->Next();			
			return SpliceRange( pSplice, pRhs, pBegin, pEnd );
		}

		//******************************************************************************
		// Splice a all nodes from another list into this list.
		// Returns false on failure.
		//******************************************************************************
		template <typename t_Element>
		inline tB tHashTableSlot<t_Element>::SpliceAll(tNode *pSplice, tThis* pRhs)
		{
			return SpliceRange(pSplice, pRhs, pRhs->GetBegin(), pRhs->GetEnd() );
		}


		//******************************************************************************
		// tHashTableBase::tHashTableBase
		// Copy Constructor
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tHashTableBase
		(
			const tThis & rhs
		)
			:
			t_ElementAllocator( rhs.SlotNodeAllocator() ),
			m_keyAccessor_keyCompare_hashFunctor_slots(
				rhs.KeyAccessor(),
				tKeyCompare_HashFunctor_Slots( rhs.KeyCompare(),
					tHashFunctor_Slots(rhs.HashFunctor(),rhs.SlotAllocator()) ) )
		{ }

		//******************************************************************************
		// Returns the end iterator on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTableSlot<t_Element>::tNode* tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Slot_InsertNode(tSlot* pSlot, tSlotNode* pInsertPos)
		{
			if( Slot_InsertOneNode( pInsertPos ) == false )
				return pSlot->GetEnd();

			return pInsertPos->Prev();
		}

		//******************************************************************************
		// Returns the end iterator on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTableSlot<t_Element>::tNode* tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Slot_InsertNode(tSlot* pSlot, tSlotNode* pInsertPos, const t_Element& element)
		{
			if( Slot_InsertOneNode( pInsertPos, element ) == false )
				return pSlot->GetEnd();

			return pInsertPos->Prev();
		}

		//******************************************************************************
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		tB tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Slot_InsertNodeRange(tSlotNode* pInsert, const tSlotNode* pBegin, const tSlotNode* pEnd)
		{
			while( pBegin != pEnd )
			{
				if( Slot_InsertOneNode( pInsert, pBegin->m_element ) == false )
					return false;

				pBegin = pBegin->Next();
			}

			return true;
		}

		//******************************************************************************
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tB tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Slot_AssignRange(tSlot* pSlot, const tSlotNode* pBegin, const tSlotNode* pEnd)
		{
			Slot_ClearNodes(pSlot);
			return Slot_InsertNodeRange( pSlot->GetBegin(), pBegin, pEnd );
		}

		//******************************************************************************
		// Returns the next node in the list
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		typename tHashTableSlot<t_Element>::tNode* tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Slot_EraseNode(tSlotNode* pErase)
		{
			tSlotNode * pNode = pErase;
			pErase = pErase->Next();
			RJ_ASSERT( pNode );

			// link the prev node to the next node
			RJ_ASSERT( pNode->Prev() );
			RJ_ASSERT( pNode->Prev()->Next() );
			pNode->Prev()->Next() = pNode->Next();

			// link the next node to the prev node
			RJ_ASSERT( pNode->Next() );
			RJ_ASSERT( pNode->Next()->Prev() );
			pNode->Next()->Prev() = pNode->Prev();
			
			// destroy this node
			RJ::Memory::Destruct( pNode );
			this->SlotNodeAllocator().Deallocate( pNode );
			
			return pNode;
		}
						
		//******************************************************************************
		// Returns the next node in the list
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		void tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Slot_ClearNodes(tSlot *pSlot)
		{
			tSlotNode * pNode = pSlot->m_endNodeLink.m_pNext;
			pSlot->m_endNodeLink.m_pNext = tSlotNode::GetNodeFromLink(&pSlot->m_endNodeLink);
			pSlot->m_endNodeLink.m_pPrev = tSlotNode::GetNodeFromLink(&pSlot->m_endNodeLink);

			while( &pNode->m_link != &pSlot->m_endNodeLink )
			{	
				tSlotNode * pNextNode = pNode->Next();

				RJ::Memory::Destruct( pNode );
				this->SlotNodeAllocator().Deallocate( pNode );

				pNode = pNextNode;
			}
		}

		//******************************************************************************
		// Returns NULL on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTableSlot<t_Element>::tNode* tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::AllocSlotNode
		(
			tSlotNode* pPrevNode,
			tSlotNode* pNextNode
		)
		{
			tSlotNode* pNode = (tSlotNode*)this->SlotNodeAllocator().Allocate(sizeof(tSlotNode));
			if( pNode == NULL )
				return NULL;

			// Make sure to construct the node directly rather than using a copy constructor
			// such that the user can be guaranteed to only have a single construction of their
			// data.
			RJ::Memory::Construct( pNode, pPrevNode, pNextNode );
			
			return (pNode);
		}


		//******************************************************************************
		// Returns NULL on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTableSlot<t_Element>::tNode* tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::AllocSlotNode(tSlotNode* pPrevNode, tSlotNode* pNextNode, const t_Element& element)
		{
			tSlotNode* pNode = (tSlotNode*)this->SlotNodeAllocator().Allocate(sizeof(tSlotNode));
			if( pNode == NULL )
				return NULL;

			RJ::Memory::Construct( pNode, pPrevNode, pNextNode, element );

			return (pNode);
		}

		//******************************************************************************
		// Returns false on failure
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		tB tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Slot_InsertOneNode(tSlotNode* pInsert)
		{
			tSlotNode * pNode = pInsert;
			RJ_ASSERT( pNode != NULL );
		    
			tSlotNode * pNewNode = AllocSlotNode( pNode->Prev(), pNode );
			if( pNewNode == NULL )
				return false;

			pNode->Prev() = pNewNode;

			RJ_ASSERT( pNewNode );
			RJ_ASSERT( pNewNode->Prev() );
			pNewNode->Prev()->Next() = pNewNode;

			return true;
		}

		//******************************************************************************
		// Returns false on failure
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		tB tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Slot_InsertOneNode(tSlotNode* pInsert, const t_Element& element)
		{
			tSlotNode * pNode = pInsert;
			RJ_ASSERT( pNode );
		    
			tSlotNode * pNewNode = AllocSlotNode( pNode->Prev(), pNode, element );
			if( pNewNode == NULL )
				return false;

			pNode->Prev() = pNewNode;

			RJ_ASSERT( pNewNode );
			RJ_ASSERT( pNewNode->Prev() );
			pNewNode->Prev()->Next() = pNewNode;

			return true;
		}

		//******************************************************************************
		// tHashTable::tHashTable
		// Constructor
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tHashTable()
		{ }

		//******************************************************************************
		// tHashTable::tHashTable
		// Copy Constructor
		// This function will assert on non empty values of rhs. It is only
		// made a public function so that the container can be supplied as a
		// template parameter to classes which might need to compile
		// the function if the user will never call said logic.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tHashTable( const tThis & rhs )
			:
			tHashTableBase<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>(rhs)
		{
			// Due to not supporting exceptions, we would ne be able to return
			// an allocation error from the copy constructor. This means that
			// it is only safe to copy an empty container.
			RJ_ASSERT( rhs.IsEmpty() );
		}


		//******************************************************************************
		// tHashTable::~tHashTable
		// Destructor
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::~tHashTable()
		{
			// clear such that slot nodes are deallocated
			Clear();
		}


		//******************************************************************************
		// tHashTable::operator =
		// This function will assert on non empty values of rhs. It is only
		// made a public function so that the container can be supplied as a
		// template parameter to classes which might need to compile
		// the function if the user will never call said logic.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator> &tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::operator =
		(
			const tThis & rhs
		)
		{
			// Due to not supporting exceptions, we would ne be able to return
			// an allocation error from the copy constructor. This means that
			// it is only safe to copy an empty container.
			RJ_ASSERT( rhs.IsEmpty() );

			// Copy should never fail due to rhs being empty
			const tB success = Copy(rhs);
			RJ_UNUSED_VARIABLE(success);
			RJ_ASSERT( success == true );

			return (*this);
		}


		//******************************************************************************
		// tHashTable::IsEmpty
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tB tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::IsEmpty() const
		{
			for(	tSlotConstItr iSlot = this->Slots().GetBegin();
					iSlot != this->Slots().GetEnd();
					++iSlot )
			{
				if( !iSlot->IsEmpty() )
					return false;
			}

			return true;
		}


		//******************************************************************************
		// tHashTable::GetSize
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tSize tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::GetSize() const
		{
			tSize result = 0;

			for(	tSlotConstItr iSlot = this->Slots().GetBegin();
					iSlot != this->Slots().GetEnd();
					++iSlot )
			{
				const tSlotNode* pBegin = iSlot->GetBegin();
				const tSlotNode* pEnd   = iSlot->GetEnd();
				while( pBegin != pEnd )
				{
					pBegin = pBegin->Next();
					++result;
				}
			}

			return result;
		}


		//******************************************************************************
		// tHashTable::ResizeSlots
		// Resize the number of slots.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tB tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::ResizeSlots
		(
			tSize size
		)
		{
			// do nothing if there is not change in size
			if( size == GetSlotSize() )
				return true;

			// splice all elements into a temproary list
			tSlot tempSlot;
			for( tSlotItr iSlot = this->Slots().GetBegin(); iSlot != this->Slots().GetEnd(); ++iSlot )
			{
				if( !tempSlot.SpliceAll( tempSlot.GetEnd(), &*iSlot ) )
					return false;
			}

			// we should have no elements in the slots
			RJ_ASSERT( IsEmpty() );

			// if we will need to construct new slots 
			if( this->Slots().GetSize() < size )
			{
				// clear the slots so that we can safely reset all of their
				// shared allocators incase they don't need to destruct from
				// the resize
				this->Slots().Clear();

				// resize
				if( this->Slots().Resize(size) == false )
					return false;
			}
			else
			{
				// the remaining slots will not be destructed so we
				// don't need to reinitialize them
				const tB resizeResult = this->Slots().Resize(size);
				RJ_UNUSED_VARIABLE(resizeResult);

				// should never fail when shrinking a vector
				RJ_ASSERT( resizeResult );
			}

			// resplice all elements back into the hash table
			while( !tempSlot.IsEmpty() )
			{
				// get the slot to add to
				RJ_ASSERT( !this->Slots().IsEmpty() );
				const tSlotItr iSlot =		this->Slots().GetBegin()
										+ (		this->HashFunctor()( this->KeyAccessor()(tempSlot.GetBegin()->m_element) )
											%	this->Slots().GetSize() );

				// check for an existing key to modify
				tSlotNode* pNode = iSlot->GetBegin();
				while( pNode != iSlot->GetEnd() )
				{
					// if we need to insert here (iElement >= element)
					if( !this->KeyCompare()( this->KeyAccessor()(pNode->m_element), this->KeyAccessor()(tempSlot.GetBegin()->m_element) ) )
					{
						// we need to insert here
						break;
					}

					pNode = pNode->Next();
				}

				// insert the new element
				if( !iSlot->Splice( pNode, &tempSlot, tempSlot.GetBegin() ) )
					return false;
			}

			return true;
		}


		//******************************************************************************
		// tHashTable::Count
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tSize tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Count
		(
			const t_Key & key
		) const
		{
			tConstRange range = FindEqualRange(key);
			return GetDistance( range.m_begin, range.m_end );
		}


		//******************************************************************************
		// tHashTable::Find
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Find
		(
			const t_Key & key
		)
		{
			if( !this->Slots().IsEmpty() )
			{
				const tSlotItr iSlot = this->Slots().GetBegin() + ( this->HashFunctor()(key) % this->Slots().GetSize() );

				for(	tSlotNode* pNode = iSlot->GetBegin();
						pNode != iSlot->GetEnd(); 
						pNode = pNode->Next() )
				{
					// if key >= iElement
					if( !this->KeyCompare()( key, this->KeyAccessor()(pNode->m_element) ) )
					{
						// if iElement >= key (thus iElement == key )
						if( !this->KeyCompare()( this->KeyAccessor()(pNode->m_element), key ) )
						{
							// we found it
							return tIterator( this, iSlot, pNode );
						}
					}
					// else key < iElement
					else
					{
						// we failed to find it
						break;
					}
				}
			}

			return GetEnd();
		}


		//******************************************************************************
		// tHashTable::Find
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tConstIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Find
		(
			const t_Key & key
		)
		const
		{
			if( !this->Slots().IsEmpty() )
			{
				const tSlotConstItr iSlot = this->Slots().GetBegin() + ( this->HashFunctor()(key) % this->Slots().GetSize() );

				for(	const tSlotNode *pNode = iSlot->GetBegin();
						pNode != iSlot->GetEnd();
						pNode = pNode->Next() )
				{
					// if key >= iElement
					if( !this->KeyCompare()( key, this->KeyAccessor()(pNode->m_element) ) )
					{
						// if iElement >= key (thus iElement == key )
						if( !this->KeyCompare()( this->KeyAccessor()(pNode->m_element), key ) )
						{
							// we found it
							return tConstIterator( this, iSlot, pNode );
						}
					}
					// else key < iElement
					else
					{
						// we failed to find it
						break;
					}
				}
			}

			return GetEnd();
		}


		//******************************************************************************
		// tHashTable::GetBegin
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::GetBegin()
		{
			for(	tSlotItr iSlot = this->Slots().GetBegin();
					iSlot != this->Slots().GetEnd();
					++iSlot )
			{
				if( !iSlot->IsEmpty() )
					return tIterator( this, iSlot, iSlot->GetBegin() );
			}
		 	
			return GetEnd();
		}


		//******************************************************************************
		// tHashTable::GetBegin
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tConstIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::GetBegin() const
		{
			for(	tSlotConstItr iSlot = this->Slots().GetBegin();
					iSlot != this->Slots().GetEnd();
					++iSlot )
			{
				if( !iSlot->IsEmpty() )
					return tConstIterator( this, iSlot, iSlot->GetBegin() );
			}
		 	
			return GetEnd();
		}


		//******************************************************************************
		// tHashTable::GetEnd
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::GetEnd()
		{
			return tIterator( this, this->Slots().GetEnd(), NULL );
		}


		//******************************************************************************
		// tHashTable::GetEnd
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tConstIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::GetEnd() const
		{
			return tConstIterator( this, this->Slots().GetEnd(), NULL );
		}


		//******************************************************************************
		// tHashTable::FindEqualRange
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tRange tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::FindEqualRange( const t_Key & key )
		{
			tRange result;
			
			// initialze range to the result of finding the first element with the key
			result.m_begin = Find(key);
			result.m_end   = result.m_begin;

			// increment the end of the range until it hits an element greater than the key ( element <= key ) or advances to the next slot
			while(		result.m_end != GetEnd()
					&&	!this->KeyCompare()( key, this->KeyAccessor()(*result.m_end) )
					&&	result.m_end.m_iSlot == result.m_begin.m_iSlot )
			{
				++result.m_end;
			}

			return result;
		}


		//******************************************************************************
		// tHashTable::FindEqualRange
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tConstRange tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::FindEqualRange( const t_Key & key ) const
		{
			tConstRange result;
			
			// initialze range to the result of finding the first element with the key
			result.m_begin = Find(key);
			result.m_end   = result.m_begin;

			// increment the end of the range until it hits an element greater than the key ( element <= key ) or advances to the next slot
			while(		result.m_end != GetEnd()
					&&	!this->KeyCompare()( key, this->KeyAccessor()(*result.m_end) )
					&&	result.m_end.m_iSlot == result.m_begin.m_iSlot )
			{
				++result.m_end;
			}

			return result;
		}
		
		//******************************************************************************
		// tHashTable::FindUniqueInsertionPoint
		// If a matching element already exists, return false and output the element
		// location. Otherwise, output the element location to insert in front of.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tB tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::FindUniqueInsertionPoint
		(
			tSlotItr *			pOutSlot,
			tSlotNode**			ppOutNode,
			const t_Key &		key
		)
		{
			// get the slot to add to
			RJ_ASSERT( !this->Slots().IsEmpty() );
			const tSlotItr iSlot = 	this->Slots().GetBegin()
									+ (		this->HashFunctor()( key )
										%	this->Slots().GetSize() );

			// check for an existing key to modify
			tSlotNode* pCur = iSlot->GetBegin();
			tSlotNode* pEnd = iSlot->GetEnd();
			while( pCur != pEnd )
			{
				// if we need to insert here (iCur >= element)
				if( !this->KeyCompare()( this->KeyAccessor()(pCur->m_element), key) )
				{
					// check for the equality case (element >= iCur)
					if( !this->KeyCompare()( key, this->KeyAccessor()(pCur->m_element) ) )
					{
						// return the preexisting element with the matching key
						*pOutSlot = iSlot;
						*ppOutNode = pCur;
						return false;
					}

					// we need to insert here
					break;
				}

				pCur = pCur->Next();
			}

			*pOutSlot = iSlot;
			*ppOutNode = pCur;
			return true;
		}
		
		//******************************************************************************
		// tHashTable::FindEqualInsertionPoint
		// Output the location to insert before.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline void tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::FindEqualInsertionPoint
		(
			tSlotItr *			pOutSlot,
			tSlotNode**			ppOutNode,
			const t_Key &		key
		)
		{
			// get the slot to add to
			RJ_ASSERT( !this->Slots().IsEmpty() );
			const tSlotItr iSlot =		this->Slots().GetBegin()
									+ (		this->HashFunctor()( key )
										%	this->Slots().GetSize() );

			// check for an existing key to modify
			tSlotNode* pCur = iSlot->GetBegin();
			tSlotNode* pEnd = iSlot->GetEnd();
			while( pCur != pEnd )
			{
				// if we need to insert here (iCur >= element)
				if( !this->KeyCompare()( this->KeyAccessor()(pCur->m_element), key ) )
				{
					// we need to insert here
					break;
				}

				pCur = pCur->Next();
			}

			*pOutSlot = iSlot;
			*ppOutNode = pCur;
		}

		//******************************************************************************
		// tHashTable::InsertUnique
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tInsertResult tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::InsertUnique
		(
			const t_Element & element
		)
		{
			tInsertResult result;

			tSlotItr iSlot;
			tSlotNode* pNode;
			if ( !FindUniqueInsertionPoint(&iSlot, &pNode, this->KeyAccessor()(element)) )
			{
				// return the preexisting element with the matching key
				result.m_location = tIterator( this, iSlot, pNode );
				result.m_inserted = false;
				return result;
			}

			// insert the new element
			pNode = tThisBase::Slot_InsertNode(&*iSlot, pNode, element);

			// check for failure
			if( pNode == iSlot->GetEnd() )
			{
				result.m_location = GetEnd();
				result.m_inserted = false;
				return result;
			}

			result.m_location = tIterator( this, iSlot, pNode );
			result.m_inserted = true;
			return result;
		}


		//******************************************************************************
		// tHashTable::InsertEqual
		// The end iterator is returned on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::InsertEqual
		(
			const t_Element & element
		)
		{
			tSlotItr iSlot;
			tSlotNode* pNode;
			FindEqualInsertionPoint(&iSlot, &pNode, this->KeyAccessor()(element));

			// insert the new element
			pNode = tThisBase::Slot_InsertNode(&*iSlot, pNode, element);

			// check for failure
			if( pNode == iSlot->GetEnd() )
				return GetEnd();

			return tIterator( this, iSlot, pNode );
		}

		//******************************************************************************
		// tHashTable::InsertKeyUnique
		// Insert an empty element at the location of a specific key. It is the user's
		// responsibility to fill in the element to match the key.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tInsertResult
		tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::InsertKeyUnique
		(
			const t_Key & key
		)
		{
			tInsertResult result;

			tSlotItr iSlot;
			tSlotNode *pNode;
			if ( !FindUniqueInsertionPoint(&iSlot, &pNode, key) )
			{
				// return the preexisting element with the matching key
				result.m_location = tIterator( this, iSlot, pNode );
				result.m_inserted = false;
				return result;
			}

			// insert the new element
			pNode = tThisBase::Slot_InsertNode( &*iSlot, pNode );

			// check for failure
			if( pNode == iSlot->GetEnd() )
			{
				result.m_location = GetEnd();
				result.m_inserted = false;
				return result;
			}

			result.m_location = tIterator( this, iSlot, pNode );
			result.m_inserted = true;
			return result;
		}


		//******************************************************************************
		// tHashTable::InsertKeyEqual
		// Insert an empty element at the location of a specific key. It is the user's
		// responsibility to fill in the element to match the key.
		//
		// The end iterator is returned on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::InsertKeyEqual
		(
			const t_Key & key
		)
		{
			tSlotItr iSlot;
			tSlotNode *pNode;
			FindEqualInsertionPoint(&iSlot, &pNode, key);

			// insert the new element
			pNode = tThisBase::Slot_InsertNode( &*iSlot, pNode );

			// check for failure
			if( pNode == iSlot->GetEnd() )
				return GetEnd();

			return tIterator( this, iSlot, pNode );
		}

		//******************************************************************************
		// tHashTable::InsertRangeUnique
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		template<typename t_Iterator>
		inline tB tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::InsertRangeUnique
		(
			t_Iterator iBegin,
			t_Iterator iEnd
		)
		{
			for( ; iBegin != iEnd; ++iBegin)
			{
				if( InsertUnique(*iBegin).First() == GetEnd() )
					return false;
			}

			return true;
		}


		//******************************************************************************
		// tHashTable::InsertRangeEqual
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		template<typename t_Iterator>
		inline tB tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::InsertRangeEqual
		(
			t_Iterator iBegin,
			t_Iterator iEnd
		)
		{
			for( ; iBegin != iEnd; ++iBegin)
			{
				if( InsertEqual(*iBegin) == GetEnd() )
					return false;
			}

			return true;
		}


		//******************************************************************************
		// tHashTable::EraseKey
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline void tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::EraseKey
		(
			const t_Key & key
		)
		{
			if( !this->Slots().IsEmpty() )
			{
				const tSlotItr iSlot = this->Slots().GetBegin() + ( this->HashFunctor()(key) % this->Slots().GetSize() );

				tSlotNode *pNode = iSlot->GetBegin();
				while( pNode != iSlot->GetEnd() )
				{
					// if key >= iElement
					if( !this->KeyCompare()( key, this->KeyAccessor()(pNode->m_element) ) )
					{
						// if iElement >= key (thus iElement == key )
						if( !this->KeyCompare()( this->KeyAccessor()(pNode->m_element), key ) )
						{
							// we found it
							pNode = tThisBase::Slot_EraseNode( pNode );
							return;
						}
					}
					// else key < iElement
					else
					{
						// we failed to find it
						return;
					}
					pNode = pNode->Next();
				}
			}
		}


		//******************************************************************************
		// tHashTable::Erase
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Erase
		(
			tIterator iErase
		)
		{
			RJ_ASSERT( ContainsItr(GetBegin(),GetEnd(),iErase) );

			tIterator iNext = iErase;
			++iNext;

			tThisBase::Slot_EraseNode(iErase.m_pNode);

			return iNext;
		}

			
		//******************************************************************************
		// tHashTable::EraseRange
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline typename tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::EraseRange
		(
			const tIterator & iBegin,
			const tIterator & iEnd
		)
		{
			RJ_ASSERT( ContainsValidItrRange(GetBegin(),GetEnd(),iBegin,iEnd) );

			if( iBegin == GetBegin() && iEnd == GetEnd() )
			{
				EraseAll();
			}
			else
			{
				tIterator iCur = iBegin;
				while( iCur != iEnd )
				{
					RJ_ASSERT( iCur != GetEnd() );
					iCur = Erase(iCur);
				}
			}

			return iEnd;
		}


		//******************************************************************************
		// tHashTable::EraseAll
		// This will erase all of the elements in the slots. The slots will
		// remain allocated.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline void tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::EraseAll()
		{
			for(	tSlotItr iSlot = this->Slots().GetBegin();
					iSlot != this->Slots().GetEnd();
					++iSlot )
			{
				tThisBase::Slot_ClearNodes(&*iSlot);
			}
		}


		//******************************************************************************
		// tHashTable::Clear
		// This will clear all of the used memory (including the slots).
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline void tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Clear()
		{
			// deallocate the slot nodes
			EraseAll();

			// deallocate the slots
			this->Slots().Clear();
		}


		//******************************************************************************
		// tHashTable::Swap
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tB tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Swap
		(
			tThis *	pRhs
		)
		{
			tThis temp;
			if (!temp.SlotNodeAllocator().CopyHeap( this->SlotNodeAllocator() ))
				return false;

			if (!temp.Slots().ElementAllocator().CopyHeap( this->Slots().ElementAllocator() ))
				return false;

			if( temp.Copy( *this ) == false )
				return false;

			if( this->Copy(*pRhs) == false )
				return false;

			if( pRhs->Copy(temp) == false )
				return false;

			return true;
		}


		//******************************************************************************
		// tHashTable::Copy
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tB tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::Copy
		(
			const tThis & rhs
		)
		{
			if( this != &rhs )
			{
				// copy the functors
				this->KeyAccessor()	= rhs.KeyAccessor();
				this->KeyCompare()	= rhs.KeyCompare();
				this->HashFunctor()	= rhs.HashFunctor();

				// clear the old data to free up the element memory before
				// performing the copy to prevent more memory being used than
				// needed suring the copy process
				Clear();

				// reinitilize our slots
				if( InitSlotsFromCopy( rhs.Slots() ) == false )
					return false;
			}

			return true;
		}


		//******************************************************************************
		// tHashTable::InitSlotsFromCopy
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tB tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::InitSlotsFromCopy
		(
			const tSlots & rhsSlots
		)
		{
			// resize the slots
			if( ResizeSlots( rhsSlots.GetSize() ) == false )
				return false;

			// copy the elements without copying the lists themselves
			// to prevent the shared allocator from being copied
			tSlotItr		iLhsSlot = this->Slots().GetBegin();
			tSlotConstItr	iRhsSlot = rhsSlots.GetBegin();
			while( iLhsSlot != this->Slots().GetEnd() )
			{
				Slot_AssignRange( &*iLhsSlot, iRhsSlot->GetBegin(), iRhsSlot->GetEnd() );
				++iLhsSlot;
				++iRhsSlot;
			}

			return true;
		}


		//******************************************************************************
		// tHashTable::IsEqual
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline tB tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::IsEqual
		(
			const tThis & rhs
		) const
		{
			if( this == &rhs )
				return true;

			// given that the keys are unique and sorted, we can just compare the slots directly
			return this->Slots() == rhs.Slots();
		}


	}
}