/*
# ---------------------------------------------------------------------
#
# 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 Indexed priority queues handled by binary trees.
*/
#ifndef __creaImageIOIndexedHeap_h_INCLUDED__
#define __creaImageIOIndexedHeap_h_INCLUDED__

#include <vector>

namespace creaImageIO 
{

	

  template <class T, 
	    class Comparator/*=Less<T>*/,
	    class Indexer/*=Index<T> */> 
  class IndexedHeap ;
  template < class T, 
	     class C, 
	     class I> 
  std::ostream& operator << (std::ostream&, const IndexedHeap<T,C,I>& );
 

  //template <class T, class Comparator=std::less<T>, class Index=IndexIndex<T> > class SlicedIndexedHeap; 


  //========================================================================
  /// \brief Indexed priority queues handled by binary trees. 
  /// 
  ///	Heap Allows :
  ///		- log(n) insertion
  ///		- constant time acces to the first element
  ///		- log(n) removal of the first element
  ///		- log(n) priority change of a random element 
  /// Indexation Allows :
  ///		- constant time access to a random element (for priority change)
  /// 
  /// The Indexer is an unary_function<T,int&> whose operator()(T& t) 
  /// returns a reference on an integer which 
  /// is maintained by the IndexedHeap in order to provide at any time 
  /// the position of the object t in the Heap 
  /// (hence allowing constant time random access to an object). 
  template <class T, 
	    class Comparator /*=Less<T>*/, 
	    class Indexer /*=Index<T>*/> 
  class IndexedHeap 
  {
    //			friend class SlicedIndexedHeap<T,Comparator,Index>;
  public :
		
    //======================================================================
    /// Constructor 
    IndexedHeap () {}
    /// Constructor 
    IndexedHeap ( const Comparator& comp, const Indexer& ind ) ;
    /// Destructor 
    ~IndexedHeap() { }
    /// Sets the comparator 
    void set( const Comparator& comp );
    /// Sets the Index 
    void set( const Indexer& ind );
    //======================================================================
    		
    //======================================================================
    /// inserts an element in the Heap and returns its position 
    int insert(T);
    /// return a reference on the first element of the Heap 
    T& top(); 
    /// return a constant reference on the first element of the Heap 
    const T& top() const;  
    /// removes and returns the first element of the Heap 
    T remove_top();
    /// removes and returns the nth element 
    T remove(int n);
    /// returns the size of the Heap 
    inline int size() const {return (int)m_p.size(); }
    /// empties the Heap 
	void clear();
    //======================================================================
	
    //======================================================================
    /// returns a constant on the stack of elements 
    const std::vector<T> & stack() const {return m_p;}
    /// returns a reference to the ith element of the stack 
    T& operator [] (int i) { return m_p[i];}
    /// returns a constant reference to the ith element of the stack 
    const T& operator [] (int i) const { return m_p[i];}
    /// returns the index (position) of t 
    inline int index(T& t) { return (*m_i)(t); }
    //======================================================================

    //======================================================================
    /// returns the position of the father of i 
    inline int father( int i ) const;
    /// returns the position of the right son of i 
    inline int rightson( int i ) const;
    /// returns the position of the leftson of i 
    inline int leftson( int i ) const;
    //======================================================================
    /// swaps ith and jth elements 
    inline void swap(int i, int j);
    /// remonte un element dans le tas tant qu'il n'est pas a sa place. 
    /// renvoie la position finale 
    inline int upsort(int);
    /// descend un element dans le tas tant qu'il n'est pas a sa place.
    /// renvoie la position finale
    inline int downsort(int);
    //======================================================================
			
  protected : 
    /// binary tree handled by a vector 
    std::vector<T> m_p;
    /// comparator pointer 
    const Comparator* m_c;
    /// Index pointer 
    const Indexer*  m_i;
  };
  //========================================================================
  // EO class IndexedHeap
  //========================================================================


#include "creaImageIOIndexedHeap.txx"


};
//===========================================================================
// EO namespace creaImageIO
//===========================================================================



//===========================================================================
// EOF
//===========================================================================
#endif