1

/* $Id$ */

     2

     3

#ifndef  BINARYHEAP_HPP

     4

#define  BINARYHEAP_HPP

     5

     6

//void* operator new (size_t size, void* p) {return p;}

     7

#if defined(_MSC_VER) && (_MSC_VER >= 1400)

     8

//void operator delete (void* p, void* p2) {}

     9

#endif

    10

    11

    12

/**

    13

 * Binary Heap as C++ template.

    14

 *

    15

 * For information about Binary Heap algotithm,

    16

 *   see: http://www.policyalmanac.org/games/binaryHeaps.htm

    17

 *

    18

 * Implementation specific notes:

    19

 *

    20

 * 1) It allocates space for item pointers (array). Items are allocated elsewhere.

    21

 *

    22

 * 2) ItemPtr [0] is never used. Total array size is max_items + 1, because we

    23

 *    use indices 1..max_items instead of zero based C indexing.

    24

 *

    25

 * 3) Item of the binary heap should support these public members:

    26

 *    - 'lower-then' operator '<' - used for comparing items before moving

    27

 *

    28

 */

    29

    30

template <class Titem_>

    31

class CBinaryHeapT {

    32

public:

    33

	typedef Titem_ *ItemPtr;

    34

private:

    35

	int                     m_size;     ///< Number of items in the heap

    36

	int                     m_max_size; ///< Maximum number of items the heap can hold

    37

	ItemPtr*                m_items;    ///< The heap item pointers

    38

    39

public:

    40

	explicit CBinaryHeapT(int max_items = 102400)

    41

		: m_size(0)

    42

		, m_max_size(max_items)

    43

	{

    44

		m_items = new ItemPtr[max_items + 1];

    45

	}

    46

    47

	~CBinaryHeapT()

    48

	{

    49

		Clear();

    50

		delete [] m_items;

    51

		m_items = NULL;

    52

	}

    53

    54

public:

    55

	/** Return the number of items stored in the priority queue.

    56

	 *  @return number of items in the queue */

    57

	FORCEINLINE int Size() const {return m_size;};

    58

    59

	/** Test if the priority queue is empty.

    60

	 *  @return true if empty */

    61

	FORCEINLINE bool IsEmpty() const {return (m_size == 0);};

    62

    63

	/** Test if the priority queue is full.

    64

	 *  @return true if full. */

    65

	FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);};

    66

    67

	/** Find the smallest item in the priority queue.

    68

	 *  Return the smallest item, or throw assert if empty. */

    69

	FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];}

    70

    71

	/** Insert new item into the priority queue, maintaining heap order.

    72

	 *  @return false if the queue is full. */

    73

	bool Push(Titem_& new_item);

    74

    75

	/** Remove and return the smallest item from the priority queue. */

    76

	FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;};

    77

    78

	/** Remove the smallest item from the priority queue. */

    79

	void RemoveHead();

    80

    81

	/** Remove item specified by index */

    82

	void RemoveByIdx(int idx);

    83

    84

	/** return index of the item that matches (using &item1 == &item2) the given item. */

    85

	int FindLinear(const Titem_& item) const;

    86

    87

	/** Make the priority queue empty.

    88

	 * All remaining items will remain untouched. */

    89

	void Clear() {m_size = 0;};

    90

    91

	/** verifies the heap consistency (added during first YAPF debug phase) */

    92

	void CheckConsistency();

    93

};

    94

    95

    96

template <class Titem_>

    97

FORCEINLINE bool CBinaryHeapT<Titem_>::Push(Titem_& new_item)

    98

{

    99

	if (IsFull()) return false;

   100

   101

	// make place for new item

   102

	int gap = ++m_size;

   103

	// Heapify up

   104

	for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2)

   105

		m_items[gap] = m_items[parent];

   106

	m_items[gap] = &new_item;

   107

	CheckConsistency();

   108

	return true;

   109

}

   110

   111

template <class Titem_>

   112

FORCEINLINE void CBinaryHeapT<Titem_>::RemoveHead()

   113

{

   114

	assert(!IsEmpty());

   115

   116

	// at index 1 we have a gap now

   117

	int gap = 1;

   118

   119

	// Heapify down:

   120

	//   last item becomes a candidate for the head. Call it new_item.

   121

	Titem_& new_item = *m_items[m_size--];

   122

   123

	// now we must maintain relation between parent and its children:

   124

	//   parent <= any child

   125

	// from head down to the tail

   126

	int child  = 2; // first child is at [parent * 2]

   127

   128

	// while children are valid

   129

	while (child <= m_size) {

   130

		// choose the smaller child

   131

		if (child < m_size && *m_items[child + 1] < *m_items[child])

   132

			child++;

   133

		// is it smaller than our parent?

   134

		if (!(*m_items[child] < new_item)) {

   135

			// the smaller child is still bigger or same as parent => we are done

   136

			break;

   137

		}

   138

		// if smaller child is smaller than parent, it will become new parent

   139

		m_items[gap] = m_items[child];

   140

		gap = child;

   141

		// where do we have our new children?

   142

		child = gap * 2;

   143

	}

   144

	// move last item to the proper place

   145

	if (m_size > 0) m_items[gap] = &new_item;

   146

	CheckConsistency();

   147

}

   148

   149

template <class Titem_>

   150

inline void CBinaryHeapT<Titem_>::RemoveByIdx(int idx)

   151

{

   152

	// at position idx we have a gap now

   153

	int gap = idx;

   154

	Titem_& last = *m_items[m_size];

   155

	if (idx < m_size) {

   156

		assert(idx >= 1);

   157

		m_size--;

   158

		// and the candidate item for fixing this gap is our last item 'last'

   159

		// Move gap / last item up:

   160

		while (gap > 1)

   161

		{

   162

			// compare [gap] with its parent

   163

			int parent = gap / 2;

   164

			if (last < *m_items[parent]) {

   165

				m_items[gap] = m_items[parent];

   166

				gap = parent;

   167

			} else {

   168

				// we don't need to continue upstairs

   169

				break;

   170

			}

   171

		}

   172

   173

		// Heapify (move gap) down:

   174

		while (true) {

   175

			// where we do have our children?

   176

			int child  = gap * 2; // first child is at [parent * 2]

   177

			if (child > m_size) break;

   178

			// choose the smaller child

   179

			if (child < m_size && *m_items[child + 1] < *m_items[child])

   180

				child++;

   181

			// is it smaller than our parent?

   182

			if (!(*m_items[child] < last)) {

   183

				// the smaller child is still bigger or same as parent => we are done

   184

				break;

   185

			}

   186

			// if smaller child is smaller than parent, it will become new parent

   187

			m_items[gap] = m_items[child];

   188

			gap = child;

   189

		}

   190

		// move parent to the proper place

   191

		if (m_size > 0) m_items[gap] = &last;

   192

	}

   193

	else {

   194

		assert(idx == m_size);

   195

		m_size--;

   196

	}

   197

	CheckConsistency();

   198

}

   199

   200

template <class Titem_>

   201

inline int CBinaryHeapT<Titem_>::FindLinear(const Titem_& item) const

   202

{

   203

	if (IsEmpty()) return 0;

   204

	for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) {

   205

		if (*ppI == &item) {

   206

			return ppI - m_items;

   207

		}

   208

	}

   209

	return 0;

   210

}

   211

   212

template <class Titem_>

   213

FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency()

   214

{

   215

	// enable it if you suspect binary heap doesn't work well

   216

#if 0

   217

	for (int child = 2; child <= m_size; child++) {

   218

		int parent = child / 2;

   219

		assert(!(m_items[child] < m_items[parent]));

   220

	}

   221

#endif

   222

}

   223

   224

   225

#endif /* BINARYHEAP_HPP */