summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authoryexo <yexo@openttd.org>2010-02-25 11:45:47 +0000
committeryexo <yexo@openttd.org>2010-02-25 11:45:47 +0000
commitcc413b8f6ef113e9fb8a4d52e96ffbf509ce923c (patch)
tree5de1d1ac5b82ae55a4f8ee027e2a89d9af3ec7fb
parentf9709a6f50044683e6c165ca9104c5e68a9bd905 (diff)
downloadopenttd-cc413b8f6ef113e9fb8a4d52e96ffbf509ce923c.tar.xz
(svn r19236) -Codechange: move method code into class definition (skidd13)
-rw-r--r--src/misc/binaryheap.hpp249
1 files changed, 121 insertions, 128 deletions
diff --git a/src/misc/binaryheap.hpp b/src/misc/binaryheap.hpp
index 073d24638..c6071853c 100644
--- a/src/misc/binaryheap.hpp
+++ b/src/misc/binaryheap.hpp
@@ -69,160 +69,153 @@ public:
/** Find the smallest item in the priority queue.
* Return the smallest item, or throw assert if empty. */
- FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];}
+ FORCEINLINE Titem_& GetHead()
+ {
+ assert(!IsEmpty());
+ return *m_items[1];
+ }
- /** Insert new item into the priority queue, maintaining heap order. */
- void Push(Titem_& new_item);
+ /** Insert new item into the priority queue, maintaining heap order.
+ * @return false if the queue is full. */
+ FORCEINLINE void Push(Titem_& new_item)
+ {
+ if (IsFull()) {
+ m_max_size *= 2;
+ m_items = ReallocT<ItemPtr>(m_items, m_max_size + 1);
+ }
+
+ /* make place for new item */
+ int gap = ++m_size;
+ /* Heapify up */
+ for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2)
+ m_items[gap] = m_items[parent];
+ m_items[gap] = &new_item;
+ CheckConsistency();
+ }
/** Remove and return the smallest item from the priority queue. */
- FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;};
+ FORCEINLINE Titem_& PopHead()
+ {
+ Titem_& ret = GetHead();
+ RemoveHead();
+ return ret;
+ }
/** Remove the smallest item from the priority queue. */
- void RemoveHead();
-
- /** Remove item specified by index */
- void RemoveByIdx(int idx);
-
- /** return index of the item that matches (using &item1 == &item2) the given item. */
- int FindLinear(const Titem_& item) const;
-
- /** Make the priority queue empty.
- * All remaining items will remain untouched. */
- void Clear() {m_size = 0;};
-
- /** verifies the heap consistency (added during first YAPF debug phase) */
- void CheckConsistency();
-};
+ FORCEINLINE void RemoveHead()
+ {
+ assert(!IsEmpty());
+ /* at index 1 we have a gap now */
+ int gap = 1;
-template <class Titem_>
-FORCEINLINE void CBinaryHeapT<Titem_>::Push(Titem_& new_item)
-{
- if (IsFull()) {
- m_max_size *= 2;
- m_items = ReallocT<ItemPtr>(m_items, m_max_size + 1);
- }
+ /* Heapify down:
+ * last item becomes a candidate for the head. Call it new_item. */
+ Titem_& new_item = *m_items[m_size--];
- /* make place for new item */
- int gap = ++m_size;
- /* Heapify up */
- for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2)
- m_items[gap] = m_items[parent];
- m_items[gap] = &new_item;
- CheckConsistency();
-}
+ /* now we must maintain relation between parent and its children:
+ * parent <= any child
+ * from head down to the tail */
+ int child = 2; // first child is at [parent * 2]
-template <class Titem_>
-FORCEINLINE void CBinaryHeapT<Titem_>::RemoveHead()
-{
- assert(!IsEmpty());
-
- /* at index 1 we have a gap now */
- int gap = 1;
-
- /* Heapify down:
- * last item becomes a candidate for the head. Call it new_item. */
- Titem_& new_item = *m_items[m_size--];
-
- /* now we must maintain relation between parent and its children:
- * parent <= any child
- * from head down to the tail */
- int child = 2; // first child is at [parent * 2]
-
- /* while children are valid */
- while (child <= m_size) {
- /* choose the smaller child */
- if (child < m_size && *m_items[child + 1] < *m_items[child])
- child++;
- /* is it smaller than our parent? */
- if (!(*m_items[child] < new_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 */
- m_items[gap] = m_items[child];
- gap = child;
- /* where do we have our new children? */
- child = gap * 2;
- }
- /* move last item to the proper place */
- if (m_size > 0) m_items[gap] = &new_item;
- CheckConsistency();
-}
-
-template <class Titem_>
-inline void CBinaryHeapT<Titem_>::RemoveByIdx(int idx)
-{
- /* at position idx we have a gap now */
- int gap = idx;
- Titem_& last = *m_items[m_size];
- if (idx < m_size) {
- assert(idx >= 1);
- m_size--;
- /* and the candidate item for fixing this gap is our last item 'last'
- * Move gap / last item up: */
- while (gap > 1)
- {
- /* compare [gap] with its parent */
- int parent = gap / 2;
- if (last < *m_items[parent]) {
- m_items[gap] = m_items[parent];
- gap = parent;
- } else {
- /* we don't need to continue upstairs */
- break;
- }
- }
-
- /* Heapify (move gap) down: */
- while (true) {
- /* where we do have our children? */
- int child = gap * 2; // first child is at [parent * 2]
- if (child > m_size) break;
+ /* while children are valid */
+ while (child <= m_size) {
/* choose the smaller child */
if (child < m_size && *m_items[child + 1] < *m_items[child])
child++;
/* is it smaller than our parent? */
- if (!(*m_items[child] < last)) {
+ if (!(*m_items[child] < new_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 */
m_items[gap] = m_items[child];
gap = child;
+ /* where do we have our new children? */
+ child = gap * 2;
}
- /* move parent to the proper place */
- if (m_size > 0) m_items[gap] = &last;
- } else {
- assert(idx == m_size);
- m_size--;
+ /* move last item to the proper place */
+ if (m_size > 0) m_items[gap] = &new_item;
+ CheckConsistency();
}
- CheckConsistency();
-}
-template <class Titem_>
-inline int CBinaryHeapT<Titem_>::FindLinear(const Titem_& item) const
-{
- if (IsEmpty()) return 0;
- for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) {
- if (*ppI == &item) {
- return ppI - m_items;
+ /** Remove item specified by index */
+ FORCEINLINE void RemoveByIdx(int idx)
+ {
+ /* at position idx we have a gap now */
+ int gap = idx;
+ Titem_& last = *m_items[m_size];
+ if (idx < m_size) {
+ assert(idx >= 1);
+ m_size--;
+ /* and the candidate item for fixing this gap is our last item 'last'
+ * Move gap / last item up: */
+ while (gap > 1)
+ {
+ /* compare [gap] with its parent */
+ int parent = gap / 2;
+ if (last < *m_items[parent]) {
+ m_items[gap] = m_items[parent];
+ gap = parent;
+ } else {
+ /* we don't need to continue upstairs */
+ break;
+ }
+ }
+
+ /* Heapify (move gap) down: */
+ while (true) {
+ /* where we do have our children? */
+ int child = gap * 2; // first child is at [parent * 2]
+ if (child > m_size) break;
+ /* choose the smaller child */
+ if (child < m_size && *m_items[child + 1] < *m_items[child])
+ child++;
+ /* is it smaller than our parent? */
+ if (!(*m_items[child] < last)) {
+ /* 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 */
+ m_items[gap] = m_items[child];
+ gap = child;
+ }
+ /* move parent to the proper place */
+ if (m_size > 0) m_items[gap] = &last;
+ } else {
+ assert(idx == m_size);
+ m_size--;
}
+ CheckConsistency();
}
- return 0;
-}
-template <class Titem_>
-FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency()
-{
- /* enable it if you suspect binary heap doesn't work well */
-#if 0
- for (int child = 2; child <= m_size; child++) {
- int parent = child / 2;
- assert(!(*m_items[child] < *m_items[parent]));
+ /** return index of the item that matches (using &item1 == &item2) the given item. */
+ FORCEINLINE int FindLinear(const Titem_& item) const
+ {
+ if (IsEmpty()) return 0;
+ for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) {
+ if (*ppI == &item) {
+ return ppI - m_items;
+ }
+ }
+ return 0;
}
-#endif
-}
+ /** Make the priority queue empty.
+ * All remaining items will remain untouched. */
+ FORCEINLINE void Clear() {m_size = 0;}
+
+ /** verifies the heap consistency (added during first YAPF debug phase) */
+ FORCEINLINE void CheckConsistency()
+ {
+ /* enable it if you suspect binary heap doesn't work well */
+#if 0
+ for (int child = 2; child <= m_size; child++) {
+ int parent = child / 2;
+ assert(!(*m_items[child] < *m_items[parent]));
+ }
+#endif
+ }
+};
#endif /* BINARYHEAP_HPP */