0
3
0
... | ... |
@@ -106,128 +106,117 @@ |
106 | 106 |
|
107 | 107 |
inline void assert_fail_log(const char *file, int line, const char *function, |
108 | 108 |
const std::string& message, const char *assertion) |
109 | 109 |
{ |
110 | 110 |
assert_fail_log(file, line, function, message.c_str(), assertion); |
111 | 111 |
} |
112 | 112 |
|
113 | 113 |
inline void assert_fail_abort(const char *file, int line, |
114 | 114 |
const char *function, |
115 | 115 |
const std::exception& exception, |
116 | 116 |
const char *assertion) |
117 | 117 |
{ |
118 |
std::cerr << file << ":" << line << ": "; |
|
119 |
if (function) |
|
120 |
std::cerr << function << ": "; |
|
121 |
std::cerr << exception.what(); |
|
122 |
if (assertion) |
|
123 |
std::cerr << " (assertion '" << assertion << "' failed)"; |
|
124 |
|
|
118 |
assert_fail_log(file, line, function, exception, assertion); |
|
125 | 119 |
std::abort(); |
126 | 120 |
} |
127 | 121 |
|
128 | 122 |
inline void assert_fail_abort(const char *file, int line, |
129 | 123 |
const char *function, const char* message, |
130 | 124 |
const char *assertion) |
131 | 125 |
{ |
132 |
std::cerr << file << ":" << line << ": "; |
|
133 |
if (function) |
|
134 |
std::cerr << function << ": "; |
|
135 |
std::cerr << message; |
|
136 |
if (assertion) |
|
137 |
std::cerr << " (assertion '" << assertion << "' failed)"; |
|
138 |
|
|
126 |
assert_fail_log(file, line, function, message, assertion); |
|
139 | 127 |
std::abort(); |
140 | 128 |
} |
141 | 129 |
|
142 | 130 |
inline void assert_fail_abort(const char *file, int line, |
143 | 131 |
const char *function, |
144 | 132 |
const std::string& message, |
145 | 133 |
const char *assertion) |
146 | 134 |
{ |
147 |
|
|
135 |
assert_fail_log(file, line, function, message.c_str(), assertion); |
|
136 |
std::abort(); |
|
148 | 137 |
} |
149 | 138 |
|
150 | 139 |
inline void assert_fail_error(const char *file, int line, |
151 | 140 |
const char *function, |
152 | 141 |
const std::exception& exception, |
153 | 142 |
const char *assertion) |
154 | 143 |
{ |
155 | 144 |
throw AssertionFailedError(file, line, function, |
156 | 145 |
exception.what(), assertion); |
157 | 146 |
} |
158 | 147 |
|
159 | 148 |
inline void assert_fail_error(const char *file, int line, |
160 | 149 |
const char *function, const char *message, |
161 | 150 |
const char *assertion) |
162 | 151 |
{ |
163 | 152 |
throw AssertionFailedError(file, line, function, message, assertion); |
164 | 153 |
} |
165 | 154 |
|
166 | 155 |
inline void assert_fail_error(const char *file, int line, |
167 | 156 |
const char *function, |
168 | 157 |
const std::string& message, |
169 | 158 |
const char *assertion) |
170 | 159 |
{ |
171 |
|
|
160 |
throw AssertionFailedError(file, line, function, message.c_str(), assertion); |
|
172 | 161 |
} |
173 | 162 |
|
174 | 163 |
template <typename Exception> |
175 | 164 |
inline void assert_fail_exception(const char *, int, const char *, |
176 | 165 |
const Exception& exception, |
177 | 166 |
const char *, const std::exception* = |
178 | 167 |
static_cast<const Exception*>(0)) |
179 | 168 |
{ |
180 | 169 |
throw exception; |
181 | 170 |
} |
182 | 171 |
|
183 | 172 |
inline void assert_fail_exception(const char *file, int line, |
184 | 173 |
const char *function, const char *message, |
185 | 174 |
const char *assertion) |
186 | 175 |
{ |
187 | 176 |
throw AssertionFailedError(file, line, function, message, assertion); |
188 | 177 |
} |
189 | 178 |
|
190 | 179 |
inline void assert_fail_exception(const char *file, int line, |
191 | 180 |
const char *function, |
192 | 181 |
const std::string& message, |
193 | 182 |
const char *assertion) |
194 | 183 |
{ |
195 |
|
|
184 |
throw AssertionFailedError(file, line, function, message.c_str(), assertion); |
|
196 | 185 |
} |
197 | 186 |
|
198 | 187 |
/// @} |
199 | 188 |
|
200 | 189 |
} |
201 | 190 |
#endif // LEMON_ASSERT_H |
202 | 191 |
|
203 | 192 |
#undef LEMON_ASSERT |
204 | 193 |
#undef LEMON_FIXME |
205 | 194 |
|
206 | 195 |
#if (defined(LEMON_ASSERT_LOG) ? 1 : 0) + \ |
207 | 196 |
(defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
208 | 197 |
(defined(LEMON_ASSERT_ERROR) ? 1 : 0) + \ |
209 | 198 |
(defined(LEMON_ASSERT_EXCEPTION) ? 1 : 0) + \ |
210 | 199 |
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1 |
211 |
#error " |
|
200 |
#error "LEMON assertion system is not set properly" |
|
212 | 201 |
#endif |
213 | 202 |
|
214 | 203 |
#if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) + \ |
215 | 204 |
(defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
216 | 205 |
(defined(LEMON_ASSERT_ERROR) ? 1 : 0) + \ |
217 | 206 |
(defined(LEMON_ASSERT_EXCEPTION) ? 1 : 0) + \ |
218 | 207 |
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 || \ |
219 |
defined( |
|
208 |
defined(LEMON_ENABLE_ASSERTS)) && \ |
|
220 | 209 |
defined(LEMON_DISABLE_ASSERTS) |
221 |
#error " |
|
210 |
#error "LEMON assertion system is not set properly" |
|
222 | 211 |
#endif |
223 | 212 |
|
224 | 213 |
|
225 | 214 |
#if defined LEMON_ASSERT_LOG |
226 | 215 |
# undef LEMON_ASSERT_HANDLER |
227 | 216 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log |
228 | 217 |
#elif defined LEMON_ASSERT_ABORT |
229 | 218 |
# undef LEMON_ASSERT_HANDLER |
230 | 219 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort |
231 | 220 |
#elif defined LEMON_ASSERT_ERROR |
232 | 221 |
# undef LEMON_ASSERT_HANDLER |
233 | 222 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_error |
... | ... |
@@ -247,91 +236,90 @@ |
247 | 236 |
# undef LEMON_ASSERT_HANDLER |
248 | 237 |
#endif |
249 | 238 |
|
250 | 239 |
|
251 | 240 |
#ifndef LEMON_FUNCTION_NAME |
252 | 241 |
# define LEMON_FUNCTION_NAME (__PRETTY_FUNCTION__) |
253 | 242 |
#endif |
254 | 243 |
|
255 | 244 |
#ifdef DOXYGEN |
256 | 245 |
|
257 | 246 |
/// \ingroup exceptions |
258 | 247 |
/// |
259 |
/// \brief Macro for |
|
248 |
/// \brief Macro for assertion with customizable message |
|
260 | 249 |
/// |
261 |
/// Macro for assertions with customizable message. |
|
262 |
/// \param exp An expression convertible to bool. If the expression is |
|
263 |
/// false, then an assertion is raised. The concrete behaviour depends |
|
264 |
/// on the settings of the assertion system. |
|
265 |
/// \param msg A \e const \e char*, a \e const std::string& or a \e |
|
266 |
/// const \e std::exception& parameter. The variable can be used to |
|
267 |
/// |
|
250 |
/// Macro for assertion with customizable message. |
|
251 |
/// \param exp An expression that must be convertible to \c bool. |
|
252 |
/// If it is \c false, then an assertion is raised. The concrete |
|
253 |
/// behaviour depends on the settings of the assertion system. |
|
254 |
/// \param msg A <tt>const char*</tt>, a <tt>const std::string&</tt> or |
|
255 |
/// a <tt>const std::exception&</tt> parameter, which can be used to |
|
256 |
/// provide information about the circumstances of the failed assertion. |
|
268 | 257 |
/// |
269 |
/// The assertions are disabled in the default behaviour. You can |
|
270 |
/// enable the assertions with the following code: |
|
258 |
/// The assertions are disabled in the default behaviour. |
|
259 |
/// You can enable them with the following code: |
|
271 | 260 |
/// \code |
272 | 261 |
/// #define LEMON_ENABLE_ASSERTS |
273 | 262 |
/// \endcode |
274 | 263 |
/// or with compilation parameters: |
275 | 264 |
/// \code |
276 | 265 |
/// g++ -DLEMON_ENABLE_ASSERTS |
277 | 266 |
/// make CXXFLAGS='-DLEMON_ENABLE_ASSERTS' |
278 | 267 |
/// \endcode |
279 | 268 |
/// |
280 |
/// The %lemon assertion system has a wide range of customization |
|
281 |
/// properties. As default behaviour the failed assertion prints a |
|
282 |
/// |
|
269 |
/// The LEMON assertion system has a wide range of customization |
|
270 |
/// properties. As a default behaviour the failed assertion prints a |
|
271 |
/// short log message to the standard error and aborts the execution. |
|
283 | 272 |
/// |
284 | 273 |
/// The following modes can be used in the assertion system: |
285 | 274 |
/// |
286 |
/// - \e LEMON_ASSERT_LOG The failed assert print a short convenient |
|
287 |
/// error message to the standard error and continues the |
|
288 |
/// execution. |
|
289 |
/// - \e LEMON_ASSERT_ABORT This mode is similar to the \e |
|
290 |
/// LEMON_ASSERT_LOG, but it aborts the program. It is the default |
|
291 |
/// operation mode when the asserts are enabled with \e |
|
292 |
/// LEMON_ENABLE_ASSERTS. |
|
293 |
/// - \e LEMON_ASSERT_ERROR The assert throws an \ref |
|
294 |
/// lemon::AssertionFailedError "AssertionFailedError". If the \c |
|
295 |
/// msg parameter is an exception, then the result of the \ref |
|
296 |
/// lemon::Exception::what() "what()" member function is passed as |
|
297 |
/// error message. |
|
298 |
/// - \e LEMON_ASSERT_EXCEPTION If the specified \c msg is an |
|
299 |
/// exception then it raised directly (solving that the exception |
|
275 |
/// - \c LEMON_ASSERT_LOG The failed assertion prints a short log |
|
276 |
/// message to the standard error and continues the execution. |
|
277 |
/// - \c LEMON_ASSERT_ABORT This mode is similar to the |
|
278 |
/// \c LEMON_ASSERT_LOG, but it aborts the program. It is the default |
|
279 |
/// behaviour mode when the assertions are enabled with |
|
280 |
/// \c LEMON_ENABLE_ASSERTS. |
|
281 |
/// - \c LEMON_ASSERT_ERROR The assertion throws an |
|
282 |
/// \ref lemon::AssertionFailedError "AssertionFailedError". |
|
283 |
/// If the \c msg parameter is an exception, then the result of the |
|
284 |
/// \ref lemon::Exception::what() "what()" member function is passed |
|
285 |
/// as error message. |
|
286 |
/// - \c LEMON_ASSERT_EXCEPTION If the specified \c msg is an |
|
287 |
/// exception, then it raised directly (solving that the exception |
|
300 | 288 |
/// can not be thrown polymorphically), otherwise an \ref |
301 | 289 |
/// lemon::AssertionFailedError "AssertionFailedError" is thrown with |
302 |
/// the given parameter. |
|
303 |
/// - \e LEMON_ASSERT_CUSTOM The user can define an own assertion |
|
304 |
/// handler functions. Three overloaded functions should be defined |
|
305 |
/// with the following parameter lists: |
|
290 |
/// the given parameters. |
|
291 |
/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler |
|
292 |
/// functions. Three overloaded functions should be defined with the |
|
293 |
/// following parameter lists: |
|
306 | 294 |
/// \code |
307 |
/// void custom_assert_handler(const char* file, int line, |
|
308 |
/// const char* function, const char* message, const char* expression); |
|
309 |
/// void custom_assert_handler(const char* file, int line, |
|
310 |
/// const char* function, const std::string& message, const char* expression); |
|
311 |
/// void custom_assert_handler(const char* file, int line, |
|
312 |
/// const char* function, const std::exception& message, const char* expression); |
|
295 |
/// void custom_assert_handler(const char* file, int line, const char* function, |
|
296 |
/// const char* message, const char* assertion); |
|
297 |
/// void custom_assert_handler(const char* file, int line, const char* function, |
|
298 |
/// const std::string& message, const char* assertion); |
|
299 |
/// void custom_assert_handler(const char* file, int line, const char* function, |
|
300 |
/// const std::exception& message, const char* assertion); |
|
313 | 301 |
/// \endcode |
314 | 302 |
/// The name of the functions should be defined as the \c |
315 | 303 |
/// LEMON_CUSTOM_ASSERT_HANDLER macro name. |
316 | 304 |
/// \code |
317 | 305 |
/// #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler |
318 | 306 |
/// \endcode |
319 | 307 |
/// Whenever an assertion is occured, one of the custom assertion |
320 |
/// |
|
308 |
/// handlers is called with appropiate parameters. |
|
321 | 309 |
/// |
322 |
/// The assertion mode can be changed within one compilation unit, if |
|
323 |
/// the macros are redefined with other settings and the |
|
324 |
/// lemon/assert.h file is reincluded then the behaviour is changed |
|
325 |
/// appropiately to the new settings. |
|
310 |
/// The assertion mode can also be changed within one compilation unit. |
|
311 |
/// If the macros are redefined with other settings and the |
|
312 |
/// \ref lemon/assert.h "assert.h" file is reincluded, then the |
|
313 |
/// behaviour is changed appropiately to the new settings. |
|
326 | 314 |
# define LEMON_ASSERT(exp, msg) \ |
327 | 315 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
328 | 316 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
329 | 317 |
LEMON_FUNCTION_NAME, \ |
330 | 318 |
msg, #exp), 0))) |
331 | 319 |
|
332 | 320 |
|
333 | 321 |
/// \ingroup exceptions |
334 | 322 |
/// |
335 | 323 |
/// \brief Macro for mark not yet implemented features. |
336 | 324 |
/// |
337 | 325 |
/// Macro for mark not yet implemented features and outstanding bugs. |
... | ... |
@@ -9,218 +9,243 @@ |
9 | 9 |
* Permission to use, modify and distribute this software is granted |
10 | 10 |
* provided that this copyright notice appears in all copies. For |
11 | 11 |
* precise terms see the accompanying LICENSE file. |
12 | 12 |
* |
13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
14 | 14 |
* express or implied, and with no claim as to its suitability for any |
15 | 15 |
* purpose. |
16 | 16 |
* |
17 | 17 |
*/ |
18 | 18 |
|
19 | 19 |
///\ingroup concept |
20 | 20 |
///\file |
21 |
///\brief Classes for representing heaps. |
|
22 |
/// |
|
21 |
///\brief The concept of heaps. |
|
23 | 22 |
|
24 | 23 |
#ifndef LEMON_CONCEPT_HEAP_H |
25 | 24 |
#define LEMON_CONCEPT_HEAP_H |
26 | 25 |
|
27 | 26 |
#include <lemon/bits/invalid.h> |
28 | 27 |
|
29 | 28 |
namespace lemon { |
29 |
|
|
30 | 30 |
namespace concepts { |
31 |
|
|
31 | 32 |
/// \addtogroup concept |
32 | 33 |
/// @{ |
33 | 34 |
|
34 |
|
|
35 |
/// \brief A concept structure describes the main interface of heaps. |
|
35 |
/// \brief The heap concept. |
|
36 | 36 |
/// |
37 |
/// A concept structure describes the main interface of heaps. |
|
38 |
/// |
|
39 |
|
|
37 |
/// Concept class describing the main interface of heaps. |
|
38 |
template <typename Priority, typename ItemIntMap> |
|
40 | 39 |
class Heap { |
41 | 40 |
public: |
42 | 41 |
|
43 |
/// |
|
42 |
/// Type of the items stored in the heap. |
|
44 | 43 |
typedef typename ItemIntMap::Key Item; |
45 | 44 |
|
45 |
/// Type of the priorities. |
|
46 |
typedef Priority Prio; |
|
46 | 47 |
|
47 |
/// \brief Type to represent the |
|
48 |
/// \brief Type to represent the states of the items. |
|
48 | 49 |
/// |
49 |
/// Each Item element have a state associated to it. It may be "in heap", |
|
50 |
/// "pre heap" or "post heap". The later two are indifferent from the |
|
51 |
/// |
|
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 |
|
52 |
/// from the point of view of the heap, but may be useful for |
|
53 |
/// the user. |
|
52 | 54 |
/// |
53 |
/// The ItemIntMap _should_ be initialized in such way, that it maps |
|
54 |
/// PRE_HEAP (-1) to any element to be put in the heap... |
|
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 | 57 |
enum State { |
56 | 58 |
IN_HEAP = 0, |
57 | 59 |
PRE_HEAP = -1, |
58 | 60 |
POST_HEAP = -2 |
59 | 61 |
}; |
60 | 62 |
|
61 | 63 |
/// \brief The constructor. |
62 | 64 |
/// |
63 | 65 |
/// The constructor. |
64 |
/// \param _iim should be given to the constructor, since it is used |
|
65 |
/// internally to handle the cross references. The value of the map |
|
66 |
/// should be PRE_HEAP (-1) for each element. |
|
67 |
explicit Heap(ItemIntMap &_iim) {} |
|
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 |
|
68 |
/// handle the cross references. The assigned value must be |
|
69 |
/// \c PRE_HEAP (<tt>-1</tt>) for every item. |
|
70 |
explicit Heap(ItemIntMap &map) {} |
|
68 | 71 |
|
69 | 72 |
/// \brief The number of items stored in the heap. |
70 | 73 |
/// |
71 | 74 |
/// Returns the number of items stored in the heap. |
72 | 75 |
int size() const { return 0; } |
73 | 76 |
|
74 |
/// \brief Checks if the heap |
|
77 |
/// \brief Checks if the heap is empty. |
|
75 | 78 |
/// |
76 |
/// Returns \c true if |
|
79 |
/// Returns \c true if the heap is empty. |
|
77 | 80 |
bool empty() const { return false; } |
78 | 81 |
|
79 |
/// \brief Makes |
|
82 |
/// \brief Makes the heap empty. |
|
80 | 83 |
/// |
81 |
/// Makes |
|
84 |
/// Makes the heap empty. |
|
82 | 85 |
void clear(); |
83 | 86 |
|
84 |
/// \brief |
|
87 |
/// \brief Inserts an item into the heap with the given priority. |
|
85 | 88 |
/// |
86 |
/// |
|
89 |
/// Inserts the given item into the heap with the given priority. |
|
87 | 90 |
/// \param i The item to insert. |
88 | 91 |
/// \param p The priority of the item. |
89 | 92 |
void push(const Item &i, const Prio &p) {} |
90 | 93 |
|
91 |
/// \brief Returns the item |
|
94 |
/// \brief Returns the item having minimum priority. |
|
92 | 95 |
/// |
93 |
/// This method returns the item with minimum priority. |
|
94 |
/// \pre The heap must be nonempty. |
|
96 |
/// Returns the item having minimum priority. |
|
97 |
/// \pre The heap must be non-empty. |
|
95 | 98 |
Item top() const {} |
96 | 99 |
|
97 |
/// \brief |
|
100 |
/// \brief The minimum priority. |
|
98 | 101 |
/// |
99 |
/// It returns the minimum priority. |
|
100 |
/// \pre The heap must be nonempty. |
|
102 |
/// Returns the minimum priority. |
|
103 |
/// \pre The heap must be non-empty. |
|
101 | 104 |
Prio prio() const {} |
102 | 105 |
|
103 |
/// \brief |
|
106 |
/// \brief Removes the item having minimum priority. |
|
104 | 107 |
/// |
105 |
/// |
|
108 |
/// Removes the item having minimum priority. |
|
106 | 109 |
/// \pre The heap must be non-empty. |
107 | 110 |
void pop() {} |
108 | 111 |
|
109 |
/// \brief |
|
112 |
/// \brief Removes an item from the heap. |
|
110 | 113 |
/// |
111 |
/// This method deletes item \c i from the heap, if \c i was |
|
112 |
/// already stored in the heap. |
|
113 |
/// |
|
114 |
/// Removes the given item from the heap if it is already stored. |
|
115 |
/// \param i The item to delete. |
|
114 | 116 |
void erase(const Item &i) {} |
115 | 117 |
|
116 |
/// \brief |
|
118 |
/// \brief The priority of an item. |
|
117 | 119 |
/// |
118 |
/// |
|
120 |
/// Returns the priority of the given item. |
|
119 | 121 |
/// \pre \c i must be in the heap. |
120 | 122 |
/// \param i The item. |
121 | 123 |
Prio operator[](const Item &i) const {} |
122 | 124 |
|
123 |
/// \brief \c i gets to the heap with priority \c p independently |
|
124 |
/// if \c i was already there. |
|
125 |
/// \brief Sets the priority of an item or inserts it, if it is |
|
126 |
/// not stored in the heap. |
|
125 | 127 |
/// |
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 |
/// |
|
128 |
/// This method sets the priority of the given item if it is |
|
129 |
/// already stored in the heap. |
|
130 |
/// Otherwise it inserts the given item with the given priority. |
|
131 |
/// |
|
132 |
/// It may throw an \ref UnderflowPriorityException. |
|
129 | 133 |
/// \param i The item. |
130 | 134 |
/// \param p The priority. |
131 | 135 |
void set(const Item &i, const Prio &p) {} |
132 | 136 |
|
133 |
/// \brief Decreases the priority of |
|
137 |
/// \brief Decreases the priority of an item to the given value. |
|
134 | 138 |
/// |
135 |
/// |
|
139 |
/// Decreases the priority of an item to the given value. |
|
136 | 140 |
/// \pre \c i must be stored in the heap with priority at least \c p. |
137 | 141 |
/// \param i The item. |
138 | 142 |
/// \param p The priority. |
139 | 143 |
void decrease(const Item &i, const Prio &p) {} |
140 | 144 |
|
141 |
/// \brief Increases the priority of |
|
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. |
|
144 |
/// \pre \c i must be stored in the heap with priority at most \c |
|
145 |
/// |
|
147 |
/// Increases the priority of an item to the given value. |
|
148 |
/// \pre \c i must be stored in the heap with priority at most \c p. |
|
146 | 149 |
/// \param i The item. |
147 | 150 |
/// \param p The priority. |
148 | 151 |
void increase(const Item &i, const Prio &p) {} |
149 | 152 |
|
150 |
/// \brief Returns if |
|
153 |
/// \brief Returns if an item is in, has already been in, or has |
|
151 | 154 |
/// never been in the heap. |
152 | 155 |
/// |
153 |
/// This method returns PRE_HEAP if \c item has never been in the |
|
154 |
/// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
155 |
/// otherwise. In the latter case it is possible that \c item will |
|
156 |
/// get back to the heap again. |
|
156 |
/// This method returns \c PRE_HEAP if the given item has never |
|
157 |
/// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
|
158 |
/// and \c POST_HEAP otherwise. |
|
159 |
/// In the latter case it is possible that the item will get back |
|
160 |
/// to the heap again. |
|
157 | 161 |
/// \param i The item. |
158 | 162 |
State state(const Item &i) const {} |
159 | 163 |
|
160 |
/// \brief Sets the state of |
|
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 |
|
163 |
/// manually clear the heap when it is important to achive the |
|
166 |
/// Sets the state of the given item in the heap. It can be used |
|
167 |
/// to manually clear the heap when it is important to achive the |
|
164 | 168 |
/// better time complexity. |
165 | 169 |
/// \param i The item. |
166 | 170 |
/// \param st The state. It should not be \c IN_HEAP. |
167 | 171 |
void state(const Item& i, State st) {} |
168 | 172 |
|
169 | 173 |
|
170 | 174 |
template <typename _Heap> |
171 | 175 |
struct Constraints { |
172 | 176 |
public: |
177 |
void constraints() { |
|
178 |
typedef typename _Heap::Item OwnItem; |
|
179 |
typedef typename _Heap::Prio OwnPrio; |
|
180 |
typedef typename _Heap::State OwnState; |
|
173 | 181 |
|
174 |
void constraints() { |
|
175 | 182 |
Item item; |
176 | 183 |
Prio prio; |
177 |
|
|
184 |
State state; |
|
178 | 185 |
item=Item(); |
179 | 186 |
prio=Prio(); |
180 |
|
|
181 | 187 |
ignore_unused_variable_warning(item); |
182 | 188 |
ignore_unused_variable_warning(prio); |
183 |
|
|
184 |
typedef typename _Heap::State State; |
|
185 |
State state; |
|
186 |
|
|
187 | 189 |
ignore_unused_variable_warning(state); |
188 | 190 |
|
189 |
|
|
191 |
OwnItem own_item; |
|
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); |
|
190 | 199 |
|
200 |
_Heap heap1(map); |
|
201 |
_Heap heap2 = heap1; |
|
191 | 202 |
ignore_unused_variable_warning(heap1); |
203 |
ignore_unused_variable_warning(heap2); |
|
192 | 204 |
|
193 |
heap. |
|
205 |
int s = heap.size(); |
|
206 |
bool e = heap.empty(); |
|
194 | 207 |
|
195 | 208 |
prio = heap.prio(); |
196 | 209 |
item = heap.top(); |
210 |
prio = heap[item]; |
|
211 |
own_prio = heap.prio(); |
|
212 |
own_item = heap.top(); |
|
213 |
own_prio = heap[own_item]; |
|
197 | 214 |
|
215 |
heap.push(item, prio); |
|
216 |
heap.push(own_item, own_prio); |
|
198 | 217 |
heap.pop(); |
199 | 218 |
|
200 | 219 |
heap.set(item, prio); |
201 | 220 |
heap.decrease(item, prio); |
202 | 221 |
heap.increase(item, prio); |
203 |
|
|
222 |
heap.set(own_item, own_prio); |
|
223 |
heap.decrease(own_item, own_prio); |
|
224 |
heap.increase(own_item, own_prio); |
|
204 | 225 |
|
205 | 226 |
heap.erase(item); |
227 |
heap.erase(own_item); |
|
228 |
heap.clear(); |
|
206 | 229 |
|
207 | 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 | 235 |
state = _Heap::PRE_HEAP; |
210 | 236 |
state = _Heap::IN_HEAP; |
211 | 237 |
state = _Heap::POST_HEAP; |
212 |
|
|
213 |
heap.clear(); |
|
238 |
own_state = _Heap::PRE_HEAP; |
|
239 |
own_state = _Heap::IN_HEAP; |
|
240 |
own_state = _Heap::POST_HEAP; |
|
214 | 241 |
} |
215 | 242 |
|
216 | 243 |
_Heap& heap; |
217 | 244 |
ItemIntMap& map; |
218 |
|
|
219 |
Constraints() : heap(0), map(0) {} |
|
220 | 245 |
}; |
221 | 246 |
}; |
222 | 247 |
|
223 | 248 |
/// @} |
224 | 249 |
} // namespace lemon |
225 | 250 |
} |
226 | 251 |
#endif // LEMON_CONCEPT_PATH_H |
... | ... |
@@ -15,25 +15,25 @@ |
15 | 15 |
* purpose. |
16 | 16 |
* |
17 | 17 |
*/ |
18 | 18 |
|
19 | 19 |
#ifndef LEMON_CONCEPT_MAPS_H |
20 | 20 |
#define LEMON_CONCEPT_MAPS_H |
21 | 21 |
|
22 | 22 |
#include <lemon/bits/utility.h> |
23 | 23 |
#include <lemon/concept_check.h> |
24 | 24 |
|
25 | 25 |
///\ingroup concept |
26 | 26 |
///\file |
27 |
///\brief |
|
27 |
///\brief The concept of maps. |
|
28 | 28 |
|
29 | 29 |
namespace lemon { |
30 | 30 |
|
31 | 31 |
namespace concepts { |
32 | 32 |
|
33 | 33 |
/// \addtogroup concept |
34 | 34 |
/// @{ |
35 | 35 |
|
36 | 36 |
/// Readable map concept |
37 | 37 |
|
38 | 38 |
/// Readable map concept. |
39 | 39 |
/// |
... | ... |
@@ -96,25 +96,25 @@ |
96 | 96 |
void constraints() { |
97 | 97 |
m.set(key, val); |
98 | 98 |
m.set(own_key, own_val); |
99 | 99 |
|
100 | 100 |
ignore_unused_variable_warning(key); |
101 | 101 |
ignore_unused_variable_warning(val); |
102 | 102 |
ignore_unused_variable_warning(own_key); |
103 | 103 |
ignore_unused_variable_warning(own_val); |
104 | 104 |
} |
105 | 105 |
const Key& key; |
106 | 106 |
const Value& val; |
107 | 107 |
const typename _WriteMap::Key& own_key; |
108 |
const typename _WriteMap::Value own_val; |
|
108 |
const typename _WriteMap::Value& own_val; |
|
109 | 109 |
_WriteMap& m; |
110 | 110 |
}; |
111 | 111 |
}; |
112 | 112 |
|
113 | 113 |
/// Read/writable map concept |
114 | 114 |
|
115 | 115 |
/// Read/writable map concept. |
116 | 116 |
/// |
117 | 117 |
template<typename K, typename T> |
118 | 118 |
class ReadWriteMap : public ReadMap<K,T>, |
119 | 119 |
public WriteMap<K,T> |
120 | 120 |
{ |
0 comments (0 inline)