5 \brief Indexed priority queues handled by binary trees.
7 #ifndef __creaImageIOIndexedHeap_h_INCLUDED__
8 #define __creaImageIOIndexedHeap_h_INCLUDED__
18 class Comparator/*=Less<T>*/,
19 class Indexer/*=Index<T> */>
24 std::ostream& operator << (std::ostream&, const IndexedHeap<T,C,I>& );
27 //template <class T, class Comparator=std::less<T>, class Index=IndexIndex<T> > class SlicedIndexedHeap;
30 //========================================================================
31 /// \brief Indexed priority queues handled by binary trees.
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)
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).
47 class Comparator /*=Less<T>*/,
48 class Indexer /*=Index<T>*/>
51 // friend class SlicedIndexedHeap<T,Comparator,Index>;
54 //======================================================================
58 IndexedHeap ( const Comparator& comp, const Indexer& ind ) ;
61 /// Sets the comparator
62 void set( const Comparator& comp );
64 void set( const Indexer& ind );
65 //======================================================================
67 //======================================================================
68 /// inserts an element in the Heap and returns its position
70 /// return a reference on the first element of the Heap
72 /// return a constant reference on the first element of the Heap
74 /// removes and returns the first element of the Heap
76 /// removes and returns the nth element
78 /// returns the size of the Heap
79 inline int size() const {return m_p.size(); }
82 //======================================================================
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 //======================================================================
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 //======================================================================
114 /// binary tree handled by a vector
116 /// comparator pointer
117 const Comparator* m_c;
121 //========================================================================
122 // EO class IndexedHeap
123 //========================================================================
126 #include "creaImageIOIndexedHeap.txx"
130 //===========================================================================
131 // EO namespace creaImageIO
132 //===========================================================================
136 //===========================================================================
138 //===========================================================================