/*
# ---------------------------------------------------------------------
#
# Copyright (c) CREATIS (Centre de Recherche en Acquisition et Traitement de l'Image 
#                        pour la Santé)
# Authors : Eduardo Davila, Frederic Cervenansky, Claire Mouton
# Previous Authors : Laurent Guigues, Jean-Pierre Roux
# CreaTools website : www.creatis.insa-lyon.fr/site/fr/creatools_accueil
#
#  This software is governed by the CeCILL-B license under French law and 
#  abiding by the rules of distribution of free software. You can  use, 
#  modify and/ or redistribute the software under the terms of the CeCILL-B 
#  license as circulated by CEA, CNRS and INRIA at the following URL 
#  http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html 
#  or in the file LICENSE.txt.
#
#  As a counterpart to the access to the source code and  rights to copy,
#  modify and redistribute granted by the license, users are provided only
#  with a limited warranty  and the software's author,  the holder of the
#  economic rights,  and the successive licensors  have only  limited
#  liability. 
#
#  The fact that you are presently reading this means that you have had
#  knowledge of the CeCILL-B license and that you accept its terms.
# ------------------------------------------------------------------------
*/


/* 

*/
/*! \file 
  \brief Code of IndexedHeap
*/
//============================================================================
template <class T, class CT, class IT>
std::ostream& operator << (std::ostream& s, const IndexedHeap<T,CT,IT>& t)
{
  s << "[";
  for (int i=0; i<t.size(); i++) s << t[i] << " "  ;
  s << "]";
  return s;
}
//============================================================================


//===========================================================
template <class T, class CT, class IT>
IndexedHeap<T,CT,IT>::IndexedHeap ( const CT& comp, const IT& index ) 
  : m_c(&comp), m_i(&index) 
{}
//===========================================================


//===========================================================
template <class T, class CT, class IT>
void IndexedHeap<T,CT,IT>::set( const CT& comp ) 
{ 
  m_c = &comp; 
}
//===========================================================

//===========================================================
template <class T, class CT, class IT>
void IndexedHeap<T,CT,IT>::set ( const IT& index ) 
{ 
  m_i = &index; 
}
//===========================================================


//===========================================================
template <class T, class CT, class IT>
int IndexedHeap<T,CT,IT>::insert(T t)
{
  m_p.push_back(t);
  (*m_i)(t) = size()-1;
  return upsort(size()-1);
}
//===========================================================

//===========================================================
template <class T, class CT, class IT>
T& IndexedHeap<T,CT,IT>::top()
{
  //  lglASSERT( size() > 0)
    return m_p.front();
}
//===========================================================


//===========================================================
template <class T, class CT, class IT>
const T& IndexedHeap<T,CT,IT>::top() const
{
  //  lglASSERT( size() > 0)
    return m_p.front();
}
//===========================================================

//===========================================================
template <class T, class CT, class IT>
T IndexedHeap<T,CT,IT>::remove_top()
{
  //  lglASSERT( size() > 0 ) 
    T f(m_p[0]);
  (*m_i)(f) = -1;
  T last = m_p.back();
  m_p.pop_back();
  if (m_p.size()>0) 
    {
    m_p[0] = last;
    (*m_i)(last) = 0;
    downsort(0);
  }
  return f;
}
//============================================================================



//============================================================================
template <class T, class CT, class IT>
T IndexedHeap<T,CT,IT>::remove(int n)
{
  //  lglASSERT ( (n>=0)&&(n<size()) ) 
    T f(m_p[n]);
  (*m_i)(f) = -1;
  T last = m_p.back();
  m_p.pop_back();
  if (m_p.size()>0) 
    {
    m_p[n] = last;
    (*m_i)(last) = n;
    downsort(n);
  }
  return f;
}
//============================================================================


//============================================================================
template <class T, class CT, class IT>
void IndexedHeap<T,CT,IT>::clear()
{
  for (typename std::vector<T>::iterator i=m_p.begin(); i!=m_p.end(); ++i) 
    { 
      (*m_i)(*i)=-1; 
    }
  m_p.clear();
}
//============================================================================


//============================================================================
template <class T, class CT, class IT>
int  IndexedHeap<T,CT,IT>::father( int  i) const
{
  return ((i-1)/2);
}
//============================================================================

//============================================================================
template <class T, class CT, class IT>
int  IndexedHeap<T,CT,IT>::rightson( int  i) const
{ 
  return (i*2+2);
}
//============================================================================

//============================================================================
template <class T, class CT, class IT>
int  IndexedHeap<T,CT,IT>::leftson( int  i) const
{ 
  return (i*2+1);
}
//============================================================================

//============================================================================
template <class T, class CT, class IT>
void IndexedHeap<T,CT,IT>::swap(int i, int j)
{
  T tmp = m_p[i];
  m_p[i] = m_p[j];
  m_p[j] = tmp;
  // update indices  
  (*m_i)(m_p[i]) = i;
  (*m_i)(m_p[j]) = j;
}
//============================================================================



//============================================================================
template <class T, class CT, class IT>
int  IndexedHeap<T,CT,IT>::upsort(int  i)
{
  //if (i==0) return i;
  int  j = father(i);
  while ((i>0)&&(*m_c)(m_p[i],m_p[j])) 
    {
    swap(i,j);
    i = j;
    j = father(j);
  }	
  return i;
}
//============================================================================


//============================================================================
template <class T, class CT, class IT>
int  IndexedHeap<T,CT,IT>::downsort(int  i)
{
  do 
    {
      
      unsigned int  ls = leftson(i);
      if (ls<m_p.size()) 
	{
      bool lc = ((*m_c)(m_p[i],m_p[ls]));
      unsigned int  rs = ls + 1;
      bool rc = true;
      if (rs<m_p.size()) rc = ((*m_c)(m_p[i],m_p[rs]));
      if  ( !lc ) 
	{ 
	if ( !rc ) 
	  { 
	  if ((*m_c)(m_p[ls],m_p[rs])) 
	    { 
	    swap(i,ls);
	    i = ls;
	  }
	  else 
	    { 
	    swap(i,rs);
	    i = rs;
	  }
	}
	else 
	  {
	  swap(i,ls);
	  i = ls;
	}
      }
      else if ( !rc ) 
	{ 
	swap(i,rs);
	i = rs;
      }
      else return i;
    } 
    else return i;
  }
  while (true);
  return i;
}
//============================================================================


//============================================================================
// EOF
//============================================================================