/******************************************************************************
  HashTable_Iterator.inl
  This file contains the hash table iterator 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
	{

		//******************************************************************************
		// tHashTable::tIterator::tIterator
		// 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>::tIterator::tIterator()
		#ifdef RJ_ENABLE_ASSERT
			:
			m_pHashTable( NULL )
		#endif
		{ }


		//******************************************************************************
		// tHashTable::tIterator::tIterator
		// 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 tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator::tIterator
		(
			const tThis & rhs
		)
			:
			m_pHashTable( rhs.m_pHashTable ),	
			m_iSlot( rhs.m_iSlot ),
			m_pNode( rhs.m_pNode )
		{ }


		//******************************************************************************
		// tHashTable::tIterator::~tIterator
		// 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>::tIterator::~tIterator()
		{ }


		//******************************************************************************
		// tHashTable::tIterator::operator =
		//******************************************************************************
		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>::tIterator::operator =
		(
			const tThis & rhs
		)
		{
			m_pHashTable	= rhs.m_pHashTable;	
			m_iSlot			= rhs.m_iSlot;
			m_pNode			= rhs.m_pNode;

			return *this;
		}
				

		//******************************************************************************
		// tHashTable::tIterator::operator *
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline t_Element & tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator::operator *() const
		{
		#	ifdef RJ_ENABLE_ASSERT
				RJ_ASSERT( Is_Initialized() );
				RJ_ASSERT( !Is_End() ); 
		#	endif

			return m_pNode->m_element;
		}


		//******************************************************************************
		// tHashTable::tIterator::operator ->
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_HashFunctor, typename t_ElementAllocator, typename t_SlotAllocator>
		inline t_Element * tHashTable<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_HashFunctor,t_ElementAllocator,t_SlotAllocator>::tIterator::operator ->() const
		{
			return &m_pNode->m_element;
		}


		//******************************************************************************
		// tHashTable::tIterator::operator ++
		// Prefix Increment
		//******************************************************************************
		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>::tIterator::operator ++()
		{
		#	ifdef RJ_ENABLE_ASSERT
				RJ_ASSERT( Is_Initialized() );
				RJ_ASSERT( !Is_End() ); 
		#	endif

			m_pNode = m_pNode->Next();
			
			// check if we need to do a slot increment
			if( m_pNode == m_iSlot->GetEnd() )
			{
				// increment the slot until we find a non-empty one or reach the end
				for(;;)
				{
					++m_iSlot;

					if( m_iSlot == (m_pHashTable->Slots().GetEnd()) )
					{
						break;
					}
					else if( !m_iSlot->IsEmpty() )
					{
						// reset the element iterator if we are not at the end slot
						m_pNode = m_iSlot->GetBegin();
						break;
					}
				}
			}
					
			return *this;
		}


		//******************************************************************************
		// tHashTable::tIterator::operator ++
		// Postfix Increment
		//******************************************************************************
		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>::tIterator::operator ++(int)
		{	
			tThis temp = *this;
			++*this;
			return temp;
		}


		//******************************************************************************
		// Prefix Decrement
		//******************************************************************************
		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>::tIterator::operator --()
		{	
		#	ifdef RJ_ENABLE_ASSERT
				RJ_ASSERT( Is_Initialized() );
				RJ_ASSERT( !Is_Begin() ); 
		#	endif

			// check if we need to do a slot decrement
			if( m_iSlot == m_pHashTable->Slots().GetEnd() || m_pNode == m_iSlot->GetBegin() )
			{
				// decrement the slot until we find a non-empty one
				do
				{
					--m_iSlot;
				}
				while( m_iSlot->IsEmpty() );

				// reset the element iterator to the end of the slot
				m_pNode = m_iSlot->GetEnd();
			}
			
			// decrement the element iterator
			m_pNode = m_pNode->Prev();
			
			return *this;
		}


		//******************************************************************************
		// Postfix Decrement
		//******************************************************************************
		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>::tIterator::operator --(int)
		{
			tThis temp = *this;
			--*this;
			return temp;
		}


		//******************************************************************************
		// Specialized 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>::tIterator::tIterator
		(
			tParent *			pHashTable,
			const tSlotItr &	iSlot,
			tSlotNode*			pNode
		)
		:
			m_pHashTable(pHashTable),
			m_iSlot(iSlot),
			m_pNode(pNode)
		{
			RJ_ASSERT( m_pHashTable != NULL );
			// Commenting out these asserts due to performance issues from calling ContainsItr in this function
			//RJ_ASSERT( m_iSlot == m_pHashTable->Slots().GetEnd() || ContainsItr(m_pHashTable->Slots().GetBegin(),m_pHashTable->Slots().GetEnd(),m_iSlot) );
			//RJ_ASSERT( m_iSlot == m_pHashTable->Slots().GetEnd() || ContainsItr(m_iSlot->GetBegin(),m_iSlot->GetEnd(),iElement) );
		}

				
		//******************************************************************************
		// Debug function to check if the iterator has been initialized
		//******************************************************************************
		#ifdef RJ_ENABLE_ASSERT
			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>::tIterator::Is_Initialized() const
			{
				return m_pHashTable != NULL;
			}
		#endif


		//******************************************************************************
		// Debug function to check if the iterator points to the begin element
		// of the bag
		//******************************************************************************
		#ifdef RJ_ENABLE_ASSERT
			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>::tIterator::Is_Begin() const
			{
				RJ_ASSERT( Is_Initialized() );
				return (*this) == m_pHashTable->GetBegin();
			}
		#endif


		//******************************************************************************
		// Debug function to check if the iterator points to the end element
		// of the bag
		//******************************************************************************
		#ifdef RJ_ENABLE_ASSERT
			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>::tIterator::Is_End() const
			{
				RJ_ASSERT( Is_Initialized() );
				return (*this) == m_pHashTable->GetEnd();
			}
		#endif


		//******************************************************************************
		// tHashTable::tIterator::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>::tIterator::IsEqual
		(
			const tThis & rhs
		) const
		{
		#	ifdef RJ_ENABLE_ASSERT
				RJ_ASSERT( Is_Initialized() );
				RJ_ASSERT( rhs.Is_Initialized() );
		#	endif

			RJ_ASSERT( m_pHashTable == rhs.m_pHashTable );

			if(		m_iSlot == m_pHashTable->Slots().GetEnd()
				||	rhs.m_iSlot == m_pHashTable->Slots().GetEnd() )
			{
				// when at the end of the slot list, the element iterator
				// is no longer valid so only compare slots
				return (m_iSlot == rhs.m_iSlot);
			}
			else
			{
				// if the elements are the same, then the slot must also be the same
				RJ_ASSERT(	(m_pNode != rhs.m_pNode) || (m_iSlot == rhs.m_iSlot ) );
				return ( m_pNode == rhs.m_pNode );
			}
		}


		//******************************************************************************
		// tHashTable::tIterator::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>::tIterator::IsEqual
		(
			const tOther & rhs
		) const
		{
		#	ifdef RJ_ENABLE_ASSERT
				RJ_ASSERT( Is_Initialized() );
				RJ_ASSERT( rhs.Is_Initialized() );
		#	endif

			RJ_ASSERT( m_pHashTable == rhs.m_pHashTable );

			if(		m_iSlot == m_pHashTable->Slots().GetEnd()
				||	rhs.m_iSlot == m_pHashTable->Slots().GetEnd() )
			{
				// when at the end of the slot list, the element iterator
				// is no longer valid so only compare slots
				return (m_iSlot == rhs.m_iSlot);
			}
			else
			{
				// if the elements are the same, then the slot must also be the same
				RJ_ASSERT(	(m_pNode != rhs.m_pNode) || (m_iSlot == rhs.m_iSlot ) );
				return ( m_pNode == rhs.m_pNode );
			}
		}


	}
}