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