src2/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)->delete();
 121       (*m_i)(*i)=-1;
 122     }
 123   m_p.clear();
 124 }
 125 //============================================================================
 126
 127
 128 //============================================================================
 129 template <class T, class CT, class IT>
 130 int  IndexedHeap<T,CT,IT>::father( int  i) const
 131 {
 132   return ((i-1)/2);
 133 }
 134 //============================================================================
 135
 136 //============================================================================
 137 template <class T, class CT, class IT>
 138 int  IndexedHeap<T,CT,IT>::rightson( int  i) const
 139 {
 140   return (i*2+2);
 141 }
 142 //============================================================================
 143
 144 //============================================================================
 145 template <class T, class CT, class IT>
 146 int  IndexedHeap<T,CT,IT>::leftson( int  i) const
 147 {
 148   return (i*2+1);
 149 }
 150 //============================================================================
 151
 152 //============================================================================
 153 template <class T, class CT, class IT>
 154 void IndexedHeap<T,CT,IT>::swap(int i, int j)
 155 {
 156   T tmp = m_p[i];
 157   m_p[i] = m_p[j];
 158   m_p[j] = tmp;
 159   // update indices
 160   (*m_i)(m_p[i]) = i;
 161   (*m_i)(m_p[j]) = j;
 162 }
 163 //============================================================================
 164
 165
 166
 167 //============================================================================
 168 template <class T, class CT, class IT>
 169 int  IndexedHeap<T,CT,IT>::upsort(int  i)
 170 {
 171   //if (i==0) return i;
 172   int  j = father(i);
 173   while ((i>0)&&(*m_c)(m_p[i],m_p[j]))
 174     {
 175     swap(i,j);
 176     i = j;
 177     j = father(j);
 178   }
 179   return i;
 180 }
 181 //============================================================================
 182
 183
 184 //============================================================================
 185 template <class T, class CT, class IT>
 186 int  IndexedHeap<T,CT,IT>::downsort(int  i)
 187 {
 188   do
 189     {
 190
 191       unsigned int  ls = leftson(i);
 192       if (ls<m_p.size())
 193         {
 194       bool lc = ((*m_c)(m_p[i],m_p[ls]));
 195       unsigned int  rs = ls + 1;
 196       bool rc = true;
 197       if (rs<m_p.size()) rc = ((*m_c)(m_p[i],m_p[rs]));
 198       if  ( !lc )
 199         {
 200         if ( !rc )
 201           {
 202           if ((*m_c)(m_p[ls],m_p[rs]))
 203             {
 204             swap(i,ls);
 205             i = ls;
 206           }
 207           else
 208             {
 209             swap(i,rs);
 210             i = rs;
 211           }
 212         }
 213         else
 214           {
 215           swap(i,ls);
 216           i = ls;
 217         }
 218       }
 219       else if ( !rc )
 220         {
 221         swap(i,rs);
 222         i = rs;
 223       }
 224       else return i;
 225     }
 226     else return i;
 227   }
 228   while (true);
 229   return i;
 230 }
 231 //============================================================================
 232
 233
 234 //============================================================================
 235 // EOF
 236 //============================================================================