src/misc/binaryheap.hpp

   1 /* $Id: binaryheap.hpp 24900 2013-01-08 22:46:42Z planetmaker $ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   8  */
   9
  10 /** @file binaryheap.hpp Binary heap implementation. */
  11
  12 #ifndef BINARYHEAP_HPP
  13 #define BINARYHEAP_HPP
  14
  15 #include "../core/alloc_func.hpp"
  16
  17 /** Enable it if you suspect binary heap doesn't work well */
  18 #define BINARYHEAP_CHECK 0
  19
  20 #if BINARYHEAP_CHECK
  21         /** Check for consistency. */
  22         #define CHECK_CONSISTY() this->CheckConsistency()
  23 #else
  24         /** Don't check for consistency. */
  25         #define CHECK_CONSISTY() ;
  26 #endif
  27
  28 /**
  29  * Binary Heap as C++ template.
  30  *  A carrier which keeps its items automatically holds the smallest item at
  31  *  the first position. The order of items is maintained by using a binary tree.
  32  *  The implementation is used for priority queue's.
  33  *
  34  * @par Usage information:
  35  * Item of the binary heap should support the 'lower-than' operator '<'.
  36  * It is used for comparing items before moving them to their position.
  37  *
  38  * @par
  39  * This binary heap allocates just the space for item pointers. The items
  40  * are allocated elsewhere.
  41  *
  42  * @par Implementation notes:
  43  * Internally the first item is never used, because that simplifies the
  44  * implementation.
  45  *
  46  * @par
  47  * For further information about the Binary Heap algorithm, see
  48  * http://www.policyalmanac.org/games/binaryHeaps.htm
  49  *
  50  * @tparam T Type of the items stored in the binary heap
  51  */
  52 template <class T>
  53 class CBinaryHeapT {
  54 private:
  55         uint items;    ///< Number of items in the heap
  56         uint capacity; ///< Maximum number of items the heap can hold
  57         T **data;      ///< The pointer to the heap item pointers
  58
  59 public:
  60         /**
  61          * Create a binary heap.
  62          * @param max_items The limit of the heap
  63          */
  64         explicit CBinaryHeapT(uint max_items)
  65                 : items(0)
  66                 , capacity(max_items)
  67         {
  68                 this->data = MallocT<T *>(max_items + 1);
  69         }
  70
  71         ~CBinaryHeapT()
  72         {
  73                 this->Clear();
  74                 free(this->data);
  75                 this->data = nullptr;
  76         }
  77
  78 protected:
  79         /**
  80          * Get position for fixing a gap (downwards).
  81          *  The gap is moved downwards in the binary tree until it
  82          *  is in order again.
  83          *
  84          * @param gap The position of the gap
  85          * @param item The proposed item for filling the gap
  86          * @return The (gap)position where the item fits
  87          */
  88         inline uint HeapifyDown(uint gap, T *item)
  89         {
  90                 assert(gap != 0);
  91
  92                 /* The first child of the gap is at [parent * 2] */
  93                 uint child = gap * 2;
  94
  95                 /* while children are valid */
  96                 while (child <= this->items) {
  97                         /* choose the smaller child */
  98                         if (child < this->items && *this->data[child + 1] < *this->data[child]) {
  99                                 child++;
 100                         }
 101                         /* is it smaller than our parent? */
 102                         if (!(*this->data[child] < *item)) {
 103                                 /* the smaller child is still bigger or same as parent => we are done */
 104                                 break;
 105                         }
 106                         /* if smaller child is smaller than parent, it will become new parent */
 107                         this->data[gap] = this->data[child];
 108                         gap = child;
 109                         /* where do we have our new children? */
 110                         child = gap * 2;
 111                 }
 112                 return gap;
 113         }
 114
 115         /**
 116          * Get position for fixing a gap (upwards).
 117          *  The gap is moved upwards in the binary tree until the
 118          *  is in order again.
 119          *
 120          * @param gap The position of the gap
 121          * @param item The proposed item for filling the gap
 122          * @return The (gap)position where the item fits
 123          */
 124         inline uint HeapifyUp(uint gap, T *item)
 125         {
 126                 assert(gap != 0);
 127
 128                 uint parent;
 129
 130                 while (gap > 1) {
 131                         /* compare [gap] with its parent */
 132                         parent = gap / 2;
 133                         if (!(*item < *this->data[parent])) {
 134                                 /* we don't need to continue upstairs */
 135                                 break;
 136                         }
 137                         this->data[gap] = this->data[parent];
 138                         gap = parent;
 139                 }
 140                 return gap;
 141         }
 142
 143 #if BINARYHEAP_CHECK
 144         /** Verify the heap consistency */
 145         inline void CheckConsistency()
 146         {
 147                 for (uint child = 2; child <= this->items; child++) {
 148                         uint parent = child / 2;
 149                         assert(!(*this->data[child] < *this->data[parent]));
 150                 }
 151         }
 152 #endif
 153
 154 public:
 155         /**
 156          * Get the number of items stored in the priority queue.
 157          *
 158          *  @return The number of items in the queue
 159          */
 160         inline uint Length() const
 161         {
 162                 return this->items;
 163         }
 164
 165         /**
 166          * Test if the priority queue is empty.
 167          *
 168          * @return True if empty
 169          */
 170         inline bool IsEmpty() const
 171         {
 172                 return this->items == 0;
 173         }
 174
 175         /**
 176          * Test if the priority queue is full.
 177          *
 178          * @return True if full.
 179          */
 180         inline bool IsFull() const
 181         {
 182                 return this->items >= this->capacity;
 183         }
 184
 185         /**
 186          * Get the smallest item in the binary tree.
 187          *
 188          * @return The smallest item, or throw assert if empty.
 189          */
 190         inline T *Begin()
 191         {
 192                 assert(!this->IsEmpty());
 193                 return this->data[1];
 194         }
 195
 196         /**
 197          * Get the LAST item in the binary tree.
 198          *
 199          * @note The last item is not necessary the biggest!
 200          *
 201          * @return The last item
 202          */
 203         inline T *End()
 204         {
 205                 return this->data[1 + this->items];
 206         }
 207
 208         /**
 209          * Insert new item into the priority queue, maintaining heap order.
 210          *
 211          * @param new_item The pointer to the new item
 212          */
 213         inline void Include(T *new_item)
 214         {
 215                 if (this->IsFull()) {
 216                         assert(this->capacity < UINT_MAX / 2);
 217
 218                         this->capacity *= 2;
 219                         this->data = ReallocT<T*>(this->data, this->capacity + 1);
 220                 }
 221
 222                 /* Make place for new item. A gap is now at the end of the tree. */
 223                 uint gap = this->HeapifyUp(++items, new_item);
 224                 this->data[gap] = new_item;
 225                 CHECK_CONSISTY();
 226         }
 227
 228         /**
 229          * Remove and return the smallest (and also first) item
 230          *  from the priority queue.
 231          *
 232          * @return The pointer to the removed item
 233          */
 234         inline T *Shift()
 235         {
 236                 assert(!this->IsEmpty());
 237
 238                 T *first = this->Begin();
 239
 240                 this->items--;
 241                 /* at index 1 we have a gap now */
 242                 T *last = this->End();
 243                 uint gap = this->HeapifyDown(1, last);
 244                 /* move last item to the proper place */
 245                 if (!this->IsEmpty()) this->data[gap] = last;
 246
 247                 CHECK_CONSISTY();
 248                 return first;
 249         }
 250
 251         /**
 252          * Remove item at given index from the priority queue.
 253          *
 254          * @param index The position of the item in the heap
 255          */
 256         inline void Remove(uint index)
 257         {
 258                 if (index < this->items) {
 259                         assert(index != 0);
 260                         this->items--;
 261                         /* at position index we have a gap now */
 262
 263                         T *last = this->End();
 264                         /* Fix binary tree up and downwards */
 265                         uint gap = this->HeapifyUp(index, last);
 266                         gap = this->HeapifyDown(gap, last);
 267                         /* move last item to the proper place */
 268                         if (!this->IsEmpty()) this->data[gap] = last;
 269                 } else {
 270                         assert(index == this->items);
 271                         this->items--;
 272                 }
 273                 CHECK_CONSISTY();
 274         }
 275
 276         /**
 277          * Search for an item in the priority queue.
 278          *  Matching is done by comparing address of the
 279          *  item.
 280          *
 281          * @param item The reference to the item
 282          * @return The index of the item or zero if not found
 283          */
 284         inline uint FindIndex(const T &item) const
 285         {
 286                 if (this->IsEmpty()) return 0;
 287                 for (T **ppI = this->data + 1, **ppLast = ppI + this->items; ppI <= ppLast; ppI++) {
 288                         if (*ppI == &item) {
 289                                 return ppI - this->data;
 290                         }
 291                 }
 292                 return 0;
 293         }
 294
 295         /**
 296          * Make the priority queue empty.
 297          * All remaining items will remain untouched.
 298          */
 299         inline void Clear()
 300         {
 301                 this->items = 0;
 302         }
 303 };
 304
 305 #endif /* BINARYHEAP_HPP */