16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 ///\ingroup concept |
19 ///\ingroup concept |
20 ///\file |
20 ///\file |
21 ///\brief Classes for representing heaps. |
21 ///\brief The concept of heaps. |
22 /// |
|
23 |
22 |
24 #ifndef LEMON_CONCEPT_HEAP_H |
23 #ifndef LEMON_CONCEPT_HEAP_H |
25 #define LEMON_CONCEPT_HEAP_H |
24 #define LEMON_CONCEPT_HEAP_H |
26 |
25 |
27 #include <lemon/bits/invalid.h> |
26 #include <lemon/bits/invalid.h> |
28 |
27 |
29 namespace lemon { |
28 namespace lemon { |
|
29 |
30 namespace concepts { |
30 namespace concepts { |
|
31 |
31 /// \addtogroup concept |
32 /// \addtogroup concept |
32 /// @{ |
33 /// @{ |
33 |
34 |
34 |
35 /// \brief The heap concept. |
35 /// \brief A concept structure describes the main interface of heaps. |
|
36 /// |
36 /// |
37 /// A concept structure describes the main interface of heaps. |
37 /// Concept class describing the main interface of heaps. |
38 /// |
38 template <typename Priority, typename ItemIntMap> |
39 template <typename Prio, typename ItemIntMap> |
|
40 class Heap { |
39 class Heap { |
41 public: |
40 public: |
42 |
41 |
43 ///\brief Type of the items stored in the heap. |
42 /// Type of the items stored in the heap. |
44 typedef typename ItemIntMap::Key Item; |
43 typedef typename ItemIntMap::Key Item; |
45 |
44 |
46 |
45 /// Type of the priorities. |
47 /// \brief Type to represent the items states. |
46 typedef Priority Prio; |
48 /// |
47 |
49 /// Each Item element have a state associated to it. It may be "in heap", |
48 /// \brief Type to represent the states of the items. |
50 /// "pre heap" or "post heap". The later two are indifferent from the |
49 /// |
51 /// heap's point of view, but may be useful to the user. |
50 /// Each item has a state associated to it. It can be "in heap", |
52 /// |
51 /// "pre heap" or "post heap". The later two are indifferent |
53 /// The ItemIntMap _should_ be initialized in such way, that it maps |
52 /// from the point of view of the heap, but may be useful for |
54 /// PRE_HEAP (-1) to any element to be put in the heap... |
53 /// the user. |
|
54 /// |
|
55 /// The \c ItemIntMap must be initialized in such a way, that it |
|
56 /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item. |
55 enum State { |
57 enum State { |
56 IN_HEAP = 0, |
58 IN_HEAP = 0, |
57 PRE_HEAP = -1, |
59 PRE_HEAP = -1, |
58 POST_HEAP = -2 |
60 POST_HEAP = -2 |
59 }; |
61 }; |
60 |
62 |
61 /// \brief The constructor. |
63 /// \brief The constructor. |
62 /// |
64 /// |
63 /// The constructor. |
65 /// The constructor. |
64 /// \param _iim should be given to the constructor, since it is used |
66 /// \param map A map that assigns \c int values to keys of type |
65 /// internally to handle the cross references. The value of the map |
67 /// \c Item. It is used internally by the heap implementations to |
66 /// should be PRE_HEAP (-1) for each element. |
68 /// handle the cross references. The assigned value must be |
67 explicit Heap(ItemIntMap &_iim) {} |
69 /// \c PRE_HEAP (<tt>-1</tt>) for every item. |
|
70 explicit Heap(ItemIntMap &map) {} |
68 |
71 |
69 /// \brief The number of items stored in the heap. |
72 /// \brief The number of items stored in the heap. |
70 /// |
73 /// |
71 /// Returns the number of items stored in the heap. |
74 /// Returns the number of items stored in the heap. |
72 int size() const { return 0; } |
75 int size() const { return 0; } |
73 |
76 |
74 /// \brief Checks if the heap stores no items. |
77 /// \brief Checks if the heap is empty. |
75 /// |
78 /// |
76 /// Returns \c true if and only if the heap stores no items. |
79 /// Returns \c true if the heap is empty. |
77 bool empty() const { return false; } |
80 bool empty() const { return false; } |
78 |
81 |
79 /// \brief Makes empty this heap. |
82 /// \brief Makes the heap empty. |
80 /// |
83 /// |
81 /// Makes this heap empty. |
84 /// Makes the heap empty. |
82 void clear(); |
85 void clear(); |
83 |
86 |
84 /// \brief Insert an item into the heap with the given heap. |
87 /// \brief Inserts an item into the heap with the given priority. |
85 /// |
88 /// |
86 /// Adds \c i to the heap with priority \c p. |
89 /// Inserts the given item into the heap with the given priority. |
87 /// \param i The item to insert. |
90 /// \param i The item to insert. |
88 /// \param p The priority of the item. |
91 /// \param p The priority of the item. |
89 void push(const Item &i, const Prio &p) {} |
92 void push(const Item &i, const Prio &p) {} |
90 |
93 |
91 /// \brief Returns the item with minimum priority. |
94 /// \brief Returns the item having minimum priority. |
92 /// |
95 /// |
93 /// This method returns the item with minimum priority. |
96 /// Returns the item having minimum priority. |
94 /// \pre The heap must be nonempty. |
97 /// \pre The heap must be non-empty. |
95 Item top() const {} |
98 Item top() const {} |
96 |
99 |
97 /// \brief Returns the minimum priority. |
100 /// \brief The minimum priority. |
98 /// |
101 /// |
99 /// It returns the minimum priority. |
102 /// Returns the minimum priority. |
100 /// \pre The heap must be nonempty. |
103 /// \pre The heap must be non-empty. |
101 Prio prio() const {} |
104 Prio prio() const {} |
102 |
105 |
103 /// \brief Deletes the item with minimum priority. |
106 /// \brief Removes the item having minimum priority. |
104 /// |
107 /// |
105 /// This method deletes the item with minimum priority. |
108 /// Removes the item having minimum priority. |
106 /// \pre The heap must be non-empty. |
109 /// \pre The heap must be non-empty. |
107 void pop() {} |
110 void pop() {} |
108 |
111 |
109 /// \brief Deletes \c i from the heap. |
112 /// \brief Removes an item from the heap. |
110 /// |
113 /// |
111 /// This method deletes item \c i from the heap, if \c i was |
114 /// Removes the given item from the heap if it is already stored. |
|
115 /// \param i The item to delete. |
|
116 void erase(const Item &i) {} |
|
117 |
|
118 /// \brief The priority of an item. |
|
119 /// |
|
120 /// Returns the priority of the given item. |
|
121 /// \pre \c i must be in the heap. |
|
122 /// \param i The item. |
|
123 Prio operator[](const Item &i) const {} |
|
124 |
|
125 /// \brief Sets the priority of an item or inserts it, if it is |
|
126 /// not stored in the heap. |
|
127 /// |
|
128 /// This method sets the priority of the given item if it is |
112 /// already stored in the heap. |
129 /// already stored in the heap. |
113 /// \param i The item to erase. |
130 /// Otherwise it inserts the given item with the given priority. |
114 void erase(const Item &i) {} |
131 /// |
115 |
132 /// It may throw an \ref UnderflowPriorityException. |
116 /// \brief Returns the priority of \c i. |
|
117 /// |
|
118 /// This function returns the priority of item \c i. |
|
119 /// \pre \c i must be in the heap. |
|
120 /// \param i The item. |
|
121 Prio operator[](const Item &i) const {} |
|
122 |
|
123 /// \brief \c i gets to the heap with priority \c p independently |
|
124 /// if \c i was already there. |
|
125 /// |
|
126 /// This method calls \ref push(\c i, \c p) if \c i is not stored |
|
127 /// in the heap and sets the priority of \c i to \c p otherwise. |
|
128 /// It may throw an \e UnderFlowPriorityException. |
|
129 /// \param i The item. |
133 /// \param i The item. |
130 /// \param p The priority. |
134 /// \param p The priority. |
131 void set(const Item &i, const Prio &p) {} |
135 void set(const Item &i, const Prio &p) {} |
132 |
136 |
133 /// \brief Decreases the priority of \c i to \c p. |
137 /// \brief Decreases the priority of an item to the given value. |
134 /// |
138 /// |
135 /// This method decreases the priority of item \c i to \c p. |
139 /// Decreases the priority of an item to the given value. |
136 /// \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. |
137 /// \param i The item. |
141 /// \param i The item. |
138 /// \param p The priority. |
142 /// \param p The priority. |
139 void decrease(const Item &i, const Prio &p) {} |
143 void decrease(const Item &i, const Prio &p) {} |
140 |
144 |
141 /// \brief Increases the priority of \c i to \c p. |
145 /// \brief Increases the priority of an item to the given value. |
142 /// |
146 /// |
143 /// This method sets the priority of item \c i to \c p. |
147 /// Increases the priority of an item to the given value. |
144 /// \pre \c i must be stored in the heap with priority at most \c |
148 /// \pre \c i must be stored in the heap with priority at most \c p. |
145 /// p relative to \c Compare. |
|
146 /// \param i The item. |
149 /// \param i The item. |
147 /// \param p The priority. |
150 /// \param p The priority. |
148 void increase(const Item &i, const Prio &p) {} |
151 void increase(const Item &i, const Prio &p) {} |
149 |
152 |
150 /// \brief Returns if \c item is in, has already been in, or has |
153 /// \brief Returns if an item is in, has already been in, or has |
151 /// never been in the heap. |
154 /// never been in the heap. |
152 /// |
155 /// |
153 /// This method returns PRE_HEAP if \c item has never been in the |
156 /// This method returns \c PRE_HEAP if the given item has never |
154 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
157 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
155 /// otherwise. In the latter case it is possible that \c item will |
158 /// and \c POST_HEAP otherwise. |
156 /// get back to the heap again. |
159 /// In the latter case it is possible that the item will get back |
|
160 /// to the heap again. |
157 /// \param i The item. |
161 /// \param i The item. |
158 State state(const Item &i) const {} |
162 State state(const Item &i) const {} |
159 |
163 |
160 /// \brief Sets the state of the \c item in the heap. |
164 /// \brief Sets the state of an item in the heap. |
161 /// |
165 /// |
162 /// Sets the state of the \c item in the heap. It can be used to |
166 /// Sets the state of the given item in the heap. It can be used |
163 /// manually clear the heap when it is important to achive the |
167 /// to manually clear the heap when it is important to achive the |
164 /// better time complexity. |
168 /// better time complexity. |
165 /// \param i The item. |
169 /// \param i The item. |
166 /// \param st The state. It should not be \c IN_HEAP. |
170 /// \param st The state. It should not be \c IN_HEAP. |
167 void state(const Item& i, State st) {} |
171 void state(const Item& i, State st) {} |
168 |
172 |
169 |
173 |
170 template <typename _Heap> |
174 template <typename _Heap> |
171 struct Constraints { |
175 struct Constraints { |
172 public: |
176 public: |
173 |
|
174 void constraints() { |
177 void constraints() { |
|
178 typedef typename _Heap::Item OwnItem; |
|
179 typedef typename _Heap::Prio OwnPrio; |
|
180 typedef typename _Heap::State OwnState; |
|
181 |
175 Item item; |
182 Item item; |
176 Prio prio; |
183 Prio prio; |
177 |
184 State state; |
178 item=Item(); |
185 item=Item(); |
179 prio=Prio(); |
186 prio=Prio(); |
180 |
|
181 ignore_unused_variable_warning(item); |
187 ignore_unused_variable_warning(item); |
182 ignore_unused_variable_warning(prio); |
188 ignore_unused_variable_warning(prio); |
183 |
|
184 typedef typename _Heap::State State; |
|
185 State state; |
|
186 |
|
187 ignore_unused_variable_warning(state); |
189 ignore_unused_variable_warning(state); |
188 |
190 |
189 _Heap heap1 = _Heap(map); |
191 OwnItem own_item; |
190 |
192 OwnPrio own_prio; |
|
193 OwnState own_state; |
|
194 own_item=Item(); |
|
195 own_prio=Prio(); |
|
196 ignore_unused_variable_warning(own_item); |
|
197 ignore_unused_variable_warning(own_prio); |
|
198 ignore_unused_variable_warning(own_state); |
|
199 |
|
200 _Heap heap1(map); |
|
201 _Heap heap2 = heap1; |
191 ignore_unused_variable_warning(heap1); |
202 ignore_unused_variable_warning(heap1); |
192 |
203 ignore_unused_variable_warning(heap2); |
193 heap.push(item, prio); |
204 |
|
205 int s = heap.size(); |
|
206 bool e = heap.empty(); |
194 |
207 |
195 prio = heap.prio(); |
208 prio = heap.prio(); |
196 item = heap.top(); |
209 item = heap.top(); |
197 |
210 prio = heap[item]; |
|
211 own_prio = heap.prio(); |
|
212 own_item = heap.top(); |
|
213 own_prio = heap[own_item]; |
|
214 |
|
215 heap.push(item, prio); |
|
216 heap.push(own_item, own_prio); |
198 heap.pop(); |
217 heap.pop(); |
199 |
218 |
200 heap.set(item, prio); |
219 heap.set(item, prio); |
201 heap.decrease(item, prio); |
220 heap.decrease(item, prio); |
202 heap.increase(item, prio); |
221 heap.increase(item, prio); |
203 prio = heap[item]; |
222 heap.set(own_item, own_prio); |
|
223 heap.decrease(own_item, own_prio); |
|
224 heap.increase(own_item, own_prio); |
204 |
225 |
205 heap.erase(item); |
226 heap.erase(item); |
|
227 heap.erase(own_item); |
|
228 heap.clear(); |
206 |
229 |
207 state = heap.state(item); |
230 state = heap.state(item); |
|
231 heap.state(item, state); |
|
232 state = heap.state(own_item); |
|
233 heap.state(own_item, own_state); |
208 |
234 |
209 state = _Heap::PRE_HEAP; |
235 state = _Heap::PRE_HEAP; |
210 state = _Heap::IN_HEAP; |
236 state = _Heap::IN_HEAP; |
211 state = _Heap::POST_HEAP; |
237 state = _Heap::POST_HEAP; |
212 |
238 own_state = _Heap::PRE_HEAP; |
213 heap.clear(); |
239 own_state = _Heap::IN_HEAP; |
|
240 own_state = _Heap::POST_HEAP; |
214 } |
241 } |
215 |
242 |
216 _Heap& heap; |
243 _Heap& heap; |
217 ItemIntMap& map; |
244 ItemIntMap& map; |
218 |
|
219 Constraints() : heap(0), map(0) {} |
|
220 }; |
245 }; |
221 }; |
246 }; |
222 |
247 |
223 /// @} |
248 /// @} |
224 } // namespace lemon |
249 } // namespace lemon |