1.1 --- a/lemon/assert.h Sat Mar 29 15:49:50 2008 +0000
1.2 +++ b/lemon/assert.h Tue Apr 01 16:25:51 2008 +0100
1.3 @@ -115,13 +115,7 @@
1.4 const std::exception& exception,
1.5 const char *assertion)
1.6 {
1.7 - std::cerr << file << ":" << line << ": ";
1.8 - if (function)
1.9 - std::cerr << function << ": ";
1.10 - std::cerr << exception.what();
1.11 - if (assertion)
1.12 - std::cerr << " (assertion '" << assertion << "' failed)";
1.13 - std::cerr << std::endl;
1.14 + assert_fail_log(file, line, function, exception, assertion);
1.15 std::abort();
1.16 }
1.17
1.18 @@ -129,13 +123,7 @@
1.19 const char *function, const char* message,
1.20 const char *assertion)
1.21 {
1.22 - std::cerr << file << ":" << line << ": ";
1.23 - if (function)
1.24 - std::cerr << function << ": ";
1.25 - std::cerr << message;
1.26 - if (assertion)
1.27 - std::cerr << " (assertion '" << assertion << "' failed)";
1.28 - std::cerr << std::endl;
1.29 + assert_fail_log(file, line, function, message, assertion);
1.30 std::abort();
1.31 }
1.32
1.33 @@ -144,7 +132,8 @@
1.34 const std::string& message,
1.35 const char *assertion)
1.36 {
1.37 - assert_fail_abort(file, line, function, message.c_str(), assertion);
1.38 + assert_fail_log(file, line, function, message.c_str(), assertion);
1.39 + std::abort();
1.40 }
1.41
1.42 inline void assert_fail_error(const char *file, int line,
1.43 @@ -168,7 +157,7 @@
1.44 const std::string& message,
1.45 const char *assertion)
1.46 {
1.47 - assert_fail_error(file, line, function, message.c_str(), assertion);
1.48 + throw AssertionFailedError(file, line, function, message.c_str(), assertion);
1.49 }
1.50
1.51 template <typename Exception>
1.52 @@ -192,7 +181,7 @@
1.53 const std::string& message,
1.54 const char *assertion)
1.55 {
1.56 - assert_fail_exception(file, line, function, message.c_str(), assertion);
1.57 + throw AssertionFailedError(file, line, function, message.c_str(), assertion);
1.58 }
1.59
1.60 /// @}
1.61 @@ -208,7 +197,7 @@
1.62 (defined(LEMON_ASSERT_ERROR) ? 1 : 0) + \
1.63 (defined(LEMON_ASSERT_EXCEPTION) ? 1 : 0) + \
1.64 (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1
1.65 -#error "Lemon assertion system is not set properly"
1.66 +#error "LEMON assertion system is not set properly"
1.67 #endif
1.68
1.69 #if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) + \
1.70 @@ -216,9 +205,9 @@
1.71 (defined(LEMON_ASSERT_ERROR) ? 1 : 0) + \
1.72 (defined(LEMON_ASSERT_EXCEPTION) ? 1 : 0) + \
1.73 (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 || \
1.74 - defined(LEMON_ENABLE_ASSERT)) && \
1.75 + defined(LEMON_ENABLE_ASSERTS)) && \
1.76 defined(LEMON_DISABLE_ASSERTS)
1.77 -#error "Lemon assertion system is not set properly"
1.78 +#error "LEMON assertion system is not set properly"
1.79 #endif
1.80
1.81
1.82 @@ -256,18 +245,18 @@
1.83
1.84 /// \ingroup exceptions
1.85 ///
1.86 -/// \brief Macro for assertions with customizable message
1.87 +/// \brief Macro for assertion with customizable message
1.88 ///
1.89 -/// Macro for assertions with customizable message.
1.90 -/// \param exp An expression convertible to bool. If the expression is
1.91 -/// false, then an assertion is raised. The concrete behaviour depends
1.92 -/// on the settings of the assertion system.
1.93 -/// \param msg A \e const \e char*, a \e const std::string& or a \e
1.94 -/// const \e std::exception& parameter. The variable can be used to
1.95 -/// provide information about the circumstances of failed assertion.
1.96 +/// Macro for assertion with customizable message.
1.97 +/// \param exp An expression that must be convertible to \c bool.
1.98 +/// If it is \c false, then an assertion is raised. The concrete
1.99 +/// behaviour depends on the settings of the assertion system.
1.100 +/// \param msg A <tt>const char*</tt>, a <tt>const std::string&</tt> or
1.101 +/// a <tt>const std::exception&</tt> parameter, which can be used to
1.102 +/// provide information about the circumstances of the failed assertion.
1.103 ///
1.104 -/// The assertions are disabled in the default behaviour. You can
1.105 -/// enable the assertions with the following code:
1.106 +/// The assertions are disabled in the default behaviour.
1.107 +/// You can enable them with the following code:
1.108 /// \code
1.109 /// #define LEMON_ENABLE_ASSERTS
1.110 /// \endcode
1.111 @@ -277,39 +266,38 @@
1.112 /// make CXXFLAGS='-DLEMON_ENABLE_ASSERTS'
1.113 /// \endcode
1.114 ///
1.115 -/// The %lemon assertion system has a wide range of customization
1.116 -/// properties. As default behaviour the failed assertion prints a
1.117 -/// short log message to the standard ouput and aborts the execution.
1.118 +/// The LEMON assertion system has a wide range of customization
1.119 +/// properties. As a default behaviour the failed assertion prints a
1.120 +/// short log message to the standard error and aborts the execution.
1.121 ///
1.122 /// The following modes can be used in the assertion system:
1.123 ///
1.124 -/// - \e LEMON_ASSERT_LOG The failed assert print a short convenient
1.125 -/// error message to the standard error and continues the
1.126 -/// execution.
1.127 -/// - \e LEMON_ASSERT_ABORT This mode is similar to the \e
1.128 -/// LEMON_ASSERT_LOG, but it aborts the program. It is the default
1.129 -/// operation mode when the asserts are enabled with \e
1.130 -/// LEMON_ENABLE_ASSERTS.
1.131 -/// - \e LEMON_ASSERT_ERROR The assert throws an \ref
1.132 -/// lemon::AssertionFailedError "AssertionFailedError". If the \c
1.133 -/// msg parameter is an exception, then the result of the \ref
1.134 -/// lemon::Exception::what() "what()" member function is passed as
1.135 -/// error message.
1.136 -/// - \e LEMON_ASSERT_EXCEPTION If the specified \c msg is an
1.137 -/// exception then it raised directly (solving that the exception
1.138 +/// - \c LEMON_ASSERT_LOG The failed assertion prints a short log
1.139 +/// message to the standard error and continues the execution.
1.140 +/// - \c LEMON_ASSERT_ABORT This mode is similar to the
1.141 +/// \c LEMON_ASSERT_LOG, but it aborts the program. It is the default
1.142 +/// behaviour mode when the assertions are enabled with
1.143 +/// \c LEMON_ENABLE_ASSERTS.
1.144 +/// - \c LEMON_ASSERT_ERROR The assertion throws an
1.145 +/// \ref lemon::AssertionFailedError "AssertionFailedError".
1.146 +/// If the \c msg parameter is an exception, then the result of the
1.147 +/// \ref lemon::Exception::what() "what()" member function is passed
1.148 +/// as error message.
1.149 +/// - \c LEMON_ASSERT_EXCEPTION If the specified \c msg is an
1.150 +/// exception, then it raised directly (solving that the exception
1.151 /// can not be thrown polymorphically), otherwise an \ref
1.152 /// lemon::AssertionFailedError "AssertionFailedError" is thrown with
1.153 -/// the given parameter.
1.154 -/// - \e LEMON_ASSERT_CUSTOM The user can define an own assertion
1.155 -/// handler functions. Three overloaded functions should be defined
1.156 -/// with the following parameter lists:
1.157 +/// the given parameters.
1.158 +/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler
1.159 +/// functions. Three overloaded functions should be defined with the
1.160 +/// following parameter lists:
1.161 /// \code
1.162 -/// void custom_assert_handler(const char* file, int line,
1.163 -/// const char* function, const char* message, const char* expression);
1.164 -/// void custom_assert_handler(const char* file, int line,
1.165 -/// const char* function, const std::string& message, const char* expression);
1.166 -/// void custom_assert_handler(const char* file, int line,
1.167 -/// const char* function, const std::exception& message, const char* expression);
1.168 +/// void custom_assert_handler(const char* file, int line, const char* function,
1.169 +/// const char* message, const char* assertion);
1.170 +/// void custom_assert_handler(const char* file, int line, const char* function,
1.171 +/// const std::string& message, const char* assertion);
1.172 +/// void custom_assert_handler(const char* file, int line, const char* function,
1.173 +/// const std::exception& message, const char* assertion);
1.174 /// \endcode
1.175 /// The name of the functions should be defined as the \c
1.176 /// LEMON_CUSTOM_ASSERT_HANDLER macro name.
1.177 @@ -317,12 +305,12 @@
1.178 /// #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler
1.179 /// \endcode
1.180 /// Whenever an assertion is occured, one of the custom assertion
1.181 -/// handler is called with appropiate parameters.
1.182 +/// handlers is called with appropiate parameters.
1.183 ///
1.184 -/// The assertion mode can be changed within one compilation unit, if
1.185 -/// the macros are redefined with other settings and the
1.186 -/// lemon/assert.h file is reincluded then the behaviour is changed
1.187 -/// appropiately to the new settings.
1.188 +/// The assertion mode can also be changed within one compilation unit.
1.189 +/// If the macros are redefined with other settings and the
1.190 +/// \ref lemon/assert.h "assert.h" file is reincluded, then the
1.191 +/// behaviour is changed appropiately to the new settings.
1.192 # define LEMON_ASSERT(exp, msg) \
1.193 (static_cast<void> (!!(exp) ? 0 : ( \
1.194 LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \
1.195 @@ -346,7 +334,7 @@
1.196 #else
1.197
1.198 # ifndef LEMON_ASSERT_HANDLER
1.199 -# define LEMON_ASSERT(exp, msg) (static_cast<void> (0))
1.200 +# define LEMON_ASSERT(exp, msg) (static_cast<void>(0))
1.201 # define LEMON_FIXME(msg) (static_cast<void>(0))
1.202 # else
1.203 # define LEMON_ASSERT(exp, msg) \
2.1 --- a/lemon/concepts/heap.h Sat Mar 29 15:49:50 2008 +0000
2.2 +++ b/lemon/concepts/heap.h Tue Apr 01 16:25:51 2008 +0100
2.3 @@ -18,8 +18,7 @@
2.4
2.5 ///\ingroup concept
2.6 ///\file
2.7 -///\brief Classes for representing heaps.
2.8 -///
2.9 +///\brief The concept of heaps.
2.10
2.11 #ifndef LEMON_CONCEPT_HEAP_H
2.12 #define LEMON_CONCEPT_HEAP_H
2.13 @@ -27,31 +26,34 @@
2.14 #include <lemon/bits/invalid.h>
2.15
2.16 namespace lemon {
2.17 +
2.18 namespace concepts {
2.19 +
2.20 /// \addtogroup concept
2.21 /// @{
2.22
2.23 -
2.24 - /// \brief A concept structure describes the main interface of heaps.
2.25 + /// \brief The heap concept.
2.26 ///
2.27 - /// A concept structure describes the main interface of heaps.
2.28 - ///
2.29 - template <typename Prio, typename ItemIntMap>
2.30 + /// Concept class describing the main interface of heaps.
2.31 + template <typename Priority, typename ItemIntMap>
2.32 class Heap {
2.33 public:
2.34
2.35 - ///\brief Type of the items stored in the heap.
2.36 - typedef typename ItemIntMap::Key Item;
2.37 -
2.38 + /// Type of the items stored in the heap.
2.39 + typedef typename ItemIntMap::Key Item;
2.40
2.41 - /// \brief Type to represent the items states.
2.42 + /// Type of the priorities.
2.43 + typedef Priority Prio;
2.44 +
2.45 + /// \brief Type to represent the states of the items.
2.46 ///
2.47 - /// Each Item element have a state associated to it. It may be "in heap",
2.48 - /// "pre heap" or "post heap". The later two are indifferent from the
2.49 - /// heap's point of view, but may be useful to the user.
2.50 + /// Each item has a state associated to it. It can be "in heap",
2.51 + /// "pre heap" or "post heap". The later two are indifferent
2.52 + /// from the point of view of the heap, but may be useful for
2.53 + /// the user.
2.54 ///
2.55 - /// The ItemIntMap _should_ be initialized in such way, that it maps
2.56 - /// PRE_HEAP (-1) to any element to be put in the heap...
2.57 + /// The \c ItemIntMap must be initialized in such a way, that it
2.58 + /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
2.59 enum State {
2.60 IN_HEAP = 0,
2.61 PRE_HEAP = -1,
2.62 @@ -61,162 +63,185 @@
2.63 /// \brief The constructor.
2.64 ///
2.65 /// The constructor.
2.66 - /// \param _iim should be given to the constructor, since it is used
2.67 - /// internally to handle the cross references. The value of the map
2.68 - /// should be PRE_HEAP (-1) for each element.
2.69 - explicit Heap(ItemIntMap &_iim) {}
2.70 + /// \param map A map that assigns \c int values to keys of type
2.71 + /// \c Item. It is used internally by the heap implementations to
2.72 + /// handle the cross references. The assigned value must be
2.73 + /// \c PRE_HEAP (<tt>-1</tt>) for every item.
2.74 + explicit Heap(ItemIntMap &map) {}
2.75
2.76 /// \brief The number of items stored in the heap.
2.77 ///
2.78 /// Returns the number of items stored in the heap.
2.79 int size() const { return 0; }
2.80
2.81 - /// \brief Checks if the heap stores no items.
2.82 + /// \brief Checks if the heap is empty.
2.83 ///
2.84 - /// Returns \c true if and only if the heap stores no items.
2.85 + /// Returns \c true if the heap is empty.
2.86 bool empty() const { return false; }
2.87
2.88 - /// \brief Makes empty this heap.
2.89 + /// \brief Makes the heap empty.
2.90 ///
2.91 - /// Makes this heap empty.
2.92 + /// Makes the heap empty.
2.93 void clear();
2.94
2.95 - /// \brief Insert an item into the heap with the given heap.
2.96 + /// \brief Inserts an item into the heap with the given priority.
2.97 ///
2.98 - /// Adds \c i to the heap with priority \c p.
2.99 + /// Inserts the given item into the heap with the given priority.
2.100 /// \param i The item to insert.
2.101 /// \param p The priority of the item.
2.102 void push(const Item &i, const Prio &p) {}
2.103
2.104 - /// \brief Returns the item with minimum priority.
2.105 + /// \brief Returns the item having minimum priority.
2.106 ///
2.107 - /// This method returns the item with minimum priority.
2.108 - /// \pre The heap must be nonempty.
2.109 + /// Returns the item having minimum priority.
2.110 + /// \pre The heap must be non-empty.
2.111 Item top() const {}
2.112
2.113 - /// \brief Returns the minimum priority.
2.114 + /// \brief The minimum priority.
2.115 ///
2.116 - /// It returns the minimum priority.
2.117 - /// \pre The heap must be nonempty.
2.118 + /// Returns the minimum priority.
2.119 + /// \pre The heap must be non-empty.
2.120 Prio prio() const {}
2.121
2.122 - /// \brief Deletes the item with minimum priority.
2.123 + /// \brief Removes the item having minimum priority.
2.124 ///
2.125 - /// This method deletes the item with minimum priority.
2.126 - /// \pre The heap must be non-empty.
2.127 + /// Removes the item having minimum priority.
2.128 + /// \pre The heap must be non-empty.
2.129 void pop() {}
2.130
2.131 - /// \brief Deletes \c i from the heap.
2.132 + /// \brief Removes an item from the heap.
2.133 ///
2.134 - /// This method deletes item \c i from the heap, if \c i was
2.135 - /// already stored in the heap.
2.136 - /// \param i The item to erase.
2.137 + /// Removes the given item from the heap if it is already stored.
2.138 + /// \param i The item to delete.
2.139 void erase(const Item &i) {}
2.140
2.141 - /// \brief Returns the priority of \c i.
2.142 + /// \brief The priority of an item.
2.143 ///
2.144 - /// This function returns the priority of item \c i.
2.145 + /// Returns the priority of the given item.
2.146 /// \pre \c i must be in the heap.
2.147 /// \param i The item.
2.148 Prio operator[](const Item &i) const {}
2.149
2.150 - /// \brief \c i gets to the heap with priority \c p independently
2.151 - /// if \c i was already there.
2.152 + /// \brief Sets the priority of an item or inserts it, if it is
2.153 + /// not stored in the heap.
2.154 ///
2.155 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
2.156 - /// in the heap and sets the priority of \c i to \c p otherwise.
2.157 - /// It may throw an \e UnderFlowPriorityException.
2.158 + /// This method sets the priority of the given item if it is
2.159 + /// already stored in the heap.
2.160 + /// Otherwise it inserts the given item with the given priority.
2.161 + ///
2.162 + /// It may throw an \ref UnderflowPriorityException.
2.163 /// \param i The item.
2.164 /// \param p The priority.
2.165 void set(const Item &i, const Prio &p) {}
2.166
2.167 - /// \brief Decreases the priority of \c i to \c p.
2.168 + /// \brief Decreases the priority of an item to the given value.
2.169 ///
2.170 - /// This method decreases the priority of item \c i to \c p.
2.171 + /// Decreases the priority of an item to the given value.
2.172 /// \pre \c i must be stored in the heap with priority at least \c p.
2.173 /// \param i The item.
2.174 /// \param p The priority.
2.175 void decrease(const Item &i, const Prio &p) {}
2.176
2.177 - /// \brief Increases the priority of \c i to \c p.
2.178 + /// \brief Increases the priority of an item to the given value.
2.179 ///
2.180 - /// This method sets the priority of item \c i to \c p.
2.181 - /// \pre \c i must be stored in the heap with priority at most \c
2.182 - /// p relative to \c Compare.
2.183 + /// Increases the priority of an item to the given value.
2.184 + /// \pre \c i must be stored in the heap with priority at most \c p.
2.185 /// \param i The item.
2.186 /// \param p The priority.
2.187 void increase(const Item &i, const Prio &p) {}
2.188
2.189 - /// \brief Returns if \c item is in, has already been in, or has
2.190 + /// \brief Returns if an item is in, has already been in, or has
2.191 /// never been in the heap.
2.192 ///
2.193 - /// This method returns PRE_HEAP if \c item has never been in the
2.194 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.195 - /// otherwise. In the latter case it is possible that \c item will
2.196 - /// get back to the heap again.
2.197 + /// This method returns \c PRE_HEAP if the given item has never
2.198 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
2.199 + /// and \c POST_HEAP otherwise.
2.200 + /// In the latter case it is possible that the item will get back
2.201 + /// to the heap again.
2.202 /// \param i The item.
2.203 State state(const Item &i) const {}
2.204
2.205 - /// \brief Sets the state of the \c item in the heap.
2.206 + /// \brief Sets the state of an item in the heap.
2.207 ///
2.208 - /// Sets the state of the \c item in the heap. It can be used to
2.209 - /// manually clear the heap when it is important to achive the
2.210 + /// Sets the state of the given item in the heap. It can be used
2.211 + /// to manually clear the heap when it is important to achive the
2.212 /// better time complexity.
2.213 /// \param i The item.
2.214 - /// \param st The state. It should not be \c IN_HEAP.
2.215 + /// \param st The state. It should not be \c IN_HEAP.
2.216 void state(const Item& i, State st) {}
2.217
2.218
2.219 template <typename _Heap>
2.220 struct Constraints {
2.221 public:
2.222 -
2.223 void constraints() {
2.224 + typedef typename _Heap::Item OwnItem;
2.225 + typedef typename _Heap::Prio OwnPrio;
2.226 + typedef typename _Heap::State OwnState;
2.227 +
2.228 Item item;
2.229 Prio prio;
2.230 -
2.231 + State state;
2.232 item=Item();
2.233 prio=Prio();
2.234 -
2.235 ignore_unused_variable_warning(item);
2.236 ignore_unused_variable_warning(prio);
2.237 + ignore_unused_variable_warning(state);
2.238
2.239 - typedef typename _Heap::State State;
2.240 - State state;
2.241 + OwnItem own_item;
2.242 + OwnPrio own_prio;
2.243 + OwnState own_state;
2.244 + own_item=Item();
2.245 + own_prio=Prio();
2.246 + ignore_unused_variable_warning(own_item);
2.247 + ignore_unused_variable_warning(own_prio);
2.248 + ignore_unused_variable_warning(own_state);
2.249
2.250 - ignore_unused_variable_warning(state);
2.251 -
2.252 - _Heap heap1 = _Heap(map);
2.253 -
2.254 + _Heap heap1(map);
2.255 + _Heap heap2 = heap1;
2.256 ignore_unused_variable_warning(heap1);
2.257 -
2.258 - heap.push(item, prio);
2.259 + ignore_unused_variable_warning(heap2);
2.260 +
2.261 + int s = heap.size();
2.262 + bool e = heap.empty();
2.263
2.264 prio = heap.prio();
2.265 item = heap.top();
2.266 + prio = heap[item];
2.267 + own_prio = heap.prio();
2.268 + own_item = heap.top();
2.269 + own_prio = heap[own_item];
2.270
2.271 + heap.push(item, prio);
2.272 + heap.push(own_item, own_prio);
2.273 heap.pop();
2.274
2.275 heap.set(item, prio);
2.276 heap.decrease(item, prio);
2.277 heap.increase(item, prio);
2.278 - prio = heap[item];
2.279 + heap.set(own_item, own_prio);
2.280 + heap.decrease(own_item, own_prio);
2.281 + heap.increase(own_item, own_prio);
2.282
2.283 heap.erase(item);
2.284 + heap.erase(own_item);
2.285 + heap.clear();
2.286
2.287 state = heap.state(item);
2.288 + heap.state(item, state);
2.289 + state = heap.state(own_item);
2.290 + heap.state(own_item, own_state);
2.291
2.292 state = _Heap::PRE_HEAP;
2.293 state = _Heap::IN_HEAP;
2.294 state = _Heap::POST_HEAP;
2.295 + own_state = _Heap::PRE_HEAP;
2.296 + own_state = _Heap::IN_HEAP;
2.297 + own_state = _Heap::POST_HEAP;
2.298 + }
2.299
2.300 - heap.clear();
2.301 - }
2.302 -
2.303 _Heap& heap;
2.304 ItemIntMap& map;
2.305 -
2.306 - Constraints() : heap(0), map(0) {}
2.307 };
2.308 };
2.309
3.1 --- a/lemon/concepts/maps.h Sat Mar 29 15:49:50 2008 +0000
3.2 +++ b/lemon/concepts/maps.h Tue Apr 01 16:25:51 2008 +0100
3.3 @@ -24,7 +24,7 @@
3.4
3.5 ///\ingroup concept
3.6 ///\file
3.7 -///\brief Map concepts checking classes for testing and documenting.
3.8 +///\brief The concept of maps.
3.9
3.10 namespace lemon {
3.11
3.12 @@ -105,7 +105,7 @@
3.13 const Key& key;
3.14 const Value& val;
3.15 const typename _WriteMap::Key& own_key;
3.16 - const typename _WriteMap::Value own_val;
3.17 + const typename _WriteMap::Value& own_val;
3.18 _WriteMap& m;
3.19 };
3.20 };