# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1207063551 -3600
# Node ID 7b44eea654d0ae8a9fe5be301d1bf74ef7edb56e
# Parent e47fb28cda5ed878df35945a0683dfd8e0075045# Parent c837d1e449dccca2d2d64379d3e545c5fa32e792
Merge
diff -r e47fb28cda5e -r 7b44eea654d0 lemon/assert.h
--- a/lemon/assert.h Sat Mar 29 15:49:50 2008 +0000
+++ b/lemon/assert.h Tue Apr 01 16:25:51 2008 +0100
@@ -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 <typename Exception>
@@ -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 <tt>const char*</tt>, a <tt>const std::string&</tt> or
+/// a <tt>const std::exception&</tt> 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<void> (!!(exp) ? 0 : ( \
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \
@@ -346,7 +334,7 @@
#else
# ifndef LEMON_ASSERT_HANDLER
-# define LEMON_ASSERT(exp, msg) (static_cast<void> (0))
+# define LEMON_ASSERT(exp, msg) (static_cast<void>(0))
# define LEMON_FIXME(msg) (static_cast<void>(0))
# else
# define LEMON_ASSERT(exp, msg) \
diff -r e47fb28cda5e -r 7b44eea654d0 lemon/concepts/heap.h
--- a/lemon/concepts/heap.h Sat Mar 29 15:49:50 2008 +0000
+++ b/lemon/concepts/heap.h Tue Apr 01 16:25:51 2008 +0100
@@ -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 <lemon/bits/invalid.h>
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 <typename Prio, typename ItemIntMap>
+ /// Concept class describing the main interface of heaps.
+ template <typename Priority, typename ItemIntMap>
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 (<tt>-1</tt>) 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 (<tt>-1</tt>) 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 <typename _Heap>
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 -r e47fb28cda5e -r 7b44eea654d0 lemon/concepts/maps.h
--- a/lemon/concepts/maps.h Sat Mar 29 15:49:50 2008 +0000
+++ b/lemon/concepts/maps.h Tue Apr 01 16:25:51 2008 +0100
@@ -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;
};
};