src/creaImageIOIndexedHeap.txx

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