[29] | 1 | // (C) Copyright Jeremy Siek 2004. |
---|
| 2 | // Distributed under the Boost Software License, Version 1.0. (See |
---|
| 3 | // accompanying file LICENSE_1_0.txt or copy at |
---|
| 4 | // http://www.boost.org/LICENSE_1_0.txt) |
---|
| 5 | #ifndef BOOST_FIBONACCI_HEAP_HPP |
---|
| 6 | #define BOOST_FIBONACCI_HEAP_HPP |
---|
| 7 | |
---|
| 8 | #if defined(__sgi) && !defined(__GNUC__) |
---|
| 9 | # include <math.h> |
---|
| 10 | #else |
---|
| 11 | # include <cmath> |
---|
| 12 | #endif |
---|
| 13 | #include <iosfwd> |
---|
| 14 | #include <vector> |
---|
| 15 | #include <functional> |
---|
| 16 | #include <boost/config.hpp> |
---|
| 17 | #include <boost/property_map.hpp> |
---|
| 18 | |
---|
| 19 | // |
---|
| 20 | // An adaptation of Knuth's Fibonacci heap implementation |
---|
| 21 | // in "The Stanford Graph Base", pages 475-482. |
---|
| 22 | // |
---|
| 23 | |
---|
| 24 | namespace boost { |
---|
| 25 | |
---|
| 26 | |
---|
| 27 | template <class T, |
---|
| 28 | class Compare = std::less<T>, |
---|
| 29 | class ID = identity_property_map> |
---|
| 30 | class fibonacci_heap |
---|
| 31 | { |
---|
| 32 | typedef typename boost::property_traits<ID>::value_type size_type; |
---|
| 33 | typedef T value_type; |
---|
| 34 | protected: |
---|
| 35 | typedef fibonacci_heap self; |
---|
| 36 | typedef std::vector<size_type> LinkVec; |
---|
| 37 | typedef typename LinkVec::iterator LinkIter; |
---|
| 38 | public: |
---|
| 39 | |
---|
| 40 | fibonacci_heap(size_type n, |
---|
| 41 | const Compare& cmp, |
---|
| 42 | const ID& id = identity_property_map()) |
---|
| 43 | : _key(n), _left(n), _right(n), _p(n), _mark(n), _degree(n), |
---|
| 44 | _n(0), _root(n), _id(id), _compare(cmp), _child(n), |
---|
| 45 | #if defined(BOOST_MSVC) || defined(__ICL) // need a new macro? |
---|
| 46 | new_roots(size_type(log(float(n))) + 5) { } |
---|
| 47 | #else |
---|
| 48 | new_roots(size_type(std::log(float(n))) + 5) { } |
---|
| 49 | #endif |
---|
| 50 | |
---|
| 51 | // 33 |
---|
| 52 | void push(const T& d) { |
---|
| 53 | ++_n; |
---|
| 54 | size_type v = get(_id, d); |
---|
| 55 | _key[v] = d; |
---|
| 56 | _p[v] = nil(); |
---|
| 57 | _degree[v] = 0; |
---|
| 58 | _mark[v] = false; |
---|
| 59 | _child[v] = nil(); |
---|
| 60 | if (_root == nil()) { |
---|
| 61 | _root = _left[v] = _right[v] = v; |
---|
| 62 | //std::cout << "root added" << std::endl; |
---|
| 63 | } else { |
---|
| 64 | size_type u = _left[_root]; |
---|
| 65 | _left[v] = u; |
---|
| 66 | _right[v] = _root; |
---|
| 67 | _left[_root] = _right[u] = v; |
---|
| 68 | if (_compare(d, _key[_root])) |
---|
| 69 | _root = v; |
---|
| 70 | //std::cout << "non-root node added" << std::endl; |
---|
| 71 | } |
---|
| 72 | } |
---|
| 73 | T& top() { return _key[_root]; } |
---|
| 74 | const T& top() const { return _key[_root]; } |
---|
| 75 | |
---|
| 76 | // 38 |
---|
| 77 | void pop() { |
---|
| 78 | --_n; |
---|
| 79 | int h = -1; |
---|
| 80 | size_type v, w; |
---|
| 81 | if (_root != nil()) { |
---|
| 82 | if (_degree[_root] == 0) { |
---|
| 83 | v = _right[_root]; |
---|
| 84 | } else { |
---|
| 85 | w = _child[_root]; |
---|
| 86 | v = _right[w]; |
---|
| 87 | _right[w] = _right[_root]; |
---|
| 88 | for (w = v; w != _right[_root]; w = _right[w]) |
---|
| 89 | _p[w] = nil(); |
---|
| 90 | } |
---|
| 91 | while (v != _root) { |
---|
| 92 | w = _right[v]; |
---|
| 93 | add_tree_to_new_roots(v, new_roots.begin(), h); |
---|
| 94 | v = w; |
---|
| 95 | } |
---|
| 96 | rebuild_root_list(new_roots.begin(), h); |
---|
| 97 | } |
---|
| 98 | } |
---|
| 99 | // 39 |
---|
| 100 | inline void add_tree_to_new_roots(size_type v, |
---|
| 101 | LinkIter new_roots, |
---|
| 102 | int& h) |
---|
| 103 | { |
---|
| 104 | int r; |
---|
| 105 | size_type u; |
---|
| 106 | r = _degree[v]; |
---|
| 107 | while (1) { |
---|
| 108 | if (h < r) { |
---|
| 109 | do { |
---|
| 110 | ++h; |
---|
| 111 | new_roots[h] = (h == r ? v : nil()); |
---|
| 112 | } while (h < r); |
---|
| 113 | break; |
---|
| 114 | } |
---|
| 115 | if (new_roots[r] == nil()) { |
---|
| 116 | new_roots[r] = v; |
---|
| 117 | break; |
---|
| 118 | } |
---|
| 119 | u = new_roots[r]; |
---|
| 120 | new_roots[r] = nil(); |
---|
| 121 | if (_compare(_key[u], _key[v])) { |
---|
| 122 | _degree[v] = r; |
---|
| 123 | std::swap(u, v); |
---|
| 124 | } |
---|
| 125 | make_child(u, v, r); |
---|
| 126 | ++r; |
---|
| 127 | } |
---|
| 128 | _degree[v] = r; |
---|
| 129 | } |
---|
| 130 | // 40 |
---|
| 131 | void make_child(size_type u, size_type v, size_type r) { |
---|
| 132 | if (r == 0) { |
---|
| 133 | _child[v] = u; |
---|
| 134 | _left[u] = u; |
---|
| 135 | _right[u] = u; |
---|
| 136 | } else { |
---|
| 137 | size_type t = _child[v]; |
---|
| 138 | _right[u] = _right[t]; |
---|
| 139 | _left[u] = t; |
---|
| 140 | _right[t] = u; |
---|
| 141 | _left[_right[u]] = u; |
---|
| 142 | } |
---|
| 143 | _p[u] = v; |
---|
| 144 | } |
---|
| 145 | // 41 |
---|
| 146 | inline void rebuild_root_list(LinkIter new_roots, int& h) |
---|
| 147 | { |
---|
| 148 | size_type u, v, w; |
---|
| 149 | if (h < 0) |
---|
| 150 | _root = nil(); |
---|
| 151 | else { |
---|
| 152 | T d; |
---|
| 153 | u = v = new_roots[h]; |
---|
| 154 | d = _key[u]; |
---|
| 155 | _root = u; |
---|
| 156 | for (h--; h >= 0; --h) |
---|
| 157 | if (new_roots[h] != nil()) { |
---|
| 158 | w = new_roots[h]; |
---|
| 159 | _left[w] = v; |
---|
| 160 | _right[v] = w; |
---|
| 161 | if (_compare(_key[w], d)) { |
---|
| 162 | _root = w; |
---|
| 163 | d = _key[w]; |
---|
| 164 | } |
---|
| 165 | v = w; |
---|
| 166 | } |
---|
| 167 | _right[v] = u; |
---|
| 168 | _left[u] = v; |
---|
| 169 | } |
---|
| 170 | } |
---|
| 171 | |
---|
| 172 | // 34 |
---|
| 173 | void update(const T& d) { |
---|
| 174 | size_type v = get(_id, d); |
---|
| 175 | assert(!_compare(_key[v], d)); |
---|
| 176 | _key[v] = d; |
---|
| 177 | size_type p = _p[v]; |
---|
| 178 | if (p == nil()) { |
---|
| 179 | if (_compare(d, _key[_root])) |
---|
| 180 | _root = v; |
---|
| 181 | } else if (_compare(d, _key[_root])) |
---|
| 182 | while (1) { |
---|
| 183 | size_type r = _degree[p]; |
---|
| 184 | if (r >= 2) |
---|
| 185 | remove_from_family(v, p); |
---|
| 186 | insert_into_forest(v, d); |
---|
| 187 | size_type pp = _p[p]; |
---|
| 188 | if (pp == nil()) { |
---|
| 189 | --_degree[p]; |
---|
| 190 | break; |
---|
| 191 | } |
---|
| 192 | if (_mark[p] == false) { |
---|
| 193 | _mark[p] = true; |
---|
| 194 | break; |
---|
| 195 | } else |
---|
| 196 | --_degree[p]; |
---|
| 197 | v = p; |
---|
| 198 | p = pp; |
---|
| 199 | } |
---|
| 200 | } |
---|
| 201 | |
---|
| 202 | inline size_type size() const { return _n; } |
---|
| 203 | inline bool empty() const { return _n == 0; } |
---|
| 204 | |
---|
| 205 | void print(std::ostream& os) { |
---|
| 206 | if (_root != nil()) { |
---|
| 207 | size_type i = _root; |
---|
| 208 | do { |
---|
| 209 | print_recur(i, os); |
---|
| 210 | os << std::endl; |
---|
| 211 | i = _right[i]; |
---|
| 212 | } while (i != _root); |
---|
| 213 | } |
---|
| 214 | } |
---|
| 215 | |
---|
| 216 | protected: |
---|
| 217 | // 35 |
---|
| 218 | inline void remove_from_family(size_type v, size_type p) { |
---|
| 219 | size_type u = _left[v]; |
---|
| 220 | size_type w = _right[v]; |
---|
| 221 | _right[u] = w; |
---|
| 222 | _left[w] = u; |
---|
| 223 | if (_child[p] == v) |
---|
| 224 | _child[p] = w; |
---|
| 225 | } |
---|
| 226 | // 36 |
---|
| 227 | inline void insert_into_forest(size_type v, const T& d) { |
---|
| 228 | _p[v] = nil(); |
---|
| 229 | size_type u = _left[_root]; |
---|
| 230 | _left[v] = u; |
---|
| 231 | _right[v] = _root; |
---|
| 232 | _left[_root] = _right[u] = v; |
---|
| 233 | if (_compare(d, _key[_root])) |
---|
| 234 | _root = v; |
---|
| 235 | } |
---|
| 236 | |
---|
| 237 | void print_recur(size_type x, std::ostream& os) { |
---|
| 238 | if (x != nil()) { |
---|
| 239 | os << x; |
---|
| 240 | if (_child[x] != nil()) { |
---|
| 241 | os << "("; |
---|
| 242 | size_type i = _child[x]; |
---|
| 243 | do { |
---|
| 244 | print_recur(i, os); os << " "; |
---|
| 245 | i = _right[i]; |
---|
| 246 | } while (i != _child[x]); |
---|
| 247 | os << ")"; |
---|
| 248 | } |
---|
| 249 | } |
---|
| 250 | } |
---|
| 251 | |
---|
| 252 | size_type nil() const { return _left.size(); } |
---|
| 253 | |
---|
| 254 | std::vector<T> _key; |
---|
| 255 | LinkVec _left, _right, _p; |
---|
| 256 | std::vector<bool> _mark; |
---|
| 257 | LinkVec _degree; |
---|
| 258 | size_type _n, _root; |
---|
| 259 | ID _id; |
---|
| 260 | Compare _compare; |
---|
| 261 | LinkVec _child; |
---|
| 262 | LinkVec new_roots; |
---|
| 263 | }; |
---|
| 264 | |
---|
| 265 | } // namespace boost |
---|
| 266 | |
---|
| 267 | |
---|
| 268 | #endif // BOOST_FIBONACCI_HEAP_HPP |
---|