/******************************************************************************
  RedBlackTree.inl
  This file contains function definitions for tRedBlackTree.

 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.
******************************************************************************/


namespace RJ
{
	namespace Containers
	{
		//******************************************************************************
		// tRedBlackTreeIteratorBase == tRedBlackTreeIteratorBase::tOther
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator, typename t_ThisElement, typename t_ThisNodePtr, typename t_OtherElement, typename t_OtherNodePtr>
		inline tB operator ==
		(
			const tRedBlackTreeIteratorBase<t_Key, t_Element, t_KeyAccessor, t_KeyCompare, t_Allocator, t_ThisElement, t_ThisNodePtr, t_OtherElement, t_OtherNodePtr> & lhs,
			const typename tRedBlackTreeIteratorBase<t_Key, t_Element, t_KeyAccessor, t_KeyCompare, 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);
		}

		//******************************************************************************
		// tRedBlackTreeNode::GetPrev
		// Return the previous node in the tree from this node for iteration.
		//******************************************************************************
		template< typename t_Element >
		inline tRedBlackTreeNode<t_Element> * tRedBlackTreeNode<t_Element>::GetPrev()
		{
			// if this is the end node, return the rightmost node
			if( Color() == tLink::C_Red && Parent()->Parent() == this )
			{
				return Right();
			}
			// else if there are smaller nodes below us, return the largest
			else if( Left() != NULL )
			{
				return GetMaxNode( Left() );
			}
			// else find the first smaller node above this one
			else
			{
				tThis * pCur	= this;
				tThis * pResult	= Parent();
				while( pCur == pResult->Left() )
				{
					pCur	= pResult;
					pResult	= pResult->Parent();
				}
				return pResult;
			}
		}


		//******************************************************************************
		// tRedBlackTreeNode::GetPrev
		// Return the previous node in the tree from this node for iteration.
		//******************************************************************************
		template< typename t_Element >
		inline const tRedBlackTreeNode<t_Element> * tRedBlackTreeNode<t_Element>::GetPrev() const
		{
			// if this is the end node, return the rightmost node
			if( Color() == tLink::C_Red && Parent()->Parent() == this )
			{
				return Right();
			}
			// else if there are smaller nodes below us, return the largest
			else if( Left() != NULL )
			{
				return GetMaxNode( Left() );
			}
			// else find the first smaller node above this one
			else
			{
				const tThis * pCur		= this;
				const tThis * pResult	= Parent();
				while( pCur == pResult->Left() )
				{
					pCur	= pResult;
					pResult	= pResult->Parent();
				}
				return pResult;
			}
		}


		//******************************************************************************
		// tRedBlackTreeNode::GetNext
		// Return the next node in the tree from this node for iteration.
		//******************************************************************************
		template< typename t_Element >
		inline tRedBlackTreeNode<t_Element> * tRedBlackTreeNode<t_Element>::GetNext()
		{
			// cannot be the end node
			RJ_ASSERT( !(Color() == tLink::C_Red && Parent()->Parent() == this) );

			// if there are greater nodes beneath us, return the smallest
			if( Right() != NULL )
			{
				return GetMinNode( Right() );
			}
			// else find the first greater node above this one
			else
			{
				tRedBlackTreeNode * pCur = this;
				tRedBlackTreeNode * pPar = Parent();
				while( pCur == pPar->Right() )
				{
					pCur = pPar;
					pPar = pPar->Parent();
				}
				
				// if we reached the end node and the rightmost node is the root node
				if( pCur->Right() == pPar )
				{
					// return the end node
					return pCur;
				}
				// else the parent of the current node is the next largest node
				else
				{
					return pPar;
				}
			}

		}

		//******************************************************************************
		// tRedBlackTreeNode::GetNext
		// Return the next node in the tree from this node for iteration.
		//******************************************************************************
		template< typename t_Element >
		inline const tRedBlackTreeNode<t_Element> * tRedBlackTreeNode<t_Element>::GetNext() const
		{
			// cannot be the end node
			RJ_ASSERT( !(Color() == tLink::C_Red && Parent()->Parent() == this) );

			// if there are greater nodes beneath us, return the smallest
			if( Right() != NULL )
			{
				return GetMinNode( Right() );
			}
			// else find the first greater node above this one
			else
			{
				const tRedBlackTreeNode * pCur = this;
				const tRedBlackTreeNode * pPar = Parent();
				while( pCur == pPar->Right() )
				{
					pCur = pPar;
					pPar = pPar->Parent();
				}
				
				// if we reached the end node and the rightmost node is the root node
				if( pCur->Right() == pPar )
				{
					// return the end node
					return pCur;
				}
				// else the parent of the current node is the next largest node
				else
				{
					return pPar;
				}
			}

		}


		//******************************************************************************
		// tRedBlackTreeNode::GetMinNode
		//******************************************************************************
		template< typename t_Element >
		inline tRedBlackTreeNode<t_Element> * tRedBlackTreeNode<t_Element>::GetMinNode(tThis * pNode)
		{
			while( pNode->Left() != NULL )
				pNode = pNode->Left();
			return pNode;
		}

		//******************************************************************************
		// tRedBlackTreeNode::GetMaxNode
		//******************************************************************************
		template< typename t_Element >
		inline tRedBlackTreeNode<t_Element> * tRedBlackTreeNode<t_Element>::GetMaxNode(tThis * pNode)
		{
			while( pNode->Right() != NULL )
				pNode = pNode->Right();
			return pNode;
		}

		//******************************************************************************
		// tRedBlackTreeNode::RotateLeft
		// - insert old node.right between node and node.parent
		// - set new node.right to old node.right.left
		//******************************************************************************
		template< typename t_Element >
		inline void tRedBlackTreeNode<t_Element>::RotateLeft
		(
			tThis *		pNode,	//     in: node to rotate around
			tThis **	ppRoot	// in/out: root of the tree
		)
		{
			tThis * pTemp	= pNode->Right();
			pNode->Right()	= pTemp->Left();

			if( pTemp->Left() != NULL )
				pTemp->Left()->Parent() = pNode;
			
			pTemp->Parent() = pNode->Parent();

			if( pNode == (*ppRoot) )
				(*ppRoot) = pTemp;
			else if( pNode == pNode->Parent()->Left() )
				pNode->Parent()->Left() = pTemp;
			else
				pNode->Parent()->Right() = pTemp;

			pTemp->Left() = pNode;
			pNode->Parent() = pTemp;
		}


		//******************************************************************************
		// tRedBlackTreeNode::RotateRight
		// - insert old node.left between node and node.parent
		// - set new node.left to old node.left.right.
		//******************************************************************************
		template< typename t_Element >
		inline void tRedBlackTreeNode<t_Element>::RotateRight
		(
			tThis *		pNode,	//     in: node to rotate around
			tThis **	ppRoot	// in/out: root of the tree
		)
		{
			tThis * pTemp = pNode->Left();
			pNode->Left() = pTemp->Right();
			
			if( pTemp->Right() != NULL )
				pTemp->Right()->Parent() = pNode;
			
			pTemp->Parent() = pNode->Parent();

			if( pNode == (*ppRoot) )
				(*ppRoot) = pTemp;
			else if( pNode == pNode->Parent()->Right() )
				pNode->Parent()->Right() = pTemp;
			else
				pNode->Parent()->Left() = pTemp;

			pTemp->Right() = pNode;
			pNode->Parent() = pTemp;
		}


		//******************************************************************************
		// tRedBlackTreeNode::Rebalance
		// Rebalance the tree after a given node was inserted.
		//******************************************************************************
		template< typename t_Element >
		inline void tRedBlackTreeNode<t_Element>::Rebalance
		(
			tThis *		pNode,	//     in: node that was inserted
			tThis **	ppRoot	// in/out: root of the tree
		)
		{
			// should be set to red before calling this
			RJ_ASSERT( pNode->Color() == tLink::C_Red );

			while(		pNode != (*ppRoot)
					&&	pNode->Parent()->Color() == tLink::C_Red )
			{
				if( pNode->Parent() == pNode->Parent()->Parent()->Left() )
				{
					tThis * const pParentParentRight = pNode->Parent()->Parent()->Right();
					if(		pParentParentRight != NULL
						&&	pParentParentRight->Color() == tLink::C_Red )
					{
						pNode->Parent()->Color()			= tLink::C_Black;
						pParentParentRight->Color()			= tLink::C_Black;
						pNode->Parent()->Parent()->Color()	= tLink::C_Red;

						pNode = pNode->Parent()->Parent();
					}
					else
					{
						if( pNode == pNode->Parent()->Right() )
						{
							pNode = pNode->Parent();
							RotateLeft( pNode, ppRoot );
						}
						
						pNode->Parent()->Color()			= tLink::C_Black;
						pNode->Parent()->Parent()->Color()	= tLink::C_Red;

						RotateRight( pNode->Parent()->Parent(), ppRoot );
					}
				}
				else
				{
					tThis * const pParentParentLeft = pNode->Parent()->Parent()->Left();
					if(		pParentParentLeft != NULL
						&&	pParentParentLeft->Color() == tLink::C_Red )
					{
						pNode->Parent()->Color()			= tLink::C_Black;
						pParentParentLeft->Color()			= tLink::C_Black;
						pNode->Parent()->Parent()->Color()	= tLink::C_Red;

						pNode = pNode->Parent()->Parent();
					}
					else
					{
						if( pNode == pNode->Parent()->Left() )
						{
							pNode = pNode->Parent();
							RotateRight( pNode, ppRoot );
						}
						pNode->Parent()->Color()			= tLink::C_Black;
						pNode->Parent()->Parent()->Color()	= tLink::C_Red;
						RotateLeft( pNode->Parent()->Parent(), ppRoot );
					}
				}
			}

			(*ppRoot)->Color() = tLink::C_Black;
		}


		//******************************************************************************
		// tRedBlackTreeNode::RebalanceForErase
		// Rebalance the tree removing a given node. This function will ensure
		// that iterators to all other nodes will remain valid.
		//******************************************************************************
		template< typename t_Element >
		inline void tRedBlackTreeNode<t_Element>::RebalanceForErase
		(
			tThis *	const	pNode,		//     in: node to be removed
			tThis **		ppRoot,		// in/out: root of the tree
			tThis **		ppLeftmost,	// in/out: leftmost node of the tree
			tThis **		ppRightmost	// in/out: rightmost node of the tree
		)
		{
			tThis * pReplaceA		= pNode;	// node that will link into pNode's spot
			tThis * pReplaceB		= NULL;		// node that will link into pReplaceA's spot (may be NULL)
			tThis * pReplaceBPar	= NULL;		// parent of pReplaceA

			// if pNode has at most one non-null child.
			if( pNode->Left() == NULL )
			{
				// Track the non-null child.
				pReplaceB = pNode->Right(); 
			}
			// else if pNode has exactly one non-null child.
			else if( pNode->Right() == NULL ) 
			{
				// Track the non-null child.
				pReplaceB = pNode->Left();    
			}
			// else pNode has two non-null children.  
			else
			{                   
				// Set pReplaceA to pNode's successor (the first node greater than pNode).
				pReplaceA = GetMinNode(pNode->Right());

				// Track the greater child. (note: pReplaceB might be NULL)
				pReplaceB = pReplaceA->Right();
			}

			// If pReplaceA is not equivalent to pNode. Note this means
			// pNode has two non-null children, and is thus neither the
			// leftmost or rightmost node. Also implies that pReplaceB is the
			// right child of pReplaceA.
			if( pReplaceA != pNode )
			{
				RJ_ASSERT( pReplaceA->Left() == NULL );

				// relink pNode's left child as pReplaceA's left child
				pNode->Left()->Parent()	= pReplaceA; 
				pReplaceA->Left()		= pNode->Left();

				// if pReplaceA is pNode's right child
				if( pReplaceA == pNode->Right() )
				{

					// the parent of pReplaceB is pReplaceA (note: pReplaceB might be NULL)
					pReplaceBPar = pReplaceA;

					// pReplaceB should already be linked to pReplaceBPar
					RJ_ASSERT( pReplaceB == NULL || pReplaceB->Parent() == pReplaceBPar );
				}
				// else pReplaceA is the min node of pNode's right child
				else
				{
					// storer the parent of pReplaceB and link pReplaceB to it if necessary
					pReplaceBPar = pReplaceA->Parent();
					if( pReplaceB != NULL )
					{
						pReplaceB->Parent() = pReplaceA->Parent();
					}

					// pReplaceA must be a left child (it is the min node)
					RJ_ASSERT( pReplaceA->Parent()->Left() == pReplaceA );

					// link the parent of pReplaceA to the node replacing it
					pReplaceA->Parent()->Left() = pReplaceB;     

					// relink pNode's right child as pReplaceA's left child
					pNode->Right()->Parent()	= pReplaceA;
					pReplaceA->Right()		= pNode->Right();
				}

				// link pNode's parent to pReplaceA
				if( (*ppRoot) == pNode )
					(*ppRoot) = pReplaceA;
				else if( pNode->Parent()->Left() == pNode )
					pNode->Parent()->Left() = pReplaceA;
				else
					pNode->Parent()->Right() = pReplaceA;

				// link pReplaceA to pNode's parent
				pReplaceA->Parent() = pNode->Parent();

				// swap the colors of the successor and node to remove
				RJ::Swap( &pReplaceA->Color(), &pNode->Color() );
			}
			// else pReplaceA == pNode
			else
			{
				// link pReplaceB to pNode's parent
				pReplaceBPar = pNode->Parent();
				if( pReplaceB != NULL )
					pReplaceB->Parent() = pNode->Parent();   
				
				// link pNode's parent to pReplaceB
				if( (*ppRoot) == pNode )
					(*ppRoot) = pReplaceB;
				else if( pNode->Parent()->Left() == pNode )
					pNode->Parent()->Left() = pReplaceB;
				else
					pNode->Parent()->Right() = pReplaceB;
			
				// If we are removing the leftmost node
				if( (*ppLeftmost) == pNode ) 
				{
					// if it has no greater child (thus no children)
					if( pNode->Right() == NULL )
						// Set the leftmost node to the parent of pNode. Note that
						// this makes pLeftmost == &m_endNodeLink if pNode == pRoot
						(*ppLeftmost) = pNode->Parent();
					else
						// Set the leftmost to the min node of what is replaced pNode
						(*ppLeftmost) = GetMinNode(pReplaceB);
				}
				
				// If we are removing the rightmost node
				if( (*ppRightmost) == pNode )
				{
					// if it has no smaller child (thus no children)
					if( pNode->Left() == NULL )
						// Set the rightmost node to the parent of pNode. Note that
						// this makes pRightmost == &m_endNodeLink if pNode == pRoot
						(*ppRightmost) = pNode->Parent();  
					else
						// Set the rightmost to the max node of what replaced pNode
						(*ppRightmost) = GetMaxNode(pReplaceB);
				}
			}

			// If pNode's color is now black. (Either originally red
			// or had two children and was replaced by a red node)
			if( pNode->Color() != tLink::C_Red )
			{ 
				// Restore the red black properties of the tree
				while(		( pReplaceB != (*ppRoot) )
						&&	( pReplaceB == NULL || pReplaceB->Color() == tLink::C_Black ) )
				{
					// if replaceB is a left child
					if( pReplaceB == pReplaceBPar->Left() )
					{
						tThis * pBParRight = pReplaceBPar->Right();
						if( pBParRight->Color() == tLink::C_Red )
						{
							pBParRight->Color()		= tLink::C_Black;
							pReplaceBPar->Color()	= tLink::C_Red;
							RotateLeft( pReplaceBPar, ppRoot );
							pBParRight = pReplaceBPar->Right();
						}
						
						if(		(pBParRight->Left() == NULL || pBParRight->Left()->Color() == tLink::C_Black)
							&&	(pBParRight->Right() == NULL || pBParRight->Right()->Color() == tLink::C_Black) )
						{
							pBParRight->Color() = tLink::C_Red;
							pReplaceB			= pReplaceBPar;
							pReplaceBPar		= pReplaceBPar->Parent();
						}
						else
						{
							if( pBParRight->Right() == 0 || pBParRight->Right()->Color() == tLink::C_Black )
							{
								if( pBParRight->Left() )
									pBParRight->Left()->Color() = tLink::C_Black;
							
								pBParRight->Color() = tLink::C_Red;
								RotateRight( pBParRight, ppRoot );
								pBParRight = pReplaceBPar->Right();
							}
							
							pBParRight->Color() = pReplaceBPar->Color();
							pReplaceBPar->Color() = tLink::C_Black;

							if( pBParRight->Right() )
								pBParRight->Right()->Color() = tLink::C_Black;

							RotateLeft( pReplaceBPar, ppRoot );
							break;
						}
					}
					// if replaceB is a right child
					else
					{
						RJ_ASSERT( pReplaceB == pReplaceBPar->Right() );

						// same as above, with m_pRight <-> m_pLeft.
						tThis * pBParLeft = pReplaceBPar->Left();
						if( pBParLeft->Color() == tLink::C_Red )
						{
							pBParLeft->Color()		= tLink::C_Black;
							pReplaceBPar->Color()	= tLink::C_Red;
							RotateRight( pReplaceBPar, ppRoot );
							pBParLeft = pReplaceBPar->Left();
						}
			
						if(		(pBParLeft->Right() == NULL || pBParLeft->Right()->Color() == tLink::C_Black)
							&&	(pBParLeft->Left() == NULL || pBParLeft->Left()->Color() == tLink::C_Black))
						{
							pBParLeft->Color() = tLink::C_Red;
							pReplaceB		= pReplaceBPar;
							pReplaceBPar	= pReplaceBPar->Parent();
						}
						else
						{
							if( pBParLeft->Left() == 0 || pBParLeft->Left()->Color() == tLink::C_Black)
							{
								if( pBParLeft->Right() )
									pBParLeft->Right()->Color() = tLink::C_Black;

								pBParLeft->Color() = tLink::C_Red;
								RotateLeft( pBParLeft, ppRoot );
								pBParLeft = pReplaceBPar->Left();
							}
							
							pBParLeft->Color() = pReplaceBPar->Color();
							pReplaceBPar->Color() = tLink::C_Black;
							if( pBParLeft->Left() )
								pBParLeft->Left()->Color() = tLink::C_Black;
							
							RotateRight( pReplaceBPar, ppRoot );
							
							break;
						}
					}
				}
					
				if( pReplaceB )
					pReplaceB->Color() = tLink::C_Black;
			}
		}


		//******************************************************************************
		// tRedBlackTreeNode::GetBlackCount
		// Return the number of inclusive black nodes between the root and
		// a given node in the tree.
		//******************************************************************************
		#ifdef RJ_ENABLE_ASSERT
			template< typename t_Element >
			inline tSize tRedBlackTreeNode<t_Element>::GetBlackCount
			(
				const tThis * pNode,
				const tThis * pRoot
			)
			{
				if( pNode == NULL )
					return 0;
				else
				{
					int blackCount = (pNode->Color() == tLink::C_Black) ? 1 : 0;
					if( pNode == pRoot )
						return blackCount;
					else
						return blackCount + GetBlackCount(pNode->Parent(), pRoot);
				}
			}
		#endif

			
		//******************************************************************************
		// tRedBlackTree::tRedBlackTree
		// Constructor
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tRedBlackTree()
			:
			m_nodeAllocator_keyAccessor_keyCompare_size(
				tCompressedPair_DefaultFirst(),
				tKeyAccessor_KeyCompare_Size(
					tCompressedPair_DefaultFirst(),
					tKeyCompare_Size( tCompressedPair_DefaultFirst(), 0 ) ) )
		{
			InitEndNode();
		}


		//******************************************************************************
		// tRedBlackTree::tRedBlackTree
		// 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_Allocator>
		inline tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tRedBlackTree
		(
			const tThis & rhs
		) 
			:
			m_nodeAllocator_keyAccessor_keyCompare_size(
				tCompressedPair_DefaultFirst(),
				tKeyAccessor_KeyCompare_Size(
					tCompressedPair_DefaultFirst(),
					tKeyCompare_Size( tCompressedPair_DefaultFirst(), 0 ) ) )
		{
			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() );

			InitEndNode();
		}

		//******************************************************************************
		// tRedBlackTree::~tRedBlackTree
		// Destructor
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::~tRedBlackTree()
		{
			Clear();
		}


		//******************************************************************************
		// tRedBlackTree::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_Allocator>
		inline tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator> & tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::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;
		}


		//******************************************************************************
		// tRedBlackTree::Count
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline tSize tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::Count
		(
			const t_Key & key
		) const
		{
			tConstRange range = FindEqualRange(key);
			return GetDistance( range.m_first, range.m_second );
		}


		//******************************************************************************
		// tRedBlackTree::Find
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::Find
		(
			const t_Key & key
		)
		{
			tNode * pEndNode = tNode::GetNodeFromLink(&m_endNodeLink);

			// Prev node which is not less than key.
			tNode * pPrevNode = pEndNode;
			
			// Current node.
			tNode * pCurNode = Root();

			while( pCurNode != NULL ) 
			{
				if( !KeyCompare()( KeyAccessor()(pCurNode->m_element), key) )
				{
					pPrevNode	= pCurNode;
					pCurNode	= pCurNode->Left();
				}
				else
				{
					pCurNode	= pCurNode->Right();
				}
			}
			
			// if the key was not found
			if( pPrevNode != pEndNode && KeyCompare()(key, KeyAccessor()( pPrevNode->m_element )) )
				pPrevNode = pEndNode;

			return tIterator(pPrevNode);
		}


		//******************************************************************************
		// tRedBlackTree::Find
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tConstIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::Find
		(
			const t_Key & key
		) const
		{
			const tNode * pEndNode = tNode::GetNodeFromLink(&m_endNodeLink);

			// Prev node which is not less than key.
			const tNode * pPrevNode = pEndNode;
			
			// Current node.
			const tNode * pCurNode = Root();

			while( pCurNode != NULL ) 
			{
				if( !KeyCompare()( KeyAccessor()(pCurNode->m_element), key) )
				{
					pPrevNode	= pCurNode;
					pCurNode	= pCurNode->Left();
				}
				else
				{
					pCurNode	= pCurNode->Right();
				}
			}
			
			// if the key was not found
			if( pPrevNode != pEndNode && KeyCompare()(key, KeyAccessor()( pPrevNode->m_element )) )
				pPrevNode = pEndNode;

			return tConstIterator(pPrevNode);
		}


		//******************************************************************************
		// tRedBlackTree::FindLowerBound
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::FindLowerBound
		(
			const t_Key & key
		)
		{
			// Prev node which is not less than key.
			tNode * pPrevNode = tNode::GetNodeFromLink(&m_endNodeLink);

			// Current node.
			tNode * pCurNode = Root();

			while( pCurNode != NULL ) 
			{
				if( !KeyCompare()( KeyAccessor()(pCurNode->m_element), key ) )
				{
					pPrevNode	= pCurNode;
					pCurNode	= pCurNode->Left();
				}
				else
				{
					pCurNode	= pCurNode->Right();
				}
			}

			return tIterator(pPrevNode);
		}


		//******************************************************************************
		// tRedBlackTree::FindLowerBound
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tConstIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::FindLowerBound
		(
			const t_Key & key
		) const
		{
			// Prev node which is not less than key.
			const tNode * pPrevNode = tNode::GetNodeFromLink(&m_endNodeLink);

			// Current node.
			const tNode * pCurNode = Root();

			while( pCurNode != NULL ) 
			{
				if( !KeyCompare()( KeyAccessor()(pCurNode->m_element), key) )
				{
					pPrevNode = pCurNode;
					pCurNode = pCurNode->Left();
				}
				else
					pCurNode = pCurNode->Right();
			}

			return tConstIterator(pPrevNode);
		}


		//******************************************************************************
		// tRedBlackTree::FindUpperBound
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::FindUpperBound
		(
			const t_Key & key
		)
		{
			// Prev node which key is less than
			tNode * pPrevNode = tNode::GetNodeFromLink(&m_endNodeLink);

			// Current node.
			tNode * pCurNode = Root();

			while( pCurNode != NULL ) 
			{
				if( KeyCompare()(key,  KeyAccessor()(pCurNode->m_element)) )
				{
					pPrevNode	= pCurNode;
					pCurNode	= pCurNode->Left();
				}
				else
					pCurNode	= pCurNode->Right();
			}

			return tIterator(pPrevNode);
		}


		//******************************************************************************
		// tRedBlackTree::FindUpperBound
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tConstIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::FindUpperBound
		(
			const t_Key & key
		) const
		{
			// Prev node which key is less than
			const tNode * pPrevNode = tNode::GetNodeFromLink(&m_endNodeLink);

			// Current node.
			const tNode * pCurNode = Root();

			while( pCurNode != NULL ) 
			{
				if( KeyCompare()( key, KeyAccessor()(pCurNode->m_element) ) )
				{
					pPrevNode = pCurNode;
					pCurNode = pCurNode->Left();
				}
				else
					pCurNode = pCurNode->Right();
			}

			return tConstIterator(pPrevNode);
		}


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


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


		//******************************************************************************
		// tRedBlackTree::InsertUnique
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tInsertResult tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertUnique
		(
			const t_Element & element
		)
		{
			tNode *pParNode = tNode::GetNodeFromLink(&m_endNodeLink);
			tNode *pCurNode = Root();
			
			tB compareResult = true;
			
			// find the leaf node to insert as a child of
			while( pCurNode != NULL )
			{
				pParNode = pCurNode;
				compareResult = KeyCompare()( KeyAccessor()(element), KeyAccessor()(pCurNode->m_element) );
				pCurNode = compareResult ? pCurNode->Left() : pCurNode->Right();
			}

			tIterator iInsert = tIterator(pParNode);   

			// if the value was less than the leaf node
			if( compareResult )
			{
				// if the leaf node was the leftmost node, insert before it
				if( iInsert == GetBegin() )
				{
					tIterator iInsertedNode = InsertNodeEqual(pParNode, element, true, false );
					tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
					return result;
				}
				// else decrement the insertion point to a node less than or equal to the value
				else
				{
					--iInsert;
				}
			}

			// if the insertion point is less than the element, insert after it
			if( KeyCompare()( KeyAccessor()(*iInsert), KeyAccessor()(element) ) )
			{
				tIterator iInsertedNode = InsertNodeEqual(pParNode, element, false, false );
				tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
				return result;
			}
			// else the insertion point is an equal value, fail to insert
			else
			{
				tInsertResult result = { iInsert, false };
				return result;
			}
		}


		//******************************************************************************
		// tRedBlackTree::InsertEqual
		// The end iterator is returned on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertEqual
		(
			const t_Element & element
		)
		{
			tNode * pParNode = tNode::GetNodeFromLink(&m_endNodeLink);
			tNode *	pCurNode = Root();

			// find the leaf node to insert as a child of
			while( pCurNode != NULL )
			{
				pParNode = pCurNode;
				pCurNode =		KeyCompare()( KeyAccessor()(element), KeyAccessor()(pCurNode->m_element) )
							?	pCurNode->Left()
							:	pCurNode->Right();
			}

			// insert under the current node
			return InsertNodeEqual( pParNode, element, false, false );
		}


		//******************************************************************************
		// tRedBlackTree::InsertUnique
		// The first element of the returned pair is set to an iterator to the
		// newly inserted node or an existing node with the same key. The
		// second value is set to true if insertion was possible (no existing
		// node had a matching key) or false if a node with the same key was
		// found.
		// If there is an attempted insertion with an allocation failure, the
		// first element of the pair is set to the end iterator and the second
		// element is set to false.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tInsertResult tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertUnique
		(
			tIterator			iHint,	// in: A hint regarding the place to start searching for the correct point of insertion
			const t_Element &	element	// in: Element to insert
		)
		{
			// if we should start searching at the being node
			if( iHint.m_pNode == Leftmost() )
			{
				// if the container is empty, fall back on InsertUnique.
				if( IsEmpty() )
					return InsertUnique(element);

				// if the element is less than the hint point
				if( KeyCompare()(KeyAccessor()(element), KeyAccessor()(*iHint)) )
				{
					// first argument just needs to be non-null
					tIterator iInsertedNode = InsertNodeEqual( iHint.m_pNode, element, true, false );
					tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
					return result;
				}
				else
				{
					// if the element is not greater than the hint point, they are equal
					if( !KeyCompare()( KeyAccessor()(*iHint), KeyAccessor()(element) ) )
					{
						tInsertResult result = { iHint, false };
						return result;
					}

					// Standard-conformance - does the insertion point fall immediately AFTER
					// the hint?
					tIterator iAfter = iHint;
					++iAfter;

					// Check for only one element -- in that case, iHint points to itself,
					// and attempting to increment will cause an infinite loop.
					if( iAfter.m_pNode == tNode::GetNodeFromLink(&m_endNodeLink) )
					{
						// Check guarantees exactly one member, so comparison was already
						// performed and we know the result; skip repeating it in Insert_Node
						// by passing true as the fourth argument.
						tIterator iInsertedNode = InsertNodeEqual( iHint.m_pNode, element, false, true );
						tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
						return result;
					}

					// Optimization to catch insert-equivalent -- save comparison results,
					// and we get this for free.
					if( KeyCompare()( KeyAccessor()(element), KeyAccessor()(*iAfter) ) )
					{
						tIterator iInsertedNode;
						if( iHint.m_pNode->Right() == NULL )
							iInsertedNode = InsertNodeEqual( iHint.m_pNode, element, false, true );
						else
							iInsertedNode = InsertNodeEqual( iAfter.m_pNode, element, true, false );

						tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
						return result;
					}
					else
					{
						return InsertUnique(element);
					}
				}
			}
			// else if we should start searching at the end node
			else if( iHint.m_pNode == tNode::GetNodeFromLink(&m_endNodeLink) )
			{
				if( KeyCompare()(	KeyAccessor()(Rightmost()->m_element),
									KeyAccessor()(element) ) )
				{
					// give hint: (rightmost < element) == true
					tIterator iInsertedNode = InsertNodeEqual( Rightmost(), element, false, true );
					tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
					return result;
				}
				else
				{
					return InsertUnique(element);
				}
			}
			// else we should start searching somewhere in the middle
			else
			{
				tIterator iBefore = iHint;
				--iBefore;

				const tB elementLessHint = KeyCompare()( KeyAccessor()(element), KeyAccessor()(*iHint) );

				if( elementLessHint && KeyCompare()( KeyAccessor()(*iBefore), KeyAccessor()(element) ) )
				{
					tIterator iInsertedNode;
					if( iBefore.m_pNode->Right() == NULL )
						// give hint: (iBefore < element) == true
						iInsertedNode = InsertNodeEqual( iBefore.m_pNode, element, false, true );
					else
						// give hint: (element < iHint) == true
						iInsertedNode = InsertNodeEqual( iHint.m_pNode, element, true, false );

					tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
					return result;
				}
				else
				{
					// Does the insertion point fall immediately AFTER the hint?
					tIterator iAfter = iHint;
					++iAfter;

					// Optimization to catch equivalent cases and avoid unnecessary comparisons
					// If the earlier comparison was true, this comparison doesn't need to be
					// performed because it must be false.  However, if the earlier comparison
					// was false, we need to perform this one because in the equal case, both will
					// be false.
					const tB hintLessElement =	elementLessHint
												?	false
												:	KeyCompare()(KeyAccessor()(*iHint), KeyAccessor()(element));

					if(		( !elementLessHint )
						&&	( hintLessElement )
						&&	( iAfter.m_pNode == tNode::GetNodeFromLink(&m_endNodeLink) || KeyCompare()( KeyAccessor()(element), KeyAccessor()(*iAfter) ) ) )
					{
						tIterator iInsertedNode;
						if( iHint.m_pNode->Right() == NULL )
							iInsertedNode = InsertNodeEqual( iHint.m_pNode, element, false, true );
						else
							iInsertedNode = InsertNodeEqual( iAfter.m_pNode, element, true, false );

						tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
						return result;
					}
					else
					{
						// Test for equivalent case
						if( elementLessHint == hintLessElement )
						{
							tInsertResult result = { iHint, false };
							return result;
						}
						else
						{
							return InsertUnique(element);
						}
					}
				}
			}
		}

		//******************************************************************************
		// tRedBlackTree::InsertEqual
		// The end iterator is returned on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertEqual
		(
			tIterator			iHint,	// in: A hint regarding the place to start searching for the correct point of insertion
			const t_Element &	element	// in: Element to insert
		)
		{
			// if we should start searching at the begin node
			if( iHint.m_pNode == Leftmost() )
			{
				// Check for zero members
				if( IsEmpty() )
					return InsertEqual(element);

				// if the hint point is not less than the element
				if( !KeyCompare()( KeyAccessor()(*iHint), KeyAccessor()(element)) )
					return InsertNodeEqual( iHint.m_pNode, element, true, false );
				else
				{
					// Check for only one member
					if( iHint.m_pNode->Left() == iHint.m_pNode )
					{
						// Unlike InsertUnique, can't avoid doing a comparison here.
						return InsertNodeEqual( iHint.m_pNode, element, false, false );
					}

					// All other cases:
					// Standard-conformance - does the insertion point fall immediately AFTER
					// the hint?
					tIterator iAfter = iHint;
					++iAfter;

					// Already know that compare(hint,element) must be true!
					// Therefore, we want to know if compare(after,element) is false.
					// (i.e., we now hint < element, now we want to know if element <= after)
					// If not, invalid hint.
					if(		iAfter.m_pNode == tNode::GetNodeFromLink(&m_endNodeLink)
						||	!KeyCompare()(	KeyAccessor()(*iAfter),
											KeyAccessor()(element) ) )
					{
						if( iHint.m_pNode->Right() == NULL )
							return InsertNodeEqual( iHint.m_pNode, element, false, true );
						else
							return InsertNodeEqual( iAfter.m_pNode, element, true, false );
					}
					else
					{
						// Invalid hint
						return InsertEqual(element);
					}
				}
			}
			// if we should start searching at the end node
			else if( iHint.m_pNode == tNode::GetNodeFromLink(&m_endNodeLink) )
			{
				if( !KeyCompare()(	KeyAccessor()(element),
									KeyAccessor()( Rightmost()->m_element)) )
				{
					return InsertNodeEqual(Rightmost(), element, false, true); 
				}
				else
				{
					return InsertEqual(element);
				}
			}
			else
			{
				tIterator iBefore = iHint;
				--iBefore;
				
				// Store the result of the comparison between iHint and element so
				// that we don't have to do it again later.
				// Test here is for before <= element <= iHint.
				const tB hintLessElement = KeyCompare()( KeyAccessor()(*iHint), KeyAccessor()(element) );
				if( !hintLessElement && !KeyCompare()(KeyAccessor()(element), KeyAccessor()(*iBefore) ) )
				{
					if( iBefore.m_pNode->Right() == NULL )
						return InsertNodeEqual( iBefore.m_pNode, element, false, true );
					else
						return InsertNodeEqual( iHint.m_pNode, element, true, false );
				}
				else
				{
					// Does the insertion point fall immediately AFTER the hint?
					// Test for iHint < element <= after
					tIterator iAfter = iHint;
					++iAfter;

					if(		hintLessElement
						&&	(		iAfter.m_pNode == tNode::GetNodeFromLink(&m_endNodeLink)
								||	!KeyCompare()( KeyAccessor()(*iAfter), KeyAccessor()(element) ) ) )
					{
						if( iHint.m_pNode->Right() == NULL )
							return InsertNodeEqual( iHint.m_pNode, element, false, true );
						else
							return InsertNodeEqual( iAfter.m_pNode, element, true, false );
					}
					else
					{
						// Invalid hint
						return InsertEqual(element);
					}
				}
			}
		}

		//******************************************************************************
		// tRedBlackTree::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.
		//
		// The first element of the returned pair is set to an iterator to the
		// newly inserted node or an existing node with the same key. The
		// second value is set to true if insertion was possible (no existing
		// node had a matching key) or false if a node with the same key was
		// found.
		// If there is an attempted insertion with an allocation failure, the
		// first element of the pair is set to the end iterator and the second
		// element is set to false.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tInsertResult tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertKeyUnique
		(
			const t_Key &	key
		)
		{
			tNode * pParNode = tNode::GetNodeFromLink(&m_endNodeLink);
			tNode *	pCurNode = Root();
			
			tB compareResult = true;
			
			// find the leaf node to insert as a child of
			while( pCurNode != NULL )
			{
				pParNode = pCurNode;
				compareResult = KeyCompare()( key, KeyAccessor()(pCurNode->m_element) );
				pCurNode =		compareResult
							?	pCurNode->Left()
							:	pCurNode->Right();
			}

			tIterator iInsert = tIterator(pParNode);   

			// if the value was less than the leaf node
			if( compareResult )
			{
				// if the leaf node was the leftmost node, insert before it
				if( iInsert == GetBegin() )
				{
					tIterator iInsertedNode = InsertNodeKeyEqual(pParNode, key, true, false );
					tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
					return result;
				}
				// else decrement the insertion point to a node less than or equal to the value
				else
				{
					--iInsert;
				}
			}

			// if the insertion point is less than the element, insert after it
			if( KeyCompare()( KeyAccessor()(*iInsert), key ) )
			{
				tIterator iInsertedNode = InsertNodeKeyEqual(pParNode, key, false, false );
				tInsertResult result = { iInsertedNode, iInsertedNode != GetEnd() };
				return result;
			}
			// else the insertion point is an equal value, fail to insert
			else
			{
				tInsertResult result = { iInsert, false };
				return result;
			}
		}
		
		//******************************************************************************
		// tRedBlackTree::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_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertKeyEqual
		(
			const t_Key & key
		)
		{
			tNode * pParNode = tNode::GetNodeFromLink(&m_endNodeLink);
			tNode *	pCurNode = Root();

			// find the leaf node to insert as a child of
			while( pCurNode != NULL )
			{
				pParNode = pCurNode;
				pCurNode =		KeyCompare()( key, KeyAccessor()(pCurNode->m_element) )
							?	pCurNode->Left()
							:	pCurNode->Right();
			}

			// insert under the current node
			return InsertNodeKeyEqual( pParNode, key, false, false );
		}


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

			return true;
		}


		//******************************************************************************
		// tRedBlackTree::InsertRangeEqual
		// Returns false on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		template<typename t_Iterator>
		inline tB tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertRangeEqual
		(
			t_Iterator iBegin,
			t_Iterator iEnd
		)
		{
			for( ; iBegin != iEnd; ++iBegin)
			{
				if( InsertEqual(*iBegin) == GetEnd() )
					return false;
			}

			return true;
		}


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

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

			// cannot erase the end node
			RJ_ASSERT( pNode != tNode::GetNodeFromLink(&m_endNodeLink) );

			// rebalance the tree removing the node
			tNode::RebalanceForErase( pNode, &Root(), &Leftmost(), &Rightmost() );

			// destroy this node
			RJ::Memory::Destruct( pNode );
			NodeAllocator().Deallocate( pNode );

			// decrement the size
			--Size();

			return iErase;
		}


		//******************************************************************************
		// tRedBlackTree::EraseRange
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,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;
		}


		//******************************************************************************
		// tRedBlackTree::EraseKey
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline tSize tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::EraseKey
		(
			const t_Key & key
		)
		{
			tRange equalRange = FindEqualRange( key );
			tSize numToErase = GetDistance( equalRange.m_begin, equalRange.m_end );
			EraseRange( equalRange.m_begin, equalRange.m_end );
			return numToErase;
		}


		//******************************************************************************
		// tRedBlackTree::Clear
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline void tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::Clear()
		{
			if( !IsEmpty() )
			{
				// erase the root and all its children
				EraseTree( Root() );

				// reset the end node
				Root()		= NULL;
				Leftmost()	= tNode::GetNodeFromLink(&m_endNodeLink);
				Rightmost() = tNode::GetNodeFromLink(&m_endNodeLink);

				// reset the size
				Size()		= 0;
			}
		}   


		//******************************************************************************
		// tRedBlackTree::Swap
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline tB tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::Swap
		(
			tThis * pRhs
		)
		{
			// if the allocator is the same
			if( NodeAllocator().CompareHeap( pRhs->NodeAllocator() ) )
			{
				// do a simple swap (accounting for self references)
				RJ::Swap( &m_endNodeLink,	&pRhs->m_endNodeLink );
				RJ::Swap( &Size(),			&pRhs->Size() );
				RJ::Swap( &KeyAccessor(),	&pRhs->KeyAccessor() );
				RJ::Swap( &KeyCompare(),	&pRhs->KeyCompare() );

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

				if( m_endNodeLink.m_pParent )
				{
					// fixup parent pointer of root nodes
					RJ_ASSERT( m_endNodeLink.m_pParent->Parent() == pRhsEndNode );
					m_endNodeLink.m_pParent->Parent() = pThisEndNode;
				}
				else
				{
					// fixup leftmost and rightmost pointers when there are no nodes
					RJ_ASSERT( m_endNodeLink.m_pLeft == pRhsEndNode );
					RJ_ASSERT( m_endNodeLink.m_pRight == pRhsEndNode );
					m_endNodeLink.m_pLeft = pThisEndNode;
					m_endNodeLink.m_pRight = pThisEndNode;
				}

				if( pRhs->m_endNodeLink.m_pParent )
				{
					// fixup parent pointer of root nodes
					RJ_ASSERT( pRhs->m_endNodeLink.m_pParent->Parent() == pThisEndNode );
					pRhs->m_endNodeLink.m_pParent->Parent() = pRhsEndNode;
				}
				else
				{
					// fixup leftmost and rightmost pointers when there are no nodes
					RJ_ASSERT( pRhs->m_endNodeLink.m_pLeft == pThisEndNode );
					RJ_ASSERT( pRhs->m_endNodeLink.m_pRight == pThisEndNode );
					pRhs->m_endNodeLink.m_pLeft = pRhsEndNode;
					pRhs->m_endNodeLink.m_pRight = pRhsEndNode;
				}
			}
			else
			{
				// store a copy of our tree
				tNode *			pOldRoot		= Root();
				tSize			oldSize			= Size();
				t_KeyAccessor	oldKeyAccessor	= KeyAccessor();
				t_KeyCompare	oldKeyCompare	= KeyCompare();

				// clear our internal tree data
				Size()		= 0;
				Root()		= NULL;
				Leftmost()	= tNode::GetNodeFromLink(&m_endNodeLink);
				Rightmost()	= tNode::GetNodeFromLink(&m_endNodeLink);

				// copy the other tree into us
				KeyAccessor()	= pRhs->KeyAccessor();
				KeyCompare()	= pRhs->KeyCompare();

				if( pRhs->Root() != NULL )
				{
					Root() = CopyTree( pRhs->Root(), tNode::GetNodeFromLink(&m_endNodeLink) );
					if( Root() == NULL )
					{
						// free the old tree data
						EraseTree( pOldRoot );
						return false;
					}

					Leftmost()	= tNode::GetMinNode( Root() );
					Rightmost()	= tNode::GetMaxNode( Root() );
					Size()		= pRhs->Size();
				}

				// clear the other tree data
				pRhs->Clear();

				// copy our old tree into the other tree
				pRhs->KeyAccessor()	= oldKeyAccessor;
				pRhs->KeyCompare()	= oldKeyCompare;

				if( pOldRoot != NULL )
				{
					pRhs->Root() = CopyTree( pOldRoot, tNode::GetNodeFromLink(&pRhs->m_endNodeLink) );
					if( pRhs->Root() == NULL )
					{
						// free the old tree data
						EraseTree( pOldRoot );
						return false;
					}

					pRhs->Leftmost()	= tNode::GetMinNode( pRhs->Root() );
					pRhs->Rightmost()	= tNode::GetMaxNode( pRhs->Root() );
					pRhs->Size()		= oldSize;

					// free the old tree data
					EraseTree( pOldRoot );
				}
			}

			return true;
		}

		//******************************************************************************
		// tRedBlackTree::Copy
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline tB tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::Copy
		(
			const tThis & rhs
		)
		{
			if( this != &rhs)
			{
				// Note that t_Key may be a constant type.
				Clear();
				
				KeyAccessor()	= rhs.KeyAccessor();
				KeyCompare()	= rhs.KeyCompare();

				if( rhs.Root() != NULL )
				{
					Root() = CopyTree( rhs.Root(), tNode::GetNodeFromLink(&m_endNodeLink) );
					if( Root() == NULL )
					{
						return false;
					}

					Leftmost()	= tNode::GetMinNode( Root() );
					Rightmost()	= tNode::GetMaxNode( Root() );
					Size()		= rhs.Size();
				}
			}

			return true;
		}

		//******************************************************************************
		// tRedBlackTree::IsValid
		//******************************************************************************
		#ifdef RJ_ENABLE_ASSERT
			template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
			tB tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::IsValid() const
			{
				if( Size() == 0 || GetBegin() == GetEnd() )
					return		Size() == 0
							&&	GetBegin() == GetEnd()
							&&	Leftmost() == tNode::GetNodeFromLink(&m_endNodeLink)
							&&	Rightmost() == tNode::GetNodeFromLink(&m_endNodeLink);

				tSize len = tNode::GetBlackCount( Leftmost(), Root() );
				
				for( tConstIterator iNode = GetBegin(); iNode != GetEnd(); ++iNode )
				{
					const tNode * pCurNode		= iNode.m_pNode;
					const tNode * pLeftNode		= pCurNode->Left();
					const tNode * pRightNode	= pCurNode->Right();

					if( pCurNode->Color() == tNodeLink::C_Red )
					{
						if(		(pLeftNode && pLeftNode->Color() == tNodeLink::C_Red)
							||	(pRightNode && pRightNode->Color() == tNodeLink::C_Red) )
						{
							return false;
						}
					}

					if( pLeftNode && KeyCompare()(KeyAccessor()(pCurNode->m_element), KeyAccessor()(pLeftNode->m_element)) )
						return false;
				
					if( pRightNode && KeyCompare()(KeyAccessor()(pRightNode->m_element), KeyAccessor()(pCurNode->m_element)) )
						return false;

					if( !pLeftNode && !pRightNode && tNode::GetBlackCount(pCurNode, Root()) != len )
						return false;
				}

				if( Leftmost() != tNode::GetMinNode(Root()) )
					return false;
				
				if( Rightmost() != tNode::GetMaxNode(Root()) )
					return false;

				return true;
			}
		#endif


		//******************************************************************************
		// tRedBlackTree::IsEqual
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline tB tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::IsEqual
		(
			const tThis &rhs
		) const
		{
			return		( Size() == rhs.Size() )
					&&	IsEqualRange( GetBegin(), GetEnd(), rhs.GetBegin() );
		}


		//******************************************************************************
		// tRedBlackTree::InitEndNode
		// Initialize the end node to a state where the tree is empty.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline void tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InitEndNode()
		{
			// flag the end node
			m_endNodeLink.m_color = tNodeLink::C_Red;

			// no nodes in the tree
			Root()		= NULL;
			Leftmost()	= tNode::GetNodeFromLink(&m_endNodeLink);
			Rightmost()	= tNode::GetNodeFromLink(&m_endNodeLink);
		}

		//******************************************************************************
		// tRedBlackTree::InsertNodeEqual
		// REturns end iterator on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertNodeEqual
		(
			tNode *			pInsert,
			tNode *			pNewNode,
			const t_Key &	key,
			tB				hintElementLessInsert,	// is (element < insert), true=yes, false=unknown
			tB				hintInsertLessElement	// is (insert < element), true=yes, false=unknown
		)
		{
			RJ_ASSERT( pInsert != NULL );
			RJ_ASSERT( pNewNode != NULL );
			
			// if inserting under the end node (implies no nodes in the tree)
			if( pInsert == tNode::GetNodeFromLink(&m_endNodeLink) )
			{
				Leftmost()	= pNewNode;
				Root()		= pNewNode;
				Rightmost() = pNewNode;
			}
			// else if inserting to the left of the node (element < insert)
			else if(	!hintInsertLessElement
					&&	(		hintElementLessInsert
							||	KeyCompare()( key, KeyAccessor()(pInsert->m_element) ) )
					)
			{
				pInsert->Left() = pNewNode;
				
				// maintain Leftmost() pointing to min node
				if( pInsert == Leftmost() )
					Leftmost() = pNewNode;		
			}
			// else inserting to the right of the node (insert < element)
			else
			{
				pInsert->Right() = pNewNode;

				// maintain Rightmost() pointing to max node
				if( pInsert == Rightmost() )
					Rightmost() = pNewNode;			
			}
			
			// rebalance the tree after the insert
			tNode::Rebalance( pNewNode, &Root() );

			// increment the size
			++Size();

			return tIterator(pNewNode);
		}

		//******************************************************************************
		// tRedBlackTree::InsertNodeEqual
		// Returns end iterator on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertNodeEqual
		(
			tNode *				pInsert,
			const t_Element &	element,
			tB					hintElementLessInsert,	// is (element < insert), true=yes, false=unknown
			tB					hintInsertLessElement	// is (insert < element), true=yes, false=unknown
		)
		{
			RJ_ASSERT( pInsert != NULL );
			tNode * pNewNode = AllocNode( tNodeLink::C_Red, pInsert, NULL, NULL, element );
			if( pNewNode == NULL )
				return GetEnd();

			return InsertNodeEqual(pInsert, pNewNode, KeyAccessor()(element), hintElementLessInsert, hintInsertLessElement);
		}

		//******************************************************************************
		// tRedBlackTree::InsertNodeKeyEqual
		// REturns end iterator on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tIterator tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::InsertNodeKeyEqual
		(
			tNode *			pInsert,
			const t_Key &	key,
			tB				hintElementLessInsert,	// is (element < insert), true=yes, false=unknown
			tB				hintInsertLessElement	// is (insert < element), true=yes, false=unknown
		)
		{
			RJ_ASSERT( pInsert != NULL );
			tNode * pNewNode = AllocNode( tNodeLink::C_Red, pInsert, NULL, NULL );
			if( pNewNode == NULL )
				return GetEnd();

			return InsertNodeEqual(pInsert, pNewNode, key, hintElementLessInsert, hintInsertLessElement);
		}

		//******************************************************************************
		// tRedBlackTree::CopyTree
		// Returns NULL on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tNode * tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::CopyTree
		(
			tNode *		pSrcRoot,	// in: root of the tree to make a copy of
			tNode *		pNewParent	// in: parent the root of the new tree should point to
		)
		{
			RJ_ASSERT( pSrcRoot != NULL );
			RJ_ASSERT( pNewParent != NULL );

			// make a copy of the src node that is a child of the dest node
			tNode * pNewRoot = AllocNode(	pSrcRoot->m_link.m_color,
											pNewParent,
											NULL,
											NULL,
											pSrcRoot->m_element );
			if( pNewRoot == NULL )
				return NULL;

			//===
			// copy the right children
			if( pSrcRoot->Right() )
			{
				pNewRoot->Right() = CopyTree( pSrcRoot->Right(), pNewRoot );
				
				if( pNewRoot->Right() == NULL )
				{
					EraseTree( pNewRoot );
					return NULL;
				}
			}
			
			//===
			// copy the left children
			pNewParent	= pNewRoot;
			pSrcRoot	= pSrcRoot->Left();

			while( pSrcRoot != NULL )
			{
				tNode * pNewChild = AllocNode(	pSrcRoot->m_link.m_color,
												pNewParent,
												NULL,
												NULL,
												pSrcRoot->m_element );
				if( pNewChild == NULL )
				{
					EraseTree( pNewRoot );
					return NULL;
				}

				pNewParent->Left() = pNewChild;
				if( pSrcRoot->Right() )
				{
					pNewChild->Right() = CopyTree( pSrcRoot->Right(), pNewChild );
					if( pNewChild->Right() == NULL )
					{
						EraseTree( pNewRoot );
						return NULL;
					}
				}
				
				pNewParent	= pNewChild;
				pSrcRoot	= pSrcRoot->Left();
			}

			return pNewRoot;
		}


		//******************************************************************************
		// tRedBlackTree::EraseTree
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline void tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::EraseTree
		(
			tNode * pNode
		)
		{
			// erase without rebalancing
			while( pNode != NULL )
			{
				EraseTree( pNode->Right() );

				tNode * pNext = pNode->Left();
				RJ::Memory::Destruct( pNode );
				NodeAllocator().Deallocate( pNode );

				pNode = pNext;
			}
		}


		//******************************************************************************
		// tRedBlackTree::AllocNode
		// Returns NULL on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tNode * tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::AllocNode
		(
			typename tNode::tColor	color,
			tNode *					pParentNode,
			tNode *					pLeftNode,
			tNode *					pRightNode
		)
		{
			tNode *pNode = (tNode*)NodeAllocator().Allocate(sizeof(tNode));
			if( pNode == NULL )
				return NULL;

			RJ::Memory::Construct( pNode, tNode(color, pParentNode, pLeftNode, pRightNode) );

			return (pNode);
		}


		//******************************************************************************
		// tRedBlackTree::AllocNode
		// Returns NULL on failure.
		//******************************************************************************
		template<typename t_Key, typename t_Element, typename t_KeyAccessor, typename t_KeyCompare, typename t_Allocator>
		inline typename tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::tNode * tRedBlackTree<t_Key,t_Element,t_KeyAccessor,t_KeyCompare,t_Allocator>::AllocNode
		(
			typename tNode::tColor	color,
			tNode *					pParentNode,
			tNode *					pLeftNode,
			tNode *					pRightNode,
			const t_Element &		element
		)
		{
			tNode *pNode = (tNode*)NodeAllocator().Allocate(sizeof(tNode));
			if( pNode == NULL )
				return NULL;

			RJ::Memory::Construct( pNode, tNode(color, pParentNode, pLeftNode, pRightNode, element) );

			return (pNode);
		}


	}
}