COIN-OR::LEMON - Graph Library

Ignore:
Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/assert.h

    r108 r112  
    116116                                const char *assertion)
    117117  {
    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     std::cerr << std::endl;
     118    assert_fail_log(file, line, function, exception, assertion);
    125119    std::abort();
    126120  }
     
    130124                                const char *assertion)
    131125  {
    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     std::cerr << std::endl;
     126    assert_fail_log(file, line, function, message, assertion);
    139127    std::abort();
    140128  }
     
    145133                                const char *assertion)
    146134  {
    147     assert_fail_abort(file, line, function, message.c_str(), assertion);
     135    assert_fail_log(file, line, function, message.c_str(), assertion);
     136    std::abort();
    148137  }
    149138
     
    169158                                  const char *assertion)
    170159  {
    171     assert_fail_error(file, line, function, message.c_str(), assertion);
     160    throw AssertionFailedError(file, line, function, message.c_str(), assertion);
    172161  }
    173162
     
    193182                                    const char *assertion)
    194183  {
    195     assert_fail_exception(file, line, function, message.c_str(), assertion);
     184    throw AssertionFailedError(file, line, function, message.c_str(), assertion);
    196185  }
    197186
     
    209198  (defined(LEMON_ASSERT_EXCEPTION) ? 1 : 0) +           \
    210199  (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1
    211 #error "Lemon assertion system is not set properly"
     200#error "LEMON assertion system is not set properly"
    212201#endif
    213202
     
    217206     (defined(LEMON_ASSERT_EXCEPTION) ? 1 : 0) +        \
    218207     (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 ||     \
    219      defined(LEMON_ENABLE_ASSERT)) &&                   \
     208     defined(LEMON_ENABLE_ASSERTS)) &&                  \
    220209  defined(LEMON_DISABLE_ASSERTS)
    221 #error "Lemon assertion system is not set properly"
     210#error "LEMON assertion system is not set properly"
    222211#endif
    223212
     
    257246/// \ingroup exceptions
    258247///
    259 /// \brief Macro for assertions with customizable message
    260 ///
    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 /// provide information about the circumstances of failed assertion.
    268 ///
    269 /// The assertions are disabled in the default behaviour. You can
    270 /// enable the assertions with the following code:
     248/// \brief Macro for assertion with customizable message
     249///
     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.
     257///
     258/// The assertions are disabled in the default behaviour.
     259/// You can enable them with the following code:
    271260/// \code
    272261/// #define LEMON_ENABLE_ASSERTS
     
    278267/// \endcode
    279268///
    280 /// The %lemon assertion system has a wide range of customization
    281 /// properties. As default behaviour the failed assertion prints a
    282 /// short log message to the standard ouput and aborts the execution.
     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.
    283272///
    284273/// The following modes can be used in the assertion system:
    285274///
    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
    300288///   can not be thrown polymorphically), otherwise an \ref
    301289///   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:
    306294///   \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);
    313301///   \endcode
    314302///   The name of the functions should be defined as the \c
     
    318306///   \endcode
    319307///   Whenever an assertion is occured, one of the custom assertion
    320 ///   handler is called with appropiate parameters.
    321 ///
    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.
     308///   handlers is called with appropiate parameters.
     309///
     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.
    326314#  define LEMON_ASSERT(exp, msg)                                        \
    327315  (static_cast<void> (!!(exp) ? 0 : (                                   \
     
    347335
    348336#  ifndef LEMON_ASSERT_HANDLER
    349 #    define LEMON_ASSERT(exp, msg)  (static_cast<void> (0))
     337#    define LEMON_ASSERT(exp, msg)  (static_cast<void>(0))
    350338#    define LEMON_FIXME(msg) (static_cast<void>(0))
    351339#  else
  • lemon/concepts/heap.h

    r100 r113  
    1919///\ingroup concept
    2020///\file
    21 ///\brief Classes for representing heaps.
    22 ///
     21///\brief The concept of heaps.
    2322
    2423#ifndef LEMON_CONCEPT_HEAP_H
     
    2827
    2928namespace lemon {
     29
    3030  namespace concepts {
     31
    3132    /// \addtogroup concept
    3233    /// @{
    3334
    34 
    35     /// \brief A concept structure describes the main interface of heaps.
     35    /// \brief The heap concept.
    3636    ///
    37     /// A concept structure describes the main interface of heaps.
    38     ///
    39     template <typename Prio, typename ItemIntMap>
     37    /// Concept class describing the main interface of heaps.
     38    template <typename Priority, typename ItemIntMap>
    4039    class Heap {
    4140    public:
    4241
    43       ///\brief Type of the items stored in the heap.
    44       typedef typename ItemIntMap::Key  Item;
    45  
    46 
    47       /// \brief Type to represent the items states.
    48       ///
    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       /// heap's point of view, but may be useful to the user.
    52       ///
    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...
     42      /// Type of the items stored in the heap.
     43      typedef typename ItemIntMap::Key Item;
     44
     45      /// Type of the priorities.
     46      typedef Priority Prio;
     47
     48      /// \brief Type to represent the states of the items.
     49      ///
     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.
     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.
    5557      enum State {
    5658        IN_HEAP = 0,
     
    6264      ///
    6365      /// 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) {}
    6871
    6972      /// \brief The number of items stored in the heap.
     
    7275      int size() const { return 0; }
    7376
    74       /// \brief Checks if the heap stores no items.
    75       ///
    76       /// Returns \c true if and only if the heap stores no items.
     77      /// \brief Checks if the heap is empty.
     78      ///
     79      /// Returns \c true if the heap is empty.
    7780      bool empty() const { return false; }
    7881
    79       /// \brief Makes empty this heap.
    80       ///
    81       /// Makes this heap empty.
     82      /// \brief Makes the heap empty.
     83      ///
     84      /// Makes the heap empty.
    8285      void clear();
    8386
    84       /// \brief Insert an item into the heap with the given heap.
     87      /// \brief Inserts an item into the heap with the given priority.
    8588      ///   
    86       /// Adds \c i to the heap with priority \c p.
     89      /// Inserts the given item into the heap with the given priority.
    8790      /// \param i The item to insert.
    8891      /// \param p The priority of the item.
    8992      void push(const Item &i, const Prio &p) {}
    9093
    91       /// \brief Returns the item with minimum priority.
    92       ///
    93       /// This method returns the item with minimum priority. 
    94       /// \pre The heap must be nonempty. 
     94      /// \brief Returns the item having minimum priority.
     95      ///
     96      /// Returns the item having minimum priority.
     97      /// \pre The heap must be non-empty.
    9598      Item top() const {}
    9699
    97       /// \brief Returns the minimum priority.
    98       ///
    99       /// It returns the minimum priority.
    100       /// \pre The heap must be nonempty.
     100      /// \brief The minimum priority.
     101      ///
     102      /// Returns the minimum priority.
     103      /// \pre The heap must be non-empty.
    101104      Prio prio() const {}
    102105
    103       /// \brief Deletes the item with minimum priority.
    104       ///
    105       /// This method deletes the item with minimum priority.
    106       /// \pre The heap must be non-empty. 
     106      /// \brief Removes the item having minimum priority.
     107      ///
     108      /// Removes the item having minimum priority.
     109      /// \pre The heap must be non-empty.
    107110      void pop() {}
    108111
    109       /// \brief Deletes \c i from the heap.
    110       ///
    111       /// This method deletes item \c i from the heap, if \c i was
     112      /// \brief Removes an item from the heap.
     113      ///
     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
    112129      /// already stored in the heap.
    113       /// \param i The item to erase.
    114       void erase(const Item &i) {}
    115 
    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.
     130      /// Otherwise it inserts the given item with the given priority.
     131      ///
     132      /// It may throw an \ref UnderflowPriorityException.
    129133      /// \param i The item.
    130134      /// \param p The priority.
    131135      void set(const Item &i, const Prio &p) {}
    132136     
    133       /// \brief Decreases the priority of \c i to \c p.
    134       ///
    135       /// This method decreases the priority of item \c i to \c p.
     137      /// \brief Decreases the priority of an item to the given value.
     138      ///
     139      /// Decreases the priority of an item to the given value.
    136140      /// \pre \c i must be stored in the heap with priority at least \c p.
    137141      /// \param i The item.
     
    139143      void decrease(const Item &i, const Prio &p) {}
    140144
    141       /// \brief Increases the priority of \c i to \c p.
    142       ///
    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       /// p relative to \c Compare.
     145      /// \brief Increases the priority of an item to the given value.
     146      ///
     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.
    146149      /// \param i The item.
    147150      /// \param p The priority.
    148151      void increase(const Item &i, const Prio &p) {}
    149152
    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
    151154      /// never been in the heap.
    152155      ///
    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.
    157161      /// \param i The item.
    158162      State state(const Item &i) const {}
    159163
    160       /// \brief Sets the state of the \c item in the heap.
    161       ///
    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
     164      /// \brief Sets the state of an item in the heap.
     165      ///
     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
    164168      /// better time complexity.
    165169      /// \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.
    167171      void state(const Item& i, State st) {}
    168172
     
    171175      struct Constraints {
    172176      public:
    173    
    174177        void constraints() {
     178          typedef typename _Heap::Item OwnItem;
     179          typedef typename _Heap::Prio OwnPrio;
     180          typedef typename _Heap::State OwnState;
     181
    175182          Item item;
    176183          Prio prio;
    177 
     184          State state;
    178185          item=Item();
    179186          prio=Prio();
    180 
    181187          ignore_unused_variable_warning(item);
    182188          ignore_unused_variable_warning(prio);
    183 
    184           typedef typename _Heap::State State;
    185           State state;
    186 
    187189          ignore_unused_variable_warning(state);
    188      
    189           _Heap heap1 = _Heap(map);
    190 
     190
     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);
     199
     200          _Heap heap1(map);
     201          _Heap heap2 = heap1;
    191202          ignore_unused_variable_warning(heap1);
    192      
    193           heap.push(item, prio);
     203          ignore_unused_variable_warning(heap2);
     204         
     205          int s = heap.size();
     206          bool e = heap.empty();
    194207
    195208          prio = heap.prio();
    196209          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);
    198217          heap.pop();
    199218
     
    201220          heap.decrease(item, prio);
    202221          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);
    204225
    205226          heap.erase(item);
     227          heap.erase(own_item);
     228          heap.clear();
    206229
    207230          state = heap.state(item);
     231          heap.state(item, state);
     232          state = heap.state(own_item);
     233          heap.state(own_item, own_state);
    208234
    209235          state = _Heap::PRE_HEAP;
    210236          state = _Heap::IN_HEAP;
    211237          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;
    214241        }
    215    
     242
    216243        _Heap& heap;
    217244        ItemIntMap& map;
    218 
    219         Constraints() : heap(0), map(0) {}
    220245      };
    221246    };
  • lemon/concepts/maps.h

    r94 r114  
    2525///\ingroup concept
    2626///\file
    27 ///\brief Map concepts checking classes for testing and documenting.
     27///\brief The concept of maps.
    2828
    2929namespace lemon {
     
    106106        const Value& val;
    107107        const typename _WriteMap::Key& own_key;
    108         const typename _WriteMap::Value own_val;
     108        const typename _WriteMap::Value& own_val;
    109109        _WriteMap& m;
    110110      };
Note: See TracChangeset for help on using the changeset viewer.