1

/* $Id$ */

     2

     3

/** @file binaryheap.hpp Binary heap implementation. */

     4

     5

#ifndef  BINARYHEAP_HPP

     6

#define  BINARYHEAP_HPP

     7

     8

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

     9

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

    10

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

    11

#endif

    12

    13

    14

/**

    15

 * Binary Heap as C++ template.

    16

 *

    17

 * For information about Binary Heap algotithm,

    18

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

    19

 *

    20

 * Implementation specific notes:

    21

 *

    22

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

    23

 *

    24

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

    25

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

    26

 *

    27

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

    28

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

    29

 *

    30

 */

    31

    32

template <class Titem_>

    33

class CBinaryHeapT {

    34

public:

    35

	typedef Titem_ *ItemPtr;

    36

private:

    37

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

    38

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

    39

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

    40

    41

public:

    42

	explicit CBinaryHeapT(int max_items = 102400)

    43

		: m_size(0)

    44

		, m_max_size(max_items)

    45

	{

    46

		m_items = new ItemPtr[max_items + 1];

    47

	}

    48

    49

	~CBinaryHeapT()

    50

	{

    51

		Clear();

    52

		delete [] m_items;

    53

		m_items = NULL;

    54

	}

    55

    56

public:

    57

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

    58

	 *  @return number of items in the queue */

    59

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

    60

    61

	/** Test if the priority queue is empty.

    62

	 *  @return true if empty */

    63

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

    64

    65

	/** Test if the priority queue is full.

    66

	 *  @return true if full. */

    67

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

    68

    69

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

    70

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

    71

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

    72

    73

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

    74

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

    75

	bool Push(Titem_& new_item);

    76

    77

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

    78

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

    79

    80

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

    81

	void RemoveHead();

    82

    83

	/** Remove item specified by index */

    84

	void RemoveByIdx(int idx);

    85

    86

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

    87

	int FindLinear(const Titem_& item) const;

    88

    89

	/** Make the priority queue empty.

    90

	 * All remaining items will remain untouched. */

    91

	void Clear() {m_size = 0;};

    92

    93

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

    94

	void CheckConsistency();

    95

};

    96

    97

    98

template <class Titem_>

    99

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

   100

{

   101

	if (IsFull()) return false;

   102

   103

	// make place for new item

   104

	int gap = ++m_size;

   105

	// Heapify up

   106

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

   107

		m_items[gap] = m_items[parent];

   108

	m_items[gap] = &new_item;

   109

	CheckConsistency();

   110

	return true;

   111

}

   112

   113

template <class Titem_>

   114

FORCEINLINE void CBinaryHeapT<Titem_>::RemoveHead()

   115

{

   116

	assert(!IsEmpty());

   117

   118

	// at index 1 we have a gap now

   119

	int gap = 1;

   120

   121

	// Heapify down:

   122

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

   123

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

   124

   125

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

   126

	//   parent <= any child

   127

	// from head down to the tail

   128

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

   129

   130

	// while children are valid

   131

	while (child <= m_size) {

   132

		// choose the smaller child

   133

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

   134

			child++;

   135

		// is it smaller than our parent?

   136

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

   137

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

   138

			break;

   139

		}

   140

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

   141

		m_items[gap] = m_items[child];

   142

		gap = child;

   143

		// where do we have our new children?

   144

		child = gap * 2;

   145

	}

   146

	// move last item to the proper place

   147

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

   148

	CheckConsistency();

   149

}

   150

   151

template <class Titem_>

   152

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

   153

{

   154

	// at position idx we have a gap now

   155

	int gap = idx;

   156

	Titem_& last = *m_items[m_size];

   157

	if (idx < m_size) {

   158

		assert(idx >= 1);

   159

		m_size--;

   160

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

   161

		// Move gap / last item up:

   162

		while (gap > 1)

   163

		{

   164

			// compare [gap] with its parent

   165

			int parent = gap / 2;

   166

			if (last < *m_items[parent]) {

   167

				m_items[gap] = m_items[parent];

   168

				gap = parent;

   169

			} else {

   170

				// we don't need to continue upstairs

   171

				break;

   172

			}

   173

		}

   174

   175

		// Heapify (move gap) down:

   176

		while (true) {

   177

			// where we do have our children?

   178

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

   179

			if (child > m_size) break;

   180

			// choose the smaller child

   181

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

   182

				child++;

   183

			// is it smaller than our parent?

   184

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

   185

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

   186

				break;

   187

			}

   188

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

   189

			m_items[gap] = m_items[child];

   190

			gap = child;

   191

		}

   192

		// move parent to the proper place

   193

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

   194

	}

   195

	else {

   196

		assert(idx == m_size);

   197

		m_size--;

   198

	}

   199

	CheckConsistency();

   200

}

   201

   202

template <class Titem_>

   203

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

   204

{

   205

	if (IsEmpty()) return 0;

   206

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

   207

		if (*ppI == &item) {

   208

			return ppI - m_items;

   209

		}

   210

	}

   211

	return 0;

   212

}

   213

   214

template <class Titem_>

   215

FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency()

   216

{

   217

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

   218

#if 0

   219

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

   220

		int parent = child / 2;

   221

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

   222

	}

   223

#endif

   224

}

   225

   226

   227

#endif /* BINARYHEAP_HPP */