Branch data Line data Source code
1 : : #include "cassert"
2 : : #include "PriorityQueue.hpp"
3 : : #include "CubitMessage.hpp"
4 : :
5 : :
6 : : #ifdef INLINE_TEMPLATES
7 : : #define MY_INLINE inline
8 : : #else
9 : : #define MY_INLINE
10 : : #endif
11 : :
12 : : template <class Object> MY_INLINE
13 : 0 : PriorityQueue<Object>::PriorityQueue(typename PriorityQueue<Object>::CompareFunc compare)
14 [ # # ][ # # ]: 0 : : theItems(1)
[ # # ][ # # ]
15 : : {
16 : 0 : lessThanFunc = compare;
17 : 0 : }
18 : : template <class Object> MY_INLINE
19 : 0 : int PriorityQueue<Object>::size() const
20 : : {
21 : 0 : return theItems.size() - 1;
22 : : }
23 : : template <class Object> MY_INLINE
24 : 0 : bool PriorityQueue<Object>::empty() const
25 : : {
26 [ # # ][ # # ]: 0 : if ( size() == 0 )
[ # # ][ # # ]
27 : 0 : return true;
28 : : else
29 : 0 : return false;
30 : : }
31 : : template <class Object> MY_INLINE
32 : 0 : const Object PriorityQueue<Object>::top() const
33 : : {
34 [ # # ][ # # ]: 0 : if ( empty() )
[ # # ][ # # ]
35 : : {
36 [ # # ][ # # ]: 0 : PRINT_ERROR("Empty priority queue had top request.\n");
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
37 [ # # ][ # # ]: 0 : assert(!empty());
[ # # ][ # # ]
38 : 0 : return (Object)0;
39 : : }
40 : 0 : return theItems[1];
41 : : }
42 : : template <class Object> MY_INLINE
43 : 0 : void PriorityQueue<Object>::push(Object x)
44 : : {
45 : 0 : theItems.push_back(x);
46 : 0 : theItems[0] = x;//stash the item here...
47 : : //Percolate up.
48 : 0 : int hole = size();
49 : : //While x is less than the parrent, do (1): then go up the tree (hole /= 2 is the parent...).
50 [ # # ][ # # ]: 0 : for ( ; lessThanFunc(x, theItems[hole/2]); hole /= 2 )
[ # # ][ # # ]
51 : : {
52 : : //(1) set the replace the parent with the child.
53 : 0 : theItems[hole] = theItems[hole/2];
54 : : }
55 : : //Now where the item is greater than the parent, set this value.
56 : 0 : theItems[hole] = x;
57 : 0 : }
58 : : template <class Object> MY_INLINE
59 : 0 : void PriorityQueue<Object>::pop()
60 : : {
61 [ # # ][ # # ]: 0 : if ( empty() )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
62 : : {
63 [ # # ][ # # ]: 0 : PRINT_ERROR("Trying to delete min from empty priority queue.\n");
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
64 [ # # ][ # # ]: 0 : assert(!empty());
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
65 : 0 : return;
66 : : }
67 : :
68 : 0 : int hole = 1;
69 : : int child;
70 : :
71 [ # # ][ # # ]: 0 : Object tmp = theItems.back();
[ # # ][ # # ]
72 [ # # ][ # # ]: 0 : theItems.pop_back();
[ # # ][ # # ]
73 [ # # ][ # # ]: 0 : int the_size = size();
[ # # ][ # # ]
74 : : //while the current isn't at the end, do (1): then set hole to child.
75 [ # # ][ # # ]: 0 : for ( ; hole*2 <= the_size; hole = child )
[ # # ][ # # ]
76 : : {
77 : 0 : child = hole*2;
78 [ # # ][ # # ]: 0 : if ( child != the_size &&
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
79 [ # # ][ # # ]: 0 : lessThanFunc(theItems[child+1], theItems[child]) )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
80 : 0 : child++;
81 [ # # ][ # # ]: 0 : if ( lessThanFunc(theItems[child], tmp) )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
82 [ # # ][ # # ]: 0 : theItems[hole] = theItems[child];
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
83 : : else
84 : 0 : break;
85 : : }
86 [ # # ][ # # ]: 0 : if ( !empty() )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
87 [ # # ][ # # ]: 0 : theItems[hole] = tmp;
[ # # ][ # # ]
88 : : }
89 : :
90 : : template <class Object> MY_INLINE
91 : : int PriorityQueue<Object>::where_is_item(Object &a, int start_index, bool queue_is_valid)
92 : : {
93 : : size_t i;
94 : :
95 : : if (!queue_is_valid)
96 : : {
97 : : for (i=0; i < theItems.size(); ++i)
98 : : {
99 : : if (theItems[i] == a) {return i;}
100 : : }
101 : : return -1;
102 : : }
103 : :
104 : : if (a == theItems[start_index]) {return start_index;}
105 : : if (!lessThanFunc(a, theItems[start_index]) && 2*start_index+1 <= size())
106 : : {
107 : : int result;
108 : : result = where_is_item(a, 2*start_index);
109 : : if (result > 0) {return result;}
110 : : result = where_is_item(a, 2*start_index+1);
111 : : if (result > 0) {return result;}
112 : : }
113 : :
114 : : return -1;
115 : : }
116 : :
117 : : template <class Object> MY_INLINE
118 : : bool PriorityQueue<Object>::update_item(Object &a, bool queue_is_valid)
119 : : {
120 : : int index = where_is_item(a, queue_is_valid);
121 : : if (index == -1) {return false;}
122 : : else {return update_item(index);}
123 : : }
124 : :
125 : : template <class Object> MY_INLINE
126 : : bool PriorityQueue<Object>::update_item(int object_index)
127 : : {
128 : : if (object_index == 0) {return true;}
129 : :
130 : : if (lessThanFunc(theItems[object_index], theItems[object_index/2]))
131 : : {
132 : : Object temp = theItems[object_index];
133 : : theItems[object_index] = theItems[object_index/2];
134 : : theItems[object_index/2] = temp;
135 : : update_item(object_index/2);
136 : : return true;
137 : : }
138 : :
139 : : int smaller_child = 2*object_index;
140 : : if (2*object_index > size()) {return true;}
141 : : if (2*object_index+1 <= size())
142 : : {
143 : : if (lessThanFunc(theItems[2*object_index+1],theItems[2*object_index])) {++smaller_child;}
144 : : }
145 : :
146 : : if (lessThanFunc(theItems[smaller_child], theItems[object_index]))
147 : : {
148 : : Object temp = theItems[object_index];
149 : : theItems[object_index] = theItems[smaller_child];
150 : : theItems[smaller_child] = temp;
151 : : update_item(smaller_child);
152 : : }
153 : :
154 : : return true;
155 : : }
156 : :
157 : : template <class Object> MY_INLINE
158 : : bool PriorityQueue<Object>::validate(int index)
159 : : {
160 : : bool fine = true, kid_one = false, kid_two = false;
161 : : if (2*index <= size())
162 : : {
163 : : kid_one = true;
164 : : if ((lessThanFunc(theItems[2*index], theItems[index])))
165 : : {
166 : : fine = false;
167 : : }
168 : : }
169 : :
170 : : if (2*index+1 <= size())
171 : : {
172 : : kid_two = true;
173 : : if ((lessThanFunc(theItems[2*index+1], theItems[index])))
174 : : {
175 : : fine = false;
176 : : }
177 : : }
178 : :
179 : : if (fine)
180 : : {
181 : : if (kid_one && !kid_two) {return validate(2*index);}
182 : : if (!kid_one && kid_two) {return validate(2*index+1);}
183 : : if (kid_one && kid_two) {return (validate(2*index) && validate(2*index+1));}
184 : : else {return true;}
185 : : }
186 : :
187 : : return false;
188 : :
189 : : }
|
