50 /// Each item has a state associated to it. It can be "in heap", |
50 /// Each item has a state associated to it. It can be "in heap", |
51 /// "pre heap" or "post heap". The later two are indifferent |
51 /// "pre heap" or "post heap". The later two are indifferent |
52 /// from the point of view of the heap, but may be useful for |
52 /// from the point of view of the heap, but may be useful for |
53 /// the user. |
53 /// the user. |
54 /// |
54 /// |
55 /// The \c ItemIntMap must be initialized in such a way, that it |
55 /// The \c ItemIntMap must be initialized in such a way, that it |
56 /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item. |
56 /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item. |
57 enum State { |
57 enum State { |
58 IN_HEAP = 0, |
58 IN_HEAP = 0, |
59 PRE_HEAP = -1, |
59 PRE_HEAP = -1, |
60 POST_HEAP = -2 |
60 POST_HEAP = -2 |
61 }; |
61 }; |
62 |
62 |
63 /// \brief The constructor. |
63 /// \brief The constructor. |
64 /// |
64 /// |
65 /// The constructor. |
65 /// The constructor. |
66 /// \param map A map that assigns \c int values to keys of type |
66 /// \param map A map that assigns \c int values to keys of type |
67 /// \c Item. It is used internally by the heap implementations to |
67 /// \c Item. It is used internally by the heap implementations to |
83 /// |
83 /// |
84 /// Makes the heap empty. |
84 /// Makes the heap empty. |
85 void clear(); |
85 void clear(); |
86 |
86 |
87 /// \brief Inserts an item into the heap with the given priority. |
87 /// \brief Inserts an item into the heap with the given priority. |
88 /// |
88 /// |
89 /// Inserts the given item into the heap with the given priority. |
89 /// Inserts the given item into the heap with the given priority. |
90 /// \param i The item to insert. |
90 /// \param i The item to insert. |
91 /// \param p The priority of the item. |
91 /// \param p The priority of the item. |
92 void push(const Item &i, const Prio &p) {} |
92 void push(const Item &i, const Prio &p) {} |
93 |
93 |
94 /// \brief Returns the item having minimum priority. |
94 /// \brief Returns the item having minimum priority. |
110 void pop() {} |
110 void pop() {} |
111 |
111 |
112 /// \brief Removes an item from the heap. |
112 /// \brief Removes an item from the heap. |
113 /// |
113 /// |
114 /// Removes the given item from the heap if it is already stored. |
114 /// Removes the given item from the heap if it is already stored. |
115 /// \param i The item to delete. |
115 /// \param i The item to delete. |
116 void erase(const Item &i) {} |
116 void erase(const Item &i) {} |
117 |
117 |
118 /// \brief The priority of an item. |
118 /// \brief The priority of an item. |
119 /// |
119 /// |
120 /// Returns the priority of the given item. |
120 /// Returns the priority of the given item. |
121 /// \pre \c i must be in the heap. |
121 /// \pre \c i must be in the heap. |
122 /// \param i The item. |
122 /// \param i The item. |
123 Prio operator[](const Item &i) const {} |
123 Prio operator[](const Item &i) const {} |
124 |
124 |
125 /// \brief Sets the priority of an item or inserts it, if it is |
125 /// \brief Sets the priority of an item or inserts it, if it is |
131 /// |
131 /// |
132 /// It may throw an \ref UnderflowPriorityException. |
132 /// It may throw an \ref UnderflowPriorityException. |
133 /// \param i The item. |
133 /// \param i The item. |
134 /// \param p The priority. |
134 /// \param p The priority. |
135 void set(const Item &i, const Prio &p) {} |
135 void set(const Item &i, const Prio &p) {} |
136 |
136 |
137 /// \brief Decreases the priority of an item to the given value. |
137 /// \brief Decreases the priority of an item to the given value. |
138 /// |
138 /// |
139 /// Decreases the priority of an item to the given value. |
139 /// Decreases the priority of an item to the given value. |
140 /// \pre \c i must be stored in the heap with priority at least \c p. |
140 /// \pre \c i must be stored in the heap with priority at least \c p. |
141 /// \param i The item. |
141 /// \param i The item. |
172 |
172 |
173 |
173 |
174 template <typename _Heap> |
174 template <typename _Heap> |
175 struct Constraints { |
175 struct Constraints { |
176 public: |
176 public: |
177 void constraints() { |
177 void constraints() { |
178 typedef typename _Heap::Item OwnItem; |
178 typedef typename _Heap::Item OwnItem; |
179 typedef typename _Heap::Prio OwnPrio; |
179 typedef typename _Heap::Prio OwnPrio; |
180 typedef typename _Heap::State OwnState; |
180 typedef typename _Heap::State OwnState; |
181 |
181 |
182 Item item; |
182 Item item; |
183 Prio prio; |
183 Prio prio; |
184 item=Item(); |
184 item=Item(); |
185 prio=Prio(); |
185 prio=Prio(); |
186 ignore_unused_variable_warning(item); |
186 ignore_unused_variable_warning(item); |
187 ignore_unused_variable_warning(prio); |
187 ignore_unused_variable_warning(prio); |
188 |
188 |
189 OwnItem own_item; |
189 OwnItem own_item; |
190 OwnPrio own_prio; |
190 OwnPrio own_prio; |
191 OwnState own_state; |
191 OwnState own_state; |
192 own_item=Item(); |
192 own_item=Item(); |
193 own_prio=Prio(); |
193 own_prio=Prio(); |
194 ignore_unused_variable_warning(own_item); |
194 ignore_unused_variable_warning(own_item); |
195 ignore_unused_variable_warning(own_prio); |
195 ignore_unused_variable_warning(own_prio); |
196 ignore_unused_variable_warning(own_state); |
196 ignore_unused_variable_warning(own_state); |
197 |
197 |
198 _Heap heap1(map); |
198 _Heap heap1(map); |
199 _Heap heap2 = heap1; |
199 _Heap heap2 = heap1; |
200 ignore_unused_variable_warning(heap1); |
200 ignore_unused_variable_warning(heap1); |
201 ignore_unused_variable_warning(heap2); |
201 ignore_unused_variable_warning(heap2); |
202 |
202 |
203 int s = heap.size(); |
203 int s = heap.size(); |
204 ignore_unused_variable_warning(s); |
204 ignore_unused_variable_warning(s); |
205 bool e = heap.empty(); |
205 bool e = heap.empty(); |
206 ignore_unused_variable_warning(e); |
206 ignore_unused_variable_warning(e); |
207 |
207 |
208 prio = heap.prio(); |
208 prio = heap.prio(); |
209 item = heap.top(); |
209 item = heap.top(); |
210 prio = heap[item]; |
210 prio = heap[item]; |
211 own_prio = heap.prio(); |
211 own_prio = heap.prio(); |
212 own_item = heap.top(); |
212 own_item = heap.top(); |
213 own_prio = heap[own_item]; |
213 own_prio = heap[own_item]; |
214 |
214 |
215 heap.push(item, prio); |
215 heap.push(item, prio); |
216 heap.push(own_item, own_prio); |
216 heap.push(own_item, own_prio); |
217 heap.pop(); |
217 heap.pop(); |
218 |
218 |
219 heap.set(item, prio); |
219 heap.set(item, prio); |
220 heap.decrease(item, prio); |
220 heap.decrease(item, prio); |
221 heap.increase(item, prio); |
221 heap.increase(item, prio); |
222 heap.set(own_item, own_prio); |
222 heap.set(own_item, own_prio); |
223 heap.decrease(own_item, own_prio); |
223 heap.decrease(own_item, own_prio); |
224 heap.increase(own_item, own_prio); |
224 heap.increase(own_item, own_prio); |
225 |
225 |
226 heap.erase(item); |
226 heap.erase(item); |
227 heap.erase(own_item); |
227 heap.erase(own_item); |
228 heap.clear(); |
228 heap.clear(); |
229 |
229 |
230 own_state = heap.state(own_item); |
230 own_state = heap.state(own_item); |
231 heap.state(own_item, own_state); |
231 heap.state(own_item, own_state); |
232 |
232 |
233 own_state = _Heap::PRE_HEAP; |
233 own_state = _Heap::PRE_HEAP; |
234 own_state = _Heap::IN_HEAP; |
234 own_state = _Heap::IN_HEAP; |
235 own_state = _Heap::POST_HEAP; |
235 own_state = _Heap::POST_HEAP; |
236 } |
236 } |
237 |
237 |
238 _Heap& heap; |
238 _Heap& heap; |
239 ItemIntMap& map; |
239 ItemIntMap& map; |
240 }; |
240 }; |
241 }; |
241 }; |
242 |
242 |
243 /// @} |
243 /// @} |
244 } // namespace lemon |
244 } // namespace lemon |