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 Code of IndexedHeap
35 //============================================================================
36 template <class T, class CT, class IT>
37 std::ostream& operator << (std::ostream& s, const IndexedHeap<T,CT,IT>& t)
40 for (int i=0; i<t.size(); i++) s << t[i] << " " ;
44 //============================================================================
47 //===========================================================
48 template <class T, class CT, class IT>
49 IndexedHeap<T,CT,IT>::IndexedHeap ( const CT& comp, const IT& index )
50 : m_c(&comp), m_i(&index)
52 //===========================================================
55 //===========================================================
56 template <class T, class CT, class IT>
57 void IndexedHeap<T,CT,IT>::set( const CT& comp )
61 //===========================================================
63 //===========================================================
64 template <class T, class CT, class IT>
65 void IndexedHeap<T,CT,IT>::set ( const IT& index )
69 //===========================================================
72 //===========================================================
73 template <class T, class CT, class IT>
74 int IndexedHeap<T,CT,IT>::insert(T t)
78 return upsort(size()-1);
80 //===========================================================
82 //===========================================================
83 template <class T, class CT, class IT>
84 T& IndexedHeap<T,CT,IT>::top()
86 // lglASSERT( size() > 0)
89 //===========================================================
92 //===========================================================
93 template <class T, class CT, class IT>
94 const T& IndexedHeap<T,CT,IT>::top() const
96 // lglASSERT( size() > 0)
99 //===========================================================
101 //===========================================================
102 template <class T, class CT, class IT>
103 T IndexedHeap<T,CT,IT>::remove_top()
105 // lglASSERT( size() > 0 )
118 //============================================================================
122 //============================================================================
123 template <class T, class CT, class IT>
124 T IndexedHeap<T,CT,IT>::remove(int n)
126 // lglASSERT ( (n>=0)&&(n<size()) )
139 //============================================================================
142 //============================================================================
143 template <class T, class CT, class IT>
144 void IndexedHeap<T,CT,IT>::clear()
146 for (typename std::vector<T>::iterator i=m_p.begin(); i!=m_p.end(); ++i)
152 //============================================================================
155 //============================================================================
156 template <class T, class CT, class IT>
157 int IndexedHeap<T,CT,IT>::father( int i) const
161 //============================================================================
163 //============================================================================
164 template <class T, class CT, class IT>
165 int IndexedHeap<T,CT,IT>::rightson( int i) const
169 //============================================================================
171 //============================================================================
172 template <class T, class CT, class IT>
173 int IndexedHeap<T,CT,IT>::leftson( int i) const
177 //============================================================================
179 //============================================================================
180 template <class T, class CT, class IT>
181 void IndexedHeap<T,CT,IT>::swap(int i, int j)
190 //============================================================================
194 //============================================================================
195 template <class T, class CT, class IT>
196 int IndexedHeap<T,CT,IT>::upsort(int i)
198 //if (i==0) return i;
200 while ((i>0)&&(*m_c)(m_p[i],m_p[j]))
208 //============================================================================
211 //============================================================================
212 template <class T, class CT, class IT>
213 int IndexedHeap<T,CT,IT>::downsort(int i)
218 unsigned int ls = leftson(i);
221 bool lc = ((*m_c)(m_p[i],m_p[ls]));
222 unsigned int rs = ls + 1;
224 if (rs<m_p.size()) rc = ((*m_c)(m_p[i],m_p[rs]));
229 if ((*m_c)(m_p[ls],m_p[rs]))
258 //============================================================================
261 //============================================================================
263 //============================================================================