//////
/// @file tstaticheap.h
/// @brief declaration and implementaion of the TStaticHeap template
//////
#ifndef TSTATICHEAP_H
#define TSTATICHEAP_H

#include <vector>
#include <functional>
#include <cassert>

/// @brief
/// This is a priority queue with a fixed enumerated number of elements.
/// It is basically just a helper class for TSequentialHeap,
/// but has the advantage that its behaviour is well defined and can be tested independently.
/// It is implemented as a normal binary heap, as described in any textbook on datastructures.
template <class T, class U = std::less<T> >
class TStaticHeap
{
public:
   typedef T value_type;
   typedef U key_compare;
   typedef typename std::vector<value_type>::size_type size_type;

   explicit TStaticHeap (
      const key_compare& rKeyCompare_p = key_compare());

   static const size_type m_lNpos = -1;
private:

   /// The number of items in the heap.
   size_type m_lHeapSize;

   /// The heap, containing the index of the value in m_tValues.
   std::vector<size_type> m_tHeap;

   /// The position of the corresponding index into m_tValues in the heap
   /// or m_lNpos if the element is not in the heap.
   std::vector<size_type> m_tHeapPos;

   /// The values managed by the heap.
   std::vector<value_type> m_tValues;

   key_compare m_KeyCompare;

public:

   /// @brief
   /// Set the number of indexes to be managed, and remove all elements currently in the heap.
   /// @param  lNrIndex_p  is the number of indexes to be managed.
   void Set_NrIndex (size_type lNrIndex_p);

   /// @brief
   /// Increase the number of indexes to be managed.
   void Increase_Heap();

   /// @brief
   /// Say, whether the heap is empty.
   /// @return  true if the heap is empty and false otherwise.
   bool Is_Empty () const;

   /// @brief
   /// Return the smallest element (the one at the top of the heap...) and its index.
   /// It is allowed to call this function even if the heap is empty. The result will
   /// be meaningless, but returned the reference will reference a valid object.
   /// @param  the appropriate index.
   /// @return  a reference to the smallest element (the one at the top of the heap...)
   const value_type& Get_Top (
      size_type& rlTopIndex_p) const;

   /// @brief
   /// Update the element lIndex_p in the heap.
   /// @param  lIndex_p  is the index of the element to be updated.
   /// @param  rtNewValue_p  is the new value of the element with index lIndex_p.
   /// @param  lOtherIndex_p  is a strange hint: it must be an element in the heap,
   ///         and m_tValues[lOtherIndex_p] will change its value to m_tValues[lIndex_p]
   ///         if m_tValues[lOtherIndex_p]==rtNewValue.
   void FastUpdate (
      size_type lIndex_p,
      const value_type& rtNewValue_p,
      size_type lOtherIndex_p);

   /// @brief
   /// Update the element lIndex_p in the heap
   /// using the fact that its already in there and will move down to speed up the work
   /// @param  lIndex_p  is the index of the element to be updated or inserted.
   /// @param  rtNewValue_p  is the new value of the element with index lIndex_p.
   void FastDown (
      size_type lIndex_p,
      const value_type& rtNewValue_p);

   /// @brief
   /// Update or insert the element lIndex_p in the heap.
   /// @param  lIndex_p  is the index of the element to be updated or inserted.
   /// @param  rtNewValue_p  is the new value of the element with index lIndex_p.
   void Update (
      size_type lIndex_p,
      const value_type& rtNewValue_p);

   /// @brief
   /// Remove the element with index lIndex_p from the heap.
   /// @param  lIndex_p  is the index of the element that will be removed from the heap.
   void Remove (size_type lIndex_p);

private:

   /// @brief
   /// Try to move the element at the (heap) position lPos_p up towards the top of the heap.
   /// @param  lIndex_p  is the index of the element to be moved up.
   void Up (size_type lIndex_p);

   /// @brief
   /// Try to move the element at the (heap) position lPos_p down away from the top of the heap.
   /// @param  lIndex_p  is the index of the element to be moved down.
   void Down (size_type lIndex_p);
};

template <class T, class U>
const typename TStaticHeap<T,U>::size_type
TStaticHeap<T,U>::m_lNpos;

template <class T, class U>
TStaticHeap<T,U>::TStaticHeap (
      const key_compare& rKeyCompare_p)
   : m_lHeapSize (0)
   , m_KeyCompare (rKeyCompare_p)
{
}

template <class T, class U>
void
TStaticHeap<T,U>::Set_NrIndex (size_type lNrIndex_p)
{
   m_lHeapSize = 0;
   m_tHeap.assign (lNrIndex_p, 0);
   // m_lNpos is used to indicate that the element is not in the heap.
   m_tHeapPos.assign (lNrIndex_p, m_lNpos);
   m_tValues.assign (lNrIndex_p, value_type());
} // TStaticHeap<T,U>::Set_NrIndex

template <class T, class U>
void
TStaticHeap<T,U>::Increase_Heap()
{
   m_tHeap.push_back (0);
   // m_lNpos is used to indicate that the element is not in the heap.
   m_tHeapPos.push_back (m_lNpos);
   m_tValues.push_back (value_type());
} // TStaticHeap<T,U>::Increase_Heap

template <class T, class U>
bool
TStaticHeap<T,U>::Is_Empty() const
{
   return (m_lHeapSize == 0);
} // TStaticHeap<T,U>::Is_Empty

template <class T, class U>
const typename TStaticHeap<T,U>::value_type&
TStaticHeap<T,U>::Get_Top(
      size_type& rlTopIndex_p) const
{
   rlTopIndex_p = m_tHeap.front();
   return m_tValues[rlTopIndex_p];
} // TStaticHeap<T,U>::Get_Top

template <class T, class U>
void
TStaticHeap<T,U>::FastUpdate (
      size_type lIndex_p,
      const value_type& rtNewValue_p,
      size_type lOtherIndex_p)
{
   assert (m_tHeapPos[lIndex_p] < m_lHeapSize);
   if (m_tValues[lIndex_p] == rtNewValue_p)
   {
      return;
   }
   assert (m_tHeapPos[lOtherIndex_p] < m_lHeapSize);
   if (m_tValues[lOtherIndex_p] != rtNewValue_p)
   {
      return Update (lIndex_p, rtNewValue_p);
   }
   m_tValues[lOtherIndex_p] = m_tValues[lIndex_p];
   m_tValues[lIndex_p] = rtNewValue_p;
   size_type lPos = m_tHeapPos[lIndex_p];
   size_type lOtherPos = m_tHeapPos[lOtherIndex_p];
   m_tHeapPos[lIndex_p] = lOtherPos;
   m_tHeapPos[lOtherIndex_p] = lPos;
   m_tHeap[lPos] = lOtherIndex_p;
   m_tHeap[lOtherPos] = lIndex_p;
} // TStaticHeap<T,U>::FastUpdate

template <class T, class U>
void
TStaticHeap<T,U>::FastDown (
      size_type lIndex_p,
      const value_type& rtNewValue_p)
{
   m_tValues[lIndex_p] = rtNewValue_p;
   Down (lIndex_p);
} // TStaticHeap<T,U>::FastDown

template <class T, class U>
void
TStaticHeap<T,U>::Update (
      size_type lIndex_p,
      const value_type& rtNewValue_p)
{
   size_type lPos = m_tHeapPos[lIndex_p];
   if (lPos < m_lHeapSize)
   {
      // the element is in the heap and probably needs a new position
      bool bDown = m_KeyCompare (m_tValues[lIndex_p], rtNewValue_p);
      m_tValues[lIndex_p] = rtNewValue_p;
      if (bDown)
      {
         Down (lIndex_p);
      }
      else
      {
         Up (lIndex_p);
      }
   }
   else
   {
      // the element is currently not in the heap, so we append it to the end,
      // and let it move up to its new position.
      m_tValues[lIndex_p] = rtNewValue_p;
      m_tHeapPos[lIndex_p] = m_lHeapSize;
      m_tHeap[m_lHeapSize] = lIndex_p;
      ++m_lHeapSize;
      Up (lIndex_p);
   }
} // TStaticHeap<T,U>::Update

template <class T, class U>
void
TStaticHeap<T,U>::Remove (size_type lIndex_p)
{
   size_type lPos = m_tHeapPos[lIndex_p];
   if (m_lHeapSize <= lPos)
   {
      // the element is not in the heap, so we don't need to remove it.
      return;
   }
   // m_lNpos is used to indicate that the element is not in the heap.
   m_tHeapPos[lIndex_p] = m_lNpos;
   --m_lHeapSize;
   if (m_lHeapSize == lPos)
   {
      // the element was the last element in the heap, so we are done.
      return;
   }
   // We take the last element in the heap, put it into the position the removed element was before
   // and determine its appropriate new position in the heap.
   size_type lLastIndex = m_tHeap[m_lHeapSize];
   m_tHeapPos[lLastIndex] = lPos;
   m_tHeap[lPos] = lLastIndex;
   bool bDown = m_KeyCompare (m_tValues[lIndex_p], m_tValues[lLastIndex]);
   if (bDown)
   {
      Down (lLastIndex);
   }
   else
   {
      Up (lLastIndex);
   }
} // TStaticHeap<T,U>::Remove

template <class T, class U>
void
TStaticHeap<T,U>::Up (size_type lIndex_p)
{
   const value_type& rtMe = m_tValues[lIndex_p];
   size_type lPos = m_tHeapPos[lIndex_p];
   while (lPos>0)
   {
      // let's go up
      const size_type lNewPos = (lPos-1)/2;
      const size_type lNewIndex = m_tHeap[lNewPos];
      if (!m_KeyCompare (rtMe, m_tValues[lNewIndex]))
      {
         break;
      }
      m_tHeapPos[lNewIndex] = lPos;
      m_tHeap[lPos] = lNewIndex;
      lPos = lNewPos;
   }
   m_tHeapPos[lIndex_p] = lPos;
   m_tHeap[lPos] = lIndex_p;
} // TStaticHeap<T,U>::Up

template <class T, class U>
void
TStaticHeap<T,U>::Down (size_type lIndex_p)
{
   const value_type& rtMe = m_tValues[lIndex_p];
   size_type lPos = m_tHeapPos[lIndex_p];
   while (2*lPos + 1 < m_lHeapSize)
   {
      // let's go down
      size_type lNewPos = 2*lPos + 1;
      if ((lNewPos+1 < m_lHeapSize)
         && m_KeyCompare (m_tValues[m_tHeap[lNewPos+1]], m_tValues[m_tHeap[lNewPos]]))
      {
         ++lNewPos;
      }
      const size_type lNewIndex = m_tHeap[lNewPos];
      if (!m_KeyCompare (m_tValues[lNewIndex], rtMe))
      {
         break;
      }
      m_tHeapPos[lNewIndex] = lPos;
      m_tHeap[lPos] = lNewIndex;
      lPos = lNewPos;
   }
   m_tHeapPos[lIndex_p] = lPos;
   m_tHeap[lPos] = lIndex_p;
} // TStaticHeap<T,U>::Down

#endif // TSTATICHEAP_H