1.1 --- a/lemon/concepts/heap.h	Thu Mar 05 10:13:20 2009 +0000
     1.2 +++ b/lemon/concepts/heap.h	Sun Mar 29 23:08:20 2009 +0200
     1.3 @@ -35,17 +35,32 @@
     1.4  
     1.5      /// \brief The heap concept.
     1.6      ///
     1.7 -    /// Concept class describing the main interface of heaps.
     1.8 -    template <typename Priority, typename ItemIntMap>
     1.9 +    /// Concept class describing the main interface of heaps. A \e heap
    1.10 +    /// is a data structure for storing items with specified values called
    1.11 +    /// \e priorities in such a way that finding the item with minimum
    1.12 +    /// priority is efficient. In a heap one can change the priority of an
    1.13 +    /// item, add or erase an item, etc.
    1.14 +    ///
    1.15 +    /// \tparam PR Type of the priority of the items.
    1.16 +    /// \tparam IM A read and writable item map with int values, used
    1.17 +    /// internally to handle the cross references.
    1.18 +    /// \tparam Comp A functor class for the ordering of the priorities.
    1.19 +    /// The default is \c std::less<PR>.
    1.20 +#ifdef DOXYGEN
    1.21 +    template <typename PR, typename IM, typename Comp = std::less<PR> >
    1.22 +#else
    1.23 +    template <typename PR, typename IM>
    1.24 +#endif
    1.25      class Heap {
    1.26      public:
    1.27  
    1.28 +      /// Type of the item-int map.
    1.29 +      typedef IM ItemIntMap;
    1.30 +      /// Type of the priorities.
    1.31 +      typedef PR Prio;
    1.32        /// Type of the items stored in the heap.
    1.33        typedef typename ItemIntMap::Key Item;
    1.34  
    1.35 -      /// Type of the priorities.
    1.36 -      typedef Priority Prio;
    1.37 -
    1.38        /// \brief Type to represent the states of the items.
    1.39        ///
    1.40        /// Each item has a state associated to it. It can be "in heap",
    1.41 @@ -53,12 +68,12 @@
    1.42        /// from the point of view of the heap, but may be useful for
    1.43        /// the user.
    1.44        ///
    1.45 -      /// The \c ItemIntMap must be initialized in such a way, that it
    1.46 -      /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
    1.47 +      /// The item-int map must be initialized in such way that it assigns
    1.48 +      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    1.49        enum State {
    1.50 -        IN_HEAP = 0,
    1.51 -        PRE_HEAP = -1,
    1.52 -        POST_HEAP = -2
    1.53 +        IN_HEAP = 0,    ///< The "in heap" state constant.
    1.54 +        PRE_HEAP = -1,  ///< The "pre heap" state constant.
    1.55 +        POST_HEAP = -2  ///< The "post heap" state constant.
    1.56        };
    1.57  
    1.58        /// \brief The constructor.
    1.59 @@ -119,8 +134,8 @@
    1.60        /// \brief The priority of an item.
    1.61        ///
    1.62        /// Returns the priority of the given item.
    1.63 +      /// \param i The item.
    1.64        /// \pre \c i must be in the heap.
    1.65 -      /// \param i The item.
    1.66        Prio operator[](const Item &i) const {}
    1.67  
    1.68        /// \brief Sets the priority of an item or inserts it, if it is
    1.69 @@ -137,17 +152,17 @@
    1.70        /// \brief Decreases the priority of an item to the given value.
    1.71        ///
    1.72        /// Decreases the priority of an item to the given value.
    1.73 -      /// \pre \c i must be stored in the heap with priority at least \c p.
    1.74        /// \param i The item.
    1.75        /// \param p The priority.
    1.76 +      /// \pre \c i must be stored in the heap with priority at least \c p.
    1.77        void decrease(const Item &i, const Prio &p) {}
    1.78  
    1.79        /// \brief Increases the priority of an item to the given value.
    1.80        ///
    1.81        /// Increases the priority of an item to the given value.
    1.82 -      /// \pre \c i must be stored in the heap with priority at most \c p.
    1.83        /// \param i The item.
    1.84        /// \param p The priority.
    1.85 +      /// \pre \c i must be stored in the heap with priority at most \c p.
    1.86        void increase(const Item &i, const Prio &p) {}
    1.87  
    1.88        /// \brief Returns if an item is in, has already been in, or has