git.sesse.net Git - casparcg/blob - dependencies/boost/boost/pending/fibonacci_heap.hpp

   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 <boost/config/no_tr1/cmath.hpp>
  12 #endif
  13 #include <iosfwd>
  14 #include <vector>
  15 #include <functional>
  16 #include <boost/config.hpp>
  17 #include <boost/property_map/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         _mark[v] = false;
 124         std::swap(u, v);
 125       }
 126       make_child(u, v, r);
 127       ++r;
 128     }
 129     _degree[v] = r;
 130     _mark[v] = false;
 131   }
 132   // 40
 133   void make_child(size_type u, size_type v, size_type r) {
 134     if (r == 0) {
 135       _child[v] = u;
 136       _left[u] = u;
 137       _right[u] = u;
 138     } else {
 139       size_type t = _child[v];
 140       _right[u] = _right[t];
 141       _left[u] = t;
 142       _right[t] = u;
 143       _left[_right[u]] = u;
 144     }
 145     _p[u] = v;
 146   }
 147   // 41
 148   inline void rebuild_root_list(LinkIter new_roots, int& h)
 149   {
 150     size_type u, v, w;
 151     if (h < 0)
 152       _root = nil();
 153     else {
 154       T d;
 155       u = v = new_roots[h];
 156       d = _key[u];
 157       _root = u;
 158       for (h--; h >= 0; --h)
 159         if (new_roots[h] != nil()) {
 160           w = new_roots[h];
 161           _left[w] = v;
 162           _right[v] = w;
 163           if (_compare(_key[w], d)) {
 164             _root = w;
 165             d = _key[w];
 166           }
 167           v = w;
 168         }
 169       _right[v] = u;
 170       _left[u] = v;
 171     }
 172   }
 173
 174   // 34
 175   void update(const T& d) {
 176     size_type v = get(_id, d);
 177     assert(!_compare(_key[v], d));
 178     _key[v] = d;
 179     size_type p = _p[v];
 180     if (p == nil()) {
 181       if (_compare(d, _key[_root]))
 182         _root = v;
 183     } else if (_compare(d, _key[p]))
 184       while (1) {
 185         size_type r = _degree[p];
 186         if (r >= 2)
 187           remove_from_family(v, p);
 188         insert_into_forest(v, d);
 189         size_type pp = _p[p];
 190         if (pp == nil()) {
 191           --_degree[p];
 192           break;
 193         }
 194         if (_mark[p] == false) {
 195           _mark[p] = true;
 196           --_degree[p];
 197           break;
 198         } else
 199           --_degree[p];
 200         v = p;
 201         p = pp;
 202       }
 203   }
 204
 205   inline size_type size() const { return _n; }
 206   inline bool empty() const { return _n == 0; }
 207
 208   void print(std::ostream& os) {
 209     if (_root != nil()) {
 210       size_type i = _root;
 211       do {
 212         print_recur(i, os);
 213         os << std::endl;
 214         i = _right[i];
 215       } while (i != _root);
 216     }
 217   }
 218
 219 protected:
 220   // 35
 221   inline void remove_from_family(size_type v, size_type p) {
 222     size_type u = _left[v];
 223     size_type w = _right[v];
 224     _right[u] = w;
 225     _left[w] = u;
 226     if (_child[p] == v)
 227       _child[p] = w;
 228   }
 229   // 36
 230   inline void insert_into_forest(size_type v, const T& d) {
 231     _p[v] = nil();
 232     size_type u = _left[_root];
 233     _left[v] = u;
 234     _right[v] = _root;
 235     _left[_root] = _right[u] = v;
 236     if (_compare(d, _key[_root]))
 237       _root = v;
 238   }
 239
 240   void print_recur(size_type x, std::ostream& os) {
 241     if (x != nil()) {
 242       os << x;
 243       if (_degree[x] > 0) {
 244         os << "(";
 245         size_type i = _child[x];
 246         do {
 247           print_recur(i, os); os << " ";
 248           i = _right[i];
 249         } while (i != _child[x]);
 250         os << ")";
 251       }
 252     }
 253   }
 254
 255   size_type nil() const { return _left.size(); }
 256
 257   std::vector<T> _key;
 258   LinkVec _left, _right, _p;
 259   std::vector<bool> _mark;
 260   LinkVec _degree;
 261   size_type _n, _root;
 262   ID _id;
 263   Compare _compare;
 264   LinkVec _child;
 265   LinkVec new_roots;
 266 };
 267
 268 } // namespace boost
 269
 270
 271 #endif // BOOST_FIBONACCI_HEAP_HPP