intern/container/CTR_UHeap.h

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