2 # ---------------------------------------------------------------------
4 # Copyright (c) CREATIS (Centre de Recherche en Acquisition et Traitement de l'Image
6 # Authors : Eduardo Davila, Frederic Cervenansky, Claire Mouton
7 # Previous Authors : Laurent Guigues, Jean-Pierre Roux
8 # CreaTools website : www.creatis.insa-lyon.fr/site/fr/creatools_accueil
10 # This software is governed by the CeCILL-B license under French law and
11 # abiding by the rules of distribution of free software. You can use,
12 # modify and/ or redistribute the software under the terms of the CeCILL-B
13 # license as circulated by CEA, CNRS and INRIA at the following URL
14 # http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html
15 # or in the file LICENSE.txt.
17 # As a counterpart to the access to the source code and rights to copy,
18 # modify and redistribute granted by the license, users are provided only
19 # with a limited warranty and the software's author, the holder of the
20 # economic rights, and the successive licensors have only limited
23 # The fact that you are presently reading this means that you have had
24 # knowledge of the CeCILL-B license and that you accept its terms.
25 # ------------------------------------------------------------------------
33 \brief Indexed priority queues handled by binary trees.
35 #ifndef __creaImageIOIndexedHeap_h_INCLUDED__
36 #define __creaImageIOIndexedHeap_h_INCLUDED__
46 class Comparator/*=Less<T>*/,
47 class Indexer/*=Index<T> */>
52 std::ostream& operator << (std::ostream&, const IndexedHeap<T,C,I>& );
55 //template <class T, class Comparator=std::less<T>, class Index=IndexIndex<T> > class SlicedIndexedHeap;
58 //========================================================================
59 /// \brief Indexed priority queues handled by binary trees.
62 /// - log(n) insertion
63 /// - constant time acces to the first element
64 /// - log(n) removal of the first element
65 /// - log(n) priority change of a random element
66 /// Indexation Allows :
67 /// - constant time access to a random element (for priority change)
69 /// The Indexer is an unary_function<T,int&> whose operator()(T& t)
70 /// returns a reference on an integer which
71 /// is maintained by the IndexedHeap in order to provide at any time
72 /// the position of the object t in the Heap
73 /// (hence allowing constant time random access to an object).
75 class Comparator /*=Less<T>*/,
76 class Indexer /*=Index<T>*/>
79 // friend class SlicedIndexedHeap<T,Comparator,Index>;
82 //======================================================================
86 IndexedHeap ( const Comparator& comp, const Indexer& ind ) ;
89 /// Sets the comparator
90 void set( const Comparator& comp );
92 void set( const Indexer& ind );
93 //======================================================================
95 //======================================================================
96 /// inserts an element in the Heap and returns its position
98 /// return a reference on the first element of the Heap
100 /// return a constant reference on the first element of the Heap
101 const T& top() const;
102 /// removes and returns the first element of the Heap
104 /// removes and returns the nth element
106 /// returns the size of the Heap
107 inline int size() const {return m_p.size(); }
110 //======================================================================
112 //======================================================================
113 /// returns a constant on the stack of elements
114 const std::vector<T> & stack() const {return m_p;}
115 /// returns a reference to the ith element of the stack
116 T& operator [] (int i) { return m_p[i];}
117 /// returns a constant reference to the ith element of the stack
118 const T& operator [] (int i) const { return m_p[i];}
119 /// returns the index (position) of t
120 inline int index(T& t) { return (*m_i)(t); }
121 //======================================================================
123 //======================================================================
124 /// returns the position of the father of i
125 inline int father( int i ) const;
126 /// returns the position of the right son of i
127 inline int rightson( int i ) const;
128 /// returns the position of the leftson of i
129 inline int leftson( int i ) const;
130 //======================================================================
131 /// swaps ith and jth elements
132 inline void swap(int i, int j);
133 /// remonte un element dans le tas tant qu'il n'est pas a sa place.
134 /// renvoie la position finale
135 inline int upsort(int);
136 /// descend un element dans le tas tant qu'il n'est pas a sa place.
137 /// renvoie la position finale
138 inline int downsort(int);
139 //======================================================================
142 /// binary tree handled by a vector
144 /// comparator pointer
145 const Comparator* m_c;
149 //========================================================================
150 // EO class IndexedHeap
151 //========================================================================
154 #include "creaImageIOIndexedHeap.txx"
158 //===========================================================================
159 // EO namespace creaImageIO
160 //===========================================================================
164 //===========================================================================
166 //===========================================================================