/*
 * Instituto Superior de Engenharia do Porto
 *
 * Estruturas de Informação
 *
 * 2000/2001
 *
 * ------------------------------------------
 *
 * Classe Heap <usa templates>
 *
 * HeapV.h
 *
 */


#include <vector>
using namespace std;


// K - key type, T - information type
template <class K, class T = char>
class CKeyHeapV 
{
 protected:

 enum { DefaultSize = 30, DefaultGrowStep = 10 };
  
  typedef struct {
    T    value;
    K    key;
  } Cell;
	
  vector<Cell> m_heap;
  int m_iCellCount;
  int m_iGrowStep;

  void clone( const CKeyHeapV& obj );

  bool resize( int nSize );
  bool resize() { return resize( m_heap.size() + m_iGrowStep ); }
  
 public:

  CKeyHeapV( int nSize = DefaultSize, int nGrowStep = DefaultGrowStep );
  CKeyHeapV( const CKeyHeapV& obj ) { clone( obj ); }
  
  int  size()  { return m_heap.size(); }
  int  count() { return m_iCellCount; } 
  bool empty() { return (m_iCellCount == 0); }
    
  bool insert( const T& value, const K& key );
  bool extract_min( T& value, K& key );

  bool insert( const K& key )
    {
      return insert( T(), key );
    }

  bool extract_min( K& key )
    {
      T dummy;
      return extract_min( dummy, key );
    }
     
  CKeyHeapV& operator=( const CKeyHeapV& o );


  /***/
  //apenas para debug
  void debug_print() const
  {
	  cout << endl;
	  for (int i = 0; i < m_iCellCount; i++)
		  cout << "[" << m_heap[i].key << "," << m_heap[i].value <<"]" << endl;
	  cout << endl;
	  cin.get();
  }
  /***/
};


template <class K, class T>
void CKeyHeapV<K,T> :: clone( const CKeyHeapV& obj )
{
  m_help       = obj.m_heap;
  m_iCellCount = obj.m_iCellCount;
  m_iGrowStep  = obj.m_iGrowStep;
}


template <class K, class T>
CKeyHeapV<K,T> :: CKeyHeapV( int nSize, int nGrowStep )
{
  m_iCellCount = 0;
  m_iGrowStep = nGrowStep;
  resize( nSize );
}


template <class K, class T>
bool CKeyHeapV<K,T> :: resize( int nSize )
{
  if ( nSize < m_iCellCount )
	  return false;
  
  int sz = m_heap.size();
  while ( sz < nSize )
	  sz += m_iGrowStep;
  m_heap.resize( sz );

  return true;
}


template <class K, class T>
CKeyHeapV<K,T>& CKeyHeapV<K,T> :: operator=( const CKeyHeapV& obj )
{
  clone( obj );
  return *this;
}


/*
template <class T>
void swap(T& v1, T& v2)
{
  T& tmp = v1;
  v1 = v2;
  v2 = tmp;
}
*/


// j - (j-1)/2
template <class K, class T>
bool CKeyHeapV<K,T> :: insert( const T& value, const K& key )
{
  if ( m_heap.size() < m_iCellCount+1 ) 
	  resize();

  m_heap[m_iCellCount].key   = key;
  m_heap[m_iCellCount].value = value;

  int i = m_iCellCount, j;
  m_iCellCount++;

  while ( i > 0 )
    {
      j = (i - 1) / 2;
      if ( key < m_heap[j].key )
	{
	  swap( m_heap[i].value, m_heap[j].value );
	  swap( m_heap[i].key,   m_heap[j].key   );
	  i = j;
	}
      else
	i = 0;
    }
  return true;
}


// i - 2i+1 - 2i+2
template <class K, class T>
bool CKeyHeapV<K,T> :: extract_min( T& value, K& key )
{
  if ( empty() ) return false;

  key   = m_heap[0].key;
  value = m_heap[0].value;

  m_heap[0].key   = m_heap[m_iCellCount-1].key;
  m_heap[0].value = m_heap[m_iCellCount-1].value;

  int i = 0, je, jd, k;

  while ( 2 * i + 1 < m_iCellCount-1 )
    {
      je = 2 * i + 1;
      jd = 2 * i + 2;

      if ( i < m_iCellCount-1 )
	{
	  k = je;
	  if ( m_heap[jd].key < m_heap[je].key ) k = jd;
	  
	  if ( m_heap[k].key < m_heap[i].key )
	    {
	      swap( m_heap[i].value, m_heap[k].value );
	      swap( m_heap[i].key,   m_heap[k].key   );
	      i = k;
	    }
	  else
	    i = m_iCellCount;
	}
    }
  m_iCellCount--;

  return true;
}