lemon-1.2: comparison lemon/bin

equal deleted inserted replaced

-:4cb040b09d6e
+:e2773c390c82
 #ifndef LEMON_BIN_HEAP_H
 #define LEMON_BIN_HEAP_H
 ///\ingroup auxdat
 ///\file
-///\brief Binary Heap implementation.
+///\brief Binary heap implementation.
 #include <vector>
 #include <utility>
 #include <functional>
 namespace lemon {
-///\ingroup auxdat
+/// \ingroup auxdat
 ///
-///\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
+/// \tparam PR Type of the priorities of the items.
-///called \e priorities in such a way that finding the item with minimum
+/// \tparam IM A read-writable item map with \c int values, used
-///priority is efficient. \c CMP specifies the ordering of the priorities.
+/// internally to handle the cross references.
-///In a heap one can change the priority of an item, add or erase an
+/// \tparam CMP A functor class for comparing the priorities.
-///item, etc.
+/// The default is \c std::less<PR>.
-///
+#ifdef DOXYGEN
-///\tparam PR Type of the priority of the items.
+template <typename PR, typename IM, typename CMP>
-///\tparam IM A read and writable item map with int values, used internally
+#else
-///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
 template <typename PR, typename IM, typename CMP = std::less<PR> >
+#endif
 class BinHeap {
 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",
+/// 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
+/// "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 {
 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
+/// Constructor.
-/// internally to handle the cross references. The value of the map
+/// \param map A map that assigns \c int values to the items.
-/// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
+/// 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.
+/// Constructor.
-/// \param map should be given to the constructor, since it is used
+/// \param map A map that assigns \c int values to the items.
-/// internally to handle the cross references. The value of the map
+/// It is used internally to handle the cross references.
-/// should be PRE_HEAP (-1) for each element.
+/// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
-///
+/// \param comp The function object used for comparing the priorities.
-/// \param comp The comparator function object.
 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.
+/// This functon makes the heap empty.
-/// If you want to reuse what is not surely empty you should first clear
+/// It does not change the cross reference map. If you want to reuse
-/// the heap and after that you should set the cross reference map for
+/// a heap that is not surely empty, you should first clear it and
-/// each item to \c PRE_HEAP.
+/// then you should set the cross reference map to \c PRE_HEAP
+/// for each item.
 void clear() {
 _data.clear();
 }
 private:
 _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);
 }
-/// \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
+/// This function returns the item having minimum priority.
-/// Compare.
+/// \pre The heap must be non-empty.
-/// \pre The heap must be nonempty.
 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.
+/// This function returns the minimum priority.
-/// \pre The heap must be nonempty.
+/// \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
+/// This function removes the item having minimum priority.
-/// Compare from the heap.
 /// \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);
 }
 _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.
+/// This function removes the given item from the heap if it is
-/// \param i The item to erase.
+/// already stored.
-/// \pre The item should be in the heap.
+/// \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 ) {
 }
 }
 _data.pop_back();
 }
+/// \brief The priority of the given item.
-/// \brief Returns the priority of \c i.
+///
-///
+/// This function returns the priority of the given item.
-/// This function returns the priority of item \c i.
+/// \param i The item.
-/// \param i The item.
+/// \pre \e i must be in the heap.
-/// \pre \c 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
+/// \brief Set the priority of an item or insert it, if it is
-/// if \c i was already there.
+/// not stored in the heap.
 ///
-/// This method calls \ref push(\c i, \c p) if \c i is not stored
+/// This method sets the priority of the given item if it is
-/// in the heap and sets the priority of \c i to \c p otherwise.
+/// 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 ) {
 else {
 bubble_down(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
+/// \pre \e i must be stored in the heap with priority at least \e p.
-/// p relative to \c Compare.
 void decrease(const Item &i, const Prio &p) {
 int idx = _iim[i];
 bubble_up(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
+/// \pre \e i must be stored in the heap with priority at most \e p.
-/// p relative to \c Compare.
 void increase(const Item &i, const Prio &p) {
 int idx = _iim[i];
 bubble_down(idx, Pair(i,p), _data.size());
 }
-/// \brief Returns if \c item is in, has already been in, or has
+/// \brief Return the state of an item.
-/// never been in the heap.
+///
-///
+/// This method returns \c PRE_HEAP if the given item has never
-/// This method returns PRE_HEAP if \c item has never been in the
+/// been in the heap, \c IN_HEAP if it is in the heap at the moment,
-/// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+/// and \c POST_HEAP otherwise.
-/// otherwise. In the latter case it is possible that \c item will
+/// In the latter case it is possible that the item will get back
-/// get back to the heap again.
+/// 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
+/// This function sets the state of the given item in the heap.
-/// manually clear the heap when it is important to achive the
+/// It can be used to manually clear the heap when it is important
-/// better time complexity.
+/// 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 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
+/// This function replaces item \c i with item \c j.
-/// be in the heap, while the \c j should be out of the heap. The
+/// Item \c i must be in the heap, while \c j must be out of the heap.
-/// \c i item will out of the heap and \c j will be in the heap
+/// After calling this method, item \c i will be out of the
-/// with the same prioriority as prevoiusly the \c i item.
+/// 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;

changeset 709	0747f332c478
parent 683	9f529abcaebf
child 710	f1fe0ddad6f7