(svn r19236) -Codechange: move method code into class definition (skidd13)

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 */