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