intern/container/CTR_UHeap.h

   1 /**
   2  * $Id$
   3  * ***** BEGIN GPL LICENSE BLOCK *****
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software Foundation,
  17  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18  *
  19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  20  * All rights reserved.
  21  *
  22  * The Original Code is: all of this file.
  23  *
  24  * Contributor(s): none yet.
  25  *
  26  * ***** END GPL LICENSE BLOCK *****
  27  */
  28
  29 /**
  30
  31  * $Id$
  32  * Copyright (C) 2001 NaN Technologies B.V.
  33  *
  34  * @author Laurence
  35  * @mainpage CTR_UHeap an updatable heap template class (also
  36  * known as an updatable priority queue)
  37  *
  38  * Todo: Make CTR_UHeapable a template class with m_key the
  39  * template parameter, so that arbitrary value types with
  40  * operators (=,>) defined can be used.
  41  *
  42  */
  43
  44 #ifndef NAN_INCLUDED_CTR_UHeap_h
  45 #define NAN_INCLUDED_CTR_UHeap_h
  46
  47 #include <vector>
  48
  49 #include "MEM_NonCopyable.h"
  50
  51 class CTR_UHeapable {
  52
  53 public :
  54                 int &
  55         HeapPos(
  56         ){
  57                 return m_ind;
  58         };
  59                 float &
  60         HeapKey(
  61         ) {
  62                 return m_key;
  63         };
  64
  65         const
  66                 float &
  67         HeapKey(
  68         ) const {
  69                 return m_key;
  70         };
  71
  72         const
  73                 int &
  74         HeapPos(
  75         ) const {
  76                 return m_ind;
  77         };
  78
  79 private :
  80
  81         float m_key;
  82         int m_ind;
  83
  84 protected :
  85
  86         CTR_UHeapable(
  87         ) : m_key (0),
  88                 m_ind (0)
  89         {
  90         };
  91
  92         ~CTR_UHeapable(
  93         ){
  94         };
  95 };
  96
  97 template <class HeapType>
  98 class CTR_UHeap : public MEM_NonCopyable
  99 {
 100
 101 public:
 102
 103         static
 104                 CTR_UHeap *
 105         New(
 106         ) {
 107                 return new CTR_UHeap();
 108         }
 109
 110                 void
 111         MakeHeap(
 112                 HeapType *base
 113         ) {
 114                 int i;
 115                 int start = Parent(m_vector.size()-1);
 116                 for (i = start; i >=0; --i) {
 117                         DownHeap(base,i);
 118                 }
 119         };
 120
 121                 void
 122         Insert(
 123                 HeapType *base,
 124                 int elem
 125         ) {
 126                 // add element to vector
 127                 m_vector.push_back(elem);
 128                 base[elem].HeapPos() = m_vector.size()-1;
 129
 130                 // push the element up the heap
 131                 UpHeap(base,m_vector.size()-1);
 132         }
 133
 134         // access to the vector for initial loading of elements
 135
 136                 std::vector<int> &
 137         HeapVector(
 138         ) {
 139                 return m_vector;
 140         };
 141
 142
 143                 void
 144         Remove(
 145                 HeapType *base,
 146                 int i
 147         ) {
 148
 149                 // exchange with last element - pop last
 150                 // element and move up or down the heap as appropriate
 151                 if (m_vector.empty()) {
 152                         assert(false);
 153                 }
 154
 155                 if (i  != int(m_vector.size())-1) {
 156
 157                         Swap(base,i,m_vector.size() - 1);
 158                         m_vector.pop_back();
 159
 160                         if (!m_vector.empty()) {
 161                                 UpHeap(base,i);
 162                                 DownHeap(base,i);
 163                         }
 164                 } else {
 165                         m_vector.pop_back();
 166                 }
 167         }
 168
 169                 int
 170         Top(
 171         ) const {
 172                 if (m_vector.empty()) return -1;
 173                 return m_vector[0];
 174         }
 175
 176
 177                 void
 178         SC_Heap(
 179                 HeapType *base
 180         ) {
 181                 int i;
 182                 for (i = 1; i < int(m_vector.size()) ; i++) {
 183
 184                         CTR_UHeapable * elem = base + m_vector[i];
 185                         CTR_UHeapable * p_elem = base + m_vector[Parent(i)];
 186
 187                         assert(p_elem->HeapKey() >= elem->HeapKey());
 188                         assert(elem->HeapPos() == i);
 189                 }
 190
 191         };
 192
 193
 194         ~CTR_UHeap(
 195         ) {
 196         };
 197
 198
 199 private:
 200
 201         CTR_UHeap(
 202         ) {
 203         };
 204
 205
 206         std::vector<int> m_vector;
 207
 208 private:
 209                 void
 210         Swap(
 211                 HeapType *base,
 212                 int i,
 213                 int j
 214         ){
 215                 std::swap(m_vector[i],m_vector[j]);
 216
 217                 CTR_UHeapable *heap_i = base + m_vector[i];
 218                 CTR_UHeapable *heap_j = base + m_vector[j];
 219
 220                 // Exchange heap positions
 221                 heap_i->HeapPos() = i;
 222                 heap_j->HeapPos() = j;
 223         }
 224
 225                 int
 226         Parent(
 227                 unsigned int i
 228         ) {
 229                  return (i-1) >> 1;
 230         }
 231                 int
 232         Left(
 233                 int i
 234         ) {
 235                 return (i<<1)+1;
 236         }
 237
 238                 int
 239         Right(
 240                 int i
 241         ) {
 242                 return (i<<1)+2;
 243         }
 244
 245                 float
 246         HeapVal(
 247                 HeapType *base,
 248                 int i
 249         ) {
 250                 return base[m_vector[i]].HeapKey();
 251         }
 252
 253                 void
 254         DownHeap(
 255                 HeapType *base,
 256                 int i
 257         ) {
 258                 int heap_size = m_vector.size();
 259
 260                 int l = Left(i);
 261                 int r = Right(i);
 262
 263                 int largest;
 264                 if (l < heap_size && HeapVal(base,l) > HeapVal(base,i)) {
 265                         largest = l;
 266                 } else {
 267                         largest = i;
 268                 }
 269
 270                 if (r < heap_size && HeapVal(base,r) > HeapVal(base,largest)) {
 271                         largest = r;
 272                 }
 273
 274                 if (largest != i) {
 275                         // exchange i and largest
 276                         Swap(base,i,largest);
 277                         DownHeap(base,largest);
 278                 }
 279         }
 280
 281                 void
 282         UpHeap(
 283                 HeapType *base,
 284                 int i
 285         ) {
 286
 287                 // swap parents untill it's found a place in the heap < it's parent or
 288                 // top of heap
 289
 290                 while (i > 0) {
 291                         int p = Parent(i);
 292                         if (HeapVal(base,i) < HeapVal(base,p)) {
 293                                 break;
 294                         }
 295                         Swap(base,p,i);
 296                         i = p;
 297                 }
 298         }
 299 };
 300
 301 #endif
 302