LEMON/LEMON-official Changeset - r756:0747f332c478

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r756:0747f332c478

« 730:9f529a

757:f1fe0d »

r756:0747f332c478

Wed, 08 Jul 2009 17:21:30

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Improve and unify the documentation of heaps (#299) and avoid a warning in SimpleBucketHeap::operator[].

0 5 0

default

5 files changed with 558 insertions and 497 deletions:

lemon/bin_heap.h

lemon/bucket_heap.h

158

131

lemon/concepts/heap.h

lemon/fib_heap.h

120

113

lemon/radix_heap.h

111

106

↑ Collapse diff ↑

lemon/bin_heap.h

Show inline comments

@@ -23,3 +23,3 @@
 		///\file
-		///\brief Binary Heap implementation.
+		///\brief Binary heap implementation.
@@ -33,39 +33,35 @@
 		  ///
-		  ///\brief A Binary Heap implementation.
+		  /// \brief Binary heap data structure.
 		  ///
 		  ///This class implements the \e binary \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  ///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. \c CMP specifies the ordering of the priorities.
 		  ///In a heap one can change the priority of an item, add or erase an
 		  ///item, etc.
 		  ///
 		  ///\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 the ordering of the priorities.
 		  /// \tparam PR Type of the priorities of the items.
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam CMP A functor class for comparing the priorities.
 		  ///The default is \c std::less<PR>.
 		  ///
 		  ///\sa FibHeap
-		  ///\sa Dijkstra
+		#ifdef DOXYGEN
 		  template <typename PR, typename IM, typename CMP>
 		#else
 		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		  class BinHeap {
 		  public:
 		  public:
 		    ///\e
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
-		    ///\e
+		    /// Type of the priorities.
 		    typedef PR Prio;
-		    ///\e
+		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
-		    ///\e
+		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
-		    ///\e
+		    /// Functor type for comparing the priorities.
 		    typedef CMP Compare;
-		    /// \brief Type to represent the items states.
+		    /// \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 latter two are indifferent from the
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
@@ -86,18 +82,18 @@
 		  public:
-		    /// \brief The constructor.
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor.
 		    /// \param map should be given to the constructor, since it is used
 		    /// internally to handle the cross references. The value of the map
 		    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
-		    /// \brief The constructor.
+		    /// \brief Constructor.
 		    ///
 		    /// The constructor.
 		    /// \param map 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.
 		    ///
 		    /// \param comp The comparator function object.
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param comp The function object used for comparing the priorities.
 		    BinHeap(ItemIntMap &map, const Compare &comp)
@@ -106,18 +102,19 @@
 		    /// The number of items stored in the heap.
+		    /// \brief The number of items stored in the heap.
 		    ///
-		    /// \brief Returns the number of items stored in the heap.
+		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
-		    /// \brief Checks if the heap stores no items.
+		    /// \brief Check if the heap is empty.
 		    ///
-		    /// Returns \c true if and only if the heap stores no items.
+		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _data.empty(); }
-		    /// \brief Make empty this heap.
+		    /// \brief Make the heap empty.
 		    ///
 		    /// Make empty this heap. It does not change the cross reference map.
 		    /// If you want to reuse what is not surely empty you should first clear
 		    /// the heap and after that you should set the cross reference map for
 		    /// each item to \c PRE_HEAP.
 		    /// 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() {
@@ -173,6 +170,9 @@
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
-		    /// Adds \c p.first to the heap with priority \c p.second.
+		    /// This function inserts \c p.first to the heap with priority
 		    /// \c p.second.
 		    /// \param p The pair to insert.
 		    /// \pre \c p.first must not be stored in the heap.
 		    void push(const Pair &p) {
@@ -183,14 +183,15 @@
-		    /// \brief Insert an item into the heap with the given heap.
+		    /// \brief Insert an item into the heap with the given priority.
 		    ///
-		    /// Adds \c i to the heap with priority \c p.
+		    /// This function 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) { push(Pair(i,p)); }
-		    /// \brief Returns the item with minimum priority relative to \c Compare.
+		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority relative to \c
 		    /// Compare.
-		    /// \pre The heap must be nonempty.
+		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
@@ -199,6 +200,6 @@
-		    /// \brief Returns the minimum priority relative to \c Compare.
+		    /// \brief The minimum priority.
 		    ///
 		    /// It returns the minimum priority relative to \c Compare.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
@@ -207,6 +208,5 @@
-		    /// \brief Deletes the item with minimum priority relative to \c Compare.
+		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This method deletes the item with minimum priority relative to \c
 		    /// Compare from the heap.
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
@@ -221,7 +221,8 @@
-		    /// \brief Deletes \c i from the heap.
+		    /// \brief Remove the given item from the heap.
 		    ///
 		    /// This method deletes item \c i from the heap.
 		    /// \param i The item to erase.
-		    /// \pre The item should be in the heap.
+		    /// This function 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) {
@@ -238,8 +239,7 @@
 		    /// \brief Returns the priority of \c i.
 		    /// \brief The priority of the given item.
 		    ///
-		    /// This function returns the priority of item \c i.
+		    /// This function returns the priority of the given item.
 		    /// \param i The item.
-		    /// \pre \c i must be in the heap.
+		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
@@ -249,7 +249,8 @@
 		    /// \brief \c i gets to the heap with priority \c p independently
 		    /// if \c i was already there.
 		    /// \brief Set the priority of an item or insert 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.
 		    /// 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.
 		    /// \param i The item.
@@ -269,9 +270,8 @@
-		    /// \brief Decreases the priority of \c i to \c p.
+		    /// \brief Decrease the priority of an item to the given value.
 		    ///
-		    /// This method decreases the priority of item \c i to \c p.
+		    /// This function decreases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \c i must be stored in the heap with priority at least \c
 		    /// p relative to \c Compare.
 		    /// \pre \e i must be stored in the heap with priority at least \e p.
 		    void decrease(const Item &i, const Prio &p) {
@@ -281,9 +281,8 @@
-		    /// \brief Increases the priority of \c i to \c p.
+		    /// \brief Increase the priority of an item to the given value.
 		    ///
-		    /// This method sets the priority of item \c i to \c p.
+		    /// This function increases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \c i must be stored in the heap with priority at most \c
 		    /// p relative to \c Compare.
 		    /// \pre \e i must be stored in the heap with priority at most \e p.
 		    void increase(const Item &i, const Prio &p) {
@@ -293,9 +292,9 @@
 		    /// \brief Returns if \c item is in, has already been in, or has
 		    /// never been in the heap.
 		    /// \brief Return the state of an item.
 		    ///
 		    /// 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.
@@ -308,7 +307,7 @@
-		    /// \brief Sets the state of the \c item in the heap.
+		    /// \brief Set 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
-		    /// better time complexity.
+		    /// 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.
 		    /// \param i The item.
@@ -329,8 +328,9 @@
-		    /// \brief Replaces an item in the heap.
+		    /// \brief Replace an item in the heap.
 		    ///
 		    /// The \c i item is replaced with \c j item. The \c i item should
 		    /// be in the heap, while the \c j should be out of the heap. The
 		    /// \c i item will out of the heap and \c j will be in the heap
 		    /// with the same prioriority as prevoiusly the \c i item.
 		    /// This function replaces item \c i with item \c j.
 		    /// Item \c i must be in the heap, while \c j must be out of the heap.
 		    /// After calling this method, item \c i will be out of the
 		    /// heap and \c j will be in the heap with the same prioriority
 		    /// as item \c i had before.
 		    void replace(const Item& i, const Item& j) {

lemon/bucket_heap.h

Show inline comments

@@ -23,3 +23,3 @@
 		///\file
-		///\brief Bucket Heap implementation.
+		///\brief Bucket heap implementation.
@@ -57,17 +57,22 @@
 		  ///
-		  /// \brief A Bucket Heap implementation.
+		  /// \brief Bucket heap data structure.
 		  ///
 		  /// This class implements the \e bucket \e heap data structure. 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. The bucket heap is very simple implementation, it can store
 		  /// only integer priorities and it stores for each priority in the
 		  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
-		  /// the priorities are small. It is not intended to use as dijkstra heap.
+		  /// This class implements the \e bucket \e heap data structure.
 		  /// It practically conforms to the \ref concepts::Heap "heap concept",
 		  /// but it has some limitations.
 		  ///
 		  /// \param IM A read and write Item int map, used internally
 		  /// to handle the cross references.
 		  /// \param MIN If the given parameter is false then instead of the
 		  /// minimum value the maximum can be retrivied with the top() and
-		  /// prio() member functions.
+		  /// The bucket heap is a very simple structure. It can store only
 		  /// \c int priorities and it maintains a list of items for each priority
 		  /// in the range <tt>[0..C)</tt>. So it should only be used when the
 		  /// priorities are small. It is not intended to use as a Dijkstra heap.
 		  ///
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
 		  /// The default is \e min-heap. If this parameter is set to \c false,
 		  /// then the comparison is reversed, so the top(), prio() and pop()
 		  /// functions deal with the item having maximum priority instead of the
 		  /// minimum.
 		  ///
 		  /// \sa SimpleBucketHeap
 		  template <typename IM, bool MIN = true>
@@ -76,10 +81,11 @@
 		  public:
 		    /// \e
 		    typedef typename IM::Key Item;
-		    /// \e
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
-		    /// \e
+		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item, Prio> Pair;
 		    /// \e
 		    typedef IM ItemIntMap;
@@ -91,6 +97,6 @@
-		    /// \brief Type to represent the items states.
+		    /// \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 latter two are indifferent from the
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
@@ -106,26 +112,28 @@
 		  public:
-		    /// \brief The constructor.
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor.
 		    /// \param map 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.
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
 		    /// The number of items stored in the heap.
+		    /// \brief The number of items stored in the heap.
 		    ///
-		    /// \brief Returns the number of items stored in the heap.
+		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
-		    /// \brief Checks if the heap stores no items.
+		    /// \brief Check if the heap is empty.
 		    ///
-		    /// Returns \c true if and only if the heap stores no items.
+		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _data.empty(); }
-		    /// \brief Make empty this heap.
+		    /// \brief Make the heap empty.
 		    ///
 		    /// Make empty this heap. It does not change the cross reference
 		    /// map.  If you want to reuse a heap what is not surely empty you
 		    /// should first clear the heap and after that you should set the
 		    /// cross reference map for each item to \c PRE_HEAP.
 		    /// 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() {
@@ -176,6 +184,9 @@
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
-		    /// Adds \c p.first to the heap with priority \c p.second.
+		    /// This function inserts \c p.first to the heap with priority
 		    /// \c p.second.
 		    /// \param p The pair to insert.
 		    /// \pre \c p.first must not be stored in the heap.
 		    void push(const Pair& p) {
@@ -186,5 +197,7 @@
 		    ///
-		    /// Adds \c i to the heap with priority \c p.
+		    /// This function 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) {
@@ -199,6 +212,6 @@
-		    /// \brief Returns the item with minimum priority.
+		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
@@ -210,6 +223,6 @@
-		    /// \brief Returns the minimum priority.
+		    /// \brief The minimum priority.
 		    ///
 		    /// It returns the minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
@@ -221,5 +234,5 @@
-		    /// \brief Deletes the item with minimum priority.
+		    /// \brief Remove the item having minimum priority.
 		    ///
-		    /// This method deletes the item with minimum priority from the heap.
+		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
@@ -235,7 +248,8 @@
-		    /// \brief Deletes \c i from the heap.
+		    /// \brief Remove the given 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.
+		    /// This function 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) {
@@ -247,8 +261,7 @@
 		    /// \brief Returns the priority of \c i.
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of item \c i.
 		    /// \pre \c i must be in the heap.
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
@@ -258,7 +271,8 @@
 		    /// \brief \c i gets to the heap with priority \c p independently
 		    /// if \c i was already there.
 		    /// \brief Set the priority of an item or insert 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.
 		    /// 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.
 		    /// \param i The item.
@@ -276,9 +290,8 @@
-		    /// \brief Decreases the priority of \c i to \c p.
+		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This method decreases the priority of item \c i to \c p.
 		    /// \pre \c i must be stored in the heap with priority at least \c
-		    /// p relative to \c Compare.
+		    /// This function 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.
 		    void decrease(const Item &i, const Prio &p) {
@@ -293,9 +306,8 @@
-		    /// \brief Increases the priority of \c i to \c p.
+		    /// \brief Increase 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.
+		    /// This function 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.
 		    void increase(const Item &i, const Prio &p) {
@@ -307,9 +319,9 @@
 		    /// \brief Returns if \c item is in, has already been in, or has
 		    /// never been in the heap.
 		    /// \brief Return the state of an item.
 		    ///
 		    /// 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.
@@ -321,7 +333,7 @@
-		    /// \brief Sets the state of the \c item in the heap.
+		    /// \brief Set 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
-		    /// better time complexity.
+		    /// 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.
 		    /// \param i The item.
@@ -363,17 +375,23 @@
 		  ///
-		  /// \brief A Simplified Bucket Heap implementation.
+		  /// \brief Simplified bucket heap data structure.
 		  ///
 		  /// This class implements a simplified \e bucket \e heap data
 		  /// structure.  It does not provide some functionality but it faster
 		  /// and simplier data structure than the BucketHeap. The main
 		  /// difference is that the BucketHeap stores for every key a double
 		  /// linked list while this class stores just simple lists. In the
 		  /// other way it does not support erasing each elements just the
 		  /// minimal and it does not supports key increasing, decreasing.
 		  /// structure. It does not provide some functionality, but it is
 		  /// faster and simpler than BucketHeap. The main difference is
 		  /// that BucketHeap stores a doubly-linked list for each key while
 		  /// this class stores only simply-linked lists. It supports erasing
 		  /// only for the item having minimum priority and it does not support
 		  /// key increasing and decreasing.
 		  ///
 		  /// \param IM A read and write Item int map, used internally
 		  /// to handle the cross references.
 		  /// \param MIN If the given parameter is false then instead of the
 		  /// minimum value the maximum can be retrivied with the top() and
-		  /// prio() member functions.
+		  /// Note that this implementation does not conform to the
 		  /// \ref concepts::Heap "heap concept" due to the lack of some
 		  /// functionality.
 		  ///
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
 		  /// The default is \e min-heap. If this parameter is set to \c false,
 		  /// then the comparison is reversed, so the top(), prio() and pop()
 		  /// functions deal with the item having maximum priority instead of the
 		  /// minimum.
 		  ///
@@ -384,6 +402,11 @@
 		  public:
-		    typedef typename IM::Key Item;
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item, Prio> Pair;
 		    typedef IM ItemIntMap;
@@ -395,6 +418,6 @@
-		    /// \brief Type to represent the items states.
+		    /// \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 latter two are indifferent from the
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
@@ -411,8 +434,8 @@
-		    /// \brief The constructor.
+		    /// \brief Constructor.
 		    ///
 		    /// The constructor.
 		    /// \param map 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.
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    explicit SimpleBucketHeap(ItemIntMap &map)
@@ -420,18 +443,19 @@
-		    /// \brief Returns the number of items stored in the heap.
+		    /// \brief The number of items stored in the heap.
 		    ///
-		    /// The number of items stored in the heap.
+		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _num; }
-		    /// \brief Checks if the heap stores no items.
+		    /// \brief Check if the heap is empty.
 		    ///
-		    /// Returns \c true if and only if the heap stores no items.
+		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _num == 0; }
-		    /// \brief Make empty this heap.
+		    /// \brief Make the heap empty.
 		    ///
 		    /// Make empty this heap. It does not change the cross reference
 		    /// map.  If you want to reuse a heap what is not surely empty you
 		    /// should first clear the heap and after that you should set the
 		    /// cross reference map for each item to \c PRE_HEAP.
 		    /// 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() {
@@ -442,4 +466,6 @@
 		    ///
-		    /// Adds \c p.first to the heap with priority \c p.second.
+		    /// This function inserts \c p.first to the heap with priority
 		    /// \c p.second.
 		    /// \param p The pair to insert.
 		    /// \pre \c p.first must not be stored in the heap.
 		    void push(const Pair& p) {
@@ -450,5 +476,7 @@
 		    ///
-		    /// Adds \c i to the heap with priority \c p.
+		    /// This function 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) {
@@ -473,6 +501,6 @@
-		    /// \brief Returns the item with minimum priority.
+		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
@@ -484,6 +512,6 @@
-		    /// \brief Returns the minimum priority.
+		    /// \brief The minimum priority.
 		    ///
 		    /// It returns the minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
@@ -495,5 +523,5 @@
-		    /// \brief Deletes the item with minimum priority.
+		    /// \brief Remove the item having minimum priority.
 		    ///
-		    /// This method deletes the item with minimum priority from the heap.
+		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
@@ -511,12 +539,11 @@
-		    /// \brief Returns the priority of \c i.
+		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of item \c i.
 		    /// \warning This operator is not a constant time function
 		    /// because it scans the whole data structure to find the proper
 		    /// value.
-		    /// \pre \c i must be in the heap.
+		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    /// \warning This operator is not a constant time function because
 		    /// it scans the whole data structure to find the proper value.
 		    Prio operator[](const Item &i) const {
 		      for (int k = 0; k < _first.size(); ++k) {
+		      for (int k = 0; k < int(_first.size()); ++k) {
 		        int idx = _first[k];
@@ -532,9 +559,9 @@
 		    /// \brief Returns if \c item is in, has already been in, or has
 		    /// never been in the heap.
 		    /// \brief Return the state of an item.
 		    ///
 		    /// 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.

lemon/concepts/heap.h

Show inline comments

@@ -18,2 +18,5 @@
 		#ifndef LEMON_CONCEPTS_HEAP_H
 		#define LEMON_CONCEPTS_HEAP_H
 		///\ingroup concept
@@ -22,5 +25,2 @@
 		#ifndef LEMON_CONCEPTS_HEAP_H
 		#define LEMON_CONCEPTS_HEAP_H
 		#include <lemon/core.h>
@@ -37,17 +37,23 @@
 		    ///
 		    /// 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.
+		    /// This concept class describes the main interface of heaps.
 		    /// The various 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.
 		    ///
 		    /// \tparam PR Type of the priority of the items.
 		    /// \tparam IM A read and writable item map with int values, used
 		    /// 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 read-writable item map with \c int values, used
 		    /// internally to handle the cross references.
-		    /// \tparam Comp A functor class for the ordering of the priorities.
+		    /// \tparam CMP A functor class for comparing the priorities.
 		    /// The default is \c std::less<PR>.
 		#ifdef DOXYGEN
-		    template <typename PR, typename IM, typename Comp = std::less<PR> >
+		    template <typename PR, typename IM, typename CMP>
 		#else
 		    template <typename PR, typename IM>
+		    template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
@@ -66,5 +72,4 @@
 		      /// 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.
+		      /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		      /// heap's point of view, but may be useful to the user.
 		      ///
@@ -74,9 +79,9 @@
 		        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
 		        PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
 		        POST_HEAP = -2  ///< = -2. The "post heap" state constant.
 		        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
 		        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
 		      };
-		      /// \brief The constructor.
+		      /// \brief Constructor.
 		      ///
-		      /// The constructor.
+		      /// Constructor.
 		      /// \param map A map that assigns \c int values to keys of type
@@ -84,30 +89,46 @@
 		      /// handle the cross references. The assigned value must be
-		      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
+		      /// \c PRE_HEAP (<tt>-1</tt>) for each 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 (<tt>-1</tt>) 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.
 		      ///
-		      /// Returns the number of items stored in the heap.
+		      /// This function returns the number of items stored in the heap.
 		      int size() const { return 0; }
-		      /// \brief Checks if the heap is empty.
+		      /// \brief Check if the heap is empty.
 		      ///
-		      /// Returns \c true if the heap is empty.
+		      /// This function returns \c true if the heap is empty.
 		      bool empty() const { return false; }
-		      /// \brief Makes the heap empty.
+		      /// \brief Make the heap empty.
 		      ///
 		      /// Makes the heap empty.
 		      void clear();
 		      /// 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 Inserts an item into the heap with the given priority.
+		      /// \brief Insert an item into the heap with the given priority.
 		      ///
-		      /// Inserts the given item into the heap with the given priority.
+		      /// This function 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 Returns the item having minimum priority.
+		      /// \brief Return the item having minimum priority.
 		      ///
-		      /// Returns the item having minimum priority.
+		      /// This function returns the item having minimum priority.
 		      /// \pre The heap must be non-empty.
@@ -117,3 +138,3 @@
 		      ///
-		      /// Returns the minimum priority.
+		      /// This function returns the minimum priority.
 		      /// \pre The heap must be non-empty.
@@ -121,5 +142,5 @@
-		      /// \brief Removes the item having minimum priority.
+		      /// \brief Remove the item having minimum priority.
 		      ///
-		      /// Removes the item having minimum priority.
+		      /// This function removes the item having minimum priority.
 		      /// \pre The heap must be non-empty.
@@ -127,16 +148,18 @@
-		      /// \brief Removes an item from the heap.
+		      /// \brief Remove the given item from the heap.
 		      ///
-		      /// Removes the given item from the heap if it is already stored.
+		      /// This function 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 an item.
+		      /// \brief The priority of the given item.
 		      ///
-		      /// Returns the priority of the given item.
+		      /// This function returns the priority of the given item.
 		      /// \param i The item.
-		      /// \pre \c i must be in the heap.
+		      /// \pre \e i must be in the heap.
 		      Prio operator[](const Item &i) const {}
-		      /// \brief Sets the priority of an item or inserts it, if it is
+		      /// \brief Set the priority of an item or insert it, if it is
 		      /// not stored in the heap.
@@ -144,4 +167,4 @@
 		      /// 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.
 		      /// already stored in the heap. Otherwise it inserts the given
 		      /// item into the heap with the given priority.
 		      ///
@@ -151,20 +174,19 @@
-		      /// \brief Decreases the priority of an item to the given value.
+		      /// \brief Decrease the priority of an item to the given value.
 		      ///
-		      /// Decreases the priority of an item to the given value.
+		      /// This function decreases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
-		      /// \pre \c i must be stored in the heap with priority at least \c p.
+		      /// \pre \e i must be stored in the heap with priority at least \e p.
 		      void decrease(const Item &i, const Prio &p) {}
-		      /// \brief Increases the priority of an item to the given value.
+		      /// \brief Increase the priority of an item to the given value.
 		      ///
-		      /// Increases the priority of an item to the given value.
+		      /// This function increases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
-		      /// \pre \c i must be stored in the heap with priority at most \c p.
+		      /// \pre \e i must be stored in the heap with priority at most \e p.
 		      void increase(const Item &i, const Prio &p) {}
 		      /// \brief Returns if an item is in, has already been in, or has
 		      /// never been in the heap.
 		      /// \brief Return the state of an item.
 		      ///
@@ -178,7 +200,7 @@
-		      /// \brief Sets the state of an item in the heap.
+		      /// \brief Set 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.
+		      /// 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.
 		      /// \param i The item.

lemon/fib_heap.h

Show inline comments

@@ -23,5 +23,6 @@
 		///\ingroup auxdat
-		///\brief Fibonacci Heap implementation.
+		///\brief Fibonacci heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
@@ -33,26 +34,20 @@
 		  ///
-		  ///\brief Fibonacci Heap.
+		  /// \brief Fibonacci heap data structure.
 		  ///
 		  ///This class implements the \e Fibonacci \e heap data structure. 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. \c CMP specifies the ordering of the priorities. In a heap
-		  ///one can change the priority of an item, add or erase an item, etc.
+		  /// This class implements the \e Fibonacci \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
 		  ///heap. In case of many calls to these operations, it is better to use a
-		  ///\ref BinHeap "binary heap".
+		  /// The methods \ref increase() and \ref erase() are not efficient in a
 		  /// Fibonacci heap. In case of many calls of these operations, it is
 		  /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
 		  ///
 		  ///\param PRIO Type of the priority of the items.
 		  ///\param IM A read and writable Item int map, used internally
 		  ///to handle the cross references.
 		  ///\param CMP A class for the ordering of the priorities. The
 		  ///default is \c std::less<PRIO>.
 		  ///
 		  ///\sa BinHeap
 		  ///\sa Dijkstra
 		  /// \tparam PR Type of the priorities of the items.
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam CMP A functor class for comparing the priorities.
 		  /// The default is \c std::less<PR>.
 		#ifdef DOXYGEN
-		  template <typename PRIO, typename IM, typename CMP>
+		  template <typename PR, typename IM, typename CMP>
 		#else
-		  template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
+		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
@@ -60,11 +55,12 @@
 		  public:
-		    ///\e
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    ///\e
 		    typedef PRIO Prio;
-		    ///\e
+		    /// Type of the priorities.
 		    typedef PR Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
-		    ///\e
+		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
-		    ///\e
+		    /// Functor type for comparing the priorities.
 		    typedef CMP Compare;
@@ -82,6 +78,6 @@
-		    /// \brief Type to represent the items states.
+		    /// \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 latter two are indifferent from the
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
@@ -96,6 +92,8 @@
-		    /// \brief The constructor
+		    /// \brief Constructor.
 		    ///
 		    /// \c map should be given to the constructor, since it is
 		    ///   used internally to handle the cross references.
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    explicit FibHeap(ItemIntMap &map)
@@ -103,7 +101,9 @@
-		    /// \brief The constructor
+		    /// \brief Constructor.
 		    ///
 		    /// \c map should be given to the constructor, since it is used
 		    /// internally to handle the cross references. \c comp is an
-		    /// object for ordering of the priorities.
+		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param comp The function object used for comparing the priorities.
 		    FibHeap(ItemIntMap &map, const Compare &comp)
@@ -113,16 +113,17 @@
 		    ///
-		    /// Returns the number of items stored in the heap.
+		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _num; }
-		    /// \brief Checks if the heap stores no items.
+		    /// \brief Check if the heap is empty.
 		    ///
-		    ///   Returns \c true if and only if the heap stores no items.
+		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _num==0; }
-		    /// \brief Make empty this heap.
+		    /// \brief Make the heap empty.
 		    ///
 		    /// Make empty this heap. It does not change the cross reference
 		    /// map.  If you want to reuse a heap what is not surely empty you
 		    /// should first clear the heap and after that you should set the
 		    /// cross reference map for each item to \c PRE_HEAP.
 		    /// 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() {
@@ -131,21 +132,10 @@
 		    /// \brief \c item gets to the heap with priority \c value independently
 		    /// if \c item was already there.
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// This method calls \ref push(\c item, \c value) if \c item is not
 		    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
 		    /// \ref increase(\c item, \c value) otherwise.
 		    void set (const Item& item, const Prio& value) {
 		      int i=_iim[item];
 		      if ( i >= 0 && _data[i].in ) {
 		        if ( _comp(value, _data[i].prio) ) decrease(item, value);
 		        if ( _comp(_data[i].prio, value) ) increase(item, value);
 		      } else push(item, value);
+		    }
 		    /// \brief Adds \c item to the heap with priority \c value.
 		    ///
 		    /// Adds \c item to the heap with priority \c value.
 		    /// \pre \c item must not be stored in the heap.
 		    void push (const Item& item, const Prio& value) {
 		    /// This function inserts the given item into the heap with the
 		    /// given priority.
 		    /// \param item The item to insert.
 		    /// \param prio The priority of the item.
 		    /// \pre \e item must not be stored in the heap.
 		    void push (const Item& item, const Prio& prio) {
 		      int i=_iim[item];
@@ -170,3 +160,3 @@
 		        _data[i].left_neighbor=_minimum;
-		        if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
+		        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
 		      } else {
@@ -175,3 +165,3 @@
+		      }
-		      _data[i].prio=value;
+		      _data[i].prio=prio;
 		      ++_num;
@@ -179,27 +169,17 @@
-		    /// \brief Returns the item with minimum priority relative to \c Compare.
+		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority relative to \c
 		    /// Compare.
-		    /// \pre The heap must be nonempty.
+		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const { return _data[_minimum].name; }
-		    /// \brief Returns the minimum priority relative to \c Compare.
+		    /// \brief The minimum priority.
 		    ///
 		    /// It returns the minimum priority relative to \c Compare.
 		    /// \pre The heap must be nonempty.
-		    const Prio& prio() const { return _data[_minimum].prio; }
+		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const { return _data[_minimum].prio; }
-		    /// \brief Returns the priority of \c item.
+		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// It returns the priority of \c item.
 		    /// \pre \c item must be in the heap.
 		    const Prio& operator[](const Item& item) const {
 		      return _data[_iim[item]].prio;
+		    }
 		    /// \brief Deletes the item with minimum priority relative to \c Compare.
 		    ///
 		    /// This method deletes the item with minimum priority relative to \c
 		    /// Compare from the heap.
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
@@ -236,6 +216,8 @@
-		    /// \brief Deletes \c item from the heap.
+		    /// \brief Remove the given item from the heap.
 		    ///
 		    /// This method deletes \c item from the heap, if \c item was already
 		    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
 		    /// This function removes the given item from the heap if it is
 		    /// already stored.
 		    /// \param item The item to delete.
 		    /// \pre \e item must be in the heap.
 		    void erase (const Item& item) {
@@ -254,13 +236,39 @@
-		    /// \brief Decreases the priority of \c item to \c value.
+		    /// \brief The priority of the given item.
 		    ///
 		    /// This method decreases the priority of \c item to \c value.
 		    /// \pre \c item must be stored in the heap with priority at least \c
 		    ///   value relative to \c Compare.
 		    void decrease (Item item, const Prio& value) {
 		    /// This function returns the priority of the given item.
 		    /// \param item The item.
 		    /// \pre \e item must be in the heap.
 		    Prio operator[](const Item& item) const {
 		      return _data[_iim[item]].prio;
+		    }
 		    /// \brief Set the priority of an item or insert 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.
 		    /// \param item The item.
 		    /// \param prio The priority.
 		    void set (const Item& item, const Prio& prio) {
 		      int i=_iim[item];
-		      _data[i].prio=value;
+		      if ( i >= 0 && _data[i].in ) {
 		        if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
 		        if ( _comp(_data[i].prio, prio) ) increase(item, prio);
 		      } else push(item, prio);
+		    }
 		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This function decreases the priority of an item to the given value.
 		    /// \param item The item.
 		    /// \param prio The priority.
 		    /// \pre \e item must be stored in the heap with priority at least \e prio.
 		    void decrease (const Item& item, const Prio& prio) {
 		      int i=_iim[item];
 		      _data[i].prio=prio;
 		      int p=_data[i].parent;
-		      if ( p!=-1 && _comp(value, _data[p].prio) ) {
+		      if ( p!=-1 && _comp(prio, _data[p].prio) ) {
 		        cut(i,p);
@@ -268,25 +276,24 @@
+		      }
-		      if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
+		      if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
+		    }
-		    /// \brief Increases the priority of \c item to \c value.
+		    /// \brief Increase the priority of an item to the given value.
 		    ///
 		    /// This method sets the priority of \c item to \c value. Though
 		    /// there is no precondition on the priority of \c item, this
 		    /// method should be used only if it is indeed necessary to increase
 		    /// (relative to \c Compare) the priority of \c item, because this
 		    /// method is inefficient.
 		    void increase (Item item, const Prio& value) {
 		    /// This function increases the priority of an item to the given value.
 		    /// \param item The item.
 		    /// \param prio The priority.
 		    /// \pre \e item must be stored in the heap with priority at most \e prio.
 		    void increase (const Item& item, const Prio& prio) {
 		      erase(item);
-		      push(item, value);
+		      push(item, prio);
+		    }
 		    /// \brief Returns if \c item is in, has already been in, or has never
-		    /// been in the heap.
+		    /// \brief Return the state of an item.
 		    ///
 		    /// 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 item The item.
 		    State state(const Item &item) const {
@@ -300,7 +307,7 @@
-		    /// \brief Sets the state of the \c item in the heap.
+		    /// \brief Set 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
-		    /// better time _complexity.
+		    /// 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.
 		    /// \param i The item.

lemon/radix_heap.h

Show inline comments

@@ -23,3 +23,3 @@
 		///\file
-		///\brief Radix Heap implementation.
+		///\brief Radix heap implementation.
@@ -31,19 +31,14 @@
-		  /// \ingroup auxdata
+		  /// \ingroup auxdat
 		  ///
-		  /// \brief A Radix Heap implementation.
+		  /// \brief Radix heap data structure.
 		  ///
 		  /// This class implements the \e radix \e heap data structure. 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. This heap type can store only items with \e int priority.
 		  /// In a heap one can change the priority of an item, add or erase an
 		  /// item, but the priority cannot be decreased under the last removed
-		  /// item's priority.
+		  /// This class implements the \e radix \e heap data structure.
 		  /// It practically conforms to the \ref concepts::Heap "heap concept",
 		  /// but it has some limitations due its special implementation.
 		  /// The type of the priorities must be \c int and the priority of an
 		  /// item cannot be decreased under the priority of the last removed item.
 		  ///
 		  /// \param IM A read and writable Item int map, used internally
 		  /// to handle the cross references.
 		  ///
 		  /// \see BinHeap
-		  /// \see Dijkstra
+		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  template <typename IM>
@@ -52,5 +47,9 @@
 		  public:
-		    typedef typename IM::Key Item;
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
-		    typedef IM ItemIntMap;
+		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
@@ -58,6 +57,5 @@
 		    ///
 		    /// This Exception is thrown when a smaller priority
 		    /// is inserted into the \e RadixHeap then the last time erased.
 		    /// This exception is thrown when an item is inserted into a
 		    /// RadixHeap with a priority smaller than the last erased one.
 		    /// \see RadixHeap
 		    class UnderFlowPriorityError : public Exception {
@@ -69,14 +67,14 @@
-		    /// \brief Type to represent the items states.
+		    /// \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 latter two are indifferent from the
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The ItemIntMap \e should be initialized in such way that it maps
 		    /// PRE_HEAP (-1) to any element to be put in the heap...
 		    /// The item-int map must be initialized in such way that it assigns
 		    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		    enum State {
 		      IN_HEAP = 0,
 		      PRE_HEAP = -1,
-		      POST_HEAP = -2
+		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
@@ -103,19 +101,18 @@
 		  public:
 		  public:
 		    /// \brief The constructor.
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor.
 		    ///
 		    /// \param map It 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.
 		    ///
 		    /// \param minimal The initial minimal value of the heap.
 		    /// \param capacity It determines the initial capacity of the heap.
 		    RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
 		      : _iim(map) {
 		      boxes.push_back(RadixBox(minimal, 1));
 		      boxes.push_back(RadixBox(minimal + 1, 1));
-		      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
+		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param minimum The initial minimum value of the heap.
 		    /// \param capacity The initial capacity of the heap.
 		    RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
 		      : _iim(map)
+		    {
 		      boxes.push_back(RadixBox(minimum, 1));
 		      boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
 		        extend();
@@ -124,22 +121,26 @@
 		    /// The number of items stored in the heap.
+		    /// \brief The number of items stored in the heap.
 		    ///
-		    /// \brief Returns the number of items stored in the heap.
+		    /// This function returns the number of items stored in the heap.
 		    int size() const { return data.size(); }
-		    /// \brief Checks if the heap stores no items.
 		    /// \brief Check if the heap is empty.
 		    ///
-		    /// Returns \c true if and only if the heap stores no items.
+		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return data.empty(); }
-		    /// \brief Make empty this heap.
+		    /// \brief Make the heap empty.
 		    ///
 		    /// Make empty this heap. It does not change the cross reference
 		    /// map.  If you want to reuse a heap what is not surely empty you
 		    /// should first clear the heap and after that you should set the
 		    /// cross reference map for each item to \c PRE_HEAP.
-		    void clear(int minimal = 0, int capacity = 0) {
+		    /// 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.
 		    /// \param minimum The minimum value of the heap.
 		    /// \param capacity The capacity of the heap.
 		    void clear(int minimum = 0, int capacity = 0) {
 		      data.clear(); boxes.clear();
 		      boxes.push_back(RadixBox(minimal, 1));
 		      boxes.push_back(RadixBox(minimal + 1, 1));
-		      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
+		      boxes.push_back(RadixBox(minimum, 1));
 		      boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
 		        extend();
@@ -158,3 +159,3 @@
-		    /// \brief Remove item from the box list.
 		    // Remove item from the box list
 		    void remove(int index) {
@@ -170,3 +171,3 @@
-		    /// \brief Insert item into the box list.
 		    // Insert item into the box list
 		    void insert(int box, int index) {
@@ -184,3 +185,3 @@
-		    /// \brief Add a new box to the box list.
 		    // Add a new box to the box list
 		    void extend() {
@@ -191,3 +192,3 @@
-		    /// \brief Move an item up into the proper box.
 		    // Move an item up into the proper box.
 		    void bubble_up(int index) {
@@ -199,3 +200,3 @@
-		    /// \brief Find up the proper box for the item with the given prio.
+		    // Find up the proper box for the item with the given priority
 		    int findUp(int start, int pr) {
@@ -209,3 +210,3 @@
-		    /// \brief Move an item down into the proper box.
 		    // Move an item down into the proper box
 		    void bubble_down(int index) {
@@ -217,3 +218,3 @@
-		    /// \brief Find up the proper box for the item with the given prio.
+		    // Find down the proper box for the item with the given priority
 		    int findDown(int start, int pr) {
@@ -225,3 +226,3 @@
-		    /// \brief Find the first not empty box.
+		    // Find the first non-empty box
 		    int findFirst() {
@@ -232,3 +233,3 @@
-		    /// \brief Gives back the minimal prio of the box.
+		    // Gives back the minimum priority of the given box
 		    int minValue(int box) {
@@ -241,4 +242,3 @@
 		    /// \brief Rearrange the items of the heap and makes the
 		    /// first box not empty.
 		    // Rearrange the items of the heap and make the first box non-empty
 		    void moveDown() {
@@ -279,5 +279,8 @@
 		    ///
-		    /// Adds \c i to the heap with priority \c p.
+		    /// This function 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.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void push(const Item &i, const Prio &p) {
@@ -293,6 +296,6 @@
-		    /// \brief Returns the item with minimum priority.
+		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
@@ -302,6 +305,6 @@
-		    /// \brief Returns the minimum priority.
+		    /// \brief The minimum priority.
 		    ///
 		    /// It returns the minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
@@ -311,5 +314,5 @@
-		    /// \brief Deletes the item with minimum priority.
+		    /// \brief Remove the item having minimum priority.
 		    ///
-		    /// This method deletes the item with minimum priority.
+		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
@@ -323,7 +326,8 @@
-		    /// \brief Deletes \c i from the heap.
+		    /// \brief Remove the given 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.
+		    /// This function 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) {
@@ -335,7 +339,7 @@
-		    /// \brief Returns the priority of \c i.
+		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of item \c i.
 		    /// \pre \c i must be in the heap.
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
@@ -345,10 +349,12 @@
 		    /// \brief \c i gets to the heap with priority \c p independently
 		    /// if \c i was already there.
 		    /// \brief Set the priority of an item or insert 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 into the heap with the given priority.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be in the heap.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void set(const Item &i, const Prio &p) {
@@ -367,10 +373,9 @@
 		    /// \brief Decreases the priority of \c i to \c p.
 		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This method decreases the priority of item \c i to \c p.
 		    /// \pre \c i must be stored in the heap with priority at least \c p, and
-		    /// \c should be greater or equal to the last removed item's priority.
+		    /// This function 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.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void decrease(const Item &i, const Prio &p) {
@@ -381,8 +386,8 @@
-		    /// \brief Increases the priority of \c i to \c p.
+		    /// \brief Increase 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
 		    /// This function 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.
 		    void increase(const Item &i, const Prio &p) {
@@ -393,9 +398,9 @@
 		    /// \brief Returns if \c item is in, has already been in, or has
 		    /// never been in the heap.
 		    /// \brief Return the state of an item.
 		    ///
 		    /// 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.
@@ -407,7 +412,7 @@
-		    /// \brief Sets the state of the \c item in the heap.
+		    /// \brief Set 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
-		    /// better time complexity.
+		    /// 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.
 		    /// \param i The item.

0 comments (0 inline)

RhodeCode

Login to your account