/******************************************************************************
  List.inl
  This file contains function definitions for tList.

 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.
	 
  This file is derived from software with the following restrictions:
   | Copyright (c) 1994
   | Hewlett-Packard Company
   | 
   | Copyright (c) 1996,1997
   | Silicon Graphics Computer Systems, Inc.
   | 
   | Copyright (c) 1997
   | Moscow Center for SPARC Technology
   | 
   | Copyright (c) 1999 
   | Boris Fomitchev
   | 
   | This material is provided "as is", with absolutely no warranty expressed
   | or implied. Any use is at your own risk.
   | 
   | Permission to use or copy this software for any purpose is hereby granted 
   | without fee, provided the above notices are retained on all copies.
   | Permission to modify the code and to distribute modified code is granted,
   | provided the above notices are retained, and a notice that the code was
   | modified is included with the above copyright notice.
******************************************************************************/


//=============================================================================
// Class Member Function Definitions
//=============================================================================

namespace RJ
{
	namespace Containers
	{
		//******************************************************************************
		// tListIteratorBase == tListIteratorBase::tOther
		//******************************************************************************
		template<typename t_Element, typename t_Allocator, typename t_ThisElement, typename t_ThisNodePtr, typename t_OtherElement, typename t_OtherNodePtr>
		inline tB operator ==
		(
			const tListIteratorBase<t_Element, t_Allocator, t_ThisElement, t_ThisNodePtr, t_OtherElement, t_OtherNodePtr> & lhs,
			const typename tListIteratorBase<t_Element, t_Allocator, t_ThisElement, t_ThisNodePtr, t_OtherElement, t_OtherNodePtr>::tOther & rhs
		)
		{
			RJ_ASSERT( lhs.m_pNode && rhs.m_pNode );
			return (lhs.m_pNode == rhs.m_pNode);
		}

		//******************************************************************************
		// tList::tList
		// Constructor
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tList<t_Element,t_Allocator>::tList()
			:
			m_endNodeLink( tNode::GetNodeFromLink(&m_endNodeLink), tNode::GetNodeFromLink(&m_endNodeLink) )
		{ }

		//******************************************************************************
		// tList::tList
		// 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_Element, typename t_Allocator>
		inline tList<t_Element,t_Allocator>::tList
		(
			const tThis & rhs
		)
			:
			m_endNodeLink( tNode::GetNodeFromLink(&m_endNodeLink), tNode::GetNodeFromLink(&m_endNodeLink) )
		{
			RJ_UNUSED_VARIABLE(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() );
		}

		//******************************************************************************
		// tList::~tList
		// Destructor
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tList<t_Element,t_Allocator>::~tList()
		{
			Clear();
		}


		//******************************************************************************
		// tList::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_Element, typename t_Allocator>
		inline tList<t_Element,t_Allocator> &tList<t_Element,t_Allocator>::operator =
		(
			const tThis & rhs
		)
		{
			RJ_UNUSED_VARIABLE(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() );
			return (*this);
		}


		//******************************************************************************
		// tList::GetSize
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tSize tList<t_Element,t_Allocator>::GetSize() const
		{
			return GetDistance( GetBegin(), GetEnd() );
		}


		//******************************************************************************
		// tList::Resize
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::Resize
		(
			tSize numElements
		)
		{
			tSize curNumElements = GetSize();

			// if we need to grow
			if( curNumElements < numElements )
			{
				if( InsertSequence( GetEnd(), numElements - curNumElements ) == false )
					return false;
			}
			// else we need to shrink
			else
			{
				while( curNumElements > numElements )
				{
					PopBack();
					--curNumElements;
				}
			}

			return true;
		}


		//******************************************************************************
		// tList::Resize
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::Resize
		(
			tSize				numElements,
			const t_Element &	element
		)
		{
			tSize curNumElements = GetSize();

			// if we need to grow
			if( curNumElements < numElements )
			{
				if( InsertSequence( GetEnd(), numElements - curNumElements, element ) == false )
					return false;
			}
			// else we need to shrink
			else
			{
				while( curNumElements > numElements )
				{
					PopBack();
					--curNumElements;
				}
			}

			return true;
		}


		//******************************************************************************
		// tList::PushFront
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::PushFront()
		{
			return InsertOne( GetBegin() );
		}


		//******************************************************************************
		// tList::PushFront
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::PushFront
		(
			const t_Element & element
		)
		{
			return InsertOne( GetBegin(), element );
		}


		//******************************************************************************
		// tList::PopFront
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tList<t_Element,t_Allocator>::PopFront()
		{
			RJ_ASSERT( !IsEmpty() );
			Erase( GetBegin() );
		}


		//******************************************************************************
		// tList::PushBack
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::PushBack()
		{
			return InsertOne( GetEnd() );
		}


		//******************************************************************************
		// tList::PushBack
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::PushBack
		(
			const t_Element & element
		)
		{
			return InsertOne( GetEnd(), element );
		}


		//******************************************************************************
		// tList::PopBack
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tList<t_Element,t_Allocator>::PopBack()
		{
			RJ_ASSERT( !IsEmpty() );
			Erase( --GetEnd() );
		}


		//******************************************************************************
		// tList::AssignRange
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Iterator>
		inline tB tList<t_Element,t_Allocator>::AssignRange
		(
			t_Iterator iBegin,
			t_Iterator iEnd
		)
		{
			Clear();
			return InsertRange( GetBegin(), iBegin, iEnd );
		}


		//******************************************************************************
		// tList::AssignSequence
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::AssignSequence
		(
			tSize				numElements,
			const t_Element &	element
		)
		{
			// make a copy incase element is in sequence
			t_Element temp(element);
			Clear();
			return InsertSequence( GetBegin(), numElements, temp );
		}


		//******************************************************************************
		// tList::Insert
		// Returns the end iterator on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline typename tList<t_Element,t_Allocator>::tIterator tList<t_Element,t_Allocator>::Insert
		(
			tIterator			iInsertPos
		)
		{
			if( InsertOne( iInsertPos ) == false )
				return GetEnd();

			return (--iInsertPos);
		}


		//******************************************************************************
		// tList::Insert
		// Returns the end iterator on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline typename tList<t_Element,t_Allocator>::tIterator tList<t_Element,t_Allocator>::Insert
		(
			tIterator			iInsertPos,
			const t_Element &	element
		)
		{
			if( InsertOne( iInsertPos, element ) == false )
				return GetEnd();

			return (--iInsertPos);
		}


		//******************************************************************************
		// tList::InsertSequence
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::InsertSequence
		(
			tIterator		iInsert,
			tSize			numElements
		)
		{
			while( numElements > 0 )
			{ 
				if( InsertOne( iInsert ) == false )
					return false;

				--numElements;
			}

			return true;
		}


		//******************************************************************************
		// tList::InsertSequence
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::InsertSequence
		(
			tIterator			iInsert,
			tSize				numElements,
			const t_Element &	element
		)
		{
			while( numElements > 0 )
			{ 
				if( InsertOne( iInsert, element ) == false )
					return false;

				--numElements;
			}

			return true;
		}


		//******************************************************************************
		// tList::InsertRange
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Iterator>
		inline tB tList<t_Element,t_Allocator>::InsertRange
		(
			tIterator	iInsert,
			t_Iterator	iBegin,
			t_Iterator	iEnd
		)
		{
			while( iBegin != iEnd )
			{
				if( InsertOne( iInsert, *iBegin ) == false )
					return false;
				++iBegin;
			}

			return true;
		}


		//******************************************************************************
		// tList::Erase
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline typename tList<t_Element,t_Allocator>::tIterator tList<t_Element,t_Allocator>::Erase
		(
			tIterator iErase
		)
		{
			RJ_ASSERT( !IsEmpty() );

			tNode * pNode = (iErase++).m_pNode;
			RJ_ASSERT( pNode );

			// cannot erase the end node
			RJ_ASSERT( &pNode->m_link != &m_endNodeLink );

			// 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->NodeAllocator().Deallocate( pNode );
			
			return iErase;
		}


		//******************************************************************************
		// tList::EraseRange
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline typename tList<t_Element,t_Allocator>::tIterator tList<t_Element,t_Allocator>::EraseRange
		(
			tIterator iBegin,
			tIterator iEnd
		)
		{
			if( iBegin == GetBegin() && iEnd == GetEnd() )
			{
				Clear();
			}
			else
			{
				while( iBegin != iEnd )
				{
					RJ_ASSERT( iBegin != GetEnd() );
					iBegin = Erase(iBegin);
				}
			}

			return iEnd;
		}


		//******************************************************************************
		// tList::Clear
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tList<t_Element,t_Allocator>::Clear()
		{
			tNode * pNode = m_endNodeLink.m_pNext;
			m_endNodeLink.m_pNext = tNode::GetNodeFromLink(&m_endNodeLink);
			m_endNodeLink.m_pPrev = tNode::GetNodeFromLink(&m_endNodeLink);

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

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

				pNode = pNextNode;
			}
		}


		//******************************************************************************
		// tList::Swap
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::Swap
		(
			tThis * pRhs
		)
		{
			// if the allocator is the same
			if( this->NodeAllocator().CompareHeap(pRhs->NodeAllocator()))
			{	
				// do a simple swap (accounting for self references)
				tNodeLink oldRhsEndNodeLink			= pRhs->m_endNodeLink;
				tNode *pOldRhsEndNodeLinkPrevNext	= pRhs->m_endNodeLink.m_pPrev->Next();
				tNode *pOldRhsEndNodeLinkNextPrev	= pRhs->m_endNodeLink.m_pNext->Prev();

				tNode *pThisEndNode = tNode::GetNodeFromLink(&m_endNodeLink);
				tNode *pRhsEndNode = tNode::GetNodeFromLink(&pRhs->m_endNodeLink);

				pRhs->m_endNodeLink.m_pPrev = (m_endNodeLink.m_pPrev == pThisEndNode) ? pRhsEndNode : m_endNodeLink.m_pPrev;
				pRhs->m_endNodeLink.m_pNext = (m_endNodeLink.m_pNext == pThisEndNode) ? pRhsEndNode : m_endNodeLink.m_pNext;

				pRhs->m_endNodeLink.m_pPrev->Next() = (m_endNodeLink.m_pPrev->Next() == pThisEndNode) ? pRhsEndNode : m_endNodeLink.m_pPrev->Next();
				pRhs->m_endNodeLink.m_pNext->Prev() = (m_endNodeLink.m_pNext->Prev() == pThisEndNode) ? pRhsEndNode : m_endNodeLink.m_pNext->Prev();

				m_endNodeLink.m_pPrev = (oldRhsEndNodeLink.m_pPrev == pRhsEndNode) ? pThisEndNode : oldRhsEndNodeLink.m_pPrev;
				m_endNodeLink.m_pNext = (oldRhsEndNodeLink.m_pNext == pRhsEndNode) ? pThisEndNode : oldRhsEndNodeLink.m_pNext;

				m_endNodeLink.m_pPrev->Next() = (pOldRhsEndNodeLinkPrevNext == pRhsEndNode) ? pThisEndNode : pOldRhsEndNodeLinkPrevNext;
				m_endNodeLink.m_pNext->Prev() = (pOldRhsEndNodeLinkNextPrev == pRhsEndNode) ? pThisEndNode : pOldRhsEndNodeLinkNextPrev;
			}
			// else there are different allocators
			else
			{	
				// Splice the elements across the containers
				tIterator iSplice = GetBegin();
				if( SpliceAll( iSplice, pRhs ) == false )
					return false;

				if( pRhs->SpliceRange( pRhs->GetBegin(), this, iSplice, GetEnd() ) == false )
					return false;
			}

			return true;
		}


		//******************************************************************************
		// tList::Copy
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::Copy
		(
			const tThis & rhs
		)
		{
			if( this != &rhs )
			{
				if( AssignRange( rhs.GetBegin(), rhs.GetEnd() ) == false )
					return false;
			}

			return true;
		}


		//******************************************************************************
		// tList::Splice
		// Splice a single node from another list into this list.
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::Splice
		(
			tIterator	iSplice,
			tThis *		pRhs,
			tIterator	iBegin
		)
		{
			tIterator iEnd = iBegin;
			++iEnd;
			
			return SpliceRange( iSplice, pRhs, iBegin, iEnd );
		}


		//******************************************************************************
		// tList::SpliceRange
		// Splice a range of nodes from another list into this list.
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::SpliceRange
		(
			tIterator	iSplice,
			tThis *		pRhs,
			tIterator	iBegin,
			tIterator	iEnd
		)
		{
			// do nothing if there is no need to splice
			if( iBegin == iEnd || (this == pRhs && iBegin == iSplice) )
				return true;
			
			RJ_ASSERT( !pRhs->IsEmpty() );
			RJ_ASSERT( iBegin != pRhs->GetEnd() );

			// if the same allocator is being used, we can do a simple relink
			if( this->NodeAllocator().CompareHeap(pRhs->NodeAllocator()) )
			{	
				// make sure the slice location is not contained within the inserted range
				RJ_ASSERT( this != pRhs || !ContainsItr(iBegin, iEnd, iSplice) );

				RJ_ASSERT( iBegin.m_pNode	!= NULL && iBegin.m_pNode->Prev()	!= NULL );
				RJ_ASSERT( iEnd.m_pNode		!= NULL && iEnd.m_pNode->Prev()		!= NULL );
				RJ_ASSERT( iSplice.m_pNode	!= NULL && iSplice.m_pNode->Prev()	!= NULL );
					
				iBegin.m_pNode->Prev()->Next()	= iEnd.m_pNode;
				iEnd.m_pNode->Prev()->Next()	= iSplice.m_pNode;
				iSplice.m_pNode->Prev()->Next()	= iBegin.m_pNode;
					
				tNode * pNode = iSplice.m_pNode->Prev();
					
				iSplice.m_pNode->Prev()	= iEnd.m_pNode->Prev();
				iEnd.m_pNode->Prev()	= iBegin.m_pNode->Prev();
				iBegin.m_pNode->Prev()	= pNode;
			}
			// else the allocators are different
			else
			{	
				// copy nodes and then Erase source
				if( InsertRange(iSplice, iBegin, iEnd) == false )
					return false;

				pRhs->EraseRange(iBegin, iEnd);
			}

			return true;
		}


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


		//******************************************************************************
		// tList::RemoveIf
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Predicate>
		inline void tList<t_Element,t_Allocator>::RemoveIf
		(
			t_Predicate predicate
		)
		{
			const tIterator iEnd = GetEnd();
			tIterator iCur = GetBegin();
			while( iCur != iEnd )
			{
				if( predicate(*iCur) )
					iCur = Erase(iCur);
				else
					++iCur;
			}
		}


		//******************************************************************************
		// tList::Remove
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tList<t_Element,t_Allocator>::Remove
		(
			const t_Element & element
		)
		{
			RemoveIf( Make_BindSecond( tEqual<t_Element>(), element ) );
		}


		//******************************************************************************
		// tList::Unique
		// Remove consequtive elements that are equal.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Predicate>
		inline void tList<t_Element,t_Allocator>::Unique
		(
			t_Predicate predicate // returns true if elements are equal
		)
		{	
			// if we need to do anything
			if( !IsEmpty() )
			{
				const tIterator iEnd = GetEnd();
				tIterator iCur  = GetBegin();
				tIterator iNext = iCur;
				++iNext;

				while( iNext != iEnd )
				{
					if( predicate( *iCur, *iNext ) )
						iNext = Erase(iNext);
					else
						iCur = iNext++;
				}
			}
		}


		//******************************************************************************
		// tList::Unique
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tList<t_Element,t_Allocator>::Unique()
		{	
			Unique(	tEqual<t_Element>() );
		}


		//******************************************************************************
		// tList::Merge
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Predicate>
		inline tB tList<t_Element,t_Allocator>::Merge
		(
			tThis *		pRhs,
			t_Predicate predicate
		)
		{	
			RJ_ASSERT( pRhs != this );

			tIterator this_cur			= GetBegin();
			const tIterator this_end	= GetEnd();

			tIterator rhs_cur		= pRhs->GetBegin();
			const tIterator rhs_end	= pRhs->GetEnd();

			// splice the rhs elements into this until we have finished
			// iterating through one of the lists
			while( this_cur != this_end && rhs_cur != rhs_end )
			{
				// if we should Splice rhs_cur in front of this_cur
				if( predicate( *rhs_cur, *this_cur ) )
				{	
					tIterator rhs_next = rhs_cur;
					if( SpliceRange( this_cur, pRhs, rhs_cur, ++rhs_next ) == false )
						return false;

					rhs_cur = rhs_next;
				}
				// else continue through this
				else
				{
					++this_cur;
				}
			}

			// if we have not finished merging all of the elements,
			// we can splice the rest of rhs at the GetEnd of this
			if( rhs_cur != rhs_end )
			{
				if( SpliceRange( this_end, pRhs, rhs_cur, rhs_end ) == false )
					return false;
			}

			// rhs should be empty at this point
			RJ_ASSERT( pRhs->IsEmpty() );
			
			return true;
		}


		//******************************************************************************
		// tList::Merge
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::Merge
		(
			tThis * pRhs
		)
		{	
			return Merge( pRhs, tLess<t_Element>() );
		}


		//******************************************************************************
		// tList::Sort
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Predicate>
		inline tB tList<t_Element,t_Allocator>::Sort
		(
			t_Predicate predicate
		)
		{
			// Do nothing if the list has length 0 or 1.
			if(		&m_endNodeLink.m_pNext->m_link != &m_endNodeLink
				&&	&m_endNodeLink.m_pNext->Next()->m_link != &m_endNodeLink )
			{
				const tSize c_Max_Bins = 30;
				
				tStaticVector<c_Max_Bins,tThis> binList;
				if( binList.Resize(c_Max_Bins) == false )
					return false;

				for (tThis *pCur = binList.GetDataBegin(), *pEnd = binList.GetDataEnd(); pCur != pEnd; ++pCur)
					if (!pCur->NodeAllocator().CopyHeap( this->NodeAllocator() ))
						return false;

				tThis tempList;
				if (!tempList.NodeAllocator().CopyHeap( this->NodeAllocator() ))
					return false;

				tSize maxBin = 0;

				// loop until all elements have been sorted into bins
				while( !IsEmpty() )
				{	
					if( tempList.Splice( tempList.GetBegin(), this, GetBegin() ) == false )
						return false;
					
					tSize binIdx = 0;

					while( binIdx < maxBin && !binList[binIdx].IsEmpty() )
					{
						if( binList[binIdx].Merge( &tempList, predicate ) == false )
							return false;

						if( binList[binIdx].Swap( &tempList ) == false )
							return false;

						++binIdx;
					}

					// if we ran out of bins
					if( binIdx == (c_Max_Bins-1) )
					{
						binList[binIdx - 1].Merge( &tempList, predicate );
					}
					else
					{
						binList[binIdx].Swap(&tempList);
						if( binIdx == maxBin )
						{
							++maxBin;
						}
					}
				}

				// generate the final sorted list from the bins
				for( tSize binIdx = 1; binIdx < maxBin; ++binIdx )
				{
					binList[binIdx].Merge( &binList[binIdx - 1], predicate );
				}
				
				// replace from last bin
				if( Swap( &binList[maxBin - 1] ) == false )
					return false;
			}

			return true;
		}


		//******************************************************************************
		// tList::Sort
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::Sort()
		{	
			return Sort( tLess<t_Element>() );
		}


		//******************************************************************************
		// tList::Reverse
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::Reverse()
		{	
			// if we need to do anything
			if( !IsEmpty() )
			{
				const tIterator iEnd = GetEnd();
				tIterator iCur = ++GetBegin();
				while( iCur != iEnd )
				{
					// move next element to beginning
					tIterator iPrev = iCur;
					if( SpliceRange( GetBegin(), this, iPrev, ++iCur ) == false )
						return false;
				}
			}

			return true;
		}


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

			tConstIterator iLhsCur = GetBegin();
			tConstIterator iRhsCur = rhs.GetBegin();

			const tConstIterator iLhsEnd = GetEnd();
			const tConstIterator iRhsEnd = rhs.GetEnd();
			
			while(		iLhsCur != iLhsEnd
					&&	iRhsCur != iRhsEnd
					&&	*iLhsCur == *iRhsCur )
			{
				++iLhsCur;
				++iRhsCur;
			}

			return (iLhsCur == iLhsEnd) && (iRhsCur == iRhsEnd);
		}


		//******************************************************************************
		// tList::IsLess
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::IsLess
		(
			const tThis & rhs
		) const
		{
			return LexicographicalCompare(	GetBegin(),
											GetEnd(),
											rhs.GetBegin(),
											rhs.GetEnd() );
		}


		//******************************************************************************
		// tList::InsertOne
		// Returns false on failure
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::InsertOne
		(
			tIterator iInsert
		)
		{
			tNode * pNode = iInsert.m_pNode;
			RJ_ASSERT( pNode != NULL );
		    
			tNode * pNewNode = AllocNode( pNode->Prev(), pNode );
			if( pNewNode == NULL )
				return false;

			pNode->Prev() = pNewNode;

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

			return true;
		}


		//******************************************************************************
		// tList::InsertOne
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tList<t_Element,t_Allocator>::InsertOne
		(
			tIterator			iInsert,
			const t_Element &	element
		)
		{
			tNode * pNode = iInsert.m_pNode;
			RJ_ASSERT( pNode );
		    
			tNode * pNewNode = AllocNode( 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;
		}


		//******************************************************************************
		// tList::AllocNode
		// Returns NULL on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline typename tList<t_Element,t_Allocator>::tNode *tList<t_Element,t_Allocator>::AllocNode
		(
			tNode * pPrevNode,
			tNode * pNextNode
		)
		{
			tNode * pNode = (tNode*)this->NodeAllocator().Allocate(sizeof(tNode));
			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);
		}


		//******************************************************************************
		// tList::AllocNode
		// Returns NULL on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline typename tList<t_Element,t_Allocator>::tNode *tList<t_Element,t_Allocator>::AllocNode
		(
			tNode *				pPrevNode,
			tNode *				pNextNode,
			const t_Element	&	element
		)
		{
			tNode *pNode = (tNode*)this->NodeAllocator().Allocate(sizeof(tNode));
			if( pNode == NULL )
				return NULL;

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

			return (pNode);
		}


	}
}