OpenTTD Source  12.0-beta2
binaryheap.hpp
Go to the documentation of this file.
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 
10 #ifndef BINARYHEAP_HPP
11 #define BINARYHEAP_HPP
12 
13 #include "../core/alloc_func.hpp"
14 
16 #define BINARYHEAP_CHECK 0
17 
18 #if BINARYHEAP_CHECK
19 
20 # define CHECK_CONSISTY() this->CheckConsistency()
21 #else
22 
23 # define CHECK_CONSISTY() ;
24 #endif
25 
50 template <class T>
51 class CBinaryHeapT {
52 private:
53  uint items;
54  uint capacity;
55  T **data;
56 
57 public:
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:
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 
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 
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:
158  inline uint Length() const
159  {
160  return this->items;
161  }
162 
168  inline bool IsEmpty() const
169  {
170  return this->items == 0;
171  }
172 
178  inline bool IsFull() const
179  {
180  return this->items >= this->capacity;
181  }
182 
188  inline T *Begin()
189  {
190  assert(!this->IsEmpty());
191  return this->data[1];
192  }
193 
201  inline T *End()
202  {
203  return this->data[1 + this->items];
204  }
205 
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 
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 
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 
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 
297  inline void Clear()
298  {
299  this->items = 0;
300  }
301 };
302 
303 #endif /* BINARYHEAP_HPP */
CBinaryHeapT::HeapifyUp
uint HeapifyUp(uint gap, T *item)
Get position for fixing a gap (upwards).
Definition: binaryheap.hpp:122
CHECK_CONSISTY
#define CHECK_CONSISTY()
Don't check for consistency.
Definition: binaryheap.hpp:23
CBinaryHeapT::items
uint items
Number of items in the heap.
Definition: binaryheap.hpp:53
CBinaryHeapT::Shift
T * Shift()
Remove and return the smallest (and also first) item from the priority queue.
Definition: binaryheap.hpp:232
CBinaryHeapT::capacity
uint capacity
Maximum number of items the heap can hold.
Definition: binaryheap.hpp:54
CBinaryHeapT::data
T ** data
The pointer to the heap item pointers.
Definition: binaryheap.hpp:55
CBinaryHeapT::IsEmpty
bool IsEmpty() const
Test if the priority queue is empty.
Definition: binaryheap.hpp:168
CBinaryHeapT
Binary Heap as C++ template.
Definition: binaryheap.hpp:51
CBinaryHeapT::Clear
void Clear()
Make the priority queue empty.
Definition: binaryheap.hpp:297
CBinaryHeapT::CBinaryHeapT
CBinaryHeapT(uint max_items)
Create a binary heap.
Definition: binaryheap.hpp:62
CBinaryHeapT::HeapifyDown
uint HeapifyDown(uint gap, T *item)
Get position for fixing a gap (downwards).
Definition: binaryheap.hpp:86
CBinaryHeapT::IsFull
bool IsFull() const
Test if the priority queue is full.
Definition: binaryheap.hpp:178
CBinaryHeapT::FindIndex
uint FindIndex(const T &item) const
Search for an item in the priority queue.
Definition: binaryheap.hpp:282
CBinaryHeapT::Include
void Include(T *new_item)
Insert new item into the priority queue, maintaining heap order.
Definition: binaryheap.hpp:211
CBinaryHeapT::End
T * End()
Get the LAST item in the binary tree.
Definition: binaryheap.hpp:201
free
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:460
CBinaryHeapT::Remove
void Remove(uint index)
Remove item at given index from the priority queue.
Definition: binaryheap.hpp:254
CBinaryHeapT::Length
uint Length() const
Get the number of items stored in the priority queue.
Definition: binaryheap.hpp:158
CBinaryHeapT::Begin
T * Begin()
Get the smallest item in the binary tree.
Definition: binaryheap.hpp:188