diff -r b5eba564bb60 -r f393a8162688 lemon/fib_heap.h --- a/lemon/fib_heap.h Thu Dec 20 15:21:22 2007 +0000 +++ b/lemon/fib_heap.h Thu Dec 27 13:40:16 2007 +0000 @@ -41,31 +41,34 @@ /// ///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 - ///\e binary \e heap. + ///\ref BinHeap "binary heap". /// - ///\param Prio Type of the priority of the items. - ///\param ItemIntMap A read and writable Item int map, used internally + ///\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. + ///\param _Compare A class for the ordering of the priorities. The + ///default is \c std::less<_Prio>. /// ///\sa BinHeap ///\sa Dijkstra ///\author Jacint Szabo #ifdef DOXYGEN - template + template #else - template > + template > #endif class FibHeap { public: + typedef _ItemIntMap ItemIntMap; + typedef _Prio Prio; typedef typename ItemIntMap::Key Item; - typedef Prio PrioType; + typedef std::pair Pair; + typedef _Compare Compare; private: class store; @@ -78,7 +81,7 @@ public: ///Status of the nodes - enum state_enum { + enum State { ///The node is in the heap IN_HEAP = 0, ///The node has never been in the heap @@ -99,8 +102,8 @@ /// \c _iimap 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. - FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), - iimap(_iimap), comp(_comp), num_items() {} + FibHeap(ItemIntMap &_iimap, const Compare &_comp) + : minimum(0), iimap(_iimap), comp(_comp), num_items() {} /// \brief The number of items stored in the heap. /// @@ -128,163 +131,19 @@ /// 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 (Item const item, PrioType const value); + void set (const Item& item, const Prio& value) { + int i=iimap[item]; + 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); + } /// \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 (Item const item, PrioType const value); - - /// \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 { return container[minimum].name; } - - /// \brief Returns the minimum priority relative to \c Compare. - /// - /// It returns the minimum priority relative to \c Compare. - /// \pre The heap must be nonempty. - PrioType prio() const { return container[minimum].prio; } - - /// \brief Returns the priority of \c item. - /// - /// This function returns the priority of \c item. - /// \pre \c item must be in the heap. - PrioType& operator[](const Item& item) { - return container[iimap[item]].prio; - } - - /// \brief 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& item) const { - return container[iimap[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. - /// \pre The heap must be non-empty. - void pop(); - - /// \brief Deletes \c 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. - void erase (const Item& item); - - /// \brief 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 relative to \c Compare. - void decrease (Item item, PrioType const value); - - /// \brief 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 it is indeed necessary to increase - /// (relative to \c Compare) the priority of \c item, because this - /// method is inefficient. - void increase (Item item, PrioType const value) { - erase(item); - push(item, value); - } - - - /// \brief 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 &item) const { - int i=iimap[item]; - if( i>=0 ) { - if ( container[i].in ) i=0; - else i=-2; - } - return state_enum(i); - } - - /// \brief Sets the state of the \c 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. - /// \param i The item. - /// \param st The state. It should not be \c IN_HEAP. - void state(const Item& i, state_enum st) { - switch (st) { - case POST_HEAP: - case PRE_HEAP: - if (state(i) == IN_HEAP) { - erase(i); - } - iimap[i] = st; - break; - case IN_HEAP: - break; - } - } - - 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 - void FibHeap::set - (Item const item, PrioType const value) - { - int i=iimap[item]; - 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); - } - - template - void FibHeap::push - (Item const item, PrioType const value) { + void push (const Item& item, const Prio& value) { int i=iimap[item]; if ( i < 0 ) { int s=container.size(); @@ -314,9 +173,33 @@ ++num_items; } - template - void FibHeap::pop() { + /// \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 { return container[minimum].name; } + + /// \brief Returns the minimum priority relative to \c Compare. + /// + /// It returns the minimum priority relative to \c Compare. + /// \pre The heap must be nonempty. + const Prio& prio() const { return container[minimum].prio; } + + /// \brief Returns the priority of \c item. + /// + /// It returns the priority of \c item. + /// \pre \c item must be in the heap. + const Prio& operator[](const Item& item) const { + return container[iimap[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. + /// \pre The heap must be non-empty. + void pop() { /*The first case is that there are only one root.*/ if ( container[minimum].left_neighbor==minimum ) { container[minimum].in=false; @@ -333,7 +216,7 @@ int left=container[minimum].left_neighbor; int child=container[minimum].child; int last_child=container[child].left_neighbor; - + makeroot(child); container[left].right_neighbor=child; @@ -347,11 +230,11 @@ --num_items; } - - template - void FibHeap::erase - (const Item& item) { + /// \brief Deletes \c 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. + void erase (const Item& item) { int i=iimap[item]; if ( i >= 0 && container[i].in ) { @@ -363,12 +246,14 @@ minimum=i; //As if its prio would be -infinity pop(); } - } - - template - void FibHeap::decrease - (Item item, PrioType const value) { + } + + /// \brief 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 relative to \c Compare. + void decrease (Item item, const Prio& value) { int i=iimap[item]; container[i].prio=value; int p=container[i].parent; @@ -378,26 +263,75 @@ cascade(p); } if ( comp(value, container[minimum].prio) ) minimum=i; - } - + } - template - void FibHeap::balance() { + /// \brief 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 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) { + erase(item); + push(item, value); + } - int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; + + /// \brief 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 state(const Item &item) const { + int i=iimap[item]; + if( i>=0 ) { + if ( container[i].in ) i=0; + else i=-2; + } + return State(i); + } + + /// \brief Sets the state of the \c 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. + /// \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); + } + iimap[i] = st; + break; + case IN_HEAP: + break; + } + } + + private: + + void balance() { + + int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; - std::vector A(maxdeg,-1); + std::vector A(maxdeg,-1); - /* - *Recall that now minimum does not point to the minimum prio element. - *We set minimum to this during balance(). - */ - int anchor=container[minimum].left_neighbor; - int next=minimum; - bool end=false; + /* + *Recall that now minimum does not point to the minimum prio element. + *We set minimum to this during balance(). + */ + int anchor=container[minimum].left_neighbor; + int next=minimum; + bool end=false; - do { + do { int active=next; if ( anchor==active ) end=true; int d=container[active].degree; @@ -414,64 +348,53 @@ ++d; } A[d]=active; - } while ( !end ); + } while ( !end ); - while ( container[minimum].parent >=0 ) minimum=container[minimum].parent; - int s=minimum; - int m=minimum; - do { - if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; - s=container[s].right_neighbor; - } while ( s != m ); + while ( container[minimum].parent >=0 ) + minimum=container[minimum].parent; + int s=minimum; + int m=minimum; + do { + if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; + s=container[s].right_neighbor; + } while ( s != m ); } - template - void FibHeap::makeroot - (int c) { + void makeroot(int c) { int s=c; do { container[s].parent=-1; s=container[s].right_neighbor; } while ( s != c ); } - - - template - void FibHeap::cut - (int a, int b) { - /* - *Replacing a from the children of b. - */ - --container[b].degree; + + void cut(int a, int b) { + /* + *Replacing a from the children of b. + */ + --container[b].degree; - if ( container[b].degree !=0 ) { - int child=container[b].child; - if ( child==a ) - container[b].child=container[child].right_neighbor; - unlace(a); + if ( container[b].degree !=0 ) { + 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; + container[a].right_neighbor=right; + container[right].left_neighbor=a; + + container[a].parent=-1; + container[a].marked=false; } - - - /*Lacing a to the roots.*/ - int right=container[minimum].right_neighbor; - container[minimum].right_neighbor=a; - container[a].left_neighbor=minimum; - container[a].right_neighbor=right; - container[right].left_neighbor=a; - - container[a].parent=-1; - container[a].marked=false; - } - - template - void FibHeap::cascade - (int a) - { + void cascade(int a) { if ( container[a].parent!=-1 ) { int p=container[a].parent; @@ -483,11 +406,7 @@ } } - - template - void FibHeap::fuse - (int a, int b) { + void fuse(int a, int b) { unlace(b); /*Lacing b under a.*/ @@ -511,20 +430,33 @@ container[b].marked=false; } - - /* - *It is invoked only if a has siblings. - */ - template - void FibHeap::unlace - (int a) { + /* + *It is invoked only if a has siblings. + */ + void 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; + Prio prio; + + store() : parent(-1), child(-1), degree(), marked(false), in(true) {} + }; + }; } //namespace lemon