lemon-0.x: comparison lemon/bin

equal deleted inserted replaced

-:1e1b4ddaf6b4
+:c5bce0ac200c
 ///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,
+template <typename Prio, typename ItemIntMap,
 	    typename Compare = std::less<Prio> >
 class BinHeap {
 public:
-typedef Item                             ItemType;
+typedef typename ItemIntMap::Key         ItemType;
 typedef Prio                             PrioType;
 typedef std::pair<ItemType,PrioType>     PairType;
 typedef ItemIntMap                       ItemIntMapType;
 typedef Compare                          PrioCompare;
 /// \brief Insert an item into the heap with the given heap.
 ///
 /// Adds \c i to the heap with priority \c p.
 /// \param i The item to insert.
 /// \param p The priority of the item.
-void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
+void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); }
 /// \brief 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 {
+ItemType top() const {
 return data[0].first;
 }
 /// \brief Returns the minimum priority relative to \c Compare.
 ///
 /// \brief Deletes \c i 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.
-void erase(const Item &i) {
+void erase(const ItemType &i) {
 rmidx(iim[i]);
 }
 /// \brief Returns the priority of \c i.
 ///
 /// This function returns the priority of item \c i.
 /// \pre \c i must be in the heap.
 /// \param i The item.
-Prio operator[](const Item &i) const {
+Prio operator[](const ItemType &i) const {
 int idx = iim[i];
 return data[idx].second;
 }
 /// \brief \c i gets to the heap with priority \c p independently
 ///
 /// 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.
 /// \param i The item.
 /// \param p The priority.
-void set(const Item &i, const Prio &p) {
+void set(const ItemType &i, const Prio &p) {
 int idx = iim[i];
 if( idx < 0 ) {
 	push(i,p);
 }
 else if( comp(p, data[idx].second) ) {
 /// 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.
 /// \param i The item.
 /// \param p The priority.
-void decrease(const Item &i, const Prio &p) {
+void decrease(const ItemType &i, const Prio &p) {
 int idx = iim[i];
 bubble_up(idx, PairType(i,p));
 }
 /// \brief 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.
 /// \param i The item.
 /// \param p The priority.
-void increase(const Item &i, const Prio &p) {
+void increase(const ItemType &i, const Prio &p) {
 int idx = iim[i];
 bubble_down(idx, PairType(i,p), data.size());
 }
 /// \brief Returns if \c item is in, has already been in, or has
 /// 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.
 /// \param i The item.
-state_enum state(const Item &i) const {
+state_enum state(const ItemType &i) const {
 int s = iim[i];
 if( s>=0 )
 	s=0;
 return state_enum(s);
 }
 /// 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.
 /// \param i The item.
 /// \param st The state. It should not be \c IN_HEAP.
-void state(const Item& i, state_enum st) {
+void state(const ItemType& i, state_enum st) {
 switch (st) {
 case POST_HEAP:
 case PRE_HEAP:
 if (state(i) == IN_HEAP) {
 erase(i);
 }
 }; // class BinHeap
-template <typename K, typename V, typename M, typename C>
+template <typename V, typename M, typename C>
-int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
+int BinHeap<V,M,C>::bubble_up(int hole, PairType 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;
 }
-template <typename K, typename V, typename M, typename C>
+template <typename V, typename M, typename C>
-int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
+int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) {
 int child = second_child(hole);
 while(child < length) {
 if( less(data[child-1], data[child]) ) {
 	--child;
 }

changeset 2346	c06a956a92fa
parent 2258	741995f3dbc4
child 2391	14a343be7a5a