8 //void operator delete (void* p, void* p2) {} |
8 //void operator delete (void* p, void* p2) {} |
9 #endif |
9 #endif |
10 |
10 |
11 |
11 |
12 /** |
12 /** |
13 * Binary Heap as C++ template. |
13 * Binary Heap as C++ template. |
14 * |
14 * |
15 * For information about Binary Heap algotithm, |
15 * For information about Binary Heap algotithm, |
16 * see: http://www.policyalmanac.org/games/binaryHeaps.htm |
16 * see: http://www.policyalmanac.org/games/binaryHeaps.htm |
17 * |
17 * |
18 * Implementation specific notes: |
18 * Implementation specific notes: |
19 * |
19 * |
20 * 1) It allocates space for item pointers (array). Items are allocated elsewhere. |
20 * 1) It allocates space for item pointers (array). Items are allocated elsewhere. |
21 * |
21 * |
22 * 2) ItemPtr [0] is never used. Total array size is max_items + 1, because we |
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. |
23 * use indices 1..max_items instead of zero based C indexing. |
24 * |
24 * |
25 * 3) Item of the binary heap should support these public members: |
25 * 3) Item of the binary heap should support these public members: |
26 * - 'lower-then' operator '<' - used for comparing items before moving |
26 * - 'lower-then' operator '<' - used for comparing items before moving |
27 * |
27 * |
28 */ |
28 */ |
29 |
29 |
30 template <class Titem_> |
30 template <class Titem_> |
31 class CBinaryHeapT { |
31 class CBinaryHeapT { |
32 public: |
32 public: |
33 typedef Titem_ *ItemPtr; |
33 typedef Titem_ *ItemPtr; |
51 m_items = NULL; |
51 m_items = NULL; |
52 } |
52 } |
53 |
53 |
54 public: |
54 public: |
55 /** Return the number of items stored in the priority queue. |
55 /** Return the number of items stored in the priority queue. |
56 * @return number of items in the queue */ |
56 * @return number of items in the queue */ |
57 FORCEINLINE int Size() const {return m_size;}; |
57 FORCEINLINE int Size() const {return m_size;}; |
58 |
58 |
59 /** Test if the priority queue is empty. |
59 /** Test if the priority queue is empty. |
60 * @return true if empty */ |
60 * @return true if empty */ |
61 FORCEINLINE bool IsEmpty() const {return (m_size == 0);}; |
61 FORCEINLINE bool IsEmpty() const {return (m_size == 0);}; |
62 |
62 |
63 /** Test if the priority queue is full. |
63 /** Test if the priority queue is full. |
64 * @return true if full. */ |
64 * @return true if full. */ |
65 FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);}; |
65 FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);}; |
66 |
66 |
67 /** Find the smallest item in the priority queue. |
67 /** Find the smallest item in the priority queue. |
68 * Return the smallest item, or throw assert if empty. */ |
68 * Return the smallest item, or throw assert if empty. */ |
69 FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];} |
69 FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];} |
70 |
70 |
71 /** Insert new item into the priority queue, maintaining heap order. |
71 /** Insert new item into the priority queue, maintaining heap order. |
72 * @return false if the queue is full. */ |
72 * @return false if the queue is full. */ |
73 bool Push(Titem_& new_item); |
73 bool Push(Titem_& new_item); |
74 |
74 |
75 /** Remove and return the smallest item from the priority queue. */ |
75 /** Remove and return the smallest item from the priority queue. */ |
76 FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;}; |
76 FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;}; |
77 |
77 |
83 |
83 |
84 /** return index of the item that matches (using &item1 == &item2) the given item. */ |
84 /** return index of the item that matches (using &item1 == &item2) the given item. */ |
85 int FindLinear(const Titem_& item) const; |
85 int FindLinear(const Titem_& item) const; |
86 |
86 |
87 /** Make the priority queue empty. |
87 /** Make the priority queue empty. |
88 * All remaining items will remain untouched. */ |
88 * All remaining items will remain untouched. */ |
89 void Clear() {m_size = 0;}; |
89 void Clear() {m_size = 0;}; |
90 |
90 |
91 /** verifies the heap consistency (added during first YAPF debug phase) */ |
91 /** verifies the heap consistency (added during first YAPF debug phase) */ |
92 void CheckConsistency(); |
92 void CheckConsistency(); |
93 }; |
93 }; |