# HG changeset patch # User Alpar Juttner # Date 2008-04-01 17:25:51 # Node ID 7b44eea654d0ae8a9fe5be301d1bf74ef7edb56e # Parent e47fb28cda5ed878df35945a0683dfd8e0075045 # Parent c837d1e449dccca2d2d64379d3e545c5fa32e792 Merge diff --git a/lemon/assert.h b/lemon/assert.h --- a/lemon/assert.h +++ b/lemon/assert.h @@ -115,13 +115,7 @@ const std::exception& exception, const char *assertion) { - std::cerr << file << ":" << line << ": "; - if (function) - std::cerr << function << ": "; - std::cerr << exception.what(); - if (assertion) - std::cerr << " (assertion '" << assertion << "' failed)"; - std::cerr << std::endl; + assert_fail_log(file, line, function, exception, assertion); std::abort(); } @@ -129,13 +123,7 @@ const char *function, const char* message, const char *assertion) { - std::cerr << file << ":" << line << ": "; - if (function) - std::cerr << function << ": "; - std::cerr << message; - if (assertion) - std::cerr << " (assertion '" << assertion << "' failed)"; - std::cerr << std::endl; + assert_fail_log(file, line, function, message, assertion); std::abort(); } @@ -144,7 +132,8 @@ const std::string& message, const char *assertion) { - assert_fail_abort(file, line, function, message.c_str(), assertion); + assert_fail_log(file, line, function, message.c_str(), assertion); + std::abort(); } inline void assert_fail_error(const char *file, int line, @@ -168,7 +157,7 @@ const std::string& message, const char *assertion) { - assert_fail_error(file, line, function, message.c_str(), assertion); + throw AssertionFailedError(file, line, function, message.c_str(), assertion); } template @@ -192,7 +181,7 @@ const std::string& message, const char *assertion) { - assert_fail_exception(file, line, function, message.c_str(), assertion); + throw AssertionFailedError(file, line, function, message.c_str(), assertion); } /// @} @@ -208,7 +197,7 @@ (defined(LEMON_ASSERT_ERROR) ? 1 : 0) + \ (defined(LEMON_ASSERT_EXCEPTION) ? 1 : 0) + \ (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1 -#error "Lemon assertion system is not set properly" +#error "LEMON assertion system is not set properly" #endif #if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) + \ @@ -216,9 +205,9 @@ (defined(LEMON_ASSERT_ERROR) ? 1 : 0) + \ (defined(LEMON_ASSERT_EXCEPTION) ? 1 : 0) + \ (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 || \ - defined(LEMON_ENABLE_ASSERT)) && \ + defined(LEMON_ENABLE_ASSERTS)) && \ defined(LEMON_DISABLE_ASSERTS) -#error "Lemon assertion system is not set properly" +#error "LEMON assertion system is not set properly" #endif @@ -256,18 +245,18 @@ /// \ingroup exceptions /// -/// \brief Macro for assertions with customizable message +/// \brief Macro for assertion with customizable message /// -/// Macro for assertions with customizable message. -/// \param exp An expression convertible to bool. If the expression is -/// false, then an assertion is raised. The concrete behaviour depends -/// on the settings of the assertion system. -/// \param msg A \e const \e char*, a \e const std::string& or a \e -/// const \e std::exception& parameter. The variable can be used to -/// provide information about the circumstances of failed assertion. +/// Macro for assertion with customizable message. +/// \param exp An expression that must be convertible to \c bool. +/// If it is \c false, then an assertion is raised. The concrete +/// behaviour depends on the settings of the assertion system. +/// \param msg A const char*, a const std::string& or +/// a const std::exception& parameter, which can be used to +/// provide information about the circumstances of the failed assertion. /// -/// The assertions are disabled in the default behaviour. You can -/// enable the assertions with the following code: +/// The assertions are disabled in the default behaviour. +/// You can enable them with the following code: /// \code /// #define LEMON_ENABLE_ASSERTS /// \endcode @@ -277,39 +266,38 @@ /// make CXXFLAGS='-DLEMON_ENABLE_ASSERTS' /// \endcode /// -/// The %lemon assertion system has a wide range of customization -/// properties. As default behaviour the failed assertion prints a -/// short log message to the standard ouput and aborts the execution. +/// The LEMON assertion system has a wide range of customization +/// properties. As a default behaviour the failed assertion prints a +/// short log message to the standard error and aborts the execution. /// /// The following modes can be used in the assertion system: /// -/// - \e LEMON_ASSERT_LOG The failed assert print a short convenient -/// error message to the standard error and continues the -/// execution. -/// - \e LEMON_ASSERT_ABORT This mode is similar to the \e -/// LEMON_ASSERT_LOG, but it aborts the program. It is the default -/// operation mode when the asserts are enabled with \e -/// LEMON_ENABLE_ASSERTS. -/// - \e LEMON_ASSERT_ERROR The assert throws an \ref -/// lemon::AssertionFailedError "AssertionFailedError". If the \c -/// msg parameter is an exception, then the result of the \ref -/// lemon::Exception::what() "what()" member function is passed as -/// error message. -/// - \e LEMON_ASSERT_EXCEPTION If the specified \c msg is an -/// exception then it raised directly (solving that the exception +/// - \c LEMON_ASSERT_LOG The failed assertion prints a short log +/// message to the standard error and continues the execution. +/// - \c LEMON_ASSERT_ABORT This mode is similar to the +/// \c LEMON_ASSERT_LOG, but it aborts the program. It is the default +/// behaviour mode when the assertions are enabled with +/// \c LEMON_ENABLE_ASSERTS. +/// - \c LEMON_ASSERT_ERROR The assertion throws an +/// \ref lemon::AssertionFailedError "AssertionFailedError". +/// If the \c msg parameter is an exception, then the result of the +/// \ref lemon::Exception::what() "what()" member function is passed +/// as error message. +/// - \c LEMON_ASSERT_EXCEPTION If the specified \c msg is an +/// exception, then it raised directly (solving that the exception /// can not be thrown polymorphically), otherwise an \ref /// lemon::AssertionFailedError "AssertionFailedError" is thrown with -/// the given parameter. -/// - \e LEMON_ASSERT_CUSTOM The user can define an own assertion -/// handler functions. Three overloaded functions should be defined -/// with the following parameter lists: +/// the given parameters. +/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler +/// functions. Three overloaded functions should be defined with the +/// following parameter lists: /// \code -/// void custom_assert_handler(const char* file, int line, -/// const char* function, const char* message, const char* expression); -/// void custom_assert_handler(const char* file, int line, -/// const char* function, const std::string& message, const char* expression); -/// void custom_assert_handler(const char* file, int line, -/// const char* function, const std::exception& message, const char* expression); +/// void custom_assert_handler(const char* file, int line, const char* function, +/// const char* message, const char* assertion); +/// void custom_assert_handler(const char* file, int line, const char* function, +/// const std::string& message, const char* assertion); +/// void custom_assert_handler(const char* file, int line, const char* function, +/// const std::exception& message, const char* assertion); /// \endcode /// The name of the functions should be defined as the \c /// LEMON_CUSTOM_ASSERT_HANDLER macro name. @@ -317,12 +305,12 @@ /// #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler /// \endcode /// Whenever an assertion is occured, one of the custom assertion -/// handler is called with appropiate parameters. +/// handlers is called with appropiate parameters. /// -/// The assertion mode can be changed within one compilation unit, if -/// the macros are redefined with other settings and the -/// lemon/assert.h file is reincluded then the behaviour is changed -/// appropiately to the new settings. +/// The assertion mode can also be changed within one compilation unit. +/// If the macros are redefined with other settings and the +/// \ref lemon/assert.h "assert.h" file is reincluded, then the +/// behaviour is changed appropiately to the new settings. # define LEMON_ASSERT(exp, msg) \ (static_cast (!!(exp) ? 0 : ( \ LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ @@ -346,7 +334,7 @@ #else # ifndef LEMON_ASSERT_HANDLER -# define LEMON_ASSERT(exp, msg) (static_cast (0)) +# define LEMON_ASSERT(exp, msg) (static_cast(0)) # define LEMON_FIXME(msg) (static_cast(0)) # else # define LEMON_ASSERT(exp, msg) \ diff --git a/lemon/concepts/heap.h b/lemon/concepts/heap.h --- a/lemon/concepts/heap.h +++ b/lemon/concepts/heap.h @@ -18,8 +18,7 @@ ///\ingroup concept ///\file -///\brief Classes for representing heaps. -/// +///\brief The concept of heaps. #ifndef LEMON_CONCEPT_HEAP_H #define LEMON_CONCEPT_HEAP_H @@ -27,31 +26,34 @@ #include namespace lemon { + namespace concepts { + /// \addtogroup concept /// @{ - - /// \brief A concept structure describes the main interface of heaps. + /// \brief The heap concept. /// - /// A concept structure describes the main interface of heaps. - /// - template + /// Concept class describing the main interface of heaps. + template class Heap { public: - ///\brief Type of the items stored in the heap. - typedef typename ItemIntMap::Key Item; - + /// Type of the items stored in the heap. + typedef typename ItemIntMap::Key Item; - /// \brief Type to represent the items states. + /// Type of the priorities. + typedef Priority Prio; + + /// \brief Type to represent the states of the items. /// - /// Each Item element have a state associated to it. It may be "in heap", - /// "pre heap" or "post heap". The later two are indifferent from the - /// heap's point of view, but may be useful to the user. + /// Each item has a state associated to it. It can be "in heap", + /// "pre heap" or "post heap". The later two are indifferent + /// from the point of view of the heap, but may be useful for + /// the user. /// - /// The ItemIntMap _should_ be initialized in such way, that it maps - /// PRE_HEAP (-1) to any element to be put in the heap... + /// The \c ItemIntMap must be initialized in such a way, that it + /// assigns \c PRE_HEAP (-1) to every item. enum State { IN_HEAP = 0, PRE_HEAP = -1, @@ -61,162 +63,185 @@ /// \brief The constructor. /// /// The constructor. - /// \param _iim should be given to the constructor, since it is used - /// internally to handle the cross references. The value of the map - /// should be PRE_HEAP (-1) for each element. - explicit Heap(ItemIntMap &_iim) {} + /// \param map A map that assigns \c int values to keys of type + /// \c Item. It is used internally by the heap implementations to + /// handle the cross references. The assigned value must be + /// \c PRE_HEAP (-1) for every item. + explicit Heap(ItemIntMap &map) {} /// \brief The number of items stored in the heap. /// /// Returns the number of items stored in the heap. int size() const { return 0; } - /// \brief Checks if the heap stores no items. + /// \brief Checks if the heap is empty. /// - /// Returns \c true if and only if the heap stores no items. + /// Returns \c true if the heap is empty. bool empty() const { return false; } - /// \brief Makes empty this heap. + /// \brief Makes the heap empty. /// - /// Makes this heap empty. + /// Makes the heap empty. void clear(); - /// \brief Insert an item into the heap with the given heap. + /// \brief Inserts an item into the heap with the given priority. /// - /// Adds \c i to the heap with priority \c p. + /// Inserts the given item into the heap with the given priority. /// \param i The item to insert. /// \param p The priority of the item. void push(const Item &i, const Prio &p) {} - /// \brief Returns the item with minimum priority. + /// \brief Returns the item having minimum priority. /// - /// This method returns the item with minimum priority. - /// \pre The heap must be nonempty. + /// Returns the item having minimum priority. + /// \pre The heap must be non-empty. Item top() const {} - /// \brief Returns the minimum priority. + /// \brief The minimum priority. /// - /// It returns the minimum priority. - /// \pre The heap must be nonempty. + /// Returns the minimum priority. + /// \pre The heap must be non-empty. Prio prio() const {} - /// \brief Deletes the item with minimum priority. + /// \brief Removes the item having minimum priority. /// - /// This method deletes the item with minimum priority. - /// \pre The heap must be non-empty. + /// Removes the item having minimum priority. + /// \pre The heap must be non-empty. void pop() {} - /// \brief Deletes \c i from the heap. + /// \brief Removes an item from the heap. /// - /// This method deletes item \c i from the heap, if \c i was - /// already stored in the heap. - /// \param i The item to erase. + /// Removes the given item from the heap if it is already stored. + /// \param i The item to delete. void erase(const Item &i) {} - /// \brief Returns the priority of \c i. + /// \brief The priority of an item. /// - /// This function returns the priority of item \c i. + /// Returns the priority of the given item. /// \pre \c i must be in the heap. /// \param i The item. Prio operator[](const Item &i) const {} - /// \brief \c i gets to the heap with priority \c p independently - /// if \c i was already there. + /// \brief Sets the priority of an item or inserts it, if it is + /// not stored in the heap. /// - /// This method calls \ref push(\c i, \c p) if \c i is not stored - /// in the heap and sets the priority of \c i to \c p otherwise. - /// It may throw an \e UnderFlowPriorityException. + /// This method sets the priority of the given item if it is + /// already stored in the heap. + /// Otherwise it inserts the given item with the given priority. + /// + /// It may throw an \ref UnderflowPriorityException. /// \param i The item. /// \param p The priority. void set(const Item &i, const Prio &p) {} - /// \brief Decreases the priority of \c i to \c p. + /// \brief Decreases the priority of an item to the given value. /// - /// This method decreases the priority of item \c i to \c p. + /// Decreases the priority of an item to the given value. /// \pre \c i must be stored in the heap with priority at least \c p. /// \param i The item. /// \param p The priority. void decrease(const Item &i, const Prio &p) {} - /// \brief Increases the priority of \c i to \c p. + /// \brief Increases the priority of an item to the given value. /// - /// This method sets the priority of item \c i to \c p. - /// \pre \c i must be stored in the heap with priority at most \c - /// p relative to \c Compare. + /// Increases the priority of an item to the given value. + /// \pre \c i must be stored in the heap with priority at most \c p. /// \param i The item. /// \param p The priority. void increase(const Item &i, const Prio &p) {} - /// \brief Returns if \c item is in, has already been in, or has + /// \brief Returns if an item is in, has already been in, or has /// never been in the heap. /// - /// This method returns PRE_HEAP if \c item has never been in the - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP - /// otherwise. In the latter case it is possible that \c item will - /// get back to the heap again. + /// This method returns \c PRE_HEAP if the given item has never + /// been in the heap, \c IN_HEAP if it is in the heap at the moment, + /// and \c POST_HEAP otherwise. + /// In the latter case it is possible that the item will get back + /// to the heap again. /// \param i The item. State state(const Item &i) const {} - /// \brief Sets the state of the \c item in the heap. + /// \brief Sets the state of an item in the heap. /// - /// Sets the state of the \c item in the heap. It can be used to - /// manually clear the heap when it is important to achive the + /// Sets the state of the given item in the heap. It can be used + /// to manually clear the heap when it is important to achive the /// better time complexity. /// \param i The item. - /// \param st The state. It should not be \c IN_HEAP. + /// \param st The state. It should not be \c IN_HEAP. void state(const Item& i, State st) {} template struct Constraints { public: - void constraints() { + typedef typename _Heap::Item OwnItem; + typedef typename _Heap::Prio OwnPrio; + typedef typename _Heap::State OwnState; + Item item; Prio prio; - + State state; item=Item(); prio=Prio(); - ignore_unused_variable_warning(item); ignore_unused_variable_warning(prio); + ignore_unused_variable_warning(state); - typedef typename _Heap::State State; - State state; + OwnItem own_item; + OwnPrio own_prio; + OwnState own_state; + own_item=Item(); + own_prio=Prio(); + ignore_unused_variable_warning(own_item); + ignore_unused_variable_warning(own_prio); + ignore_unused_variable_warning(own_state); - ignore_unused_variable_warning(state); - - _Heap heap1 = _Heap(map); - + _Heap heap1(map); + _Heap heap2 = heap1; ignore_unused_variable_warning(heap1); - - heap.push(item, prio); + ignore_unused_variable_warning(heap2); + + int s = heap.size(); + bool e = heap.empty(); prio = heap.prio(); item = heap.top(); + prio = heap[item]; + own_prio = heap.prio(); + own_item = heap.top(); + own_prio = heap[own_item]; + heap.push(item, prio); + heap.push(own_item, own_prio); heap.pop(); heap.set(item, prio); heap.decrease(item, prio); heap.increase(item, prio); - prio = heap[item]; + heap.set(own_item, own_prio); + heap.decrease(own_item, own_prio); + heap.increase(own_item, own_prio); heap.erase(item); + heap.erase(own_item); + heap.clear(); state = heap.state(item); + heap.state(item, state); + state = heap.state(own_item); + heap.state(own_item, own_state); state = _Heap::PRE_HEAP; state = _Heap::IN_HEAP; state = _Heap::POST_HEAP; + own_state = _Heap::PRE_HEAP; + own_state = _Heap::IN_HEAP; + own_state = _Heap::POST_HEAP; + } - heap.clear(); - } - _Heap& heap; ItemIntMap& map; - - Constraints() : heap(0), map(0) {} }; }; diff --git a/lemon/concepts/maps.h b/lemon/concepts/maps.h --- a/lemon/concepts/maps.h +++ b/lemon/concepts/maps.h @@ -24,7 +24,7 @@ ///\ingroup concept ///\file -///\brief Map concepts checking classes for testing and documenting. +///\brief The concept of maps. namespace lemon { @@ -105,7 +105,7 @@ const Key& key; const Value& val; const typename _WriteMap::Key& own_key; - const typename _WriteMap::Value own_val; + const typename _WriteMap::Value& own_val; _WriteMap& m; }; };