Chris@16: // (C) Copyright Jeremy Siek    2004.
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: #ifndef BOOST_FIBONACCI_HEAP_HPP
Chris@16: #define BOOST_FIBONACCI_HEAP_HPP
Chris@16: 
Chris@16: #if defined(__sgi) && !defined(__GNUC__)
Chris@16: # include <math.h>
Chris@16: #else
Chris@16: # include <boost/config/no_tr1/cmath.hpp>
Chris@16: #endif
Chris@16: #include <iosfwd>
Chris@16: #include <vector>
Chris@16: #include <functional>
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: 
Chris@16: //
Chris@16: // An adaptation of Knuth's Fibonacci heap implementation
Chris@16: // in "The Stanford Graph Base", pages 475-482.
Chris@16: //
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: 
Chris@16: template <class T, 
Chris@16:           class Compare = std::less<T>,
Chris@16:           class ID = identity_property_map>
Chris@16: class fibonacci_heap
Chris@16: {
Chris@16:   typedef typename boost::property_traits<ID>::value_type size_type;
Chris@16:   typedef T value_type;
Chris@16: protected:
Chris@16:   typedef fibonacci_heap self;
Chris@16:   typedef std::vector<size_type> LinkVec;
Chris@16:   typedef typename LinkVec::iterator LinkIter;
Chris@16: public:
Chris@16: 
Chris@16:   fibonacci_heap(size_type n, 
Chris@16:                  const Compare& cmp, 
Chris@16:                  const ID& id = identity_property_map())
Chris@16:     : _key(n), _left(n), _right(n), _p(n), _mark(n), _degree(n),
Chris@16:       _n(0), _root(n), _id(id), _compare(cmp), _child(n),
Chris@16: #if defined(BOOST_MSVC) || defined(__ICL) // need a new macro?
Chris@16:       new_roots(size_type(log(float(n))) + 5) { }
Chris@16: #else
Chris@16:       new_roots(size_type(std::log(float(n))) + 5) { }
Chris@16: #endif
Chris@16: 
Chris@16:   // 33
Chris@16:   void push(const T& d) {
Chris@16:     ++_n;
Chris@16:     size_type v = get(_id, d);
Chris@16:     _key[v] = d;
Chris@16:     _p[v] = nil();
Chris@16:     _degree[v] = 0;
Chris@16:     _mark[v] = false;
Chris@16:     _child[v] = nil();
Chris@16:     if (_root == nil()) {
Chris@16:       _root = _left[v] = _right[v] = v;
Chris@16:       //std::cout << "root added" << std::endl;
Chris@16:     } else {
Chris@16:       size_type u = _left[_root];
Chris@16:       _left[v] = u;
Chris@16:       _right[v] = _root;
Chris@16:       _left[_root] = _right[u] = v;
Chris@16:       if (_compare(d, _key[_root]))
Chris@16:         _root = v;
Chris@16:       //std::cout << "non-root node added" << std::endl;
Chris@16:     }
Chris@16:   }
Chris@16:   T& top() { return _key[_root]; }
Chris@16:   const T& top() const { return _key[_root]; }
Chris@16: 
Chris@16:   // 38
Chris@16:   void pop() {
Chris@16:     --_n;
Chris@16:     int h = -1;
Chris@16:     size_type v, w;
Chris@16:     if (_root != nil()) {
Chris@16:       if (_degree[_root] == 0) {
Chris@16:         v = _right[_root];
Chris@16:       } else {
Chris@16:         w = _child[_root];
Chris@16:         v = _right[w];
Chris@16:         _right[w] = _right[_root];
Chris@16:         for (w = v; w != _right[_root]; w = _right[w])
Chris@16:           _p[w] = nil();
Chris@16:       }
Chris@16:       while (v != _root) {
Chris@16:         w = _right[v];
Chris@16:         add_tree_to_new_roots(v, new_roots.begin(), h);
Chris@16:         v = w;
Chris@16:       }
Chris@16:       rebuild_root_list(new_roots.begin(), h);
Chris@16:     }
Chris@16:   }
Chris@16:   // 39
Chris@16:   inline void add_tree_to_new_roots(size_type v, 
Chris@16:                                     LinkIter new_roots,
Chris@16:                                     int& h)
Chris@16:   {
Chris@16:     int r;
Chris@16:     size_type u;
Chris@16:     r = _degree[v];
Chris@16:     while (1) {
Chris@16:       if (h < r) {
Chris@16:         do { 
Chris@16:           ++h; 
Chris@16:           new_roots[h] = (h == r ? v : nil());
Chris@16:         } while (h < r);
Chris@16:         break;
Chris@16:       }
Chris@16:       if (new_roots[r] == nil()) {
Chris@16:         new_roots[r] = v;
Chris@16:         break;
Chris@16:       }
Chris@16:       u = new_roots[r];
Chris@16:       new_roots[r] = nil();
Chris@16:       if (_compare(_key[u], _key[v])) {
Chris@16:         _degree[v] = r;
Chris@16:         _mark[v] = false;
Chris@16:         std::swap(u, v);
Chris@16:       }
Chris@16:       make_child(u, v, r);
Chris@16:       ++r;
Chris@16:     }
Chris@16:     _degree[v] = r;
Chris@16:     _mark[v] = false;
Chris@16:   }
Chris@16:   // 40
Chris@16:   void make_child(size_type u, size_type v, size_type r) {
Chris@16:     if (r == 0) {
Chris@16:       _child[v] = u;
Chris@16:       _left[u] = u;
Chris@16:       _right[u] = u;
Chris@16:     } else {
Chris@16:       size_type t = _child[v];
Chris@16:       _right[u] = _right[t];
Chris@16:       _left[u] = t;
Chris@16:       _right[t] = u;
Chris@16:       _left[_right[u]] = u;
Chris@16:     }
Chris@16:     _p[u] = v;
Chris@16:   }
Chris@16:   // 41
Chris@16:   inline void rebuild_root_list(LinkIter new_roots, int& h)
Chris@16:   {
Chris@16:     size_type u, v, w;
Chris@16:     if (h < 0)
Chris@16:       _root = nil();
Chris@16:     else {
Chris@16:       T d;
Chris@16:       u = v = new_roots[h];
Chris@16:       d = _key[u];
Chris@16:       _root = u;
Chris@16:       for (h--; h >= 0; --h)
Chris@16:         if (new_roots[h] != nil()) {
Chris@16:           w = new_roots[h];
Chris@16:           _left[w] = v;
Chris@16:           _right[v] = w;
Chris@16:           if (_compare(_key[w], d)) {
Chris@16:             _root = w;
Chris@16:             d = _key[w];
Chris@16:           }
Chris@16:           v = w;
Chris@16:         }
Chris@16:       _right[v] = u;
Chris@16:       _left[u] = v;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // 34
Chris@16:   void update(const T& d) {
Chris@16:     size_type v = get(_id, d);
Chris@16:     assert(!_compare(_key[v], d));
Chris@16:     _key[v] = d;
Chris@16:     size_type p = _p[v];
Chris@16:     if (p == nil()) {
Chris@16:       if (_compare(d, _key[_root]))
Chris@16:         _root = v;
Chris@16:     } else if (_compare(d, _key[p]))
Chris@16:       while (1) {
Chris@16:         size_type r = _degree[p];
Chris@16:         if (r >= 2)
Chris@16:           remove_from_family(v, p);
Chris@16:         insert_into_forest(v, d);
Chris@16:         size_type pp = _p[p];
Chris@16:         if (pp == nil()) {
Chris@16:           --_degree[p];
Chris@16:           break;
Chris@16:         }
Chris@16:         if (_mark[p] == false) {
Chris@16:           _mark[p] = true;
Chris@16:           --_degree[p];
Chris@16:           break;
Chris@16:         } else
Chris@16:           --_degree[p];
Chris@16:         v = p;
Chris@16:         p = pp;
Chris@16:       }
Chris@16:   }
Chris@16: 
Chris@16:   inline size_type size() const { return _n; }
Chris@16:   inline bool empty() const { return _n == 0; }
Chris@16: 
Chris@16:   void print(std::ostream& os) {
Chris@16:     if (_root != nil()) {
Chris@16:       size_type i = _root;
Chris@16:       do {
Chris@16:         print_recur(i, os);
Chris@16:         os << std::endl;
Chris@16:         i = _right[i];
Chris@16:       } while (i != _root);
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16: protected:
Chris@16:   // 35
Chris@16:   inline void remove_from_family(size_type v, size_type p) {
Chris@16:     size_type u = _left[v];
Chris@16:     size_type w = _right[v];
Chris@16:     _right[u] = w;
Chris@16:     _left[w] = u;
Chris@16:     if (_child[p] == v)
Chris@16:       _child[p] = w;
Chris@16:   }
Chris@16:   // 36
Chris@16:   inline void insert_into_forest(size_type v, const T& d) {
Chris@16:     _p[v] = nil();
Chris@16:     size_type u = _left[_root];
Chris@16:     _left[v] = u;
Chris@16:     _right[v] = _root;
Chris@16:     _left[_root] = _right[u] = v;
Chris@16:     if (_compare(d, _key[_root]))
Chris@16:       _root = v;
Chris@16:   }
Chris@16: 
Chris@16:   void print_recur(size_type x, std::ostream& os) {
Chris@16:     if (x != nil()) {
Chris@16:       os << x;
Chris@16:       if (_degree[x] > 0) {
Chris@16:         os << "(";
Chris@16:         size_type i = _child[x];
Chris@16:         do {
Chris@16:           print_recur(i, os); os << " ";
Chris@16:           i = _right[i];
Chris@16:         } while (i != _child[x]);
Chris@16:         os << ")";
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16:   
Chris@16:   size_type nil() const { return _left.size(); }
Chris@16: 
Chris@16:   std::vector<T> _key;
Chris@16:   LinkVec _left, _right, _p;
Chris@16:   std::vector<bool> _mark;
Chris@16:   LinkVec _degree;
Chris@16:   size_type _n, _root;
Chris@16:   ID _id;
Chris@16:   Compare _compare;
Chris@16:   LinkVec _child;
Chris@16:   LinkVec new_roots;
Chris@16: };
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_FIBONACCI_HEAP_HPP