86 /// Constructor. |
86 /// Constructor. |
87 /// \param map A map that assigns \c int values to keys of type |
87 /// \param map A map that assigns \c int values to keys of type |
88 /// \c Item. It is used internally by the heap implementations to |
88 /// \c Item. It is used internally by the heap implementations to |
89 /// handle the cross references. The assigned value must be |
89 /// handle the cross references. The assigned value must be |
90 /// \c PRE_HEAP (<tt>-1</tt>) for each item. |
90 /// \c PRE_HEAP (<tt>-1</tt>) for each item. |
|
91 #ifdef DOXYGEN |
91 explicit Heap(ItemIntMap &map) {} |
92 explicit Heap(ItemIntMap &map) {} |
|
93 #else |
|
94 explicit Heap(ItemIntMap&) {} |
|
95 #endif |
92 |
96 |
93 /// \brief Constructor. |
97 /// \brief Constructor. |
94 /// |
98 /// |
95 /// Constructor. |
99 /// Constructor. |
96 /// \param map A map that assigns \c int values to keys of type |
100 /// \param map A map that assigns \c int values to keys of type |
97 /// \c Item. It is used internally by the heap implementations to |
101 /// \c Item. It is used internally by the heap implementations to |
98 /// handle the cross references. The assigned value must be |
102 /// handle the cross references. The assigned value must be |
99 /// \c PRE_HEAP (<tt>-1</tt>) for each item. |
103 /// \c PRE_HEAP (<tt>-1</tt>) for each item. |
100 /// \param comp The function object used for comparing the priorities. |
104 /// \param comp The function object used for comparing the priorities. |
|
105 #ifdef DOXYGEN |
101 explicit Heap(ItemIntMap &map, const CMP &comp) {} |
106 explicit Heap(ItemIntMap &map, const CMP &comp) {} |
|
107 #else |
|
108 explicit Heap(ItemIntMap&, const CMP&) {} |
|
109 #endif |
102 |
110 |
103 /// \brief The number of items stored in the heap. |
111 /// \brief The number of items stored in the heap. |
104 /// |
112 /// |
105 /// This function returns the number of items stored in the heap. |
113 /// This function returns the number of items stored in the heap. |
106 int size() const { return 0; } |
114 int size() const { return 0; } |
124 /// This function inserts the given item into the heap with the |
132 /// This function inserts the given item into the heap with the |
125 /// given priority. |
133 /// given priority. |
126 /// \param i The item to insert. |
134 /// \param i The item to insert. |
127 /// \param p The priority of the item. |
135 /// \param p The priority of the item. |
128 /// \pre \e i must not be stored in the heap. |
136 /// \pre \e i must not be stored in the heap. |
|
137 #ifdef DOXYGEN |
129 void push(const Item &i, const Prio &p) {} |
138 void push(const Item &i, const Prio &p) {} |
|
139 #else |
|
140 void push(const Item&, const Prio&) {} |
|
141 #endif |
130 |
142 |
131 /// \brief Return the item having minimum priority. |
143 /// \brief Return the item having minimum priority. |
132 /// |
144 /// |
133 /// This function returns the item having minimum priority. |
145 /// This function returns the item having minimum priority. |
134 /// \pre The heap must be non-empty. |
146 /// \pre The heap must be non-empty. |
135 Item top() const {} |
147 Item top() const { return Item(); } |
136 |
148 |
137 /// \brief The minimum priority. |
149 /// \brief The minimum priority. |
138 /// |
150 /// |
139 /// This function returns the minimum priority. |
151 /// This function returns the minimum priority. |
140 /// \pre The heap must be non-empty. |
152 /// \pre The heap must be non-empty. |
141 Prio prio() const {} |
153 Prio prio() const { return Prio(); } |
142 |
154 |
143 /// \brief Remove the item having minimum priority. |
155 /// \brief Remove the item having minimum priority. |
144 /// |
156 /// |
145 /// This function removes the item having minimum priority. |
157 /// This function removes the item having minimum priority. |
146 /// \pre The heap must be non-empty. |
158 /// \pre The heap must be non-empty. |
150 /// |
162 /// |
151 /// This function removes the given item from the heap if it is |
163 /// This function removes the given item from the heap if it is |
152 /// already stored. |
164 /// already stored. |
153 /// \param i The item to delete. |
165 /// \param i The item to delete. |
154 /// \pre \e i must be in the heap. |
166 /// \pre \e i must be in the heap. |
|
167 #ifdef DOXYGEN |
155 void erase(const Item &i) {} |
168 void erase(const Item &i) {} |
|
169 #else |
|
170 void erase(const Item&) {} |
|
171 #endif |
156 |
172 |
157 /// \brief The priority of the given item. |
173 /// \brief The priority of the given item. |
158 /// |
174 /// |
159 /// This function returns the priority of the given item. |
175 /// This function returns the priority of the given item. |
160 /// \param i The item. |
176 /// \param i The item. |
161 /// \pre \e i must be in the heap. |
177 /// \pre \e i must be in the heap. |
|
178 #ifdef DOXYGEN |
162 Prio operator[](const Item &i) const {} |
179 Prio operator[](const Item &i) const {} |
|
180 #else |
|
181 Prio operator[](const Item&) const { return Prio(); } |
|
182 #endif |
163 |
183 |
164 /// \brief Set the priority of an item or insert it, if it is |
184 /// \brief Set the priority of an item or insert it, if it is |
165 /// not stored in the heap. |
185 /// not stored in the heap. |
166 /// |
186 /// |
167 /// This method sets the priority of the given item if it is |
187 /// This method sets the priority of the given item if it is |
168 /// already stored in the heap. Otherwise it inserts the given |
188 /// already stored in the heap. Otherwise it inserts the given |
169 /// item into the heap with the given priority. |
189 /// item into the heap with the given priority. |
170 /// |
190 /// |
171 /// \param i The item. |
191 /// \param i The item. |
172 /// \param p The priority. |
192 /// \param p The priority. |
|
193 #ifdef DOXYGEN |
173 void set(const Item &i, const Prio &p) {} |
194 void set(const Item &i, const Prio &p) {} |
|
195 #else |
|
196 void set(const Item&, const Prio&) {} |
|
197 #endif |
174 |
198 |
175 /// \brief Decrease the priority of an item to the given value. |
199 /// \brief Decrease the priority of an item to the given value. |
176 /// |
200 /// |
177 /// This function decreases the priority of an item to the given value. |
201 /// This function decreases the priority of an item to the given value. |
178 /// \param i The item. |
202 /// \param i The item. |
179 /// \param p The priority. |
203 /// \param p The priority. |
180 /// \pre \e i must be stored in the heap with priority at least \e p. |
204 /// \pre \e i must be stored in the heap with priority at least \e p. |
|
205 #ifdef DOXYGEN |
181 void decrease(const Item &i, const Prio &p) {} |
206 void decrease(const Item &i, const Prio &p) {} |
|
207 #else |
|
208 void decrease(const Item&, const Prio&) {} |
|
209 #endif |
182 |
210 |
183 /// \brief Increase the priority of an item to the given value. |
211 /// \brief Increase the priority of an item to the given value. |
184 /// |
212 /// |
185 /// This function increases the priority of an item to the given value. |
213 /// This function increases the priority of an item to the given value. |
186 /// \param i The item. |
214 /// \param i The item. |
187 /// \param p The priority. |
215 /// \param p The priority. |
188 /// \pre \e i must be stored in the heap with priority at most \e p. |
216 /// \pre \e i must be stored in the heap with priority at most \e p. |
|
217 #ifdef DOXYGEN |
189 void increase(const Item &i, const Prio &p) {} |
218 void increase(const Item &i, const Prio &p) {} |
|
219 #else |
|
220 void increase(const Item&, const Prio&) {} |
|
221 #endif |
190 |
222 |
191 /// \brief Return the state of an item. |
223 /// \brief Return the state of an item. |
192 /// |
224 /// |
193 /// This method returns \c PRE_HEAP if the given item has never |
225 /// This method returns \c PRE_HEAP if the given item has never |
194 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
226 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
195 /// and \c POST_HEAP otherwise. |
227 /// and \c POST_HEAP otherwise. |
196 /// In the latter case it is possible that the item will get back |
228 /// In the latter case it is possible that the item will get back |
197 /// to the heap again. |
229 /// to the heap again. |
198 /// \param i The item. |
230 /// \param i The item. |
|
231 #ifdef DOXYGEN |
199 State state(const Item &i) const {} |
232 State state(const Item &i) const {} |
|
233 #else |
|
234 State state(const Item&) const { return PRE_HEAP; } |
|
235 #endif |
200 |
236 |
201 /// \brief Set the state of an item in the heap. |
237 /// \brief Set the state of an item in the heap. |
202 /// |
238 /// |
203 /// This function sets the state of the given item in the heap. |
239 /// This function sets the state of the given item in the heap. |
204 /// It can be used to manually clear the heap when it is important |
240 /// It can be used to manually clear the heap when it is important |
205 /// to achive better time complexity. |
241 /// to achive better time complexity. |
206 /// \param i The item. |
242 /// \param i The item. |
207 /// \param st The state. It should not be \c IN_HEAP. |
243 /// \param st The state. It should not be \c IN_HEAP. |
|
244 #ifdef DOXYGEN |
208 void state(const Item& i, State st) {} |
245 void state(const Item& i, State st) {} |
|
246 #else |
|
247 void state(const Item&, State) {} |
|
248 #endif |
209 |
249 |
210 |
250 |
211 template <typename _Heap> |
251 template <typename _Heap> |
212 struct Constraints { |
252 struct Constraints { |
213 public: |
253 public: |