/******************************************************************************
  Heap.inl
  This file contains function definitions for tHeap.

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

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

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

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

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

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


namespace RJ
{
	namespace Containers
	{
		//******************************************************************************
		// tHeapIteratorBase == tHeapIteratorBase::tOther
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator, typename t_ThisElement, typename t_ThisNodeItr, typename t_OtherElement, typename t_OtherNodeItr>
		inline tB operator ==
		(
			const tHeapIteratorBase<t_Element, t_Compare, t_ElementAllocator, t_HeapAllocator, t_ThisElement, t_ThisNodeItr, t_OtherElement, t_OtherNodeItr> & lhs,
			const typename tHeapIteratorBase<t_Element, t_Compare, t_ElementAllocator, t_HeapAllocator, t_ThisElement, t_ThisNodeItr, t_OtherElement, t_OtherNodeItr>::tOther & rhs
		)
		{
			return (lhs.m_iNode == rhs.m_iNode);
		}

		//******************************************************************************
		// tHeap::tHeap
		// Constructor
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::tHeap()
		{ }


		//******************************************************************************
		// tHeap::tHeap
		// 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_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::tHeap
		(
			const tThis & rhs
		) 
			:
			m_itrCompare_itrs(rhs.ItrCompare(),tCompressedPair_DefaultSecond())
		{
			// 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() );
		}

		//******************************************************************************
		// tHeap::~tHeap
		// Destructor
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::~tHeap()
		{ }


		//******************************************************************************
		// tHeap::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_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator> & tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::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);
		}


		//******************************************************************************
		// tHeap::Pop
		// Pop the top element off the heap.
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline void tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::Pop()
		{
			RJ_ASSERT( !IsEmpty() );

			// erase the node
			m_nodes.Erase( Itrs().Front() );

			// if there are other elements to adjust back into a valid heap
			if( !m_nodes.IsEmpty() )
			{
				// adjust the heap to no longer use the top element
				AdjustHeap(	Itrs().GetBegin(),
								static_cast<tHeapIdx>(0),
								static_cast<tHeapIdx>((Itrs().GetEnd() - Itrs().GetBegin()) - 1),
								*(Itrs().GetEnd() - 1),
								ItrCompare(),
								tUpdateHeapIdx() );
			}

			// pop off the hole now at the end of the heap
			Itrs().PopBack();
		}


		//******************************************************************************
		// tHeap::Push
		// Push an element into the heap. Returns the end iterator on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline typename tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::tIterator tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::Push
		(
			const t_Element & element
		)
		{
			// add the node
			tNodeItr iNewNode = m_nodes.Insert( m_nodes.GetEnd(), tNode(element) );
			if( iNewNode == m_nodes.GetEnd() )
				return GetEnd();

			// add a hole to the end of the heap
			// (note: make sure no allocations will occur)
			RJ_ASSERT( Itrs().GetSize() < Itrs().GetCapacity() );
			Itrs().Resize( Itrs().GetSize() + 1 );

			// push the new element into the heap with the hole at the end
			InternalPushHeapElement(	Itrs().GetBegin(),
										static_cast<tHeapIdx>((Itrs().GetEnd() - Itrs().GetBegin()) - 1),
										static_cast<tHeapIdx>(0),
										iNewNode,
										ItrCompare(),
										tUpdateHeapIdx() );

			return iNewNode;
		}


		//******************************************************************************
		// tHeap::PushRange
		// Push a range of elements into the heap.Returns false on failure.
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		template<typename t_Iterator>
		inline tB tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::PushRange
		(
			t_Iterator iBegin,
			t_Iterator iEnd
		)
		{
			for( ; iBegin != iEnd; ++iBegin)
			{
				if( Push(*iBegin) == GetEnd() )
					return false;
			}

			return true;
		}


		//******************************************************************************
		// tHeap::Promote
		// Call this function on an element after increasing its value with
		// respect to the predicate. This will then update the element's
		// position within the heap. Note this will only work properly if the
		// elements new value is greater than or equal to it's previous value
		// with respect to the predicate.
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline void tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::Promote
		(
			const tIterator & iPromote
		)
		{
			// repush the element from its current position to promote it up the heap
			InternalPushHeapElement(	Itrs().GetBegin(),
										static_cast<tHeapIdx>( iPromote.m_iNode->m_heapIdx ),
										static_cast<tHeapIdx>( 0 ), 
										ItrCompare(),
										tUpdateHeapIdx() );
		}


		//******************************************************************************
		// tHeap::EraseAll
		// This will only erase the elements. The reserve will not be cleared.
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline void tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::EraseAll()
		{
			m_nodes.Clear();
			Itrs().EraseAll();
		}


		//******************************************************************************
		// tHeap::Clear
		// This will clear the elements and the reserve.
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline void tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::Clear()
		{
			m_nodes.Clear();
			Itrs().Clear();
		}


		//******************************************************************************
		// tHeap::Swap
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline tB tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::Swap
		(
			tThis * pRhs
		)
		{
			if( m_nodes.Swap( &(pRhs->m_nodes) ) == false )
				return false;
			
			if( this->Itrs().ElementAllocator().CompareHeap( pRhs->Itrs().ElementAllocator() ) )
			{
				// do a fast swap when allocators match
				if( Itrs().Swap( &(pRhs->Itrs()) ) == false )
					return false;
			}
			else
			{
				// just resize itr vectors instead of copying data that will be overwritten
				const tSize oldSize = Itrs().GetSize();
				
				if( Itrs().Resize( pRhs->Itrs().GetSize() ) == false )
					return false;

				if(  pRhs->Itrs().Resize( oldSize ) == false )
					return false;
			}

			RJ::Swap( &ItrCompare(), &ItrCompare() );

			// rebuild the iterator data
			InitItrs();
			pRhs->InitItrs();

			return true;
		}

		//******************************************************************************
		// tHeap::Copy
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline tB tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::Copy
		(
			const tThis & rhs
		)
		{
			if( this != &rhs)
			{
				if( m_nodes.Copy( rhs.m_nodes ) == false )
					return false;

				if( Itrs().Resize( rhs.Itrs().GetSize() ) == false )
					return false;

				ItrCompare() = rhs.ItrCompare();
				InitItrs();
			}

			return true;
		}

		//******************************************************************************
		// tHeap::InitItrs
		// Initialize the heap of iterators based on the indices stored in
		// the element nodes.
		//******************************************************************************
		template<typename t_Element, typename t_Compare, typename t_ElementAllocator, typename t_HeapAllocator>
		inline void tHeap<t_Element,t_Compare,t_ElementAllocator,t_HeapAllocator>::InitItrs()
		{
			RJ_ASSERT( m_nodes.GetSize() == Itrs().GetSize() );

			// relink the heap to the list nodes (should have already been set up)
			for(	tNodeItr iNode = m_nodes.GetBegin();
					iNode != m_nodes.GetEnd();
					++iNode )
			{
				Itrs()[iNode->m_heapIdx] = iNode;
			}
		}

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

			if( Itrs().GetSize() != rhs.Itrs().GetSize() )
				return false;

			typename tItrVector::tConstIterator iThisCur = Itrs().GetBegin();
			typename tItrVector::tConstIterator iRhsCur = rhs.Itrs().GetBegin();
			const typename tItrVector::tConstIterator iThisEnd = Itrs().GetEnd();
			
			while( iThisCur != iThisEnd )
			{
				// compare the node values
				if( (**iThisCur).m_element != (**iRhsCur).m_element )
					return false;

				++iThisCur;
				++iRhsCur;
			}

			return true;
		}


	}
}