Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/boost/pending/fibonacci_heap.hpp @ 47

Last change on this file since 47 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1

File size: 6.0 KB
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    _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
216protected:
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
Note: See TracBrowser for help on using the repository browser.