// (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