123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271 |
- // (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 <boost/config/no_tr1/cmath.hpp>
- #endif
- #include <iosfwd>
- #include <vector>
- #include <functional>
- #include <boost/config.hpp>
- #include <boost/property_map/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;
- _mark[v] = false;
- std::swap(u, v);
- }
- make_child(u, v, r);
- ++r;
- }
- _degree[v] = r;
- _mark[v] = false;
- }
- // 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[p]))
- 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;
- --_degree[p];
- 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 (_degree[x] > 0) {
- 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
|