LEMON/LEMON-main Changeset - r712:6d5f547e5bfb

Repositories » LEMON » LEMON-main

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

Changeset - r712:6d5f547e5bfb

« 711:28cfac
« 708:5d313b

868:0513cc »
797:30cb42 »
729:be48a6 »
715:ece801 »

r712:6d5f547e5bfb

Mon, 31 Aug 2009 20:27:38

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 6 0

merge default

0 files changed with 691 insertions and 609 deletions:

doc/groups.dox

lemon/bin_heap.h

110

lemon/bucket_heap.h

166

139

lemon/concepts/heap.h

lemon/fib_heap.h

125

118

lemon/radix_heap.h

184

179

↑ Collapse diff ↑

doc/groups.dox

Show inline comments

@@ -213,53 +213,74 @@
 		  DoubleArcMap speed(graph);
 		  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 		  TimeMap time(length, speed);
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief %Path structures implemented in LEMON.
 		This group contains the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
-		\sa lemon::concepts::Path
+		\sa \ref concepts::Path "Path concept"
 		*/
 		/**
 		@defgroup heaps Heap Structures
 		@ingroup datas
 		\brief %Heap structures implemented in LEMON.
 		This group contains the heap structures implemented in LEMON.
 		LEMON provides several heap classes. They 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.
 		Heaps are crucial in several algorithms, such as Dijkstra and Prim.
 		The heap implementations have the same interface, thus any of them can be
 		used easily in such algorithms.
 		\sa \ref concepts::Heap "Heap concept"
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group contains some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group contains the several algorithms
 		implemented in LEMON.

lemon/bin_heap.h

Show inline comments

@@ -6,342 +6,342 @@
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BIN_HEAP_H
 		#define LEMON_BIN_HEAP_H
-		///\ingroup auxdat
+		///\ingroup heaps
 		///\file
-		///\brief Binary Heap implementation.
+		///\brief Binary heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
-		  ///\ingroup auxdat
+		  /// \ingroup heaps
 		  ///
-		  ///\brief A Binary Heap implementation.
+		  /// \brief Binary heap data structure.
 		  ///
 		  ///This class implements the \e binary \e 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.
 		  ///The default is \c std::less<PR>.
 		  ///
 		  ///\sa FibHeap
 		  ///\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 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.
 		    ///
 		    /// 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,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  private:
 		    std::vector<Pair> _data;
 		    Compare _comp;
 		    ItemIntMap &_iim;
 		  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)
 		      : _iim(map), _comp(comp) {}
 		    /// 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() {
 		      _data.clear();
+		    }
 		  private:
 		    static int parent(int i) { return (i-1)/2; }
-		    static int second_child(int i) { return 2*i+2; }
+		    static int secondChild(int i) { return 2*i+2; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
-		    int bubble_up(int hole, Pair p) {
+		    int bubbleUp(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
 		      return hole;
+		    }
 		    int bubble_down(int hole, Pair p, int length) {
 		      int child = second_child(hole);
 		    int bubbleDown(int hole, Pair p, int length) {
 		      int child = secondChild(hole);
 		      while(child < length) {
 		        if( less(_data[child-1], _data[child]) ) {
 		          --child;
+		        }
 		        if( !less(_data[child], p) )
 		          goto ok;
 		        move(_data[child], hole);
 		        hole = child;
-		        child = second_child(hole);
+		        child = secondChild(hole);
+		      }
 		      child--;
 		      if( child<length && less(_data[child], p) ) {
 		        move(_data[child], hole);
 		        hole=child;
+		      }
 		    ok:
 		      move(p, hole);
 		      return hole;
+		    }
 		    void move(const Pair &p, int i) {
 		      _data[i] = p;
 		      _iim.set(p.first, i);
+		    }
 		  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) {
 		      int n = _data.size();
 		      _data.resize(n+1);
-		      bubble_up(n, p);
+		      bubbleUp(n, p);
+		    }
-		    /// \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 {
 		      return _data[0].first;
+		    }
-		    /// \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 {
 		      return _data[0].second;
+		    }
-		    /// \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.
 		    void pop() {
 		      int n = _data.size()-1;
 		      _iim.set(_data[0].first, POST_HEAP);
 		      if (n > 0) {
-		        bubble_down(0, _data[n], n);
+		        bubbleDown(0, _data[n], n);
+		      }
 		      _data.pop_back();
+		    }
-		    /// \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) {
 		      int h = _iim[i];
 		      int n = _data.size()-1;
 		      _iim.set(_data[h].first, POST_HEAP);
 		      if( h < n ) {
 		        if ( bubble_up(h, _data[n]) == h) {
 		          bubble_down(h, _data[n], n);
 		        if ( bubbleUp(h, _data[n]) == h) {
 		          bubbleDown(h, _data[n], n);
+		        }
+		      }
 		      _data.pop_back();
+		    }
 		    /// \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 {
 		      int idx = _iim[i];
 		      return _data[idx].second;
+		    }
 		    /// \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.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      if( idx < 0 ) {
 		        push(i,p);
+		      }
 		      else if( _comp(p, _data[idx].second) ) {
-		        bubble_up(idx, Pair(i,p));
+		        bubbleUp(idx, Pair(i,p));
+		      }
 		      else {
-		        bubble_down(idx, Pair(i,p), _data.size());
+		        bubbleDown(idx, Pair(i,p), _data.size());
+		      }
+		    }
-		    /// \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) {
 		      int idx = _iim[i];
-		      bubble_up(idx, Pair(i,p));
+		      bubbleUp(idx, Pair(i,p));
+		    }
-		    /// \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) {
 		      int idx = _iim[i];
-		      bubble_down(idx, Pair(i,p), _data.size());
+		      bubbleDown(idx, Pair(i,p), _data.size());
+		    }
 		    /// \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.
 		    State state(const Item &i) const {
 		      int s = _iim[i];
 		      if( s>=0 )
 		        s=0;
 		      return State(s);
+		    }
-		    /// \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.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
-		    /// \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) {
 		      int idx = _iim[i];
 		      _iim.set(i, _iim[j]);
 		      _iim.set(j, idx);
 		      _data[idx].first = j;
+		    }
 		  }; // class BinHeap
 		} // namespace lemon
 		#endif // LEMON_BIN_HEAP_H

lemon/bucket_heap.h

Show inline comments

@@ -6,148 +6,156 @@
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BUCKET_HEAP_H
 		#define LEMON_BUCKET_HEAP_H
-		///\ingroup auxdat
+		///\ingroup heaps
 		///\file
-		///\brief Bucket Heap implementation.
+		///\brief Bucket heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
 		  namespace _bucket_heap_bits {
 		    template <bool MIN>
 		    struct DirectionTraits {
 		      static bool less(int left, int right) {
 		        return left < right;
+		      }
 		      static void increase(int& value) {
 		        ++value;
+		      }
 		    };
 		    template <>
 		    struct DirectionTraits<false> {
 		      static bool less(int left, int right) {
 		        return left > right;
+		      }
 		      static void increase(int& value) {
 		        --value;
+		      }
 		    };
+		  }
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
-		  /// \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>
 		  class BucketHeap {
 		  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
 		    typedef std::pair<Item, Prio> Pair;
 		    /// \e
 		    typedef IM ItemIntMap;
 		    /// 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;
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
 		  public:
-		    /// \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 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,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  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() {
 		      _data.clear(); _first.clear(); _minimum = 0;
+		    }
 		  private:
-		    void relocate_last(int idx) {
+		    void relocateLast(int idx) {
 		      if (idx + 1 < int(_data.size())) {
 		        _data[idx] = _data.back();
 		        if (_data[idx].prev != -1) {
 		          _data[_data[idx].prev].next = idx;
 		        } else {
 		          _first[_data[idx].value] = idx;
+		        }
 		        if (_data[idx].next != -1) {
 		          _data[_data[idx].next].prev = idx;
+		        }
 		        _iim[_data[idx].item] = idx;
+		      }
 		      _data.pop_back();
+		    }
 		    void unlace(int idx) {
@@ -161,182 +169,186 @@
+		      }
+		    }
 		    void lace(int idx) {
 		      if (int(_first.size()) <= _data[idx].value) {
 		        _first.resize(_data[idx].value + 1, -1);
+		      }
 		      _data[idx].next = _first[_data[idx].value];
 		      if (_data[idx].next != -1) {
 		        _data[_data[idx].next].prev = idx;
+		      }
 		      _first[_data[idx].value] = idx;
 		      _data[idx].prev = -1;
+		    }
 		  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) {
 		      push(p.first, p.second);
+		    }
 		    /// \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) {
 		      int idx = _data.size();
 		      _iim[i] = idx;
 		      _data.push_back(BucketItem(i, p));
 		      lace(idx);
 		      if (Direction::less(p, _minimum)) {
 		        _minimum = p;
+		      }
+		    }
-		    /// \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 {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _data[_first[_minimum]].item;
+		    }
-		    /// \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 {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _minimum;
+		    }
-		    /// \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.
 		    void pop() {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      int idx = _first[_minimum];
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
-		      relocate_last(idx);
+		      relocateLast(idx);
+		    }
-		    /// \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) {
 		      int idx = _iim[i];
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
-		      relocate_last(idx);
+		      relocateLast(idx);
+		    }
 		    /// \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 {
 		      int idx = _iim[i];
 		      return _data[idx].value;
+		    }
 		    /// \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.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      if (idx < 0) {
 		        push(i, p);
 		      } else if (Direction::less(p, _data[idx].value)) {
 		        decrease(i, p);
 		      } else {
 		        increase(i, p);
+		      }
+		    }
-		    /// \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) {
 		      int idx = _iim[i];
 		      unlace(idx);
 		      _data[idx].value = p;
 		      if (Direction::less(p, _minimum)) {
 		        _minimum = p;
+		      }
 		      lace(idx);
+		    }
-		    /// \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) {
 		      int idx = _iim[i];
 		      unlace(idx);
 		      _data[idx].value = p;
 		      lace(idx);
+		    }
 		    /// \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.
 		    State state(const Item &i) const {
 		      int idx = _iim[i];
 		      if (idx >= 0) idx = 0;
 		      return State(idx);
+		    }
-		    /// \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.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
@@ -346,210 +358,225 @@
 		      BucketItem(const Item& _item, int _value)
 		        : item(_item), value(_value) {}
 		      Item item;
 		      int value;
 		      int prev, next;
 		    };
 		    ItemIntMap& _iim;
 		    std::vector<int> _first;
 		    std::vector<BucketItem> _data;
 		    mutable int _minimum;
 		  }; // class BucketHeap
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
-		  /// \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.
 		  ///
 		  /// \sa BucketHeap
 		  template <typename IM, bool MIN = true >
 		  class SimpleBucketHeap {
 		  public:
-		    typedef typename IM::Key Item;
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    typedef std::pair<Item, Prio> Pair;
 		    typedef IM ItemIntMap;
 		    /// 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;
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
 		  public:
-		    /// \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 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,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  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 SimpleBucketHeap(ItemIntMap &map)
 		      : _iim(map), _free(-1), _num(0), _minimum(0) {}
-		    /// \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() {
 		      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
+		    }
 		    /// \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) {
 		      push(p.first, p.second);
+		    }
 		    /// \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) {
 		      int idx;
 		      if (_free == -1) {
 		        idx = _data.size();
 		        _data.push_back(BucketItem(i));
 		      } else {
 		        idx = _free;
 		        _free = _data[idx].next;
 		        _data[idx].item = i;
+		      }
 		      _iim[i] = idx;
 		      if (p >= int(_first.size())) _first.resize(p + 1, -1);
 		      _data[idx].next = _first[p];
 		      _first[p] = idx;
 		      if (Direction::less(p, _minimum)) {
 		        _minimum = p;
+		      }
 		      ++_num;
+		    }
-		    /// \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 {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _data[_first[_minimum]].item;
+		    }
-		    /// \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 {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _minimum;
+		    }
-		    /// \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.
 		    void pop() {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      int idx = _first[_minimum];
 		      _iim[_data[idx].item] = -2;
 		      _first[_minimum] = _data[idx].next;
 		      _data[idx].next = _free;
 		      _free = idx;
 		      --_num;
+		    }
-		    /// \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];
 		        while (idx != -1) {
 		          if (_data[idx].item == i) {
 		            return k;
+		          }
 		          idx = _data[idx].next;
+		        }
+		      }
 		      return -1;
+		    }
 		    /// \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.
 		    State state(const Item &i) const {
 		      int idx = _iim[i];
 		      if (idx >= 0) idx = 0;
 		      return State(idx);
+		    }
 		  private:
 		    struct BucketItem {
 		      BucketItem(const Item& _item)
 		        : item(_item) {}
 		      Item item;
 		      int next;
 		    };

lemon/concepts/heap.h

Show inline comments

@@ -3,197 +3,219 @@
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#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 <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief The heap concept.
 		    ///
 		    /// 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 \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.
 		    ///
 		    /// \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
 		    class Heap {
 		    public:
 		      /// Type of the item-int map.
 		      typedef IM ItemIntMap;
 		      /// Type of the priorities.
 		      typedef PR Prio;
 		      /// Type of the items stored in the heap.
 		      typedef typename ItemIntMap::Key Item;
 		      /// \brief Type to represent the states of the items.
 		      ///
 		      /// 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.
 		      ///
 		      /// 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,    ///< = 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
 		      /// \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.
+		      /// \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.
 		      Item top() const {}
 		      /// \brief The minimum priority.
 		      ///
-		      /// Returns the minimum priority.
+		      /// This function returns the minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Prio prio() const {}
-		      /// \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.
 		      void pop() {}
-		      /// \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.
 		      ///
 		      /// 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.
 		      ///
 		      /// \param i The item.
 		      /// \param p The priority.
 		      void set(const Item &i, const Prio &p) {}
-		      /// \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.
 		      ///
 		      /// 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 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.
 		      /// \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;
 		          item=Item();

lemon/fib_heap.h

Show inline comments

@@ -7,315 +7,322 @@
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_FIB_HEAP_H
 		#define LEMON_FIB_HEAP_H
 		///\file
 		///\ingroup auxdat
 		///\brief Fibonacci Heap implementation.
 		///\ingroup heaps
 		///\brief Fibonacci heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		#include <lemon/math.h>
 		namespace lemon {
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
-		  ///\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
 		  class FibHeap {
 		  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;
 		  private:
 		    class Store;
 		    std::vector<Store> _data;
 		    int _minimum;
 		    ItemIntMap &_iim;
 		    Compare _comp;
 		    int _num;
 		  public:
-		    /// \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 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,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
-		    /// \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)
 		      : _minimum(0), _iim(map), _num() {}
-		    /// \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)
 		      : _minimum(0), _iim(map), _comp(comp), _num() {}
 		    /// \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 _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() {
 		      _data.clear(); _minimum = 0; _num = 0;
+		    }
 		    /// \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];
 		      if ( i < 0 ) {
 		        int s=_data.size();
 		        _iim.set( item, s );
 		        Store st;
 		        st.name=item;
 		        _data.push_back(st);
 		        i=s;
 		      } else {
 		        _data[i].parent=_data[i].child=-1;
 		        _data[i].degree=0;
 		        _data[i].in=true;
 		        _data[i].marked=false;
+		      }
 		      if ( _num ) {
 		        _data[_data[_minimum].right_neighbor].left_neighbor=i;
 		        _data[i].right_neighbor=_data[_minimum].right_neighbor;
 		        _data[_minimum].right_neighbor=i;
 		        _data[i].left_neighbor=_minimum;
-		        if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
+		        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
 		      } else {
 		        _data[i].right_neighbor=_data[i].left_neighbor=i;
 		        _minimum=i;
+		      }
-		      _data[i].prio=value;
+		      _data[i].prio=prio;
 		      ++_num;
+		    }
-		    /// \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.
 		    void pop() {
 		      /*The first case is that there are only one root.*/
 		      if ( _data[_minimum].left_neighbor==_minimum ) {
 		        _data[_minimum].in=false;
 		        if ( _data[_minimum].degree!=0 ) {
-		          makeroot(_data[_minimum].child);
+		          makeRoot(_data[_minimum].child);
 		          _minimum=_data[_minimum].child;
 		          balance();
+		        }
 		      } else {
 		        int right=_data[_minimum].right_neighbor;
 		        unlace(_minimum);
 		        _data[_minimum].in=false;
 		        if ( _data[_minimum].degree > 0 ) {
 		          int left=_data[_minimum].left_neighbor;
 		          int child=_data[_minimum].child;
 		          int last_child=_data[child].left_neighbor;
-		          makeroot(child);
+		          makeRoot(child);
 		          _data[left].right_neighbor=child;
 		          _data[child].left_neighbor=left;
 		          _data[right].left_neighbor=last_child;
 		          _data[last_child].right_neighbor=right;
+		        }
 		        _minimum=right;
 		        balance();
 		      } // the case where there are more roots
 		      --_num;
+		    }
-		    /// \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) {
 		      int i=_iim[item];
 		      if ( i >= 0 && _data[i].in ) {
 		        if ( _data[i].parent!=-1 ) {
 		          int p=_data[i].parent;
 		          cut(i,p);
 		          cascade(p);
+		        }
 		        _minimum=i;     //As if its prio would be -infinity
 		        pop();
+		      }
+		    }
-		    /// \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);
 		        cascade(p);
+		      }
-		      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 {
 		      int i=_iim[item];
 		      if( i>=0 ) {
 		        if ( _data[i].in ) i=0;
 		        else i=-2;
+		      }
 		      return State(i);
+		    }
-		    /// \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.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
@@ -352,33 +359,33 @@
 		          ++d;
+		        }
 		        A[d]=active;
 		      } while ( !end );
 		      while ( _data[_minimum].parent >=0 )
 		        _minimum=_data[_minimum].parent;
 		      int s=_minimum;
 		      int m=_minimum;
 		      do {
 		        if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
 		        s=_data[s].right_neighbor;
 		      } while ( s != m );
+		    }
-		    void makeroot(int c) {
+		    void makeRoot(int c) {
 		      int s=c;
 		      do {
 		        _data[s].parent=-1;
 		        s=_data[s].right_neighbor;
 		      } while ( s != c );
+		    }
 		    void cut(int a, int b) {
 		      /*
 		       *Replacing a from the children of b.
 		       */
 		      --_data[b].degree;
 		      if ( _data[b].degree !=0 ) {
 		        int child=_data[b].child;
 		        if ( child==a )

lemon/radix_heap.h

Show inline comments

@@ -6,423 +6,428 @@
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_RADIX_HEAP_H
 		#define LEMON_RADIX_HEAP_H
-		///\ingroup auxdat
+		///\ingroup heaps
 		///\file
-		///\brief Radix Heap implementation.
+		///\brief Radix heap implementation.
 		#include <vector>
 		#include <lemon/error.h>
 		namespace lemon {
-		  /// \ingroup auxdata
+		  /// \ingroup heaps
 		  ///
-		  /// \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>
 		  class RadixHeap {
 		  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;
 		    /// \brief Exception thrown by RadixHeap.
 		    ///
 		    /// 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 {
 		    class PriorityUnderflowError : public Exception {
 		    public:
 		      virtual const char* what() const throw() {
-		        return "lemon::RadixHeap::UnderFlowPriorityError";
+		        return "lemon::RadixHeap::PriorityUnderflowError";
+		      }
 		    };
-		    /// \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.
 		    };
 		  private:
 		    struct RadixItem {
 		      int prev, next, box;
 		      Item item;
 		      int prio;
 		      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
 		    };
 		    struct RadixBox {
 		      int first;
 		      int min, size;
 		      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
 		    };
 		    std::vector<RadixItem> data;
 		    std::vector<RadixBox> boxes;
 		    std::vector<RadixItem> _data;
 		    std::vector<RadixBox> _boxes;
 		    ItemIntMap &_iim;
 		  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();
+		      }
+		    }
 		    /// 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.
 		    int size() const { return data.size(); }
-		    /// \brief Checks if the heap stores no items.
+		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// Returns \c true if and only if the heap stores no items.
 		    bool empty() const { return data.empty(); }
 		    /// 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) {
 		      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)) {
+		    /// 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(minimum, 1));
 		      _boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
 		        extend();
+		      }
+		    }
 		  private:
 		    bool upper(int box, Prio pr) {
-		      return pr < boxes[box].min;
+		      return pr < _boxes[box].min;
+		    }
 		    bool lower(int box, Prio pr) {
-		      return pr >= boxes[box].min + boxes[box].size;
+		      return pr >= _boxes[box].min + _boxes[box].size;
+		    }
-		    /// \brief Remove item from the box list.
 		    // Remove item from the box list
 		    void remove(int index) {
 		      if (data[index].prev >= 0) {
 		        data[data[index].prev].next = data[index].next;
 		      if (_data[index].prev >= 0) {
 		        _data[_data[index].prev].next = _data[index].next;
 		      } else {
-		        boxes[data[index].box].first = data[index].next;
+		        _boxes[_data[index].box].first = _data[index].next;
+		      }
 		      if (data[index].next >= 0) {
 		        data[data[index].next].prev = data[index].prev;
 		      if (_data[index].next >= 0) {
 		        _data[_data[index].next].prev = _data[index].prev;
+		      }
+		    }
-		    /// \brief Insert item into the box list.
 		    // Insert item into the box list
 		    void insert(int box, int index) {
 		      if (boxes[box].first == -1) {
 		        boxes[box].first = index;
-		        data[index].next = data[index].prev = -1;
+		      if (_boxes[box].first == -1) {
 		        _boxes[box].first = index;
 		        _data[index].next = _data[index].prev = -1;
 		      } else {
 		        data[index].next = boxes[box].first;
 		        data[boxes[box].first].prev = index;
 		        data[index].prev = -1;
 		        boxes[box].first = index;
 		        _data[index].next = _boxes[box].first;
 		        _data[_boxes[box].first].prev = index;
 		        _data[index].prev = -1;
 		        _boxes[box].first = index;
+		      }
-		      data[index].box = box;
+		      _data[index].box = box;
+		    }
-		    /// \brief Add a new box to the box list.
 		    // Add a new box to the box list
 		    void extend() {
 		      int min = boxes.back().min + boxes.back().size;
 		      int bs = 2 * boxes.back().size;
-		      boxes.push_back(RadixBox(min, bs));
+		      int min = _boxes.back().min + _boxes.back().size;
 		      int bs = 2 * _boxes.back().size;
 		      _boxes.push_back(RadixBox(min, bs));
+		    }
 		    /// \brief Move an item up into the proper box.
 		    void bubble_up(int index) {
-		      if (!lower(data[index].box, data[index].prio)) return;
+		    // Move an item up into the proper box.
 		    void bubbleUp(int index) {
 		      if (!lower(_data[index].box, _data[index].prio)) return;
 		      remove(index);
-		      int box = findUp(data[index].box, data[index].prio);
+		      int box = findUp(_data[index].box, _data[index].prio);
 		      insert(box, index);
+		    }
-		    /// \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) {
 		      while (lower(start, pr)) {
-		        if (++start == int(boxes.size())) {
+		        if (++start == int(_boxes.size())) {
 		          extend();
+		        }
+		      }
 		      return start;
+		    }
 		    /// \brief Move an item down into the proper box.
 		    void bubble_down(int index) {
-		      if (!upper(data[index].box, data[index].prio)) return;
+		    // Move an item down into the proper box
 		    void bubbleDown(int index) {
 		      if (!upper(_data[index].box, _data[index].prio)) return;
 		      remove(index);
-		      int box = findDown(data[index].box, data[index].prio);
+		      int box = findDown(_data[index].box, _data[index].prio);
 		      insert(box, index);
+		    }
-		    /// \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) {
 		      while (upper(start, pr)) {
-		        if (--start < 0) throw UnderFlowPriorityError();
+		        if (--start < 0) throw PriorityUnderflowError();
+		      }
 		      return start;
+		    }
-		    /// \brief Find the first not empty box.
+		    // Find the first non-empty box
 		    int findFirst() {
 		      int first = 0;
-		      while (boxes[first].first == -1) ++first;
+		      while (_boxes[first].first == -1) ++first;
 		      return first;
+		    }
-		    /// \brief Gives back the minimal prio of the box.
+		    // Gives back the minimum priority of the given box
 		    int minValue(int box) {
 		      int min = data[boxes[box].first].prio;
 		      for (int k = boxes[box].first; k != -1; k = data[k].next) {
-		        if (data[k].prio < min) min = data[k].prio;
+		      int min = _data[_boxes[box].first].prio;
 		      for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
 		        if (_data[k].prio < min) min = _data[k].prio;
+		      }
 		      return min;
+		    }
 		    /// \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() {
 		      int box = findFirst();
 		      if (box == 0) return;
 		      int min = minValue(box);
 		      for (int i = 0; i <= box; ++i) {
 		        boxes[i].min = min;
 		        min += boxes[i].size;
 		        _boxes[i].min = min;
 		        min += _boxes[i].size;
+		      }
-		      int curr = boxes[box].first, next;
+		      int curr = _boxes[box].first, next;
 		      while (curr != -1) {
 		        next = data[curr].next;
 		        bubble_down(curr);
 		        next = _data[curr].next;
 		        bubbleDown(curr);
 		        curr = next;
+		      }
+		    }
 		    void relocate_last(int index) {
 		      if (index != int(data.size()) - 1) {
 		        data[index] = data.back();
 		        if (data[index].prev != -1) {
-		          data[data[index].prev].next = index;
+		    void relocateLast(int index) {
 		      if (index != int(_data.size()) - 1) {
 		        _data[index] = _data.back();
 		        if (_data[index].prev != -1) {
 		          _data[_data[index].prev].next = index;
 		        } else {
-		          boxes[data[index].box].first = index;
+		          _boxes[_data[index].box].first = index;
+		        }
 		        if (data[index].next != -1) {
 		          data[data[index].next].prev = index;
 		        if (_data[index].next != -1) {
 		          _data[_data[index].next].prev = index;
+		        }
-		        _iim[data[index].item] = index;
+		        _iim[_data[index].item] = index;
+		      }
-		      data.pop_back();
+		      _data.pop_back();
+		    }
 		  public:
 		    /// \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.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void push(const Item &i, const Prio &p) {
-		      int n = data.size();
+		      int n = _data.size();
 		      _iim.set(i, n);
 		      data.push_back(RadixItem(i, p));
 		      while (lower(boxes.size() - 1, p)) {
 		      _data.push_back(RadixItem(i, p));
 		      while (lower(_boxes.size() - 1, p)) {
 		        extend();
+		      }
-		      int box = findDown(boxes.size() - 1, p);
+		      int box = findDown(_boxes.size() - 1, p);
 		      insert(box, n);
+		    }
-		    /// \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 {
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
-		      return data[boxes[0].first].item;
+		      return _data[_boxes[0].first].item;
+		    }
-		    /// \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 {
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
-		      return data[boxes[0].first].prio;
+		      return _data[_boxes[0].first].prio;
+		     }
-		    /// \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.
 		    void pop() {
 		      moveDown();
 		      int index = boxes[0].first;
 		      _iim[data[index].item] = POST_HEAP;
 		      int index = _boxes[0].first;
 		      _iim[_data[index].item] = POST_HEAP;
 		      remove(index);
-		      relocate_last(index);
+		      relocateLast(index);
+		    }
-		    /// \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) {
 		      int index = _iim[i];
 		      _iim[i] = POST_HEAP;
 		      remove(index);
-		      relocate_last(index);
+		      relocateLast(index);
+		   }
-		    /// \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 {
 		      int idx = _iim[i];
-		      return data[idx].prio;
+		      return _data[idx].prio;
+		    }
 		    /// \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) {
 		      int idx = _iim[i];
 		      if( idx < 0 ) {
 		        push(i, p);
+		      }
 		      else if( p >= data[idx].prio ) {
 		        data[idx].prio = p;
-		        bubble_up(idx);
+		      else if( p >= _data[idx].prio ) {
 		        _data[idx].prio = p;
 		        bubbleUp(idx);
 		      } else {
 		        data[idx].prio = p;
 		        bubble_down(idx);
 		        _data[idx].prio = p;
 		        bubbleDown(idx);
+		      }
+		    }
 		    /// \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) {
 		      int idx = _iim[i];
 		      data[idx].prio = p;
 		      bubble_down(idx);
 		      _data[idx].prio = p;
 		      bubbleDown(idx);
+		    }
-		    /// \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) {
 		      int idx = _iim[i];
 		      data[idx].prio = p;
 		      bubble_up(idx);
 		      _data[idx].prio = p;
 		      bubbleUp(idx);
+		    }
 		    /// \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.
 		    State state(const Item &i) const {
 		      int s = _iim[i];
 		      if( s >= 0 ) s = 0;
 		      return State(s);
+		    }
-		    /// \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.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }

0 comments (0 inline)

RhodeCode

Login to your account