KUDr@5633: /* $Id$ */
KUDr@5633: 
belugas@6481: /** @file binaryheap.hpp */
belugas@6481: 
KUDr@5633: #ifndef  BINARYHEAP_HPP
KUDr@5633: #define  BINARYHEAP_HPP
KUDr@5633: 
KUDr@5633: //void* operator new (size_t size, void* p) {return p;}
KUDr@5633: #if defined(_MSC_VER) && (_MSC_VER >= 1400)
KUDr@5633: //void operator delete (void* p, void* p2) {}
KUDr@5633: #endif
KUDr@5633: 
KUDr@5633: 
KUDr@5633: /**
KUDr@5633:  * Binary Heap as C++ template.
KUDr@5633:  *
KUDr@5633:  * For information about Binary Heap algotithm,
KUDr@5633:  *   see: http://www.policyalmanac.org/games/binaryHeaps.htm
KUDr@5633:  *
KUDr@5633:  * Implementation specific notes:
KUDr@5633:  *
KUDr@5633:  * 1) It allocates space for item pointers (array). Items are allocated elsewhere.
KUDr@5633:  *
KUDr@5633:  * 2) ItemPtr [0] is never used. Total array size is max_items + 1, because we
KUDr@5633:  *    use indices 1..max_items instead of zero based C indexing.
KUDr@5633:  *
KUDr@5633:  * 3) Item of the binary heap should support these public members:
KUDr@5633:  *    - 'lower-then' operator '<' - used for comparing items before moving
KUDr@5633:  *
KUDr@5633:  */
KUDr@5633: 
KUDr@5633: template <class Titem_>
KUDr@5633: class CBinaryHeapT {
KUDr@5633: public:
KUDr@5633: 	typedef Titem_ *ItemPtr;
KUDr@5633: private:
KUDr@5633: 	int                     m_size;     ///< Number of items in the heap
KUDr@5633: 	int                     m_max_size; ///< Maximum number of items the heap can hold
KUDr@5633: 	ItemPtr*                m_items;    ///< The heap item pointers
KUDr@5633: 
KUDr@5633: public:
KUDr@5633: 	explicit CBinaryHeapT(int max_items = 102400)
KUDr@5633: 		: m_size(0)
KUDr@5633: 		, m_max_size(max_items)
KUDr@5633: 	{
KUDr@5633: 		m_items = new ItemPtr[max_items + 1];
KUDr@5633: 	}
KUDr@5633: 
KUDr@5633: 	~CBinaryHeapT()
KUDr@5633: 	{
KUDr@5633: 		Clear();
KUDr@5633: 		delete [] m_items;
KUDr@5633: 		m_items = NULL;
KUDr@5633: 	}
KUDr@5633: 
KUDr@5633: public:
KUDr@5633: 	/** Return the number of items stored in the priority queue.
KUDr@5633: 	 *  @return number of items in the queue */
KUDr@5633: 	FORCEINLINE int Size() const {return m_size;};
KUDr@5633: 
KUDr@5633: 	/** Test if the priority queue is empty.
KUDr@5633: 	 *  @return true if empty */
KUDr@5633: 	FORCEINLINE bool IsEmpty() const {return (m_size == 0);};
KUDr@5633: 
KUDr@5633: 	/** Test if the priority queue is full.
KUDr@5633: 	 *  @return true if full. */
KUDr@5633: 	FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);};
KUDr@5633: 
KUDr@5633: 	/** Find the smallest item in the priority queue.
KUDr@5633: 	 *  Return the smallest item, or throw assert if empty. */
KUDr@5633: 	FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];}
KUDr@5633: 
KUDr@5633: 	/** Insert new item into the priority queue, maintaining heap order.
KUDr@5633: 	 *  @return false if the queue is full. */
KUDr@5633: 	bool Push(Titem_& new_item);
KUDr@5633: 
KUDr@5633: 	/** Remove and return the smallest item from the priority queue. */
KUDr@5633: 	FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;};
KUDr@5633: 
KUDr@5633: 	/** Remove the smallest item from the priority queue. */
KUDr@5633: 	void RemoveHead();
KUDr@5633: 
KUDr@5633: 	/** Remove item specified by index */
KUDr@5633: 	void RemoveByIdx(int idx);
KUDr@5633: 
KUDr@5633: 	/** return index of the item that matches (using &item1 == &item2) the given item. */
KUDr@5633: 	int FindLinear(const Titem_& item) const;
KUDr@5633: 
KUDr@5633: 	/** Make the priority queue empty.
KUDr@5633: 	 * All remaining items will remain untouched. */
KUDr@5633: 	void Clear() {m_size = 0;};
KUDr@5633: 
KUDr@5633: 	/** verifies the heap consistency (added during first YAPF debug phase) */
KUDr@5633: 	void CheckConsistency();
KUDr@5633: };
KUDr@5633: 
KUDr@5633: 
KUDr@5633: template <class Titem_>
KUDr@5633: FORCEINLINE bool CBinaryHeapT<Titem_>::Push(Titem_& new_item)
KUDr@5633: {
KUDr@5633: 	if (IsFull()) return false;
KUDr@5633: 
KUDr@5633: 	// make place for new item
KUDr@5633: 	int gap = ++m_size;
KUDr@5633: 	// Heapify up
KUDr@5633: 	for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2)
KUDr@5633: 		m_items[gap] = m_items[parent];
KUDr@5633: 	m_items[gap] = &new_item;
KUDr@5633: 	CheckConsistency();
KUDr@5633: 	return true;
KUDr@5633: }
KUDr@5633: 
KUDr@5633: template <class Titem_>
KUDr@5633: FORCEINLINE void CBinaryHeapT<Titem_>::RemoveHead()
KUDr@5633: {
KUDr@5633: 	assert(!IsEmpty());
KUDr@5633: 
KUDr@5633: 	// at index 1 we have a gap now
KUDr@5633: 	int gap = 1;
KUDr@5633: 
KUDr@5633: 	// Heapify down:
KUDr@5633: 	//   last item becomes a candidate for the head. Call it new_item.
KUDr@5633: 	Titem_& new_item = *m_items[m_size--];
KUDr@5633: 
KUDr@5633: 	// now we must maintain relation between parent and its children:
KUDr@5633: 	//   parent <= any child
KUDr@5633: 	// from head down to the tail
KUDr@5633: 	int child  = 2; // first child is at [parent * 2]
KUDr@5633: 
KUDr@5633: 	// while children are valid
KUDr@5633: 	while (child <= m_size) {
KUDr@5633: 		// choose the smaller child
KUDr@5633: 		if (child < m_size && *m_items[child + 1] < *m_items[child])
KUDr@5633: 			child++;
KUDr@5633: 		// is it smaller than our parent?
KUDr@5633: 		if (!(*m_items[child] < new_item)) {
KUDr@5633: 			// the smaller child is still bigger or same as parent => we are done
KUDr@5633: 			break;
KUDr@5633: 		}
KUDr@5633: 		// if smaller child is smaller than parent, it will become new parent
KUDr@5633: 		m_items[gap] = m_items[child];
KUDr@5633: 		gap = child;
KUDr@5633: 		// where do we have our new children?
KUDr@5633: 		child = gap * 2;
KUDr@5633: 	}
KUDr@5633: 	// move last item to the proper place
KUDr@5633: 	if (m_size > 0) m_items[gap] = &new_item;
KUDr@5633: 	CheckConsistency();
KUDr@5633: }
KUDr@5633: 
KUDr@5633: template <class Titem_>
KUDr@5633: inline void CBinaryHeapT<Titem_>::RemoveByIdx(int idx)
KUDr@5633: {
KUDr@5633: 	// at position idx we have a gap now
KUDr@5633: 	int gap = idx;
KUDr@5633: 	Titem_& last = *m_items[m_size];
KUDr@5633: 	if (idx < m_size) {
KUDr@5633: 		assert(idx >= 1);
KUDr@5633: 		m_size--;
KUDr@5633: 		// and the candidate item for fixing this gap is our last item 'last'
KUDr@5633: 		// Move gap / last item up:
KUDr@5633: 		while (gap > 1)
KUDr@5633: 		{
KUDr@5633: 			// compare [gap] with its parent
KUDr@5633: 			int parent = gap / 2;
KUDr@5633: 			if (last < *m_items[parent]) {
KUDr@5633: 				m_items[gap] = m_items[parent];
KUDr@5633: 				gap = parent;
KUDr@5633: 			} else {
KUDr@5633: 				// we don't need to continue upstairs
KUDr@5633: 				break;
KUDr@5633: 			}
KUDr@5633: 		}
KUDr@5633: 
KUDr@5633: 		// Heapify (move gap) down:
KUDr@5633: 		while (true) {
KUDr@5633: 			// where we do have our children?
KUDr@5633: 			int child  = gap * 2; // first child is at [parent * 2]
KUDr@5633: 			if (child > m_size) break;
KUDr@5633: 			// choose the smaller child
KUDr@5633: 			if (child < m_size && *m_items[child + 1] < *m_items[child])
KUDr@5633: 				child++;
KUDr@5633: 			// is it smaller than our parent?
KUDr@5633: 			if (!(*m_items[child] < last)) {
KUDr@5633: 				// the smaller child is still bigger or same as parent => we are done
KUDr@5633: 				break;
KUDr@5633: 			}
KUDr@5633: 			// if smaller child is smaller than parent, it will become new parent
KUDr@5633: 			m_items[gap] = m_items[child];
KUDr@5633: 			gap = child;
KUDr@5633: 		}
KUDr@5633: 		// move parent to the proper place
KUDr@5633: 		if (m_size > 0) m_items[gap] = &last;
KUDr@5633: 	}
KUDr@5633: 	else {
KUDr@5633: 		assert(idx == m_size);
KUDr@5633: 		m_size--;
KUDr@5633: 	}
KUDr@5633: 	CheckConsistency();
KUDr@5633: }
KUDr@5633: 
KUDr@5633: template <class Titem_>
KUDr@5633: inline int CBinaryHeapT<Titem_>::FindLinear(const Titem_& item) const
KUDr@5633: {
KUDr@5633: 	if (IsEmpty()) return 0;
KUDr@5633: 	for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) {
KUDr@5633: 		if (*ppI == &item) {
KUDr@5633: 			return ppI - m_items;
KUDr@5633: 		}
KUDr@5633: 	}
KUDr@5633: 	return 0;
KUDr@5633: }
KUDr@5633: 
KUDr@5633: template <class Titem_>
KUDr@5633: FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency()
KUDr@5633: {
KUDr@5633: 	// enable it if you suspect binary heap doesn't work well
KUDr@5633: #if 0
KUDr@5633: 	for (int child = 2; child <= m_size; child++) {
KUDr@5633: 		int parent = child / 2;
KUDr@5633: 		assert(!(m_items[child] < m_items[parent]));
KUDr@5633: 	}
KUDr@5633: #endif
KUDr@5633: }
KUDr@5633: 
KUDr@5633: 
KUDr@5633: #endif /* BINARYHEAP_HPP */