/******************************************************************************
  Deque.inl
  This file contains function definitions for tDeque.

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

#include "../../../RJ_Core/RJ/Iterator_Funcs.h"


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

namespace RJ
{
	namespace Containers
	{
		//******************************************************************************
		// tDequeIteratorBase == tDequeIteratorBase::tOther
		//******************************************************************************
		template<typename t_Element, typename t_Allocator, typename t_ThisParentPtr, typename t_ThisElement, typename t_OtherParentPtr, typename t_OtherElement>
		inline tB operator ==
		(
			const tDequeIteratorBase<t_Element, t_Allocator, t_ThisParentPtr, t_ThisElement, t_OtherParentPtr, t_OtherElement> & lhs,
			const typename tDequeIteratorBase<t_Element, t_Allocator, t_ThisParentPtr, t_ThisElement, t_OtherParentPtr, t_OtherElement>::tOther & rhs
		)
		{
			RJ_ASSERT( lhs.m_pDeque && rhs.m_pDeque );
			RJ_ASSERT( lhs.m_pDeque == rhs.m_pDeque );
			return (lhs.m_offset == rhs.m_offset);
		}

		//******************************************************************************
		// tDequeIteratorBase < tDequeIteratorBase::tOther
		//******************************************************************************
		template<typename t_Element, typename t_Allocator, typename t_ThisParentPtr, typename t_ThisElement, typename t_OtherParentPtr, typename t_OtherElement>
		inline tB operator <
		(
			const tDequeIteratorBase<t_Element, t_Allocator, t_ThisParentPtr, t_ThisElement, t_OtherParentPtr, t_OtherElement> & lhs,
			const typename tDequeIteratorBase<t_Element, t_Allocator, t_ThisParentPtr, t_ThisElement, t_OtherParentPtr, t_OtherElement>::tOther & rhs
		)
		{
			RJ_ASSERT( lhs.m_pDeque && rhs.m_pDeque );
			RJ_ASSERT( lhs.m_pDeque == rhs.m_pDeque );
			RJ_ASSERT( lhs.m_offset <= lhs.m_pDeque->GetSize() );
			RJ_ASSERT( rhs.m_offset <= lhs.m_pDeque->GetSize() );
			return lhs.m_offset < rhs.m_offset;
		}

		//******************************************************************************
		// tDeque::tDeque
		// Constructor
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tDeque<t_Element,t_Allocator>::tDeque()
			:
			tDequeBase<t_Element,t_Allocator>(),
			m_beginIdx(0),
			m_size(0),
			m_pBufferBegin(NULL),
			m_pBufferEnd(NULL)
		{ }


		//******************************************************************************
		// tDeque::tDeque
		// 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 tDeque<t_Element,t_Allocator>::tDeque
		(
			const tThis & rhs
		)
			:
			tDequeBase<t_Element,t_Allocator>(),
			m_beginIdx(0),
			m_size(0),
			m_pBufferBegin(NULL),
			m_pBufferEnd(NULL)
		{
			// 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_UNUSED_VARIABLE( rhs );
			RJ_ASSERT( rhs.IsEmpty() );
		}

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

		//******************************************************************************
		// tDeque::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 tDeque<t_Element,t_Allocator> &tDeque<t_Element,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 sucess = Copy(rhs);
			RJ_UNUSED_VARIABLE(sucess);
			RJ_ASSERT( sucess == true );

			return (*this);
		}


		//******************************************************************************
		// tDeque::Reserve
		// Return false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tDeque<t_Element,t_Allocator>::Reserve
		(
			tSize numElements
		)
		{
			// ensure the allocator will support the new size
			RJ_ASSERT( numElements <= GetMaxSize() );

			// if we do not already have enough room
			if( GetCapacity() < numElements )
			{	
				// allocate new elemnets buffer
				t_Element *pNewElements = (t_Element*)this->ElementAllocator().Allocate(sizeof(t_Element)*numElements);
				if( pNewElements == NULL )
					return false;

				// copy elements into the new buffer
				if( GetSize() != 0 )
				{
					tElement *pElementsBegin	= m_pBufferBegin + m_beginIdx;
					tElement *pElementsEnd		= m_pBufferBegin + GetEndElementIdx();
					
					if( pElementsEnd > pElementsBegin )
					{
						RJ::ConstructAndCopyRange(pElementsBegin, pElementsEnd, pNewElements);
					}
					else
					{
						RJ_ASSERT( static_cast<tSize>(m_pBufferEnd - pElementsBegin) <= GetSize() );
						t_Element *pMid = RJ::ConstructAndCopyRange(pElementsBegin, m_pBufferEnd, pNewElements);
						RJ::ConstructAndCopyRange( m_pBufferBegin, pElementsEnd, pMid );	
					}
				}

				// destroy and deallocate old buffer
				if( m_pBufferBegin != NULL )
				{	
					DestroyRangeElements( 0, GetSize() );
					this->ElementAllocator().Deallocate( m_pBufferBegin );
				}

				// update data (elements size stays the same)
				m_pBufferBegin	= pNewElements;
				m_pBufferEnd	= pNewElements + numElements;
				m_beginIdx		= 0;
			}

			return true;
		}


		//******************************************************************************
		// tDeque::Resize
		// Returns false on failure
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tDeque<t_Element,t_Allocator>::Resize
		(
			tSize numElements
		)
		{
			if( GetSize() < numElements )
			{
				if( GetCapacity() < numElements )
				{
					if( Reserve( numElements ) == false )
						return false;
				}

				AppendSequence( numElements - GetSize() );
			}
			else if( numElements < GetSize() )
			{
				EraseRange( GetBegin() + numElements, GetEnd() );
			}

			return true;
		}


		//******************************************************************************
		// tDeque::Resize
		// Returns false on failure
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tDeque<t_Element,t_Allocator>::Resize
		(
			tSize				numElements,
			const t_Element	&	element
		)
		{
			if( GetSize() < numElements )
			{
				if( GetCapacity() < numElements )
				{
					if( Reserve( numElements ) == false )
						return false;
				}

				AppendSequence( numElements - GetSize(), element );
			}
			else if( numElements < GetSize() )
			{
				EraseRange( GetBegin() + numElements, GetEnd() );
			}

			return true;
		}


		//******************************************************************************
		// tDeque::ResizeMax
		// Returns false on failure
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tDeque<t_Element,t_Allocator>::ResizeMax()
		{
			const tSize maxSize = GetMaxSize();
			RJ_ASSERT( GetSize() <= maxSize );

			if( GetSize() != maxSize )
			{
				RJ_ASSERT( GetCapacity() <= maxSize );
				if( GetCapacity() != maxSize )
				{
					if( Reserve( maxSize ) == false )
						return false;
				}

				AppendSequence( maxSize - GetSize() );
			}

			return true;
		}


		//******************************************************************************
		// tDeque::ResizeMax
		// Returns false on failure
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tDeque<t_Element,t_Allocator>::ResizeMax
		(
			const t_Element & element
		)
		{
			const tSize maxSize = GetMaxSize();
			RJ_ASSERT( GetSize() <= maxSize );

			if( GetSize() != maxSize )
			{
				RJ_ASSERT( GetCapacity() <= maxSize );
				if( GetCapacity() != maxSize )
				{
					if( Reserve( maxSize ) == false )
						return false;
				}

				AppendSequence( maxSize - GetSize(), element );
			}

			return true;
		}


		//******************************************************************************
		// tDeque::PushFront
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::PushFront()
		{
			// make sure we have enough memory
			RJ_ASSERT( GetSize() < GetCapacity() );

			// update begin index
			if( m_beginIdx == 0 )
				m_beginIdx = GetCapacity()-1;
			else
				--m_beginIdx;

			// construct element
			RJ::Memory::Construct( m_pBufferBegin + m_beginIdx );
			
			// update element count
			++m_size;
		}


		//******************************************************************************
		// tDeque::PushFront
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::PushFront
		(
			const t_Element & element
		)
		{
			// make sure we have enough memory
			RJ_ASSERT( GetSize() < GetCapacity() );

			// update begin index
			if( m_beginIdx == 0 )
				m_beginIdx = GetCapacity()-1;
			else
				--m_beginIdx;

			// construct element
			RJ::Memory::Construct( m_pBufferBegin + m_beginIdx, element );
			
			// update element count
			++m_size;
		}


		//******************************************************************************
		// tDeque::PopFront
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::PopFront()
		{
			RJ_ASSERT( !IsEmpty() );
			
			// destruct element
			RJ::Memory::Destruct( m_pBufferBegin + m_beginIdx );
			
			// update begin index
			++m_beginIdx;
			if( m_beginIdx == GetCapacity() )
				m_beginIdx = 0;

			// update element count
			--m_size;
		}


		//******************************************************************************
		// tDeque::PushBack
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::PushBack()
		{
			// make sure we have enough memory
			RJ_ASSERT( GetSize() < GetCapacity() );

			// construct element
			tSize newBackIdx = GetEndElementIdx();
			RJ::Memory::Construct( m_pBufferBegin + newBackIdx );
			
			// update element count
			++m_size;
		}


		//******************************************************************************
		// tDeque::PushBack
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::PushBack
		(
			const t_Element & element
		)
		{
			// make sure we have enough memory
			RJ_ASSERT( GetSize() < GetCapacity() );

			// construct element
			tSize newBackIdx = GetEndElementIdx();
			RJ::Memory::Construct( m_pBufferBegin + newBackIdx, element );
			
			// update element count
			++m_size;
		}


		//******************************************************************************
		// tDeque::PopBack
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::PopBack()
		{
			RJ_ASSERT( !IsEmpty() );
			
			// destruct element
			RJ::Memory::Destruct( &Back() );
			
			// update element count
			--m_size;
		}


		//******************************************************************************
		// tDeque::AssignSequence
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::AssignSequence
		(
			tSize				numElements,
			const t_Element &	element
		)
		{
			// use temporary storate incase element is in the sequence
			t_Element temp(element);	
			EraseAll();
			InsertSequence( GetBegin(), numElements, temp );
		}


		//******************************************************************************
		// tDeque::AssignRange
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Iterator>
		inline void tDeque<t_Element,t_Allocator>::AssignRange
		(
			t_Iterator iBegin,
			t_Iterator iEnd
		)
		{
			EraseAll();
			InsertRange( GetBegin(), iBegin, iEnd );
		}


		//******************************************************************************
		// tDeque::Insert
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline typename tDeque<t_Element,t_Allocator>::tIterator tDeque<t_Element,t_Allocator>::Insert
		(
			tIterator			iInsert,
			const t_Element &	element
		)
		{
			typename tIterator::tElementPtrDiff offset = IsEmpty() ? 0 : iInsert - GetBegin();
			InsertSequence( iInsert, static_cast<tSize>(1), element );
			return (GetBegin() + offset);
		}


		//******************************************************************************
		// tDeque::InsertSequence
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::InsertSequence
		(
			tIterator			iInsert,
			tSize				numElements,
			const t_Element &	element
		)
		{
			// make sure we have enough memory
			RJ_ASSERT( GetSize() + numElements <= GetCapacity() );

			// check if we don't need to insert
			if( numElements == 0 )
				return;

			// use a temp value incase element is in part of the sequence
			// that will be modified
			t_Element temp(element);

			// if it would be faster to push out the back
			if( iInsert.m_offset > GetSize() / 2 )
			{
				// if the new elements will extend off the current end
				if( (m_size - iInsert.m_offset) < numElements )
				{
					// shift the suffix forward in the buffer
					ConstructAndCopyRangeElements( iInsert.m_offset, m_size, iInsert.m_offset + numElements );
				
					// insert the portion of the new elements that goes past the old end
					ConstructAndFillSequenceElements( m_size, numElements - (m_size - iInsert.m_offset), temp );

					// copy in the non overflowing new elements
					FillSequenceElements( iInsert.m_offset, m_size - iInsert.m_offset, temp );
				}
				// else the new elements fit inside the existing constructed elements
				else
				{
					// shift the suffix forward in the buffer
					ConstructAndCopyRangeElements( m_size - numElements, m_size, m_size );
					
					// copy the elements that will be overwritten
					CopyRangeBackwardElements( iInsert.m_offset, m_size - numElements, m_size );	
					
					// insert the new elements
					FillSequenceElements( iInsert.m_offset, numElements, temp );
				}
			}
			// else it would be faster to push out the front
			else
			{
				// update the begin pointer
				if( m_beginIdx < numElements )
					m_beginIdx = m_beginIdx + (GetCapacity() - numElements);
				else
					m_beginIdx -= numElements;

				// if the new elements will extend off the current begin
				if( iInsert.m_offset < numElements )
				{
					// shift the prefix backward in the buffer
					ConstructAndCopyRangeElements( numElements, numElements+iInsert.m_offset, 0 );
				
					// insert the portion of the new elements that goes before the old begin
					ConstructAndFillSequenceElements( iInsert.m_offset, numElements - iInsert.m_offset, temp );

					// copy in the non overflowing new elements
					FillSequenceElements( numElements, iInsert.m_offset, temp );
				}
				// else the new elements fit inside the existing constructed elements
				else
				{
					// shift the prefix backward in the buffer
					ConstructAndCopyRangeElements( numElements, numElements+numElements, 0 );
					
					// copy the elements that will be overwritten
					CopyRangeElements( numElements+numElements, numElements+iInsert.m_offset, numElements );	
					
					// insert the new elements
					FillSequenceElements( iInsert.m_offset, numElements, temp );
				}
			}

			// update the element count
			m_size += numElements;
		}

		//******************************************************************************
		// tDeque::InsertRange
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Iterator>
		inline void tDeque<t_Element,t_Allocator>::InsertRange
		(
			tIterator	iInsert,
			t_Iterator	iBegin,
			t_Iterator	iEnd
		)
		{
			InsertRange(	iInsert,
							iBegin,
							iEnd,
							typename tIteratorTraits<t_Iterator>::tIteratorCategory() );
		}


		//******************************************************************************
		// tDeque::Erase
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline typename tDeque<t_Element,t_Allocator>::tIterator tDeque<t_Element,t_Allocator>::Erase
		(
			tIterator iErase
		)
		{
			return EraseRange( iErase, iErase+1 );
		}


		//******************************************************************************
		// tDeque::EraseRange
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline typename tDeque<t_Element,t_Allocator>::tIterator tDeque<t_Element,t_Allocator>::EraseRange
		(
			tIterator iBegin,
			tIterator iEnd
		)
		{
			RJ_ASSERT( iBegin.m_pDeque == this  );
			RJ_ASSERT( iEnd.m_pDeque == this  );
			RJ_ASSERT( iBegin.m_offset <= GetSize() );
			RJ_ASSERT( iEnd.m_offset <= GetSize() );

			// if we need to erase
			if( iBegin != iEnd)
			{	
				RJ_ASSERT( !IsEmpty() );

				const typename tIterator::tElementPtrDiff eraseCount = iEnd.m_offset - iBegin.m_offset;

				// if it would be more efficient to pull in the back
				const tSize midEraseIdx = (iBegin.m_offset + iEnd.m_offset) / 2;
				if( midEraseIdx > GetSize()/2 )
				{
					// contract
					CopyRangeElements( iEnd.m_offset, m_size, iBegin.m_offset );

					// destroy the back
					DestroyRangeElements( m_size - eraseCount, m_size );
				}
				// else it would be more efficient to pull in the front
				else
				{
					// contract
					CopyRangeBackwardElements( 0, iBegin.m_offset, eraseCount+iBegin.m_offset );

					// destroy the front
					DestroyRangeElements( 0, eraseCount );
				}

				// update the element count
				m_size -= eraseCount;
			}

			// return the same iterator (the index points to the next element now)
			return iBegin;
		}


		//******************************************************************************
		// tDeque::EraseAll
		// This will only erase the elements. The reserve will not be cleared.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::EraseAll()
		{
			Resize(0);
		}


		//******************************************************************************
		// tDeque::Clear
		// This will clear the elements and the reserve.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::Clear()
		{
			// if there is anything to clear
			if( m_pBufferBegin != NULL )
			{
				DestroyRangeElements( 0, GetSize() );
				this->ElementAllocator().Deallocate( m_pBufferBegin );

				m_beginIdx		= 0;
				m_size			= 0;
				m_pBufferBegin	= NULL;
				m_pBufferEnd	= NULL;
			}
		}


		//******************************************************************************
		// tDeque::Swap
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tDeque<t_Element,t_Allocator>::Swap
		(
			tThis * pRhs
		)
		{
			// if the allocator is the same
			if( this->ElementAllocator().CompareHeap(pRhs->ElementAllocator()) )
			{	
				// swap control information
				RJ::Swap( &m_beginIdx,		&pRhs->m_beginIdx );
				RJ::Swap( &m_size,			&pRhs->m_size );
				RJ::Swap( &m_pBufferBegin,	&pRhs->m_pBufferBegin );
				RJ::Swap( &m_pBufferEnd,	&pRhs->m_pBufferEnd );
			}
			// else the allocators are different
			else
			{
				tThis temp;
				if (!temp.ElementAllocator().CopyHeap( this->ElementAllocator() ))
					return false;

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

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

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

			return true;
		}

		//******************************************************************************
		// tDeque::Copy
		// Copy the contents of another container into this container. The
		// capacity will be increased if necessary. On failure this function
		// will result in an empty vector and will return false.
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tDeque<t_Element,t_Allocator>::Copy(const tThis & rhs)
		{
			// optimize out equal containers
			if( this != &rhs )
			{
				// if we have enough buffered space
				if( rhs.GetSize() <= GetCapacity() )
				{
					// destroy our current elements
					DestroyRangeElements( 0, GetSize() );
				}
				else
				{
					// clear our elements and reallocate
					Clear();

					// allocate
					if( Alloc( rhs.GetSize() ) == false )
						return false;
				}

				// update data
				m_beginIdx	= 0;
				m_size		= 0;

				// copy new
				const tSize rhsSize		= rhs.GetSize();

				if( rhsSize != 0 )
				{
					tElement *pRhsBegin	= rhs.m_pBufferBegin + rhs.m_beginIdx;
					tElement *pRhsEnd		= rhs.m_pBufferBegin + rhs.GetEndElementIdx();
					
					if( pRhsEnd > pRhsBegin )
					{
						ConstructAndCopyRange(pRhsBegin, pRhsEnd, 0);	
					}
					else
					{
						RJ_ASSERT( static_cast<tSize>(rhs.m_pBufferEnd - pRhsBegin) <= rhsSize );
						ConstructAndCopyRange(pRhsBegin, rhs.m_pBufferEnd, 0);	
						ConstructAndCopyRange( rhs.m_pBufferBegin, pRhsEnd, (rhs.m_pBufferEnd-pRhsBegin) );	
					}

					// update data
					m_size		= rhsSize;
				}
			}

			return true;
		}

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

			return ( GetSize() == rhs.GetSize() ) && IsEqualRange( GetBegin(), GetEnd(), rhs.GetBegin() );
		}


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


		//******************************************************************************
		// tDeque::InsertRange<t_Iterator>
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Iterator>
		inline void tDeque<t_Element,t_Allocator>::InsertRange
		(
			tIterator	iInsert,
			t_Iterator	iBegin,
			t_Iterator	iEnd,
			tInputItrCategory
		)
		{
			for( ; iBegin != iEnd; ++iBegin, ++iInsert )
				iInsert = Insert( iInsert, *iBegin );
		}


		//******************************************************************************
		// tDeque::InsertRange<t_Iterator>
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Iterator>
		inline void tDeque<t_Element,t_Allocator>::InsertRange
		(
			tIterator	iInsert,
			t_Iterator	iBegin,
			t_Iterator	iEnd,
			tForwardItrCategory
		)
		{
			// determine how many elements need to be inserted
			tSize numElements = GetDistance( iBegin, iEnd );

			// make sure we have enough memory
			RJ_ASSERT( GetSize() + numElements <= GetCapacity() );

			// check if we don't need to insert
			if( numElements == 0 )
				return;

			// if it would be faster to push out the back
			if( iInsert.m_offset > GetSize() / 2 )
			{
				// if the new elements will extend off the current end
				if( (m_size - iInsert.m_offset) < numElements )
				{
					// shift the suffix forward in the buffer
					ConstructAndCopyRangeElements( iInsert.m_offset, m_size, iInsert.m_offset + numElements );
				
					// get the position in the new elements where it overflows
					// past the end of the old elements
					t_Iterator iMid = iBegin;
					Advance( &iMid, GetEnd() - iInsert );

					// insert the portion of the new elements that goes past the old end
					ConstructAndCopyRange( iMid, iEnd, m_size );
				
					// copy in the non overflowing new elements
					CopyRange( iBegin, iMid, iInsert.m_offset );
				}
				// else the new elements fit inside the existing constructed elements
				else
				{
					// shift the suffix forward in the buffer
					ConstructAndCopyRangeElements( m_size - numElements, m_size, m_size );
					
					// copy the elements that will be overwritten
					CopyRangeBackwardElements( iInsert.m_offset, m_size - numElements, m_size );	
					
					// insert the new elements
					CopyRange( iBegin, iEnd, iInsert.m_offset );
				}
			}
			// else it would be faster to push out the front
			else
			{
				// update the begin pointer
				if( m_beginIdx < numElements )
					m_beginIdx = m_beginIdx + (GetCapacity() - numElements);
				else
					m_beginIdx -= numElements;

				// if the new elements will extend off the current begin
				if( iInsert.m_offset < numElements )
				{
					// shift the prefix backward in the buffer
					ConstructAndCopyRangeElements( numElements, numElements+iInsert.m_offset, 0 );
				
					// get the position in the new elements where it stops
					// overflowing before the begin of the old elements
					t_Iterator iMid = iBegin;
					Advance( &iMid, numElements - iInsert.m_offset );

					// insert the portion of the new elements that goes before the old begin
					ConstructAndCopyRange( iBegin, iMid, iInsert.m_offset );
				
					// copy in the non overflowing new elements
					CopyRange( iMid, iEnd, numElements );
				}
				// else the new elements fit inside the existing constructed elements
				else
				{
					// shift the prefix backward in the buffer
					ConstructAndCopyRangeElements( numElements, numElements+numElements, 0 );
					
					// copy the elements that will be overwritten
					CopyRangeElements( numElements+numElements, numElements+iInsert.m_offset, numElements );	
					
					// insert the new elements
					CopyRange( iBegin, iEnd, iInsert.m_offset );
				}
			}

			// update the element count
			m_size += numElements;
		}


		//******************************************************************************
		// tDeque::AppendSequence
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::AppendSequence
		(
			tSize numElements
		)
		{
			// make sure we have enough memory
			RJ_ASSERT( GetSize() + numElements <= GetCapacity() );

			// check if we don't need to insert
			if( numElements == 0 )
				return;

			// insert the portion of the new elements that goes past the old end
			ConstructSequenceElements( m_size, numElements );

			// update the element count
			m_size += numElements;
		}


		//******************************************************************************
		// tDeque::AppendSequence
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::AppendSequence
		(
			tSize numElements,
			const t_Element &element
		)
		{
			// make sure we have enough memory
			RJ_ASSERT( GetSize() + numElements <= GetCapacity() );

			// check if we don't need to insert
			if( numElements == 0 )
				return;

			// insert the portion of the new elements that goes past the old end
			ConstructAndFillSequenceElements( m_size, numElements, element );

			// update the element count
			m_size += numElements;
		}


		//******************************************************************************
		// tDeque::Alloc
		// Rerturns false on failure
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline tB tDeque<t_Element,t_Allocator>::Alloc( tSize numElements )
		{	
			RJ_ASSERT( m_beginIdx		== 0 );
			RJ_ASSERT( m_size			== 0 );
			RJ_ASSERT( m_pBufferBegin	== NULL );
			RJ_ASSERT( m_pBufferEnd		== NULL );

			if( numElements == 0 )
				return true;

			// allocate storage
			m_pBufferBegin = (t_Element*)this->ElementAllocator().Allocate( sizeof(t_Element)*numElements );
			if( m_pBufferBegin == NULL )
				return false;

			m_pBufferEnd = m_pBufferBegin + numElements;

			return true;
		}


		//******************************************************************************
		// tDeque::DestroyRangeElements
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::DestroyRangeElements
		(
			tSize beginOffset,
			tSize endOffset
		)
		{
			RJ_ASSERT( beginOffset <= endOffset );
			RJ_ASSERT( beginOffset <= m_size );
			RJ_ASSERT( endOffset <= m_size );

			const tSize numElements = endOffset - beginOffset;

			if( numElements != 0 )
			{
				tElement * pElementsBegin	= m_pBufferBegin + GetElementIdx(beginOffset);
				tElement * pElementsEnd	= m_pBufferBegin + GetElementIdx(endOffset);

				if( pElementsEnd > pElementsBegin )
				{
					RJ::DestructRange( pElementsBegin, pElementsEnd );	
				}
				else
				{
					RJ_ASSERT( static_cast<tSize>(m_pBufferEnd - pElementsBegin) <= numElements );
					RJ::DestructRange( pElementsBegin, m_pBufferEnd );
					RJ::DestructRange( m_pBufferBegin, pElementsEnd );
				}
			}
		}


		//******************************************************************************
		// tDeque::CopyRange<t_Iterator>
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Iterator>
		inline void tDeque<t_Element,t_Allocator>::CopyRange
		(
			t_Iterator	iSrcBegin,
			t_Iterator	iSrcEnd,
			tSize		destBeginOffset
		)
		{
			const tSize numElements = GetDistance( iSrcBegin, iSrcEnd );

			RJ_ASSERT( numElements <= GetCapacity() );
			RJ_ASSERT( destBeginOffset <= GetCapacity()-numElements );
			
			if( numElements != 0 )
			{
				tElement * pDestBegin	= m_pBufferBegin + GetElementIdx(destBeginOffset);
				tElement * pDestEnd	= m_pBufferBegin + GetElementIdx(destBeginOffset+numElements);

				if( pDestEnd > pDestBegin )
				{
					RJ::CopyRange(iSrcBegin, iSrcEnd, pDestBegin);
				}
				else
				{
					RJ_ASSERT( static_cast<tSize>(m_pBufferEnd-pDestBegin) <= numElements );
					t_Iterator iSrcMid = iSrcBegin;
					Advance( &iSrcMid, m_pBufferEnd - pDestBegin );
					RJ::CopyRange(iSrcBegin, iSrcMid, pDestBegin);
					RJ::CopyRange(iSrcMid, iSrcEnd, m_pBufferBegin);
				}
			}
		}

			
		//******************************************************************************
		// tDeque::CopyRangeElements
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::CopyRangeElements
		(
			tSize srcBeginOffset,
			tSize srcEndOffset,
			tSize destBeginOffset
		)
		{
			RJ_ASSERT( srcBeginOffset <= srcEndOffset );
			RJ_ASSERT( srcEndOffset <= m_size );
			RJ_ASSERT( destBeginOffset <= m_size-(srcEndOffset-srcBeginOffset) );
			RJ_ASSERT( destBeginOffset <= srcBeginOffset || destBeginOffset >= srcEndOffset );

			const tSize numElements = srcEndOffset - srcBeginOffset;

			if( numElements != 0 )
			{
				tElement * pSrcBegin		= m_pBufferBegin + GetElementIdx(srcBeginOffset);
				tElement * pSrcEnd			= m_pBufferBegin + GetElementIdx(srcEndOffset);
				tElement * pDestBegin		= m_pBufferBegin + GetElementIdx(destBeginOffset);
				tElement * pDestEnd			= m_pBufferBegin + GetElementIdx(destBeginOffset+numElements);

				if( pSrcEnd > pSrcBegin )
				{
					if( pDestEnd > pDestBegin )
					{
						RJ::CopyRange( pSrcBegin, pSrcEnd, pDestBegin );
					}
					else
					{
						tElement *pSrcMid = pSrcBegin + (m_pBufferEnd - pDestBegin);
						RJ::CopyRange( pSrcBegin, pSrcMid, pDestBegin );
						RJ::CopyRange( pSrcMid, pSrcEnd, m_pBufferBegin );
					}
				}
				else
				{
					if( pDestEnd > pDestBegin )
					{
						tElement *pDestMid = RJ::CopyRange( pSrcBegin, m_pBufferEnd, pDestBegin );
						RJ::CopyRange( m_pBufferBegin, pSrcEnd, pDestMid );
					}
					else
					{
						// If both ranges loop past the buffer end, that means they
						// intersect and the src range must be after the dest in memory
						// given that this function will only copy left given an
						// intersecting src and dest range.
						RJ_ASSERT( pSrcBegin >= pDestBegin );
						tElement *pDestMid = RJ::CopyRange( pSrcBegin, m_pBufferEnd, pDestBegin );
						tElement *pSrcMid = m_pBufferBegin + (m_pBufferEnd - pDestMid);
						RJ::CopyRange( m_pBufferBegin, pSrcMid, pDestMid );
						RJ_ASSERT( (pSrcEnd - pSrcMid) == (pDestMid - m_pBufferBegin) );
						RJ::CopyRange( pSrcMid, pSrcEnd, m_pBufferBegin );
					}
				}
			}
		}


		//******************************************************************************
		// tDeque::CopyRangeBackwardElements
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::CopyRangeBackwardElements
		(
			tSize srcBeginOffset,
			tSize srcEndOffset,
			tSize destEndOffset
		)
		{
			RJ_ASSERT( srcBeginOffset <= srcEndOffset );
			RJ_ASSERT( srcEndOffset <= m_size );
			RJ_ASSERT( destEndOffset >= (srcEndOffset-srcBeginOffset) && destEndOffset <= m_size );
			RJ_ASSERT( destEndOffset <= srcBeginOffset || destEndOffset >= srcEndOffset );

			const tSize numElements = srcEndOffset - srcBeginOffset;

			if( numElements != 0 )
			{
				tElement * pSrcBegin		= m_pBufferBegin + GetElementIdx(srcBeginOffset);
				tElement * pSrcEnd			= m_pBufferBegin + GetElementIdx(srcEndOffset);
				tElement * pDestBegin		= m_pBufferBegin + GetElementIdx(destEndOffset-numElements);
				tElement * pDestEnd			= m_pBufferBegin + GetElementIdx(destEndOffset);

				if( pSrcEnd > pSrcBegin )
				{
					if( pDestEnd > pDestBegin )
					{
						CopyRangeBackward( pSrcBegin, pSrcEnd, pDestEnd );
					}
					else
					{
						tElement *pSrcMid = pSrcBegin + (m_pBufferEnd - pDestBegin);
						CopyRangeBackward( pSrcMid, pSrcEnd, pDestEnd );
						CopyRangeBackward( pSrcBegin, pSrcMid, m_pBufferEnd );
					}
				}
				else
				{
					if( pDestEnd > pDestBegin )
					{
						tElement *pDestMid = CopyRangeBackward( m_pBufferBegin, pSrcEnd, pDestEnd );
						CopyRangeBackward( pSrcBegin, m_pBufferEnd, pDestMid );			
					}
					else
					{
						// If both ranges loop past the buffer end, that means they
						// intersect and the src range must be before the dest in memory
						// given that this function will only copy right given an
						// intersecting src and dest range.
						RJ_ASSERT( pSrcBegin <= pDestBegin );
						tElement *pDestMid = CopyRangeBackward( m_pBufferBegin, pSrcEnd, pDestEnd );
						tElement *pSrcMid = m_pBufferEnd - (pDestMid - m_pBufferBegin);
						CopyRangeBackward( pSrcMid, m_pBufferEnd, pDestMid );
						RJ_ASSERT( (pSrcMid-pSrcBegin) == (m_pBufferEnd-pDestBegin) );
						CopyRangeBackward( pSrcBegin, pSrcMid, m_pBufferEnd );
					}
				}
			}
		}


		//******************************************************************************
		// tDeque::FillSequenceElements
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::FillSequenceElements
		(
			tSize	beginOffset,
			tSize	numElements
		)
		{
			RJ_ASSERT( numElements <= GetCapacity() );
			RJ_ASSERT( beginOffset >= 0 && beginOffset <= GetCapacity()-numElements );
			
			if( numElements != 0 )
			{
				tElement *pBegin	= m_pBufferBegin + GetElementIdx(beginOffset);
				tElement *pEnd		= m_pBufferBegin + GetElementIdx(beginOffset+numElements);

				if( pEnd > pBegin )
				{
					return FillSequence(pBegin, numElements);
				}
				else
				{
					RJ_ASSERT( static_cast<tSize>(m_pBufferEnd-pBegin) <= numElements );
					tSize beginToBufferEnd = m_pBufferEnd - pBegin;
					FillSequence(pBegin, beginToBufferEnd);
					FillSequence(m_pBufferBegin, numElements-beginToBufferEnd);
				}
			}
		}


		//******************************************************************************
		// tDeque::FillSequenceElements
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::FillSequenceElements
		(
			tSize				beginOffset,
			tSize				numElements,
			const t_Element &	element
		)
		{
			RJ_ASSERT( numElements <= GetCapacity() );
			RJ_ASSERT( beginOffset <= GetCapacity()-numElements );
			
			if( numElements != 0 )
			{
				tElement *pBegin	= m_pBufferBegin + GetElementIdx(beginOffset);
				tElement *pEnd		= m_pBufferBegin + GetElementIdx(beginOffset+numElements);

				if( pEnd > pBegin )
				{
					return FillSequence(pBegin, numElements, element);
				}
				else
				{
					RJ_ASSERT( static_cast<tSize>(m_pBufferEnd-pBegin) <= numElements );
					tSize beginToBufferEnd = m_pBufferEnd - pBegin;
					FillSequence(pBegin, beginToBufferEnd, element);
					return FillSequence(m_pBufferBegin, numElements-beginToBufferEnd, element);
				}
			}
		}


		//******************************************************************************
		// tDeque::ConstructAndCopyRange<t_Iterator>
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		template<typename t_Iterator>
		inline void tDeque<t_Element,t_Allocator>::ConstructAndCopyRange
		(
			t_Iterator	iSrcBegin,
			t_Iterator	iSrcEnd,
			tSize		destBeginOffset
		)
		{
			const typename tIteratorTraits<t_Iterator>::tElementPtrDiff numElements = GetDistance( iSrcBegin, iSrcEnd );

			RJ_ASSERT( numElements >= 0 );
			RJ_ASSERT( GetCapacity() >= static_cast<tSize>(numElements) );
			RJ_ASSERT( destBeginOffset <= GetCapacity()-static_cast<tSize>(numElements) );
			
			if( numElements != 0 )
			{
				tElement *pDestBegin	= m_pBufferBegin + GetElementIdx(destBeginOffset);
				tElement *pDestEnd		= m_pBufferBegin + GetElementIdx(destBeginOffset+numElements);

				if( pDestEnd > pDestBegin )
				{
					RJ::ConstructAndCopyRange(iSrcBegin, iSrcEnd, pDestBegin);
				}
				else
				{
					RJ_ASSERT( m_pBufferEnd-pDestBegin <= numElements );
					t_Iterator iSrcMid = iSrcBegin;
					Advance( &iSrcMid, m_pBufferEnd - pDestBegin );
					RJ::ConstructAndCopyRange(iSrcBegin, iSrcMid, pDestBegin);
					RJ::ConstructAndCopyRange(iSrcMid, iSrcEnd, m_pBufferBegin);
				}
			}
		}


		//******************************************************************************
		// tDeque::ConstructAndCopyRangeElements
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::ConstructAndCopyRangeElements
		(
			tSize	srcBeginOffset,
			tSize	srcEndOffset,
			tSize	destBeginOffset
		)
		{
			RJ_ASSERT( srcBeginOffset <= srcEndOffset );
			RJ_ASSERT( srcEndOffset <= GetCapacity() );
			RJ_ASSERT( destBeginOffset <= GetCapacity()-(srcEndOffset-srcBeginOffset) );
			
			tSize numElements = srcEndOffset - srcBeginOffset;

			if( numElements != 0 )
			{
				tElement *pSrcBegin		= m_pBufferBegin + GetElementIdx(srcBeginOffset);
				tElement *pSrcEnd			= m_pBufferBegin + GetElementIdx(srcEndOffset);
				tElement *pDestBegin		= m_pBufferBegin + GetElementIdx(destBeginOffset);
				tElement *pDestEnd			= m_pBufferBegin + GetElementIdx(destBeginOffset+numElements);

				if( pSrcEnd > pSrcBegin )
				{
					if( pDestEnd > pDestBegin )
					{
						RJ::ConstructAndCopyRange(pSrcBegin, pSrcEnd, pDestBegin);
					}
					else
					{
						tElement *pSrcMid = pSrcBegin + (m_pBufferEnd - pDestBegin);
						RJ::ConstructAndCopyRange( pSrcBegin, pSrcMid, pDestBegin );
						RJ::ConstructAndCopyRange( pSrcMid, pSrcEnd, m_pBufferBegin );
					}
				}
				else
				{
					// The dest range must be uninitialized memory and the src range
					// must be initialized memory.  From this, it is concluded that
					// the two ranges do not intersect and thus they cannot both wrap
					// across the end of the buffer.
					RJ_ASSERT( pDestEnd > pDestBegin );

					tElement *pDestMid = RJ::ConstructAndCopyRange(pSrcBegin, m_pBufferEnd, pDestBegin);
					RJ::ConstructAndCopyRange(m_pBufferBegin, pSrcEnd, pDestMid);
				}
			}
		}


		//******************************************************************************
		// tDeque::ConstructSequenceElements
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::ConstructSequenceElements
		(
			tSize	beginOffset,
			tSize	numElements
		)
		{
			RJ_ASSERT( numElements <= GetCapacity() );
			RJ_ASSERT( beginOffset >= GetSize() && beginOffset <= GetCapacity()-numElements );
			
			if( numElements != 0 )
			{
				tElement *pBegin			= m_pBufferBegin + GetElementIdx(beginOffset);
				tElement *pEnd				= m_pBufferBegin + GetElementIdx(beginOffset+numElements);

				if( pEnd > pBegin )
				{
					RJ::ConstructSequence(pBegin, numElements);
				}
				else
				{
					RJ_ASSERT( m_pBufferEnd-pBegin >= 0 );
					tSize beginToBufferEnd = static_cast<tSize>(m_pBufferEnd - pBegin);
					RJ_ASSERT( beginToBufferEnd <= numElements );
					RJ::ConstructSequence(pBegin, beginToBufferEnd);
					RJ::ConstructSequence(m_pBufferBegin, numElements-beginToBufferEnd);
				}
			}
		}


		//******************************************************************************
		// tDeque::ConstructAndFillSequenceElements
		//******************************************************************************
		template<typename t_Element, typename t_Allocator>
		inline void tDeque<t_Element,t_Allocator>::ConstructAndFillSequenceElements
		(
			tSize				beginOffset,
			tSize				numElements,
			const t_Element &	element
		)
		{
			RJ_ASSERT( numElements <= GetCapacity() );
			RJ_ASSERT( beginOffset <= GetCapacity() - numElements );
			
			if( numElements != 0 )
			{
				tElement *pBegin			= m_pBufferBegin + GetElementIdx(beginOffset);
				tElement *pEnd				= m_pBufferBegin + GetElementIdx(beginOffset+numElements);

				if( pEnd > pBegin )
				{
					RJ::ConstructAndFillSequence(pBegin, numElements, element);
				}
				else
				{
					RJ_ASSERT( static_cast<tSize>(m_pBufferEnd-pBegin) <= numElements );
					tSize beginToBufferEnd = m_pBufferEnd - pBegin;
					RJ::ConstructAndFillSequence(pBegin, beginToBufferEnd, element);
					RJ::ConstructAndFillSequence(m_pBufferBegin, numElements-beginToBufferEnd, element);
				}
			}
		}



	}
}