src/creaImageIOIndexedHeap.h

   1 /*
   2
   3 */
   4 /*! \file
   5         \brief Indexed priority queues handled by binary trees.
   6 */
   7 #ifndef __creaImageIOIndexedHeap_h_INCLUDED__
   8 #define __creaImageIOIndexedHeap_h_INCLUDED__
   9
  10 #include <vector>
  11
  12 namespace creaImageIO
  13 {
  14
  15
  16
  17   template <class T,
  18             class Comparator/*=Less<T>*/,
  19             class Indexer/*=Index<T> */>
  20   class IndexedHeap ;
  21   template < class T,
  22              class C,
  23              class I>
  24   std::ostream& operator << (std::ostream&, const IndexedHeap<T,C,I>& );
  25
  26
  27   //template <class T, class Comparator=std::less<T>, class Index=IndexIndex<T> > class SlicedIndexedHeap;
  28
  29
  30   //========================================================================
  31   /// \brief Indexed priority queues handled by binary trees.
  32   ///
  33   ///   Heap Allows :
  34   ///           - log(n) insertion
  35   ///           - constant time acces to the first element
  36   ///           - log(n) removal of the first element
  37   ///           - log(n) priority change of a random element
  38   /// Indexation Allows :
  39   ///           - constant time access to a random element (for priority change)
  40   ///
  41   /// The Indexer is an unary_function<T,int&> whose operator()(T& t)
  42   /// returns a reference on an integer which
  43   /// is maintained by the IndexedHeap in order to provide at any time
  44   /// the position of the object t in the Heap
  45   /// (hence allowing constant time random access to an object).
  46   template <class T,
  47             class Comparator /*=Less<T>*/,
  48             class Indexer /*=Index<T>*/>
  49   class IndexedHeap
  50   {
  51     //                  friend class SlicedIndexedHeap<T,Comparator,Index>;
  52   public :
  53
  54     //======================================================================
  55     /// Constructor
  56     IndexedHeap () {}
  57     /// Constructor
  58     IndexedHeap ( const Comparator& comp, const Indexer& ind ) ;
  59     /// Destructor
  60     ~IndexedHeap() { }
  61     /// Sets the comparator
  62     void set( const Comparator& comp );
  63     /// Sets the Index
  64     void set( const Indexer& ind );
  65     //======================================================================
  66
  67     //======================================================================
  68     /// inserts an element in the Heap and returns its position
  69     int insert(T);
  70     /// return a reference on the first element of the Heap
  71     T& top();
  72     /// return a constant reference on the first element of the Heap
  73     const T& top() const;
  74     /// removes and returns the first element of the Heap
  75     T remove_top();
  76     /// removes and returns the nth element
  77     T remove(int n);
  78     /// returns the size of the Heap
  79     inline int size() const {return m_p.size(); }
  80     /// empties the Heap
  81         void clear();
  82     //======================================================================
  83
  84     //======================================================================
  85     /// returns a constant on the stack of elements
  86     const std::vector<T> & stack() const {return m_p;}
  87     /// returns a reference to the ith element of the stack
  88     T& operator [] (int i) { return m_p[i];}
  89     /// returns a constant reference to the ith element of the stack
  90     const T& operator [] (int i) const { return m_p[i];}
  91     /// returns the index (position) of t
  92     inline int index(T& t) { return (*m_i)(t); }
  93     //======================================================================
  94
  95     //======================================================================
  96     /// returns the position of the father of i
  97     inline int father( int i ) const;
  98     /// returns the position of the right son of i
  99     inline int rightson( int i ) const;
 100     /// returns the position of the leftson of i
 101     inline int leftson( int i ) const;
 102     //======================================================================
 103     /// swaps ith and jth elements
 104     inline void swap(int i, int j);
 105     /// remonte un element dans le tas tant qu'il n'est pas a sa place.
 106     /// renvoie la position finale
 107     inline int upsort(int);
 108     /// descend un element dans le tas tant qu'il n'est pas a sa place.
 109     /// renvoie la position finale
 110     inline int downsort(int);
 111     //======================================================================
 112
 113   protected :
 114     /// binary tree handled by a vector
 115     std::vector<T> m_p;
 116     /// comparator pointer
 117     const Comparator* m_c;
 118     /// Index pointer
 119     const Indexer*  m_i;
 120   };
 121   //========================================================================
 122   // EO class IndexedHeap
 123   //========================================================================
 124
 125
 126 #include "creaImageIOIndexedHeap.txx"
 127
 128
 129 };
 130 //===========================================================================
 131 // EO namespace creaImageIO
 132 //===========================================================================
 133
 134
 135
 136 //===========================================================================
 137 // EOF
 138 //===========================================================================
 139 #endif