1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ossrv_pub/boost_apis/boost/pending/fibonacci_heap.hpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,268 @@
1.4 +// (C) Copyright Jeremy Siek 2004.
1.5 +// Distributed under the Boost Software License, Version 1.0. (See
1.6 +// accompanying file LICENSE_1_0.txt or copy at
1.7 +// http://www.boost.org/LICENSE_1_0.txt)
1.8 +#ifndef BOOST_FIBONACCI_HEAP_HPP
1.9 +#define BOOST_FIBONACCI_HEAP_HPP
1.10 +
1.11 +#if defined(__sgi) && !defined(__GNUC__)
1.12 +# include <math.h>
1.13 +#else
1.14 +# include <cmath>
1.15 +#endif
1.16 +#include <iosfwd>
1.17 +#include <vector>
1.18 +#include <functional>
1.19 +#include <boost/config.hpp>
1.20 +#include <boost/property_map.hpp>
1.21 +
1.22 +//
1.23 +// An adaptation of Knuth's Fibonacci heap implementation
1.24 +// in "The Stanford Graph Base", pages 475-482.
1.25 +//
1.26 +
1.27 +namespace boost {
1.28 +
1.29 +
1.30 +template <class T,
1.31 + class Compare = std::less<T>,
1.32 + class ID = identity_property_map>
1.33 +class fibonacci_heap
1.34 +{
1.35 + typedef typename boost::property_traits<ID>::value_type size_type;
1.36 + typedef T value_type;
1.37 +protected:
1.38 + typedef fibonacci_heap self;
1.39 + typedef std::vector<size_type> LinkVec;
1.40 + typedef typename LinkVec::iterator LinkIter;
1.41 +public:
1.42 +
1.43 + fibonacci_heap(size_type n,
1.44 + const Compare& cmp,
1.45 + const ID& id = identity_property_map())
1.46 + : _key(n), _left(n), _right(n), _p(n), _mark(n), _degree(n),
1.47 + _n(0), _root(n), _id(id), _compare(cmp), _child(n),
1.48 +#if defined(BOOST_MSVC) || defined(__ICL) // need a new macro?
1.49 + new_roots(size_type(log(float(n))) + 5) { }
1.50 +#else
1.51 + new_roots(size_type(std::log(float(n))) + 5) { }
1.52 +#endif
1.53 +
1.54 + // 33
1.55 + void push(const T& d) {
1.56 + ++_n;
1.57 + size_type v = get(_id, d);
1.58 + _key[v] = d;
1.59 + _p[v] = nil();
1.60 + _degree[v] = 0;
1.61 + _mark[v] = false;
1.62 + _child[v] = nil();
1.63 + if (_root == nil()) {
1.64 + _root = _left[v] = _right[v] = v;
1.65 + //std::cout << "root added" << std::endl;
1.66 + } else {
1.67 + size_type u = _left[_root];
1.68 + _left[v] = u;
1.69 + _right[v] = _root;
1.70 + _left[_root] = _right[u] = v;
1.71 + if (_compare(d, _key[_root]))
1.72 + _root = v;
1.73 + //std::cout << "non-root node added" << std::endl;
1.74 + }
1.75 + }
1.76 + T& top() { return _key[_root]; }
1.77 + const T& top() const { return _key[_root]; }
1.78 +
1.79 + // 38
1.80 + void pop() {
1.81 + --_n;
1.82 + int h = -1;
1.83 + size_type v, w;
1.84 + if (_root != nil()) {
1.85 + if (_degree[_root] == 0) {
1.86 + v = _right[_root];
1.87 + } else {
1.88 + w = _child[_root];
1.89 + v = _right[w];
1.90 + _right[w] = _right[_root];
1.91 + for (w = v; w != _right[_root]; w = _right[w])
1.92 + _p[w] = nil();
1.93 + }
1.94 + while (v != _root) {
1.95 + w = _right[v];
1.96 + add_tree_to_new_roots(v, new_roots.begin(), h);
1.97 + v = w;
1.98 + }
1.99 + rebuild_root_list(new_roots.begin(), h);
1.100 + }
1.101 + }
1.102 + // 39
1.103 + inline void add_tree_to_new_roots(size_type v,
1.104 + LinkIter new_roots,
1.105 + int& h)
1.106 + {
1.107 + int r;
1.108 + size_type u;
1.109 + r = _degree[v];
1.110 + while (1) {
1.111 + if (h < r) {
1.112 + do {
1.113 + ++h;
1.114 + new_roots[h] = (h == r ? v : nil());
1.115 + } while (h < r);
1.116 + break;
1.117 + }
1.118 + if (new_roots[r] == nil()) {
1.119 + new_roots[r] = v;
1.120 + break;
1.121 + }
1.122 + u = new_roots[r];
1.123 + new_roots[r] = nil();
1.124 + if (_compare(_key[u], _key[v])) {
1.125 + _degree[v] = r;
1.126 + std::swap(u, v);
1.127 + }
1.128 + make_child(u, v, r);
1.129 + ++r;
1.130 + }
1.131 + _degree[v] = r;
1.132 + }
1.133 + // 40
1.134 + void make_child(size_type u, size_type v, size_type r) {
1.135 + if (r == 0) {
1.136 + _child[v] = u;
1.137 + _left[u] = u;
1.138 + _right[u] = u;
1.139 + } else {
1.140 + size_type t = _child[v];
1.141 + _right[u] = _right[t];
1.142 + _left[u] = t;
1.143 + _right[t] = u;
1.144 + _left[_right[u]] = u;
1.145 + }
1.146 + _p[u] = v;
1.147 + }
1.148 + // 41
1.149 + inline void rebuild_root_list(LinkIter new_roots, int& h)
1.150 + {
1.151 + size_type u, v, w;
1.152 + if (h < 0)
1.153 + _root = nil();
1.154 + else {
1.155 + T d;
1.156 + u = v = new_roots[h];
1.157 + d = _key[u];
1.158 + _root = u;
1.159 + for (h--; h >= 0; --h)
1.160 + if (new_roots[h] != nil()) {
1.161 + w = new_roots[h];
1.162 + _left[w] = v;
1.163 + _right[v] = w;
1.164 + if (_compare(_key[w], d)) {
1.165 + _root = w;
1.166 + d = _key[w];
1.167 + }
1.168 + v = w;
1.169 + }
1.170 + _right[v] = u;
1.171 + _left[u] = v;
1.172 + }
1.173 + }
1.174 +
1.175 + // 34
1.176 + void update(const T& d) {
1.177 + size_type v = get(_id, d);
1.178 + assert(!_compare(_key[v], d));
1.179 + _key[v] = d;
1.180 + size_type p = _p[v];
1.181 + if (p == nil()) {
1.182 + if (_compare(d, _key[_root]))
1.183 + _root = v;
1.184 + } else if (_compare(d, _key[_root]))
1.185 + while (1) {
1.186 + size_type r = _degree[p];
1.187 + if (r >= 2)
1.188 + remove_from_family(v, p);
1.189 + insert_into_forest(v, d);
1.190 + size_type pp = _p[p];
1.191 + if (pp == nil()) {
1.192 + --_degree[p];
1.193 + break;
1.194 + }
1.195 + if (_mark[p] == false) {
1.196 + _mark[p] = true;
1.197 + break;
1.198 + } else
1.199 + --_degree[p];
1.200 + v = p;
1.201 + p = pp;
1.202 + }
1.203 + }
1.204 +
1.205 + inline size_type size() const { return _n; }
1.206 + inline bool empty() const { return _n == 0; }
1.207 +
1.208 + void print(std::ostream& os) {
1.209 + if (_root != nil()) {
1.210 + size_type i = _root;
1.211 + do {
1.212 + print_recur(i, os);
1.213 + os << std::endl;
1.214 + i = _right[i];
1.215 + } while (i != _root);
1.216 + }
1.217 + }
1.218 +
1.219 +protected:
1.220 + // 35
1.221 + inline void remove_from_family(size_type v, size_type p) {
1.222 + size_type u = _left[v];
1.223 + size_type w = _right[v];
1.224 + _right[u] = w;
1.225 + _left[w] = u;
1.226 + if (_child[p] == v)
1.227 + _child[p] = w;
1.228 + }
1.229 + // 36
1.230 + inline void insert_into_forest(size_type v, const T& d) {
1.231 + _p[v] = nil();
1.232 + size_type u = _left[_root];
1.233 + _left[v] = u;
1.234 + _right[v] = _root;
1.235 + _left[_root] = _right[u] = v;
1.236 + if (_compare(d, _key[_root]))
1.237 + _root = v;
1.238 + }
1.239 +
1.240 + void print_recur(size_type x, std::ostream& os) {
1.241 + if (x != nil()) {
1.242 + os << x;
1.243 + if (_child[x] != nil()) {
1.244 + os << "(";
1.245 + size_type i = _child[x];
1.246 + do {
1.247 + print_recur(i, os); os << " ";
1.248 + i = _right[i];
1.249 + } while (i != _child[x]);
1.250 + os << ")";
1.251 + }
1.252 + }
1.253 + }
1.254 +
1.255 + size_type nil() const { return _left.size(); }
1.256 +
1.257 + std::vector<T> _key;
1.258 + LinkVec _left, _right, _p;
1.259 + std::vector<bool> _mark;
1.260 + LinkVec _degree;
1.261 + size_type _n, _root;
1.262 + ID _id;
1.263 + Compare _compare;
1.264 + LinkVec _child;
1.265 + LinkVec new_roots;
1.266 +};
1.267 +
1.268 +} // namespace boost
1.269 +
1.270 +
1.271 +#endif // BOOST_FIBONACCI_HEAP_HPP