• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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, class Compare = std::less< T >,
28     class ID = identity_property_map >
29 class fibonacci_heap
30 {
31     typedef typename boost::property_traits< ID >::value_type size_type;
32     typedef T value_type;
33 
34 protected:
35     typedef fibonacci_heap self;
36     typedef std::vector< size_type > LinkVec;
37     typedef typename LinkVec::iterator LinkIter;
38 
39 public:
fibonacci_heap(size_type n,const Compare & cmp,const ID & id=identity_property_map ())40     fibonacci_heap(
41         size_type n, const Compare& cmp, const ID& id = identity_property_map())
42     : _key(n)
43     , _left(n)
44     , _right(n)
45     , _p(n)
46     , _mark(n)
47     , _degree(n)
48     , _n(0)
49     , _root(n)
50     , _id(id)
51     , _compare(cmp)
52     , _child(n)
53     ,
54 #if defined(BOOST_MSVC) || defined(__ICL) // need a new macro?
55         new_roots(size_type(log(float(n))) + 5)
56     {
57     }
58 #else
59         new_roots(size_type(std::log(float(n))) + 5)
60     {
61     }
62 #endif
63 
64     // 33
push(const T & d)65     void push(const T& d)
66     {
67         ++_n;
68         size_type v = get(_id, d);
69         _key[v] = d;
70         _p[v] = nil();
71         _degree[v] = 0;
72         _mark[v] = false;
73         _child[v] = nil();
74         if (_root == nil())
75         {
76             _root = _left[v] = _right[v] = v;
77             // std::cout << "root added" << std::endl;
78         }
79         else
80         {
81             size_type u = _left[_root];
82             _left[v] = u;
83             _right[v] = _root;
84             _left[_root] = _right[u] = v;
85             if (_compare(d, _key[_root]))
86                 _root = v;
87             // std::cout << "non-root node added" << std::endl;
88         }
89     }
top()90     T& top() { return _key[_root]; }
top() const91     const T& top() const { return _key[_root]; }
92 
93     // 38
pop()94     void pop()
95     {
96         --_n;
97         int h = -1;
98         size_type v, w;
99         if (_root != nil())
100         {
101             if (_degree[_root] == 0)
102             {
103                 v = _right[_root];
104             }
105             else
106             {
107                 w = _child[_root];
108                 v = _right[w];
109                 _right[w] = _right[_root];
110                 for (w = v; w != _right[_root]; w = _right[w])
111                     _p[w] = nil();
112             }
113             while (v != _root)
114             {
115                 w = _right[v];
116                 add_tree_to_new_roots(v, new_roots.begin(), h);
117                 v = w;
118             }
119             rebuild_root_list(new_roots.begin(), h);
120         }
121     }
122     // 39
add_tree_to_new_roots(size_type v,LinkIter new_roots,int & h)123     inline void add_tree_to_new_roots(size_type v, LinkIter new_roots, int& h)
124     {
125         int r;
126         size_type u;
127         r = _degree[v];
128         while (1)
129         {
130             if (h < r)
131             {
132                 do
133                 {
134                     ++h;
135                     new_roots[h] = (h == r ? v : nil());
136                 } while (h < r);
137                 break;
138             }
139             if (new_roots[r] == nil())
140             {
141                 new_roots[r] = v;
142                 break;
143             }
144             u = new_roots[r];
145             new_roots[r] = nil();
146             if (_compare(_key[u], _key[v]))
147             {
148                 _degree[v] = r;
149                 _mark[v] = false;
150                 std::swap(u, v);
151             }
152             make_child(u, v, r);
153             ++r;
154         }
155         _degree[v] = r;
156         _mark[v] = false;
157     }
158     // 40
make_child(size_type u,size_type v,size_type r)159     void make_child(size_type u, size_type v, size_type r)
160     {
161         if (r == 0)
162         {
163             _child[v] = u;
164             _left[u] = u;
165             _right[u] = u;
166         }
167         else
168         {
169             size_type t = _child[v];
170             _right[u] = _right[t];
171             _left[u] = t;
172             _right[t] = u;
173             _left[_right[u]] = u;
174         }
175         _p[u] = v;
176     }
177     // 41
rebuild_root_list(LinkIter new_roots,int & h)178     inline void rebuild_root_list(LinkIter new_roots, int& h)
179     {
180         size_type u, v, w;
181         if (h < 0)
182             _root = nil();
183         else
184         {
185             T d;
186             u = v = new_roots[h];
187             d = _key[u];
188             _root = u;
189             for (h--; h >= 0; --h)
190                 if (new_roots[h] != nil())
191                 {
192                     w = new_roots[h];
193                     _left[w] = v;
194                     _right[v] = w;
195                     if (_compare(_key[w], d))
196                     {
197                         _root = w;
198                         d = _key[w];
199                     }
200                     v = w;
201                 }
202             _right[v] = u;
203             _left[u] = v;
204         }
205     }
206 
207     // 34
update(const T & d)208     void update(const T& d)
209     {
210         size_type v = get(_id, d);
211         assert(!_compare(_key[v], d));
212         _key[v] = d;
213         size_type p = _p[v];
214         if (p == nil())
215         {
216             if (_compare(d, _key[_root]))
217                 _root = v;
218         }
219         else if (_compare(d, _key[p]))
220             while (1)
221             {
222                 size_type r = _degree[p];
223                 if (r >= 2)
224                     remove_from_family(v, p);
225                 insert_into_forest(v, d);
226                 size_type pp = _p[p];
227                 if (pp == nil())
228                 {
229                     --_degree[p];
230                     break;
231                 }
232                 if (_mark[p] == false)
233                 {
234                     _mark[p] = true;
235                     --_degree[p];
236                     break;
237                 }
238                 else
239                     --_degree[p];
240                 v = p;
241                 p = pp;
242             }
243     }
244 
size() const245     inline size_type size() const { return _n; }
empty() const246     inline bool empty() const { return _n == 0; }
247 
print(std::ostream & os)248     void print(std::ostream& os)
249     {
250         if (_root != nil())
251         {
252             size_type i = _root;
253             do
254             {
255                 print_recur(i, os);
256                 os << std::endl;
257                 i = _right[i];
258             } while (i != _root);
259         }
260     }
261 
262 protected:
263     // 35
remove_from_family(size_type v,size_type p)264     inline void remove_from_family(size_type v, size_type p)
265     {
266         size_type u = _left[v];
267         size_type w = _right[v];
268         _right[u] = w;
269         _left[w] = u;
270         if (_child[p] == v)
271             _child[p] = w;
272     }
273     // 36
insert_into_forest(size_type v,const T & d)274     inline void insert_into_forest(size_type v, const T& d)
275     {
276         _p[v] = nil();
277         size_type u = _left[_root];
278         _left[v] = u;
279         _right[v] = _root;
280         _left[_root] = _right[u] = v;
281         if (_compare(d, _key[_root]))
282             _root = v;
283     }
284 
print_recur(size_type x,std::ostream & os)285     void print_recur(size_type x, std::ostream& os)
286     {
287         if (x != nil())
288         {
289             os << x;
290             if (_degree[x] > 0)
291             {
292                 os << "(";
293                 size_type i = _child[x];
294                 do
295                 {
296                     print_recur(i, os);
297                     os << " ";
298                     i = _right[i];
299                 } while (i != _child[x]);
300                 os << ")";
301             }
302         }
303     }
304 
nil() const305     size_type nil() const { return _left.size(); }
306 
307     std::vector< T > _key;
308     LinkVec _left, _right, _p;
309     std::vector< bool > _mark;
310     LinkVec _degree;
311     size_type _n, _root;
312     ID _id;
313     Compare _compare;
314     LinkVec _child;
315     LinkVec new_roots;
316 };
317 
318 } // namespace boost
319 
320 #endif // BOOST_FIBONACCI_HEAP_HPP
321