lemon-0.x: comparison src/include/fib

equal deleted inserted replaced

-:e278b2cefb1d
+:95019c912ea8
 namespace hugo {
 /// An implementation of the Fibonacci Heap.
 /**
-This class implements the \e Fibonacci \e heap data structure. A \e
+This class implements the \e Fibonacci \e heap data structure. A \e heap
-heap is a data structure for storing items with specified priorities,
+is a data structure for storing items with specified values called \e
-such that finding the item with minimum priority is efficient. In a
+priorities, such that finding the item with minimum priority with respect
-heap one can change the priority of an item, and to add or erase an
+to \e Compare is efficient. In a heap one can change the priority of an
-item.
+item, add or erase an item, etc.
-The methods \ref increase and \ref erase are not efficient, in
+The methods \ref increase and \ref erase are not efficient in a Fibonacci
-case of many calls to these operations, it is better to use
+heap. In case of many calls to these operations, it is better to use a
-a binary heap.
+\e binary \e heap.
-/param Item The type of the items to be stored.
+\param Item The type of the items to be stored.
-/param Prio The type of the priority of the items.
+\param Prio The type of the priority of the items.
-/param ItemIntMap A read and writable Item int map, for the usage of
+\param ItemIntMap A read and writable Item int map, for the usage of
 the heap.
-/param Compare A class for the comparison of the priorities. The
+\param Compare A class for the comparison of the priorities. The
 default is \c std::less<Prio>.
 */
 #ifdef DOXYGEN
 	    typename Prio,
 	    typename ItemIntMap,
 	    typename Compare = std::less<Prio> >
 #endif
 class FibHeap {
 public:
 typedef Prio PrioType;
 private:
 class store;
 IN_HEAP = 0,
 PRE_HEAP = -1,
 POST_HEAP = -2
 };
-public :
 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
 iimap(_iimap), comp(_comp), num_items() {}
 ///The number of items stored in the heap.
 /**
 Returns the number of items stored in the heap.
 */
 int size() const { return num_items; }
 ///Checks if the heap stores no items.
 /**
-Returns true iff the heap stores no items.
+Returns \c true iff the heap stores no items.
 */
 bool empty() const { return num_items==0; }
-///Item \c item gets to the heap with priority \c value independently if \c item was already there.
+///\c item gets to the heap with priority \c value independently if \c item was already there.
 /**
-This method calls \ref push(item, value) if \c item is not
+This method calls \ref push(\c item, \c value) if \c item is not
-stored in the heap, and it calls \ref decrease(it, \c value) or
+stored in the heap and it calls \ref decrease(\c item, \c value) or
-\ref increase(it, \c value) otherwise.
+\ref increase(\c item, \c value) otherwise.
 */
-void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van
+void set (Item const item, PrioType const value);
 ///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 (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/
+void push (Item const item, PrioType const value);
 ///Returns the item having the minimum priority w.r.t.  Compare.
 /**
 /**
 It returns the priority of \c item.
 \pre \c item must be in the heap.
 */
-PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }
+PrioType& operator[](const Item& item) {
+return container[iimap[item]].prio;
+}
 ///Returns the priority of \c item.
 /**
 It returns the priority of \c item.
 \pre \c item must be in the heap.
 */
-const PrioType& operator[](const Item& it) const {
+const PrioType& operator[](const Item& item) const {
-return container[iimap[it]].prio;
+return container[iimap[item]].prio;
 }
 ///Deletes the item with minimum priority w.r.t.  Compare.
 /**
 This method deletes \c item from the heap, if \c item was already
 stored in the heap. It is quite inefficient in Fibonacci heaps.
 */
-void erase (const Item& item); /*vigyazat: az implementacioban it van*/
+void erase (const Item& item);
 ///Decreases the priority of \c item to \c value.
 /**
 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 w.r.t.  Compare.
 */
-void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/
+void decrease (Item item, PrioType const value);
 ///Increases the priority of \c item to \c 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 one wants to \e increase
+method should be used only if there is a need to really \e increase
 (w.r.t.  Compare) the priority of \c item, because this
 method is inefficient.
 */
-void increase (Item it, PrioType const value) {
+void increase (Item item, PrioType const value) {
-erase(it);
+erase(item);
-push(it, value);
+push(item, value);
 }
-///Tells if \c item is in, was in, or has not been in the heap.
+///Tells if \c item is in, was already 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 &it);  /*vigyazat: az implementacioban it van*/
+state_enum state(const Item &item) const {
+int i=iimap[item];
+if( i>=0 ) {
+	if ( container[i].in ) i=0;
+	else i=-2;
+}
+return state_enum(i);
+}
+private:
+void balance();
+void makeroot(int c);
+void cut(int a, int b);
+void cascade(int a);
+void fuse(int a, int b);
+void unlace(int a);
+class store {
+friend class FibHeap;
+Item name;
+int parent;
+int left_neighbor;
+int right_neighbor;
+int child;
+int degree;
+bool marked;
+bool in;
+PrioType prio;
+store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
+};
+};
 // **********************************************************************
 //  IMPLEMENTATIONS
 // **********************************************************************
+template <typename Item, typename Prio, typename ItemIntMap,
-void set (Item const it, PrioType const value) {
+typename Compare>
-int i=iimap[it];
+void FibHeap<Item, Prio, ItemIntMap, Compare>::set
-if ( i >= 0 && container[i].in ) {
+(Item const item, PrioType const value)
-	if ( comp(value, container[i].prio) ) decrease(it, value);
+{
-	if ( comp(container[i].prio, value) ) increase(it, value);
+int i=iimap[item];
-} else push(it, value);
+if ( i >= 0 && container[i].in ) {
-}
+if ( comp(value, container[i].prio) ) decrease(item, value);
+if ( comp(container[i].prio, value) ) increase(item, value);
+} else push(item, value);
-void push (Item const it, PrioType const value) {
+}
-int i=iimap[it];
+template <typename Item, typename Prio, typename ItemIntMap,
+typename Compare>
+void FibHeap<Item, Prio, ItemIntMap, Compare>::push
+(Item const item, PrioType const value) {
+int i=iimap[item];
 if ( i < 0 ) {
 	int s=container.size();
-	iimap.set( it, s );
+	iimap.set( item, s );
 	store st;
-	st.name=it;
+	st.name=item;
 	container.push_back(st);
 	i=s;
 } else {
 	container[i].parent=container[i].child=-1;
 	container[i].degree=0;
 }
 container[i].prio=value;
 ++num_items;
 }
+template <typename Item, typename Prio, typename ItemIntMap,
-void pop() {
+typename Compare>
+void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
 /*The first case is that there are only one root.*/
 if ( container[minimum].left_neighbor==minimum ) {
 	container[minimum].in=false;
 	if ( container[minimum].degree!=0 ) {
 	  makeroot(container[minimum].child);
 	balance();
 } // the case where there are more roots
 --num_items;
 }
-void erase (const Item& it) {
+template <typename Item, typename Prio, typename ItemIntMap,
-int i=iimap[it];
+typename Compare>
+void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
+(const Item& item) {
+int i=iimap[item];
 if ( i >= 0 && container[i].in ) {
 	if ( container[i].parent!=-1 ) {
 	  int p=container[i].parent;
 	  cut(i,p);
 	  cascade(p);
 	}
 	minimum=i;     //As if its prio would be -infinity
 	pop();
 }
 }
+template <typename Item, typename Prio, typename ItemIntMap,
-void decrease (Item it, PrioType const value) {
+typename Compare>
-int i=iimap[it];
+void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
+(Item item, PrioType const value) {
+int i=iimap[item];
 container[i].prio=value;
 int p=container[i].parent;
 if ( p!=-1 && comp(value, container[p].prio) ) {
 	cut(i,p);
 	cascade(p);
 }
 if ( comp(value, container[minimum].prio) ) minimum=i;
 }
-state_enum state(const Item &it) const {
+template <typename Item, typename Prio, typename ItemIntMap,
-int i=iimap[it];
+typename Compare>
-if( i>=0 ) {
+void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
-	if ( container[i].in ) i=0;
-	else i=-2;
-}
-return state_enum(i);
-}
-private:
-void balance() {
 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
 std::vector<int> A(maxdeg,-1);
 	 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
 	 s=container[s].right_neighbor;
 } while ( s != m );
 }
+template <typename Item, typename Prio, typename ItemIntMap,
-void makeroot (int c) {
+typename Compare>
+void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
+(int c) {
 int s=c;
 do {
 	container[s].parent=-1;
 	s=container[s].right_neighbor;
 } while ( s != c );
 }
-void cut (int a, int b) {
+template <typename Item, typename Prio, typename ItemIntMap,
-/*
+typename Compare>
-*Replacing a from the children of b.
+void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
-*/
+(int a, int b) {
---container[b].degree;
+/*
+*Replacing a from the children of b.
-if ( container[b].degree !=0 ) {
+*/
-	int child=container[b].child;
+--container[b].degree;
-	if ( child==a )
-	  container[b].child=container[child].right_neighbor;
+if ( container[b].degree !=0 ) {
-	unlace(a);
+int child=container[b].child;
-}
+if ( child==a )
+	container[b].child=container[child].right_neighbor;
+unlace(a);
-/*Lacing a to the roots.*/
+}
-int right=container[minimum].right_neighbor;
-container[minimum].right_neighbor=a;
-container[a].left_neighbor=minimum;
+/*Lacing a to the roots.*/
-container[a].right_neighbor=right;
+int right=container[minimum].right_neighbor;
-container[right].left_neighbor=a;
+container[minimum].right_neighbor=a;
+container[a].left_neighbor=minimum;
-container[a].parent=-1;
+container[a].right_neighbor=right;
-container[a].marked=false;
+container[right].left_neighbor=a;
-}
+container[a].parent=-1;
+container[a].marked=false;
-void cascade (int a)
+}
+template <typename Item, typename Prio, typename ItemIntMap,
+typename Compare>
+void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
+(int a)
 {
 if ( container[a].parent!=-1 ) {
 	int p=container[a].parent;
 	if ( container[a].marked==false ) container[a].marked=true;
 	}
 }
 }
-void fuse (int a, int b) {
+template <typename Item, typename Prio, typename ItemIntMap,
+typename Compare>
+void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
+(int a, int b) {
 unlace(b);
 /*Lacing b under a.*/
 container[b].parent=a;
 ++container[a].degree;
 container[b].marked=false;
 }
 /*
 *It is invoked only if a has siblings.
 */
-void unlace (int a) {
+template <typename Item, typename Prio, typename ItemIntMap,
+typename Compare>
+void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
+(int a) {
 int leftn=container[a].left_neighbor;
 int rightn=container[a].right_neighbor;
 container[leftn].right_neighbor=rightn;
 container[rightn].left_neighbor=leftn;
 }
-class store {
-friend class FibHeap;
-Item name;
-int parent;
-int left_neighbor;
-int right_neighbor;
-int child;
-int degree;
-bool marked;
-bool in;
-PrioType prio;
-store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
-};
-};
 } //namespace hugo
 #endif

changeset 417	4ce3d5f675ea
parent 373	259ea2d741a2
child 430	60e4627e8c74