lemon-0.x: comparison src/lemon/bin

equal deleted inserted replaced

-:a3b9d4212c2d
+:452dcf21a330
 #define LEMON_BIN_HEAP_H
 ///\ingroup auxdat
 ///\file
 ///\brief Binary Heap implementation.
-///\todo It should be documented.
 #include <vector>
 #include <utility>
 #include <functional>
 namespace lemon {
 /// \addtogroup auxdat
 /// @{
 /// A Binary Heap implementation.
-///\todo Please document...
+///This class implements the \e binary \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 Compare specifies the ordering of the priorities. In a heap
+///one can change the priority of an item, add or erase an item, etc.
+///
+///\param Item Type of the items to be stored.
+///\param Prio Type of the priority of the items.
+///\param ItemIntMap A read and writable Item int map, used internally
+///to handle the cross references.
+///\param Compare A class for the ordering of the priorities. The
+///default is \c std::less<Prio>.
 ///
 ///\sa FibHeap
 ///\sa Dijkstra
 template <typename Item, typename Prio, typename ItemIntMap,
 	    typename Compare = std::less<Prio> >
 Compare comp;
 // FIXME: jo ez igy???
 ItemIntMap &iim;
 public:
-///\e
+///The constructor
+/**
+\c _iim should be given to the constructor, since it is used
+internally to handle the cross references.
+*/
 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
-///\e
+///The constructor
+/**
+\c _iim 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.
+*/
 BinHeap(ItemIntMap &_iim, const Compare &_comp)
 : iim(_iim), comp(_comp) {}
-///\e
+///The number of items stored in the heap.
+/**
+Returns the number of items stored in the heap.
+*/
 int size() const { return data.size(); }
-///\e
+///Checks if the heap stores no items.
+/**
+Returns \c true if and only if the heap stores no items.
+*/
 bool empty() const { return data.empty(); }
 private:
 static int parent(int i) { return (i-1)/2; }
 static int second_child(int i) { return 2*i+2; }
 	data.pop_back();
 }
 }
 public:
-///\e
+///Adds \c p.first to the heap with priority \c p.second.
+/**
+Adds \c p.first to the heap with priority \c p.second.
+\c p.first must not be stored in the heap.
+*/
 void push(const PairType &p) {
 int n = data.size();
 data.resize(n+1);
 bubble_up(n, p);
 }
-///\e
+///Adds \c i to the heap with priority \c p.
+/**
+Adds \c i to the heap with priority \c p.
+\pre \c i must not be stored in the heap.
+*/
 void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
-///\e
+///Returns the item with minimum priority relative to \c Compare.
+/**
+This method returns the item with minimum priority relative to \c
+Compare.
+\pre The heap must be nonempty.
+*/
 Item top() const {
 return data[0].first;
 }
-/// Returns the prio of the top element of the heap.
+///Returns the minimum priority relative to \c Compare.
+/**
+It returns the minimum priority relative to \c Compare.
+\pre The heap must be nonempty.
+*/
 Prio prio() const {
 return data[0].second;
 }
-///\e
+///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.
+\pre The heap must be non-empty.
+*/
 void pop() {
 rmidx(0);
 }
-///\e
+///Deletes \c i from the heap.
+/**
+This method deletes item \c i from the heap, if \c i was
+already stored in the heap.
+*/
 void erase(const Item &i) {
 rmidx(iim[i]);
 }
-///\e
+///Returns the priority of \c i.
+/**
+This function returns the priority of item \c i.
+\pre \c i must be in the heap.
+*/
 Prio operator[](const Item &i) const {
 int idx = iim[i];
 return data[idx].second;
 }
-///\e
+///\c i gets to the heap with priority \c p independently if \c i was already there.
+/**
+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.
+*/
 void set(const Item &i, const Prio &p) {
 int idx = iim[i];
 if( idx < 0 ) {
 	push(i,p);
 }
 else {
 	bubble_down(idx, PairType(i,p), data.size());
 }
 }
-///\e
+///Decreases the priority of \c i to \c p.
+/**
+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.
+*/
 void decrease(const Item &i, const Prio &p) {
 int idx = iim[i];
 bubble_up(idx, PairType(i,p));
 }
-///\e
+///Increases the priority of \c i to \c p.
+/**
+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.
+*/
 void increase(const Item &i, const Prio &p) {
 int idx = iim[i];
 bubble_down(idx, PairType(i,p), data.size());
 }
-///\e
+///Returns if \c item is in, has already been in, or has never been in the heap.
+/**
+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.
+*/
 state_enum state(const Item &i) const {
 int s = iim[i];
 if( s>=0 )
 	s=0;
 return state_enum(s);

changeset 1294	2dec219d9ca2
parent 1191	c988f12c6c0c
child 1331	7e93d3f0406d