src/misc/binaryheap.hpp

   1 /* $Id$ */
   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 = NULL;
  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 { return this->items; }
 161
 162         /**
 163          * Test if the priority queue is empty.
 164          *
 165          * @return True if empty
 166          */
 167         inline bool IsEmpty() const { return this->items == 0; }
 168
 169         /**
 170          * Test if the priority queue is full.
 171          *
 172          * @return True if full.
 173          */
 174         inline bool IsFull() const { return this->items >= this->capacity; }
 175
 176         /**
 177          * Get the smallest item in the binary tree.
 178          *
 179          * @return The smallest item, or throw assert if empty.
 180          */
 181         inline T *Begin()
 182         {
 183                 assert(!this->IsEmpty());
 184                 return this->data[1];
 185         }
 186
 187         /**
 188          * Get the LAST item in the binary tree.
 189          *
 190          * @note The last item is not necessary the biggest!
 191          *
 192          * @return The last item
 193          */
 194         inline T *End()
 195         {
 196                 return this->data[1 + this->items];
 197         }
 198
 199         /**
 200          * Insert new item into the priority queue, maintaining heap order.
 201          *
 202          * @param new_item The pointer to the new item
 203          */
 204         inline void Include(T *new_item)
 205         {
 206                 if (this->IsFull()) {
 207                         assert(this->capacity < UINT_MAX / 2);
 208
 209                         this->capacity *= 2;
 210                         this->data = ReallocT<T*>(this->data, this->capacity + 1);
 211                 }
 212
 213                 /* Make place for new item. A gap is now at the end of the tree. */
 214                 uint gap = this->HeapifyUp(++items, new_item);
 215                 this->data[gap] = new_item;
 216                 CHECK_CONSISTY();
 217         }
 218
 219         /**
 220          * Remove and return the smallest (and also first) item
 221          *  from the priority queue.
 222          *
 223          * @return The pointer to the removed item
 224          */
 225         inline T *Shift()
 226         {
 227                 assert(!this->IsEmpty());
 228
 229                 T *first = this->Begin();
 230
 231                 this->items--;
 232                 /* at index 1 we have a gap now */
 233                 T *last = this->End();
 234                 uint gap = this->HeapifyDown(1, last);
 235                 /* move last item to the proper place */
 236                 if (!this->IsEmpty()) this->data[gap] = last;
 237
 238                 CHECK_CONSISTY();
 239                 return first;
 240         }
 241
 242         /**
 243          * Remove item at given index from the priority queue.
 244          *
 245          * @param index The position of the item in the heap
 246          */
 247         inline void Remove(uint index)
 248         {
 249                 if (index < this->items) {
 250                         assert(index != 0);
 251                         this->items--;
 252                         /* at position index we have a gap now */
 253
 254                         T *last = this->End();
 255                         /* Fix binary tree up and downwards */
 256                         uint gap = this->HeapifyUp(index, last);
 257                         gap = this->HeapifyDown(gap, last);
 258                         /* move last item to the proper place */
 259                         if (!this->IsEmpty()) this->data[gap] = last;
 260                 } else {
 261                         assert(index == this->items);
 262                         this->items--;
 263                 }
 264                 CHECK_CONSISTY();
 265         }
 266
 267         /**
 268          * Search for an item in the priority queue.
 269          *  Matching is done by comparing address of the
 270          *  item.
 271          *
 272          * @param item The reference to the item
 273          * @return The index of the item or zero if not found
 274          */
 275         inline uint FindIndex(const T &item) const
 276         {
 277                 if (this->IsEmpty()) return 0;
 278                 for (T **ppI = this->data + 1, **ppLast = ppI + this->items; ppI <= ppLast; ppI++) {
 279                         if (*ppI == &item) {
 280                                 return ppI - this->data;
 281                         }
 282                 }
 283                 return 0;
 284         }
 285
 286         /**
 287          * Make the priority queue empty.
 288          * All remaining items will remain untouched.
 289          */
 290         inline void Clear() { this->items = 0; }
 291 };
 292
 293 #endif /* BINARYHEAP_HPP */