57 typedef Prio PrioType; |
57 typedef Prio PrioType; |
58 typedef std::pair<ItemType,PrioType> PairType; |
58 typedef std::pair<ItemType,PrioType> PairType; |
59 typedef ItemIntMap ItemIntMapType; |
59 typedef ItemIntMap ItemIntMapType; |
60 typedef Compare PrioCompare; |
60 typedef Compare PrioCompare; |
61 |
61 |
62 /** |
62 /// \brief Type to represent the items states. |
63 * Each Item element have a state associated to it. It may be "in heap", |
63 /// |
64 * "pre heap" or "post heap". The later two are indifferent from the |
64 /// Each Item element have a state associated to it. It may be "in heap", |
65 * heap's point of view, but may be useful to the user. |
65 /// "pre heap" or "post heap". The later two are indifferent from the |
66 * |
66 /// heap's point of view, but may be useful to the user. |
67 * The ItemIntMap _should_ be initialized in such way, that it maps |
67 /// |
68 * PRE_HEAP (-1) to any element to be put in the heap... |
68 /// The ItemIntMap _should_ be initialized in such way, that it maps |
69 */ |
69 /// PRE_HEAP (-1) to any element to be put in the heap... |
70 ///\todo it is used nowhere |
|
71 /// |
|
72 enum state_enum { |
70 enum state_enum { |
73 IN_HEAP = 0, |
71 IN_HEAP = 0, |
74 PRE_HEAP = -1, |
72 PRE_HEAP = -1, |
75 POST_HEAP = -2 |
73 POST_HEAP = -2 |
76 }; |
74 }; |
77 |
75 |
78 private: |
76 private: |
79 std::vector<PairType> data; |
77 std::vector<PairType> data; |
80 Compare comp; |
78 Compare comp; |
81 // FIXME: jo ez igy??? |
|
82 ItemIntMap &iim; |
79 ItemIntMap &iim; |
83 |
80 |
84 public: |
81 public: |
85 ///The constructor |
82 /// \brief The constructor. |
86 |
83 /// |
87 /** |
84 /// The constructor. |
88 \c _iim should be given to the constructor, since it is used |
85 /// \param _iim should be given to the constructor, since it is used |
89 internally to handle the cross references. |
86 /// internally to handle the cross references. The value of the map |
90 */ |
87 /// should be PRE_HEAP (-1) for each element. |
91 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} |
88 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} |
92 |
89 |
93 ///The constructor |
90 /// \brief The constructor. |
94 |
91 /// |
95 /** |
92 /// The constructor. |
96 \c _iim should be given to the constructor, since it is used |
93 /// \param _iim should be given to the constructor, since it is used |
97 internally to handle the cross references. \c _comp is an |
94 /// internally to handle the cross references. The value of the map |
98 object for ordering of the priorities. |
95 /// should be PRE_HEAP (-1) for each element. |
99 */ |
96 /// |
|
97 /// \param _comp The comparator function object. |
100 BinHeap(ItemIntMap &_iim, const Compare &_comp) |
98 BinHeap(ItemIntMap &_iim, const Compare &_comp) |
101 : iim(_iim), comp(_comp) {} |
99 : iim(_iim), comp(_comp) {} |
102 |
100 |
103 |
101 |
104 ///The number of items stored in the heap. |
102 /// The number of items stored in the heap. |
105 |
103 /// |
106 /** |
104 /// \brief Returns the number of items stored in the heap. |
107 Returns the number of items stored in the heap. |
|
108 */ |
|
109 int size() const { return data.size(); } |
105 int size() const { return data.size(); } |
110 |
106 |
111 ///Checks if the heap stores no items. |
107 /// \brief Checks if the heap stores no items. |
112 |
108 /// |
113 /** |
109 /// Returns \c true if and only if the heap stores no items. |
114 Returns \c true if and only if the heap stores no items. |
|
115 */ |
|
116 bool empty() const { return data.empty(); } |
110 bool empty() const { return data.empty(); } |
117 |
111 |
118 private: |
112 private: |
119 static int parent(int i) { return (i-1)/2; } |
113 static int parent(int i) { return (i-1)/2; } |
120 static int second_child(int i) { return 2*i+2; } |
114 static int second_child(int i) { return 2*i+2; } |
140 data.pop_back(); |
134 data.pop_back(); |
141 } |
135 } |
142 } |
136 } |
143 |
137 |
144 public: |
138 public: |
145 ///Adds \c p.first to the heap with priority \c p.second. |
139 /// \brief Insert a pair of item and priority into the heap. |
146 |
140 /// |
147 /** |
141 /// Adds \c p.first to the heap with priority \c p.second. |
148 Adds \c p.first to the heap with priority \c p.second. |
142 /// \param p The pair to insert. |
149 \c p.first must not be stored in the heap. |
|
150 */ |
|
151 void push(const PairType &p) { |
143 void push(const PairType &p) { |
152 int n = data.size(); |
144 int n = data.size(); |
153 data.resize(n+1); |
145 data.resize(n+1); |
154 bubble_up(n, p); |
146 bubble_up(n, p); |
155 } |
147 } |
156 |
148 |
157 ///Adds \c i to the heap with priority \c p. |
149 /// \brief Insert an item into the heap with the given heap. |
158 |
150 /// |
159 /** |
151 /// Adds \c i to the heap with priority \c p. |
160 Adds \c i to the heap with priority \c p. |
152 /// \param i The item to insert. |
161 \pre \c i must not be stored in the heap. |
153 /// \param p The priority of the item. |
162 */ |
|
163 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } |
154 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } |
164 |
155 |
165 ///Returns the item with minimum priority relative to \c Compare. |
156 /// \brief Returns the item with minimum priority relative to \c Compare. |
166 |
157 /// |
167 /** |
158 /// This method returns the item with minimum priority relative to \c |
168 This method returns the item with minimum priority relative to \c |
159 /// Compare. |
169 Compare. |
160 /// \pre The heap must be nonempty. |
170 \pre The heap must be nonempty. |
|
171 */ |
|
172 Item top() const { |
161 Item top() const { |
173 return data[0].first; |
162 return data[0].first; |
174 } |
163 } |
175 |
164 |
176 ///Returns the minimum priority relative to \c Compare. |
165 /// \brief Returns the minimum priority relative to \c Compare. |
177 |
166 /// |
178 /** |
167 /// It returns the minimum priority relative to \c Compare. |
179 It returns the minimum priority relative to \c Compare. |
168 /// \pre The heap must be nonempty. |
180 \pre The heap must be nonempty. |
|
181 */ |
|
182 Prio prio() const { |
169 Prio prio() const { |
183 return data[0].second; |
170 return data[0].second; |
184 } |
171 } |
185 |
172 |
186 ///Deletes the item with minimum priority relative to \c Compare. |
173 /// \brief Deletes the item with minimum priority relative to \c Compare. |
187 |
174 /// |
188 /** |
175 /// This method deletes the item with minimum priority relative to \c |
189 This method deletes the item with minimum priority relative to \c |
176 /// Compare from the heap. |
190 Compare from the heap. |
177 /// \pre The heap must be non-empty. |
191 \pre The heap must be non-empty. |
|
192 */ |
|
193 void pop() { |
178 void pop() { |
194 rmidx(0); |
179 rmidx(0); |
195 } |
180 } |
196 |
181 |
197 ///Deletes \c i from the heap. |
182 /// \brief Deletes \c i from the heap. |
198 |
183 /// |
199 /** |
184 /// This method deletes item \c i from the heap, if \c i was |
200 This method deletes item \c i from the heap, if \c i was |
185 /// already stored in the heap. |
201 already stored in the heap. |
186 /// \param i The item to erase. |
202 */ |
|
203 void erase(const Item &i) { |
187 void erase(const Item &i) { |
204 rmidx(iim[i]); |
188 rmidx(iim[i]); |
205 } |
189 } |
206 |
190 |
207 |
191 |
208 ///Returns the priority of \c i. |
192 /// \brief Returns the priority of \c i. |
209 |
193 /// |
210 /** |
194 /// This function returns the priority of item \c i. |
211 This function returns the priority of item \c i. |
195 /// \pre \c i must be in the heap. |
212 \pre \c i must be in the heap. |
196 /// \param i The item. |
213 */ |
|
214 Prio operator[](const Item &i) const { |
197 Prio operator[](const Item &i) const { |
215 int idx = iim[i]; |
198 int idx = iim[i]; |
216 return data[idx].second; |
199 return data[idx].second; |
217 } |
200 } |
218 |
201 |
219 ///\c i gets to the heap with priority \c p independently if \c i was already there. |
202 /// \brief \c i gets to the heap with priority \c p independently |
220 |
203 /// if \c i was already there. |
221 /** |
204 /// |
222 This method calls \ref push(\c i, \c p) if \c i is not stored |
205 /// This method calls \ref push(\c i, \c p) if \c i is not stored |
223 in the heap and sets the priority of \c i to \c p otherwise. |
206 /// in the heap and sets the priority of \c i to \c p otherwise. |
224 */ |
207 /// \param i The item. |
|
208 /// \param p The priority. |
225 void set(const Item &i, const Prio &p) { |
209 void set(const Item &i, const Prio &p) { |
226 int idx = iim[i]; |
210 int idx = iim[i]; |
227 if( idx < 0 ) { |
211 if( idx < 0 ) { |
228 push(i,p); |
212 push(i,p); |
229 } |
213 } |
233 else { |
217 else { |
234 bubble_down(idx, PairType(i,p), data.size()); |
218 bubble_down(idx, PairType(i,p), data.size()); |
235 } |
219 } |
236 } |
220 } |
237 |
221 |
238 ///Decreases the priority of \c i to \c p. |
222 /// \brief Decreases the priority of \c i to \c p. |
239 |
223 |
240 /** |
224 /// This method decreases the priority of item \c i to \c p. |
241 This method decreases the priority of item \c i to \c p. |
225 /// \pre \c i must be stored in the heap with priority at least \c |
242 \pre \c i must be stored in the heap with priority at least \c |
226 /// p relative to \c Compare. |
243 p relative to \c Compare. |
227 /// \param i The item. |
244 */ |
228 /// \param p The priority. |
245 void decrease(const Item &i, const Prio &p) { |
229 void decrease(const Item &i, const Prio &p) { |
246 int idx = iim[i]; |
230 int idx = iim[i]; |
247 bubble_up(idx, PairType(i,p)); |
231 bubble_up(idx, PairType(i,p)); |
248 } |
232 } |
249 |
233 |
250 ///Increases the priority of \c i to \c p. |
234 /// \brief Increases the priority of \c i to \c p. |
251 |
235 /// |
252 /** |
236 /// This method sets the priority of item \c i to \c p. |
253 This method sets the priority of item \c i to \c p. |
237 /// \pre \c i must be stored in the heap with priority at most \c |
254 \pre \c i must be stored in the heap with priority at most \c |
238 /// p relative to \c Compare. |
255 p relative to \c Compare. |
239 /// \param i The item. |
256 */ |
240 /// \param p The priority. |
257 void increase(const Item &i, const Prio &p) { |
241 void increase(const Item &i, const Prio &p) { |
258 int idx = iim[i]; |
242 int idx = iim[i]; |
259 bubble_down(idx, PairType(i,p), data.size()); |
243 bubble_down(idx, PairType(i,p), data.size()); |
260 } |
244 } |
261 |
245 |
262 ///Returns if \c item is in, has already been in, or has never been in the heap. |
246 /// \brief Returns if \c item is in, has already been in, or has |
263 |
247 /// never been in the heap. |
264 /** |
248 /// |
265 This method returns PRE_HEAP if \c item has never been in the |
249 /// This method returns PRE_HEAP if \c item has never been in the |
266 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
250 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
267 otherwise. In the latter case it is possible that \c item will |
251 /// otherwise. In the latter case it is possible that \c item will |
268 get back to the heap again. |
252 /// get back to the heap again. |
269 */ |
253 /// \param i The item. |
270 state_enum state(const Item &i) const { |
254 state_enum state(const Item &i) const { |
271 int s = iim[i]; |
255 int s = iim[i]; |
272 if( s>=0 ) |
256 if( s>=0 ) |
273 s=0; |
257 s=0; |
274 return state_enum(s); |
258 return state_enum(s); |