deba@681: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@681:  *
deba@681:  * This file is a part of LEMON, a generic C++ optimization library.
deba@681:  *
deba@681:  * Copyright (C) 2003-2009
deba@681:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@681:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@681:  *
deba@681:  * Permission to use, modify and distribute this software is granted
deba@681:  * provided that this copyright notice appears in all copies. For
deba@681:  * precise terms see the accompanying LICENSE file.
deba@681:  *
deba@681:  * This software is provided "AS IS" with no warranty of any kind,
deba@681:  * express or implied, and with no claim as to its suitability for any
deba@681:  * purpose.
deba@681:  *
deba@681:  */
deba@681: 
deba@681: #ifndef LEMON_FIB_HEAP_H
deba@681: #define LEMON_FIB_HEAP_H
deba@681: 
deba@681: ///\file
kpeter@710: ///\ingroup heaps
kpeter@709: ///\brief Fibonacci heap implementation.
deba@681: 
deba@681: #include <vector>
kpeter@709: #include <utility>
deba@681: #include <functional>
deba@681: #include <lemon/math.h>
deba@681: 
deba@681: namespace lemon {
deba@681: 
kpeter@710:   /// \ingroup heaps
deba@681:   ///
kpeter@709:   /// \brief Fibonacci heap data structure.
deba@681:   ///
kpeter@709:   /// This class implements the \e Fibonacci \e heap data structure.
kpeter@709:   /// It fully conforms to the \ref concepts::Heap "heap concept".
deba@681:   ///
kpeter@709:   /// The methods \ref increase() and \ref erase() are not efficient in a
kpeter@709:   /// Fibonacci heap. In case of many calls of these operations, it is
kpeter@709:   /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
deba@681:   ///
kpeter@709:   /// \tparam PR Type of the priorities of the items.
kpeter@709:   /// \tparam IM A read-writable item map with \c int values, used
kpeter@709:   /// internally to handle the cross references.
kpeter@709:   /// \tparam CMP A functor class for comparing the priorities.
kpeter@709:   /// The default is \c std::less<PR>.
deba@681: #ifdef DOXYGEN
kpeter@709:   template <typename PR, typename IM, typename CMP>
deba@681: #else
kpeter@709:   template <typename PR, typename IM, typename CMP = std::less<PR> >
deba@681: #endif
deba@681:   class FibHeap {
deba@681:   public:
kpeter@709: 
kpeter@709:     /// Type of the item-int map.
deba@683:     typedef IM ItemIntMap;
kpeter@709:     /// Type of the priorities.
kpeter@709:     typedef PR Prio;
kpeter@709:     /// Type of the items stored in the heap.
deba@681:     typedef typename ItemIntMap::Key Item;
kpeter@709:     /// Type of the item-priority pairs.
deba@681:     typedef std::pair<Item,Prio> Pair;
kpeter@709:     /// Functor type for comparing the priorities.
deba@683:     typedef CMP Compare;
deba@681: 
deba@681:   private:
deba@683:     class Store;
deba@681: 
deba@683:     std::vector<Store> _data;
deba@683:     int _minimum;
deba@683:     ItemIntMap &_iim;
deba@683:     Compare _comp;
deba@683:     int _num;
deba@681: 
deba@681:   public:
deba@683: 
kpeter@709:     /// \brief Type to represent the states of the items.
deba@683:     ///
kpeter@709:     /// Each item has a state associated to it. It can be "in heap",
kpeter@709:     /// "pre-heap" or "post-heap". The latter two are indifferent from the
deba@683:     /// heap's point of view, but may be useful to the user.
deba@683:     ///
deba@683:     /// The item-int map must be initialized in such way that it assigns
deba@683:     /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
deba@681:     enum State {
deba@683:       IN_HEAP = 0,    ///< = 0.
deba@683:       PRE_HEAP = -1,  ///< = -1.
deba@683:       POST_HEAP = -2  ///< = -2.
deba@681:     };
deba@681: 
kpeter@709:     /// \brief Constructor.
deba@681:     ///
kpeter@709:     /// Constructor.
kpeter@709:     /// \param map A map that assigns \c int values to the items.
kpeter@709:     /// It is used internally to handle the cross references.
kpeter@709:     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
deba@683:     explicit FibHeap(ItemIntMap &map)
deba@683:       : _minimum(0), _iim(map), _num() {}
deba@681: 
kpeter@709:     /// \brief Constructor.
deba@681:     ///
kpeter@709:     /// Constructor.
kpeter@709:     /// \param map A map that assigns \c int values to the items.
kpeter@709:     /// It is used internally to handle the cross references.
kpeter@709:     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
kpeter@709:     /// \param comp The function object used for comparing the priorities.
deba@683:     FibHeap(ItemIntMap &map, const Compare &comp)
deba@683:       : _minimum(0), _iim(map), _comp(comp), _num() {}
deba@681: 
deba@681:     /// \brief The number of items stored in the heap.
deba@681:     ///
kpeter@709:     /// This function returns the number of items stored in the heap.
deba@683:     int size() const { return _num; }
deba@681: 
kpeter@709:     /// \brief Check if the heap is empty.
deba@681:     ///
kpeter@709:     /// This function returns \c true if the heap is empty.
deba@683:     bool empty() const { return _num==0; }
deba@681: 
kpeter@709:     /// \brief Make the heap empty.
deba@681:     ///
kpeter@709:     /// This functon makes the heap empty.
kpeter@709:     /// It does not change the cross reference map. If you want to reuse
kpeter@709:     /// a heap that is not surely empty, you should first clear it and
kpeter@709:     /// then you should set the cross reference map to \c PRE_HEAP
kpeter@709:     /// for each item.
deba@681:     void clear() {
deba@683:       _data.clear(); _minimum = 0; _num = 0;
deba@681:     }
deba@681: 
kpeter@709:     /// \brief Insert an item into the heap with the given priority.
deba@681:     ///
kpeter@709:     /// This function inserts the given item into the heap with the
kpeter@709:     /// given priority.
kpeter@709:     /// \param item The item to insert.
kpeter@709:     /// \param prio The priority of the item.
kpeter@709:     /// \pre \e item must not be stored in the heap.
kpeter@709:     void push (const Item& item, const Prio& prio) {
deba@683:       int i=_iim[item];
deba@681:       if ( i < 0 ) {
deba@683:         int s=_data.size();
deba@683:         _iim.set( item, s );
deba@683:         Store st;
deba@681:         st.name=item;
deba@683:         _data.push_back(st);
deba@681:         i=s;
deba@681:       } else {
deba@683:         _data[i].parent=_data[i].child=-1;
deba@683:         _data[i].degree=0;
deba@683:         _data[i].in=true;
deba@683:         _data[i].marked=false;
deba@681:       }
deba@681: 
deba@683:       if ( _num ) {
deba@683:         _data[_data[_minimum].right_neighbor].left_neighbor=i;
deba@683:         _data[i].right_neighbor=_data[_minimum].right_neighbor;
deba@683:         _data[_minimum].right_neighbor=i;
deba@683:         _data[i].left_neighbor=_minimum;
kpeter@709:         if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
deba@681:       } else {
deba@683:         _data[i].right_neighbor=_data[i].left_neighbor=i;
deba@683:         _minimum=i;
deba@681:       }
kpeter@709:       _data[i].prio=prio;
deba@683:       ++_num;
deba@681:     }
deba@681: 
kpeter@709:     /// \brief Return the item having minimum priority.
deba@681:     ///
kpeter@709:     /// This function returns the item having minimum priority.
kpeter@709:     /// \pre The heap must be non-empty.
deba@683:     Item top() const { return _data[_minimum].name; }
deba@681: 
kpeter@709:     /// \brief The minimum priority.
deba@681:     ///
kpeter@709:     /// This function returns the minimum priority.
kpeter@709:     /// \pre The heap must be non-empty.
kpeter@709:     Prio prio() const { return _data[_minimum].prio; }
deba@681: 
kpeter@709:     /// \brief Remove the item having minimum priority.
deba@681:     ///
kpeter@709:     /// This function removes the item having minimum priority.
deba@681:     /// \pre The heap must be non-empty.
deba@681:     void pop() {
deba@681:       /*The first case is that there are only one root.*/
deba@683:       if ( _data[_minimum].left_neighbor==_minimum ) {
deba@683:         _data[_minimum].in=false;
deba@683:         if ( _data[_minimum].degree!=0 ) {
kpeter@711:           makeRoot(_data[_minimum].child);
deba@683:           _minimum=_data[_minimum].child;
deba@681:           balance();
deba@681:         }
deba@681:       } else {
deba@683:         int right=_data[_minimum].right_neighbor;
deba@683:         unlace(_minimum);
deba@683:         _data[_minimum].in=false;
deba@683:         if ( _data[_minimum].degree > 0 ) {
deba@683:           int left=_data[_minimum].left_neighbor;
deba@683:           int child=_data[_minimum].child;
deba@683:           int last_child=_data[child].left_neighbor;
deba@681: 
kpeter@711:           makeRoot(child);
deba@681: 
deba@683:           _data[left].right_neighbor=child;
deba@683:           _data[child].left_neighbor=left;
deba@683:           _data[right].left_neighbor=last_child;
deba@683:           _data[last_child].right_neighbor=right;
deba@681:         }
deba@683:         _minimum=right;
deba@681:         balance();
deba@681:       } // the case where there are more roots
deba@683:       --_num;
deba@681:     }
deba@681: 
kpeter@709:     /// \brief Remove the given item from the heap.
deba@681:     ///
kpeter@709:     /// This function removes the given item from the heap if it is
kpeter@709:     /// already stored.
kpeter@709:     /// \param item The item to delete.
kpeter@709:     /// \pre \e item must be in the heap.
deba@681:     void erase (const Item& item) {
deba@683:       int i=_iim[item];
deba@681: 
deba@683:       if ( i >= 0 && _data[i].in ) {
deba@683:         if ( _data[i].parent!=-1 ) {
deba@683:           int p=_data[i].parent;
deba@681:           cut(i,p);
deba@681:           cascade(p);
deba@681:         }
deba@683:         _minimum=i;     //As if its prio would be -infinity
deba@681:         pop();
deba@681:       }
deba@681:     }
deba@681: 
kpeter@709:     /// \brief The priority of the given item.
deba@681:     ///
kpeter@709:     /// This function returns the priority of the given item.
kpeter@709:     /// \param item The item.
kpeter@709:     /// \pre \e item must be in the heap.
kpeter@709:     Prio operator[](const Item& item) const {
kpeter@709:       return _data[_iim[item]].prio;
kpeter@709:     }
kpeter@709: 
kpeter@709:     /// \brief Set the priority of an item or insert it, if it is
kpeter@709:     /// not stored in the heap.
kpeter@709:     ///
kpeter@709:     /// This method sets the priority of the given item if it is
kpeter@709:     /// already stored in the heap. Otherwise it inserts the given
kpeter@709:     /// item into the heap with the given priority.
kpeter@709:     /// \param item The item.
kpeter@709:     /// \param prio The priority.
kpeter@709:     void set (const Item& item, const Prio& prio) {
deba@683:       int i=_iim[item];
kpeter@709:       if ( i >= 0 && _data[i].in ) {
kpeter@709:         if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
kpeter@709:         if ( _comp(_data[i].prio, prio) ) increase(item, prio);
kpeter@709:       } else push(item, prio);
kpeter@709:     }
kpeter@709: 
kpeter@709:     /// \brief Decrease the priority of an item to the given value.
kpeter@709:     ///
kpeter@709:     /// This function decreases the priority of an item to the given value.
kpeter@709:     /// \param item The item.
kpeter@709:     /// \param prio The priority.
kpeter@709:     /// \pre \e item must be stored in the heap with priority at least \e prio.
kpeter@709:     void decrease (const Item& item, const Prio& prio) {
kpeter@709:       int i=_iim[item];
kpeter@709:       _data[i].prio=prio;
deba@683:       int p=_data[i].parent;
deba@681: 
kpeter@709:       if ( p!=-1 && _comp(prio, _data[p].prio) ) {
deba@681:         cut(i,p);
deba@681:         cascade(p);
deba@681:       }
kpeter@709:       if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
deba@681:     }
deba@681: 
kpeter@709:     /// \brief Increase the priority of an item to the given value.
deba@681:     ///
kpeter@709:     /// This function increases the priority of an item to the given value.
kpeter@709:     /// \param item The item.
kpeter@709:     /// \param prio The priority.
kpeter@709:     /// \pre \e item must be stored in the heap with priority at most \e prio.
kpeter@709:     void increase (const Item& item, const Prio& prio) {
deba@681:       erase(item);
kpeter@709:       push(item, prio);
deba@681:     }
deba@681: 
kpeter@709:     /// \brief Return the state of an item.
deba@681:     ///
kpeter@709:     /// This method returns \c PRE_HEAP if the given item has never
kpeter@709:     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
kpeter@709:     /// and \c POST_HEAP otherwise.
kpeter@709:     /// In the latter case it is possible that the item will get back
kpeter@709:     /// to the heap again.
kpeter@709:     /// \param item The item.
deba@681:     State state(const Item &item) const {
deba@683:       int i=_iim[item];
deba@681:       if( i>=0 ) {
deba@683:         if ( _data[i].in ) i=0;
deba@681:         else i=-2;
deba@681:       }
deba@681:       return State(i);
deba@681:     }
deba@681: 
kpeter@709:     /// \brief Set the state of an item in the heap.
deba@681:     ///
kpeter@709:     /// This function sets the state of the given item in the heap.
kpeter@709:     /// It can be used to manually clear the heap when it is important
kpeter@709:     /// to achive better time complexity.
deba@681:     /// \param i The item.
deba@681:     /// \param st The state. It should not be \c IN_HEAP.
deba@681:     void state(const Item& i, State st) {
deba@681:       switch (st) {
deba@681:       case POST_HEAP:
deba@681:       case PRE_HEAP:
deba@681:         if (state(i) == IN_HEAP) {
deba@681:           erase(i);
deba@681:         }
deba@683:         _iim[i] = st;
deba@681:         break;
deba@681:       case IN_HEAP:
deba@681:         break;
deba@681:       }
deba@681:     }
deba@681: 
deba@681:   private:
deba@681: 
deba@681:     void balance() {
deba@681: 
deba@683:       int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
deba@681: 
deba@681:       std::vector<int> A(maxdeg,-1);
deba@681: 
deba@681:       /*
deba@681:        *Recall that now minimum does not point to the minimum prio element.
deba@681:        *We set minimum to this during balance().
deba@681:        */
deba@683:       int anchor=_data[_minimum].left_neighbor;
deba@683:       int next=_minimum;
deba@681:       bool end=false;
deba@681: 
deba@681:       do {
deba@681:         int active=next;
deba@681:         if ( anchor==active ) end=true;
deba@683:         int d=_data[active].degree;
deba@683:         next=_data[active].right_neighbor;
deba@681: 
deba@681:         while (A[d]!=-1) {
deba@683:           if( _comp(_data[active].prio, _data[A[d]].prio) ) {
deba@681:             fuse(active,A[d]);
deba@681:           } else {
deba@681:             fuse(A[d],active);
deba@681:             active=A[d];
deba@681:           }
deba@681:           A[d]=-1;
deba@681:           ++d;
deba@681:         }
deba@681:         A[d]=active;
deba@681:       } while ( !end );
deba@681: 
deba@681: 
deba@683:       while ( _data[_minimum].parent >=0 )
deba@683:         _minimum=_data[_minimum].parent;
deba@683:       int s=_minimum;
deba@683:       int m=_minimum;
deba@681:       do {
deba@683:         if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
deba@683:         s=_data[s].right_neighbor;
deba@681:       } while ( s != m );
deba@681:     }
deba@681: 
kpeter@711:     void makeRoot(int c) {
deba@681:       int s=c;
deba@681:       do {
deba@683:         _data[s].parent=-1;
deba@683:         s=_data[s].right_neighbor;
deba@681:       } while ( s != c );
deba@681:     }
deba@681: 
deba@681:     void cut(int a, int b) {
deba@681:       /*
deba@681:        *Replacing a from the children of b.
deba@681:        */
deba@683:       --_data[b].degree;
deba@681: 
deba@683:       if ( _data[b].degree !=0 ) {
deba@683:         int child=_data[b].child;
deba@681:         if ( child==a )
deba@683:           _data[b].child=_data[child].right_neighbor;
deba@681:         unlace(a);
deba@681:       }
deba@681: 
deba@681: 
deba@681:       /*Lacing a to the roots.*/
deba@683:       int right=_data[_minimum].right_neighbor;
deba@683:       _data[_minimum].right_neighbor=a;
deba@683:       _data[a].left_neighbor=_minimum;
deba@683:       _data[a].right_neighbor=right;
deba@683:       _data[right].left_neighbor=a;
deba@681: 
deba@683:       _data[a].parent=-1;
deba@683:       _data[a].marked=false;
deba@681:     }
deba@681: 
deba@681:     void cascade(int a) {
deba@683:       if ( _data[a].parent!=-1 ) {
deba@683:         int p=_data[a].parent;
deba@681: 
deba@683:         if ( _data[a].marked==false ) _data[a].marked=true;
deba@681:         else {
deba@681:           cut(a,p);
deba@681:           cascade(p);
deba@681:         }
deba@681:       }
deba@681:     }
deba@681: 
deba@681:     void fuse(int a, int b) {
deba@681:       unlace(b);
deba@681: 
deba@681:       /*Lacing b under a.*/
deba@683:       _data[b].parent=a;
deba@681: 
deba@683:       if (_data[a].degree==0) {
deba@683:         _data[b].left_neighbor=b;
deba@683:         _data[b].right_neighbor=b;
deba@683:         _data[a].child=b;
deba@681:       } else {
deba@683:         int child=_data[a].child;
deba@683:         int last_child=_data[child].left_neighbor;
deba@683:         _data[child].left_neighbor=b;
deba@683:         _data[b].right_neighbor=child;
deba@683:         _data[last_child].right_neighbor=b;
deba@683:         _data[b].left_neighbor=last_child;
deba@681:       }
deba@681: 
deba@683:       ++_data[a].degree;
deba@681: 
deba@683:       _data[b].marked=false;
deba@681:     }
deba@681: 
deba@681:     /*
deba@681:      *It is invoked only if a has siblings.
deba@681:      */
deba@681:     void unlace(int a) {
deba@683:       int leftn=_data[a].left_neighbor;
deba@683:       int rightn=_data[a].right_neighbor;
deba@683:       _data[leftn].right_neighbor=rightn;
deba@683:       _data[rightn].left_neighbor=leftn;
deba@681:     }
deba@681: 
deba@681: 
deba@683:     class Store {
deba@681:       friend class FibHeap;
deba@681: 
deba@681:       Item name;
deba@681:       int parent;
deba@681:       int left_neighbor;
deba@681:       int right_neighbor;
deba@681:       int child;
deba@681:       int degree;
deba@681:       bool marked;
deba@681:       bool in;
deba@681:       Prio prio;
deba@681: 
deba@683:       Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
deba@681:     };
deba@681:   };
deba@681: 
deba@681: } //namespace lemon
deba@681: 
deba@681: #endif //LEMON_FIB_HEAP_H
deba@681: