source: NonGTP/Boost/boost/pending/fibonacci_heap.hpp @ 857

Revision 857, 6.3 KB checked in by igarcia, 19 years ago (diff)
Line 
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
24namespace boost {
25
26
27template <class T,
28          class Compare = std::less<T>,
29          class ID = identity_property_map>
30class fibonacci_heap
31{
32  typedef typename boost::property_traits<ID>::value_type size_type;
33  typedef T value_type;
34protected:
35  typedef fibonacci_heap self;
36  typedef std::vector<size_type> LinkVec;
37  typedef typename LinkVec::iterator LinkIter;
38public:
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  }
144  // 41
145  inline void rebuild_root_list(LinkIter new_roots, int& h)
146  {
147    size_type u, v, w;
148    if (h < 0)
149      _root = nil();
150    else {
151      T d;
152      u = v = new_roots[h];
153      d = _key[u];
154      _root = u;
155      for (h--; h >= 0; --h)
156        if (new_roots[h] != nil()) {
157          w = new_roots[h];
158          _left[w] = v;
159          _right[v] = w;
160          if (_compare(_key[w], d)) {
161            _root = w;
162            d = _key[w];
163          }
164          v = w;
165        }
166      _right[v] = u;
167      _left[u] = v;
168    }
169  }
170
171  // 34
172  void update(const T& d) {
173    size_type v = get(_id, d);
174    assert(!_compare(_key[v], d));
175    _key[v] = d;
176    size_type p = _p[v];
177    if (p == nil()) {
178      if (_compare(d, _key[_root]))
179        _root = v;
180    } else if (_compare(d, _key[_root]))
181      while (1) {
182        size_type r = _degree[p];
183        if (r >= 2)
184          remove_from_family(v, p);
185        insert_into_forest(v, d);
186        size_type pp = _p[p];
187        if (pp == nil()) {
188          --_degree[p];
189          break;
190        }
191        if (_mark[p] == false) {
192          _mark[p] = true;
193          break;
194        } else
195          --_degree[p];
196        v = p;
197        p = pp;
198      }
199  }
200
201  inline size_type size() const { return _n; }
202  inline bool empty() const { return _n == 0; }
203
204  void print(std::ostream& os) {
205    if (_root != nil()) {
206      size_type i = _root;
207      do {
208        print_recur(i, os);
209        os << std::endl;
210        i = _right[i];
211      } while (i != _root);
212    }
213  }
214
215protected:
216  // 35
217  inline void remove_from_family(size_type v, size_type p) {
218    size_type u = _left[v];
219    size_type w = _right[v];
220    _right[u] = w;
221    _left[w] = u;
222    if (_child[p] == v)
223      _child[p] = w;
224  }
225  // 36
226  inline void insert_into_forest(size_type v, const T& d) {
227    _p[v] = nil();
228    size_type u = _left[_root];
229    _left[v] = u;
230    _right[v] = _root;
231    _left[_root] = _right[u] = v;
232    if (_compare(d, _key[_root]))
233      _root = v;
234  }
235
236  void print_recur(size_type x, std::ostream& os) {
237    if (x != nil()) {
238      os << x;
239      if (_child[x] != nil()) {
240        os << "(";
241        size_type i = _child[x];
242        do {
243          print_recur(i, os); os << " ";
244          i = _right[i];
245        } while (i != _child[x]);
246        os << ")";
247      }
248    }
249  }
250 
251  size_type nil() const { return _left.size(); }
252
253  std::vector<T> _key;
254  LinkVec _left, _right, _p;
255  std::vector<bool> _mark;
256  LinkVec _degree;
257  size_type _n, _root;
258  ID _id;
259  Compare _compare;
260  LinkVec _child;
261  LinkVec new_roots;
262};
263
264} // namespace boost
265
266
267#endif // BOOST_FIBONACCI_HEAP_HPP
Note: See TracBrowser for help on using the repository browser.