Index: lemon/concepts/heap.h
===================================================================
 lemon/concepts/heap.h (revision 757)
+++ lemon/concepts/heap.h (revision 631)
@@ 17,11 +17,11 @@
*/
#ifndef LEMON_CONCEPTS_HEAP_H
#define LEMON_CONCEPTS_HEAP_H

///\ingroup concept
///\file
///\brief The concept of heaps.
+#ifndef LEMON_CONCEPTS_HEAP_H
+#define LEMON_CONCEPTS_HEAP_H
+
#include
#include
@@ 36,25 +36,19 @@
/// \brief The heap concept.
///
 /// This concept class describes the main interface of heaps.
 /// The various \ref heaps "heap structures" are efficient
 /// implementations of the abstract data type \e priority \e queue.
 /// They store items with specified values called \e priorities
 /// in such a way that finding and removing the item with minimum
 /// priority are efficient. The basic operations are adding and
 /// erasing items, changing the priority of an item, etc.
+ /// Concept class describing the main interface of heaps. A \e heap
+ /// is a data structure for storing items with specified values called
+ /// \e priorities in such a way that finding the item with minimum
+ /// priority is efficient. In a heap one can change the priority of an
+ /// item, add or erase an item, etc.
///
 /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
 /// Any class that conforms to this concept can be used easily in such
 /// algorithms.
 ///
 /// \tparam PR Type of the priorities of the items.
 /// \tparam IM A readwritable item map with \c int values, used
+ /// \tparam PR Type of the priority of the items.
+ /// \tparam IM A read and writable item map with int values, used
/// internally to handle the cross references.
 /// \tparam CMP A functor class for comparing the priorities.
+ /// \tparam Comp A functor class for the ordering of the priorities.
/// The default is \c std::less.
#ifdef DOXYGEN
 template
+ template >
#else
 template >
+ template
#endif
class Heap {
@@ 71,6 +65,7 @@
///
/// Each item has a state associated to it. It can be "in heap",
 /// "preheap" or "postheap". The latter two are indifferent from the
 /// heap's point of view, but may be useful to the user.
+ /// "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 itemint map must be initialized in such way that it assigns
@@ 78,58 +73,42 @@
enum State {
IN_HEAP = 0, ///< = 0. The "in heap" state constant.
 PRE_HEAP = 1, ///< = 1. The "preheap" state constant.
 POST_HEAP = 2 ///< = 2. The "postheap" state constant.
+ PRE_HEAP = 1, ///< = 1. The "pre heap" state constant.
+ POST_HEAP = 2 ///< = 2. The "post heap" state constant.
};
 /// \brief Constructor.
 ///
 /// Constructor.
+ /// \brief The constructor.
+ ///
+ /// The constructor.
/// \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 each item.
+ /// \c PRE_HEAP (1) for every item.
explicit Heap(ItemIntMap &map) {}
 /// \brief Constructor.
 ///
 /// Constructor.
 /// \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 each item.
 /// \param comp The function object used for comparing the priorities.
 explicit Heap(ItemIntMap &map, const CMP &comp) {}

/// \brief The number of items stored in the heap.
///
 /// This function returns the number of items stored in the heap.
+ /// Returns the number of items stored in the heap.
int size() const { return 0; }
 /// \brief Check if the heap is empty.
 ///
 /// This function returns \c true if the heap is empty.
+ /// \brief Checks if the heap is empty.
+ ///
+ /// Returns \c true if the heap is empty.
bool empty() const { return false; }
 /// \brief Make the heap empty.
 ///
 /// This functon makes the heap empty.
 /// It does not change the cross reference map. If you want to reuse
 /// a heap that is not surely empty, you should first clear it and
 /// then you should set the cross reference map to \c PRE_HEAP
 /// for each item.
 void clear() {}

 /// \brief Insert an item into the heap with the given priority.
 ///
 /// This function inserts the given item into the heap with the
 /// given priority.
+ /// \brief Makes the heap empty.
+ ///
+ /// Makes the heap empty.
+ void clear();
+
+ /// \brief Inserts an item into the heap with the given priority.
+ ///
+ /// Inserts the given item into the heap with the given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
 /// \pre \e i must not be stored in the heap.
void push(const Item &i, const Prio &p) {}
 /// \brief Return the item having minimum priority.
 ///
 /// This function returns the item having minimum priority.
+ /// \brief Returns the item having minimum priority.
+ ///
+ /// Returns the item having minimum priority.
/// \pre The heap must be nonempty.
Item top() const {}
@@ 137,35 +116,33 @@
/// \brief The minimum priority.
///
 /// This function returns the minimum priority.
+ /// Returns the minimum priority.
/// \pre The heap must be nonempty.
Prio prio() const {}
 /// \brief Remove the item having minimum priority.
 ///
 /// This function removes the item having minimum priority.
+ /// \brief Removes the item having minimum priority.
+ ///
+ /// Removes the item having minimum priority.
/// \pre The heap must be nonempty.
void pop() {}
 /// \brief Remove the given item from the heap.
 ///
 /// This function removes the given item from the heap if it is
 /// already stored.
+ /// \brief Removes an item from the heap.
+ ///
+ /// Removes the given item from the heap if it is already stored.
/// \param i The item to delete.
 /// \pre \e i must be in the heap.
void erase(const Item &i) {}
 /// \brief The priority of the given item.
 ///
 /// This function returns the priority of the given item.
 /// \param i The item.
 /// \pre \e i must be in the heap.
+ /// \brief The priority of an item.
+ ///
+ /// Returns the priority of the given item.
+ /// \param i The item.
+ /// \pre \c i must be in the heap.
Prio operator[](const Item &i) const {}
 /// \brief Set the priority of an item or insert it, if it is
+ /// \brief Sets the priority of an item or inserts it, if it is
/// not stored in the heap.
///
/// This method sets the priority of the given item if it is
 /// already stored in the heap. Otherwise it inserts the given
 /// item into the heap with the given priority.
+ /// already stored in the heap.
+ /// Otherwise it inserts the given item with the given priority.
///
/// \param i The item.
@@ 173,21 +150,22 @@
void set(const Item &i, const Prio &p) {}
 /// \brief Decrease the priority of an item to the given value.
 ///
 /// This function decreases the priority of an item to the given value.
+ /// \brief Decreases the priority of an item to the given value.
+ ///
+ /// Decreases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
 /// \pre \e i must be stored in the heap with priority at least \e p.
+ /// \pre \c i must be stored in the heap with priority at least \c p.
void decrease(const Item &i, const Prio &p) {}
 /// \brief Increase the priority of an item to the given value.
 ///
 /// This function increases the priority of an item to the given value.
+ /// \brief Increases the priority of an item to the given value.
+ ///
+ /// Increases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
 /// \pre \e i must be stored in the heap with priority at most \e p.
+ /// \pre \c i must be stored in the heap with priority at most \c p.
void increase(const Item &i, const Prio &p) {}
 /// \brief Return the state of an item.
+ /// \brief Returns if an item is in, has already been in, or has
+ /// never been in the heap.
///
/// This method returns \c PRE_HEAP if the given item has never
@@ 199,9 +177,9 @@
State state(const Item &i) const {}
 /// \brief Set the state of an item in the heap.
 ///
 /// This function 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 better time complexity.
+ /// \brief Sets the state of an item in the heap.
+ ///
+ /// 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.
Index: lemon/concepts/maps.h
===================================================================
 lemon/concepts/maps.h (revision 576)
+++ lemon/concepts/maps.h (revision 765)
@@ 183,5 +183,6 @@
template
struct Constraints {
 void constraints() {
+ typename enable_if::type
+ constraints() {
checkConcept, _ReferenceMap >();
ref = m[key];