author | peter1138 |
Tue, 22 Jan 2008 07:27:06 +0000 | |
changeset 8374 | 7a1b6c89cb89 |
parent 6481 | 85ad87daf4b0 |
child 9111 | 48ce04029fe4 |
permissions | -rw-r--r-- |
5633
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
1 |
/* $Id$ */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
2 |
|
6481
85ad87daf4b0
(svn r9662) -Documentation: Doxygen corrections and @file omissions
belugas
parents:
5633
diff
changeset
|
3 |
/** @file binaryheap.hpp */ |
85ad87daf4b0
(svn r9662) -Documentation: Doxygen corrections and @file omissions
belugas
parents:
5633
diff
changeset
|
4 |
|
5633
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
5 |
#ifndef BINARYHEAP_HPP |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
6 |
#define BINARYHEAP_HPP |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
7 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
8 |
//void* operator new (size_t size, void* p) {return p;} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
9 |
#if defined(_MSC_VER) && (_MSC_VER >= 1400) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
10 |
//void operator delete (void* p, void* p2) {} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
11 |
#endif |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
12 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
13 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
14 |
/** |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
15 |
* Binary Heap as C++ template. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
16 |
* |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
17 |
* For information about Binary Heap algotithm, |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
18 |
* see: http://www.policyalmanac.org/games/binaryHeaps.htm |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
19 |
* |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
20 |
* Implementation specific notes: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
21 |
* |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
22 |
* 1) It allocates space for item pointers (array). Items are allocated elsewhere. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
23 |
* |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
24 |
* 2) ItemPtr [0] is never used. Total array size is max_items + 1, because we |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
25 |
* use indices 1..max_items instead of zero based C indexing. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
26 |
* |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
27 |
* 3) Item of the binary heap should support these public members: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
28 |
* - 'lower-then' operator '<' - used for comparing items before moving |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
29 |
* |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
30 |
*/ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
31 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
32 |
template <class Titem_> |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
33 |
class CBinaryHeapT { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
34 |
public: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
35 |
typedef Titem_ *ItemPtr; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
36 |
private: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
37 |
int m_size; ///< Number of items in the heap |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
38 |
int m_max_size; ///< Maximum number of items the heap can hold |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
39 |
ItemPtr* m_items; ///< The heap item pointers |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
40 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
41 |
public: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
42 |
explicit CBinaryHeapT(int max_items = 102400) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
43 |
: m_size(0) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
44 |
, m_max_size(max_items) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
45 |
{ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
46 |
m_items = new ItemPtr[max_items + 1]; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
47 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
48 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
49 |
~CBinaryHeapT() |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
50 |
{ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
51 |
Clear(); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
52 |
delete [] m_items; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
53 |
m_items = NULL; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
54 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
55 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
56 |
public: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
57 |
/** Return the number of items stored in the priority queue. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
58 |
* @return number of items in the queue */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
59 |
FORCEINLINE int Size() const {return m_size;}; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
60 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
61 |
/** Test if the priority queue is empty. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
62 |
* @return true if empty */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
63 |
FORCEINLINE bool IsEmpty() const {return (m_size == 0);}; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
64 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
65 |
/** Test if the priority queue is full. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
66 |
* @return true if full. */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
67 |
FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);}; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
68 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
69 |
/** Find the smallest item in the priority queue. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
70 |
* Return the smallest item, or throw assert if empty. */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
71 |
FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
72 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
73 |
/** Insert new item into the priority queue, maintaining heap order. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
74 |
* @return false if the queue is full. */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
75 |
bool Push(Titem_& new_item); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
76 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
77 |
/** Remove and return the smallest item from the priority queue. */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
78 |
FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;}; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
79 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
80 |
/** Remove the smallest item from the priority queue. */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
81 |
void RemoveHead(); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
82 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
83 |
/** Remove item specified by index */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
84 |
void RemoveByIdx(int idx); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
85 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
86 |
/** return index of the item that matches (using &item1 == &item2) the given item. */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
87 |
int FindLinear(const Titem_& item) const; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
88 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
89 |
/** Make the priority queue empty. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
90 |
* All remaining items will remain untouched. */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
91 |
void Clear() {m_size = 0;}; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
92 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
93 |
/** verifies the heap consistency (added during first YAPF debug phase) */ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
94 |
void CheckConsistency(); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
95 |
}; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
96 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
97 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
98 |
template <class Titem_> |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
99 |
FORCEINLINE bool CBinaryHeapT<Titem_>::Push(Titem_& new_item) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
100 |
{ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
101 |
if (IsFull()) return false; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
102 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
103 |
// make place for new item |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
104 |
int gap = ++m_size; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
105 |
// Heapify up |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
106 |
for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
107 |
m_items[gap] = m_items[parent]; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
108 |
m_items[gap] = &new_item; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
109 |
CheckConsistency(); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
110 |
return true; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
111 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
112 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
113 |
template <class Titem_> |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
114 |
FORCEINLINE void CBinaryHeapT<Titem_>::RemoveHead() |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
115 |
{ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
116 |
assert(!IsEmpty()); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
117 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
118 |
// at index 1 we have a gap now |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
119 |
int gap = 1; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
120 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
121 |
// Heapify down: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
122 |
// last item becomes a candidate for the head. Call it new_item. |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
123 |
Titem_& new_item = *m_items[m_size--]; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
124 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
125 |
// now we must maintain relation between parent and its children: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
126 |
// parent <= any child |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
127 |
// from head down to the tail |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
128 |
int child = 2; // first child is at [parent * 2] |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
129 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
130 |
// while children are valid |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
131 |
while (child <= m_size) { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
132 |
// choose the smaller child |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
133 |
if (child < m_size && *m_items[child + 1] < *m_items[child]) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
134 |
child++; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
135 |
// is it smaller than our parent? |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
136 |
if (!(*m_items[child] < new_item)) { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
137 |
// the smaller child is still bigger or same as parent => we are done |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
138 |
break; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
139 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
140 |
// if smaller child is smaller than parent, it will become new parent |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
141 |
m_items[gap] = m_items[child]; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
142 |
gap = child; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
143 |
// where do we have our new children? |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
144 |
child = gap * 2; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
145 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
146 |
// move last item to the proper place |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
147 |
if (m_size > 0) m_items[gap] = &new_item; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
148 |
CheckConsistency(); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
149 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
150 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
151 |
template <class Titem_> |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
152 |
inline void CBinaryHeapT<Titem_>::RemoveByIdx(int idx) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
153 |
{ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
154 |
// at position idx we have a gap now |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
155 |
int gap = idx; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
156 |
Titem_& last = *m_items[m_size]; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
157 |
if (idx < m_size) { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
158 |
assert(idx >= 1); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
159 |
m_size--; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
160 |
// and the candidate item for fixing this gap is our last item 'last' |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
161 |
// Move gap / last item up: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
162 |
while (gap > 1) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
163 |
{ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
164 |
// compare [gap] with its parent |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
165 |
int parent = gap / 2; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
166 |
if (last < *m_items[parent]) { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
167 |
m_items[gap] = m_items[parent]; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
168 |
gap = parent; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
169 |
} else { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
170 |
// we don't need to continue upstairs |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
171 |
break; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
172 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
173 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
174 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
175 |
// Heapify (move gap) down: |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
176 |
while (true) { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
177 |
// where we do have our children? |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
178 |
int child = gap * 2; // first child is at [parent * 2] |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
179 |
if (child > m_size) break; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
180 |
// choose the smaller child |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
181 |
if (child < m_size && *m_items[child + 1] < *m_items[child]) |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
182 |
child++; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
183 |
// is it smaller than our parent? |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
184 |
if (!(*m_items[child] < last)) { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
185 |
// the smaller child is still bigger or same as parent => we are done |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
186 |
break; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
187 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
188 |
// if smaller child is smaller than parent, it will become new parent |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
189 |
m_items[gap] = m_items[child]; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
190 |
gap = child; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
191 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
192 |
// move parent to the proper place |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
193 |
if (m_size > 0) m_items[gap] = &last; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
194 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
195 |
else { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
196 |
assert(idx == m_size); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
197 |
m_size--; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
198 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
199 |
CheckConsistency(); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
200 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
201 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
202 |
template <class Titem_> |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
203 |
inline int CBinaryHeapT<Titem_>::FindLinear(const Titem_& item) const |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
204 |
{ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
205 |
if (IsEmpty()) return 0; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
206 |
for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
207 |
if (*ppI == &item) { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
208 |
return ppI - m_items; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
209 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
210 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
211 |
return 0; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
212 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
213 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
214 |
template <class Titem_> |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
215 |
FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency() |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
216 |
{ |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
217 |
// enable it if you suspect binary heap doesn't work well |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
218 |
#if 0 |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
219 |
for (int child = 2; child <= m_size; child++) { |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
220 |
int parent = child / 2; |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
221 |
assert(!(m_items[child] < m_items[parent])); |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
222 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
223 |
#endif |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
224 |
} |
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
225 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
226 |
|
e1905dacc378
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
KUDr
parents:
diff
changeset
|
227 |
#endif /* BINARYHEAP_HPP */ |