src/misc/binaryheap.hpp

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