src/creaImageIOIndexedHeap.txx

   1 /*
   2 # ---------------------------------------------------------------------
   3 #
   4 # Copyright (c) CREATIS (Centre de Recherche en Acquisition et Traitement de l'Image
   5 #                        pour la Santé)
   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
   9 #
  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.
  16 #
  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
  21 #  liability.
  22 #
  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 # ------------------------------------------------------------------------
  26 */
  27
  28
  29 /*
  30
  31 */
  32 /*! \file
  33   \brief Code of IndexedHeap
  34 */
  35 //============================================================================
  36 template <class T, class CT, class IT>
  37 std::ostream& operator << (std::ostream& s, const IndexedHeap<T,CT,IT>& t)
  38 {
  39   s << "[";
  40   for (int i=0; i<t.size(); i++) s << t[i] << " "  ;
  41   s << "]";
  42   return s;
  43 }
  44 //============================================================================
  45
  46
  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)
  51 {}
  52 //===========================================================
  53
  54
  55 //===========================================================
  56 template <class T, class CT, class IT>
  57 void IndexedHeap<T,CT,IT>::set( const CT& comp )
  58 {
  59   m_c = &comp;
  60 }
  61 //===========================================================
  62
  63 //===========================================================
  64 template <class T, class CT, class IT>
  65 void IndexedHeap<T,CT,IT>::set ( const IT& index )
  66 {
  67   m_i = &index;
  68 }
  69 //===========================================================
  70
  71
  72 //===========================================================
  73 template <class T, class CT, class IT>
  74 int IndexedHeap<T,CT,IT>::insert(T t)
  75 {
  76   m_p.push_back(t);
  77   (*m_i)(t) = size()-1;
  78   return upsort(size()-1);
  79 }
  80 //===========================================================
  81
  82 //===========================================================
  83 template <class T, class CT, class IT>
  84 T& IndexedHeap<T,CT,IT>::top()
  85 {
  86   //  lglASSERT( size() > 0)
  87     return m_p.front();
  88 }
  89 //===========================================================
  90
  91
  92 //===========================================================
  93 template <class T, class CT, class IT>
  94 const T& IndexedHeap<T,CT,IT>::top() const
  95 {
  96   //  lglASSERT( size() > 0)
  97     return m_p.front();
  98 }
  99 //===========================================================
 100
 101 //===========================================================
 102 template <class T, class CT, class IT>
 103 T IndexedHeap<T,CT,IT>::remove_top()
 104 {
 105   //  lglASSERT( size() > 0 )
 106     T f(m_p[0]);
 107   (*m_i)(f) = -1;
 108   T last = m_p.back();
 109   m_p.pop_back();
 110   if (m_p.size()>0)
 111     {
 112     m_p[0] = last;
 113     (*m_i)(last) = 0;
 114     downsort(0);
 115   }
 116   return f;
 117 }
 118 //============================================================================
 119
 120
 121
 122 //============================================================================
 123 template <class T, class CT, class IT>
 124 T IndexedHeap<T,CT,IT>::remove(int n)
 125 {
 126   //  lglASSERT ( (n>=0)&&(n<size()) )
 127     T f(m_p[n]);
 128   (*m_i)(f) = -1;
 129   T last = m_p.back();
 130   m_p.pop_back();
 131   if (m_p.size()>0)
 132     {
 133     m_p[n] = last;
 134     (*m_i)(last) = n;
 135     downsort(n);
 136   }
 137   return f;
 138 }
 139 //============================================================================
 140
 141
 142 //============================================================================
 143 template <class T, class CT, class IT>
 144 void IndexedHeap<T,CT,IT>::clear()
 145 {
 146   for (typename std::vector<T>::iterator i=m_p.begin(); i!=m_p.end(); ++i)
 147     {
 148       (*m_i)(*i)=-1;
 149     }
 150   m_p.clear();
 151 }
 152 //============================================================================
 153
 154
 155 //============================================================================
 156 template <class T, class CT, class IT>
 157 int  IndexedHeap<T,CT,IT>::father( int  i) const
 158 {
 159   return ((i-1)/2);
 160 }
 161 //============================================================================
 162
 163 //============================================================================
 164 template <class T, class CT, class IT>
 165 int  IndexedHeap<T,CT,IT>::rightson( int  i) const
 166 {
 167   return (i*2+2);
 168 }
 169 //============================================================================
 170
 171 //============================================================================
 172 template <class T, class CT, class IT>
 173 int  IndexedHeap<T,CT,IT>::leftson( int  i) const
 174 {
 175   return (i*2+1);
 176 }
 177 //============================================================================
 178
 179 //============================================================================
 180 template <class T, class CT, class IT>
 181 void IndexedHeap<T,CT,IT>::swap(int i, int j)
 182 {
 183   T tmp = m_p[i];
 184   m_p[i] = m_p[j];
 185   m_p[j] = tmp;
 186   // update indices
 187   (*m_i)(m_p[i]) = i;
 188   (*m_i)(m_p[j]) = j;
 189 }
 190 //============================================================================
 191
 192
 193
 194 //============================================================================
 195 template <class T, class CT, class IT>
 196 int  IndexedHeap<T,CT,IT>::upsort(int  i)
 197 {
 198   //if (i==0) return i;
 199   int  j = father(i);
 200   while ((i>0)&&(*m_c)(m_p[i],m_p[j]))
 201     {
 202     swap(i,j);
 203     i = j;
 204     j = father(j);
 205   }
 206   return i;
 207 }
 208 //============================================================================
 209
 210
 211 //============================================================================
 212 template <class T, class CT, class IT>
 213 int  IndexedHeap<T,CT,IT>::downsort(int  i)
 214 {
 215   do
 216     {
 217
 218       unsigned int  ls = leftson(i);
 219       if (ls<m_p.size())
 220         {
 221       bool lc = ((*m_c)(m_p[i],m_p[ls]));
 222       unsigned int  rs = ls + 1;
 223       bool rc = true;
 224       if (rs<m_p.size()) rc = ((*m_c)(m_p[i],m_p[rs]));
 225       if  ( !lc )
 226         {
 227         if ( !rc )
 228           {
 229           if ((*m_c)(m_p[ls],m_p[rs]))
 230             {
 231             swap(i,ls);
 232             i = ls;
 233           }
 234           else
 235             {
 236             swap(i,rs);
 237             i = rs;
 238           }
 239         }
 240         else
 241           {
 242           swap(i,ls);
 243           i = ls;
 244         }
 245       }
 246       else if ( !rc )
 247         {
 248         swap(i,rs);
 249         i = rs;
 250       }
 251       else return i;
 252     }
 253     else return i;
 254   }
 255   while (true);
 256   return i;
 257 }
 258 //============================================================================
 259
 260
 261 //============================================================================
 262 // EOF
 263 //============================================================================