// (C) Copyright Jeremy Siek    2004.

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

 // accompanying file LICENSE_1_0.txt or copy at

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

 #ifndef BOOST_FIBONACCI_HEAP_HPP

 #define BOOST_FIBONACCI_HEAP_HPP

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

 # include <math.h>

 #else

 # include <cmath>

 #endif

 #include <iosfwd>

 #include <vector>

 #include <functional>

 #include <boost/config.hpp>

 #include <boost/property_map.hpp>

 //

 // An adaptation of Knuth's Fibonacci heap implementation

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

 //

 namespace boost {

 template <class T, 

           class Compare = std::less<T>,

           class ID = identity_property_map>

 class fibonacci_heap

 {

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

   typedef T value_type;

 protected:

   typedef fibonacci_heap self;

   typedef std::vector<size_type> LinkVec;

   typedef typename LinkVec::iterator LinkIter;

 public:

   fibonacci_heap(size_type n, 

                  const Compare& cmp, 

                  const ID& id = identity_property_map())

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

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

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

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

 #else

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

 #endif

   // 33

   void push(const T& d) {

     ++_n;

     size_type v = get(_id, d);

     _key[v] = d;

     _p[v] = nil();

     _degree[v] = 0;

     _mark[v] = false;

     _child[v] = nil();

     if (_root == nil()) {

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

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

     } else {

       size_type u = _left[_root];

       _left[v] = u;

       _right[v] = _root;

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

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

         _root = v;

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

     }

   }

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

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

   // 38

   void pop() {

     --_n;

     int h = -1;

     size_type v, w;

     if (_root != nil()) {

       if (_degree[_root] == 0) {

         v = _right[_root];

       } else {

         w = _child[_root];

         v = _right[w];

         _right[w] = _right[_root];

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

           _p[w] = nil();

       }

       while (v != _root) {

         w = _right[v];

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

         v = w;

       }

       rebuild_root_list(new_roots.begin(), h);

     }

   }

   // 39

   inline void add_tree_to_new_roots(size_type v, 

                                     LinkIter new_roots,

                                     int& h)

   {

     int r;

     size_type u;

     r = _degree[v];

     while (1) {

       if (h < r) {

         do { 

           ++h; 

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

         } while (h < r);

         break;

       }

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

         new_roots[r] = v;

         break;

       }

       u = new_roots[r];

       new_roots[r] = nil();

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

         _degree[v] = r;

         std::swap(u, v);

       }

       make_child(u, v, r);

       ++r;

     }

     _degree[v] = r;

   }

   // 40

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

     if (r == 0) {

       _child[v] = u;

       _left[u] = u;

       _right[u] = u;

     } else {

       size_type t = _child[v];

       _right[u] = _right[t];

       _left[u] = t;

       _right[t] = u;

       _left[_right[u]] = u;

     }

     _p[u] = v;

   }

   // 41

   inline void rebuild_root_list(LinkIter new_roots, int& h)

   {

     size_type u, v, w;

     if (h < 0)

       _root = nil();

     else {

       T d;

       u = v = new_roots[h];

       d = _key[u];

       _root = u;

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

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

           w = new_roots[h];

           _left[w] = v;

           _right[v] = w;

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

             _root = w;

             d = _key[w];

           }

           v = w;

         }

       _right[v] = u;

       _left[u] = v;

     }

   }

   // 34

   void update(const T& d) {

     size_type v = get(_id, d);

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

     _key[v] = d;

     size_type p = _p[v];

     if (p == nil()) {

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

         _root = v;

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

       while (1) {

         size_type r = _degree[p];

         if (r >= 2)

           remove_from_family(v, p);

         insert_into_forest(v, d);

         size_type pp = _p[p];

         if (pp == nil()) {

           --_degree[p];

           break;

         }

         if (_mark[p] == false) {

           _mark[p] = true;

           break;

         } else

           --_degree[p];

         v = p;

         p = pp;

       }

   }

   inline size_type size() const { return _n; }

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

   void print(std::ostream& os) {

     if (_root != nil()) {

       size_type i = _root;

       do {

         print_recur(i, os);

         os << std::endl;

         i = _right[i];

       } while (i != _root);

     }

   }

 protected:

   // 35

   inline void remove_from_family(size_type v, size_type p) {

     size_type u = _left[v];

     size_type w = _right[v];

     _right[u] = w;

     _left[w] = u;

     if (_child[p] == v)

       _child[p] = w;

   }

   // 36

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

     _p[v] = nil();

     size_type u = _left[_root];

     _left[v] = u;

     _right[v] = _root;

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

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

       _root = v;

   }

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

     if (x != nil()) {

       os << x;

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

         os << "(";

         size_type i = _child[x];

         do {

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

           i = _right[i];

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

         os << ")";

       }

     }

   }

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

   std::vector<T> _key;

   LinkVec _left, _right, _p;

   std::vector<bool> _mark;

   LinkVec _degree;

   size_type _n, _root;

   ID _id;

   Compare _compare;

   LinkVec _child;

   LinkVec new_roots;

 };

 } // namespace boost

 #endif // BOOST_FIBONACCI_HEAP_HPP