1 // (C) Copyright Jeremy Siek    2004.

     2 // Distributed under the Boost Software License, Version 1.0. (See

     3 // accompanying file LICENSE_1_0.txt or copy at

     4 // http://www.boost.org/LICENSE_1_0.txt)

     5 #ifndef BOOST_FIBONACCI_HEAP_HPP

     6 #define BOOST_FIBONACCI_HEAP_HPP

     7 

     8 #if defined(__sgi) && !defined(__GNUC__)

     9 # include <math.h>

    10 #else

    11 # include <cmath>

    12 #endif

    13 #include <iosfwd>

    14 #include <vector>

    15 #include <functional>

    16 #include <boost/config.hpp>

    17 #include <boost/property_map.hpp>

    18 

    19 //

    20 // An adaptation of Knuth's Fibonacci heap implementation

    21 // in "The Stanford Graph Base", pages 475-482.

    22 //

    23 

    24 namespace boost {

    25 

    26 

    27 template <class T, 

    28           class Compare = std::less<T>,

    29           class ID = identity_property_map>

    30 class fibonacci_heap

    31 {

    32   typedef typename boost::property_traits<ID>::value_type size_type;

    33   typedef T value_type;

    34 protected:

    35   typedef fibonacci_heap self;

    36   typedef std::vector<size_type> LinkVec;

    37   typedef typename LinkVec::iterator LinkIter;

    38 public:

    39 

    40   fibonacci_heap(size_type n, 

    41                  const Compare& cmp, 

    42                  const ID& id = identity_property_map())

    43     : _key(n), _left(n), _right(n), _p(n), _mark(n), _degree(n),

    44       _n(0), _root(n), _id(id), _compare(cmp), _child(n),

    45 #if defined(BOOST_MSVC) || defined(__ICL) // need a new macro?

    46       new_roots(size_type(log(float(n))) + 5) { }

    47 #else

    48       new_roots(size_type(std::log(float(n))) + 5) { }

    49 #endif

    50 

    51   // 33

    52   void push(const T& d) {

    53     ++_n;

    54     size_type v = get(_id, d);

    55     _key[v] = d;

    56     _p[v] = nil();

    57     _degree[v] = 0;

    58     _mark[v] = false;

    59     _child[v] = nil();

    60     if (_root == nil()) {

    61       _root = _left[v] = _right[v] = v;

    62       //std::cout << "root added" << std::endl;

    63     } else {

    64       size_type u = _left[_root];

    65       _left[v] = u;

    66       _right[v] = _root;

    67       _left[_root] = _right[u] = v;

    68       if (_compare(d, _key[_root]))

    69         _root = v;

    70       //std::cout << "non-root node added" << std::endl;

    71     }

    72   }

    73   T& top() { return _key[_root]; }

    74   const T& top() const { return _key[_root]; }

    75 

    76   // 38

    77   void pop() {

    78     --_n;

    79     int h = -1;

    80     size_type v, w;

    81     if (_root != nil()) {

    82       if (_degree[_root] == 0) {

    83         v = _right[_root];

    84       } else {

    85         w = _child[_root];

    86         v = _right[w];

    87         _right[w] = _right[_root];

    88         for (w = v; w != _right[_root]; w = _right[w])

    89           _p[w] = nil();

    90       }

    91       while (v != _root) {

    92         w = _right[v];

    93         add_tree_to_new_roots(v, new_roots.begin(), h);

    94         v = w;

    95       }

    96       rebuild_root_list(new_roots.begin(), h);

    97     }

    98   }

    99   // 39

   100   inline void add_tree_to_new_roots(size_type v, 

   101                                     LinkIter new_roots,

   102                                     int& h)

   103   {

   104     int r;

   105     size_type u;

   106     r = _degree[v];

   107     while (1) {

   108       if (h < r) {

   109         do { 

   110           ++h; 

   111           new_roots[h] = (h == r ? v : nil());

   112         } while (h < r);

   113         break;

   114       }

   115       if (new_roots[r] == nil()) {

   116         new_roots[r] = v;

   117         break;

   118       }

   119       u = new_roots[r];

   120       new_roots[r] = nil();

   121       if (_compare(_key[u], _key[v])) {

   122         _degree[v] = r;

   123         std::swap(u, v);

   124       }

   125       make_child(u, v, r);

   126       ++r;

   127     }

   128     _degree[v] = r;

   129   }

   130   // 40

   131   void make_child(size_type u, size_type v, size_type r) {

   132     if (r == 0) {

   133       _child[v] = u;

   134       _left[u] = u;

   135       _right[u] = u;

   136     } else {

   137       size_type t = _child[v];

   138       _right[u] = _right[t];

   139       _left[u] = t;

   140       _right[t] = u;

   141       _left[_right[u]] = u;

   142     }

   143     _p[u] = v;

   144   }

   145   // 41

   146   inline void rebuild_root_list(LinkIter new_roots, int& h)

   147   {

   148     size_type u, v, w;

   149     if (h < 0)

   150       _root = nil();

   151     else {

   152       T d;

   153       u = v = new_roots[h];

   154       d = _key[u];

   155       _root = u;

   156       for (h--; h >= 0; --h)

   157         if (new_roots[h] != nil()) {

   158           w = new_roots[h];

   159           _left[w] = v;

   160           _right[v] = w;

   161           if (_compare(_key[w], d)) {

   162             _root = w;

   163             d = _key[w];

   164           }

   165           v = w;

   166         }

   167       _right[v] = u;

   168       _left[u] = v;

   169     }

   170   }

   171 

   172   // 34

   173   void update(const T& d) {

   174     size_type v = get(_id, d);

   175     assert(!_compare(_key[v], d));

   176     _key[v] = d;

   177     size_type p = _p[v];

   178     if (p == nil()) {

   179       if (_compare(d, _key[_root]))

   180         _root = v;

   181     } else if (_compare(d, _key[_root]))

   182       while (1) {

   183         size_type r = _degree[p];

   184         if (r >= 2)

   185           remove_from_family(v, p);

   186         insert_into_forest(v, d);

   187         size_type pp = _p[p];

   188         if (pp == nil()) {

   189           --_degree[p];

   190           break;

   191         }

   192         if (_mark[p] == false) {

   193           _mark[p] = true;

   194           break;

   195         } else

   196           --_degree[p];

   197         v = p;

   198         p = pp;

   199       }

   200   }

   201 

   202   inline size_type size() const { return _n; }

   203   inline bool empty() const { return _n == 0; }

   204 

   205   void print(std::ostream& os) {

   206     if (_root != nil()) {

   207       size_type i = _root;

   208       do {

   209         print_recur(i, os);

   210         os << std::endl;

   211         i = _right[i];

   212       } while (i != _root);

   213     }

   214   }

   215 

   216 protected:

   217   // 35

   218   inline void remove_from_family(size_type v, size_type p) {

   219     size_type u = _left[v];

   220     size_type w = _right[v];

   221     _right[u] = w;

   222     _left[w] = u;

   223     if (_child[p] == v)

   224       _child[p] = w;

   225   }

   226   // 36

   227   inline void insert_into_forest(size_type v, const T& d) {

   228     _p[v] = nil();

   229     size_type u = _left[_root];

   230     _left[v] = u;

   231     _right[v] = _root;

   232     _left[_root] = _right[u] = v;

   233     if (_compare(d, _key[_root]))

   234       _root = v;

   235   }

   236 

   237   void print_recur(size_type x, std::ostream& os) {

   238     if (x != nil()) {

   239       os << x;

   240       if (_child[x] != nil()) {

   241         os << "(";

   242         size_type i = _child[x];

   243         do {

   244           print_recur(i, os); os << " ";

   245           i = _right[i];

   246         } while (i != _child[x]);

   247         os << ")";

   248       }

   249     }

   250   }

   251   

   252   size_type nil() const { return _left.size(); }

   253 

   254   std::vector<T> _key;

   255   LinkVec _left, _right, _p;

   256   std::vector<bool> _mark;

   257   LinkVec _degree;

   258   size_type _n, _root;

   259   ID _id;

   260   Compare _compare;

   261   LinkVec _child;

   262   LinkVec new_roots;

   263 };

   264 

   265 } // namespace boost

   266 

   267 

   268 #endif // BOOST_FIBONACCI_HEAP_HPP