boost/pending/fibonacci_heap.hpp

0001 // (C) Copyright Jeremy Siek    2004.
0002 // Distributed under the Boost Software License, Version 1.0. (See
0003 // accompanying file LICENSE_1_0.txt or copy at
0004 // http://www.boost.org/LICENSE_1_0.txt)
0005 #ifndef BOOST_FIBONACCI_HEAP_HPP
0006 #define BOOST_FIBONACCI_HEAP_HPP
0007
0008 #if defined(__sgi) && !defined(__GNUC__)
0009 #include <math.h>
0010 #else
0011 #include <boost/config/no_tr1/cmath.hpp>
0012 #endif
0013 #include <iosfwd>
0014 #include <vector>
0015 #include <functional>
0016 #include <boost/config.hpp>
0017 #include <boost/property_map/property_map.hpp>
0018
0019 //
0020 // An adaptation of Knuth's Fibonacci heap implementation
0021 // in "The Stanford Graph Base", pages 475-482.
0022 //
0023
0024 namespace boost
0025 {
0026
0027 template < class T, class Compare = std::less< T >,
0028     class ID = identity_property_map >
0029 class fibonacci_heap
0030 {
0031     typedef typename boost::property_traits< ID >::value_type size_type;
0032     typedef T value_type;
0033
0034 protected:
0035     typedef fibonacci_heap self;
0036     typedef std::vector< size_type > LinkVec;
0037     typedef typename LinkVec::iterator LinkIter;
0038
0039 public:
0040     fibonacci_heap(
0041         size_type n, const Compare& cmp, const ID& id = identity_property_map())
0042     : _key(n)
0043     , _left(n)
0044     , _right(n)
0045     , _p(n)
0046     , _mark(n)
0047     , _degree(n)
0048     , _n(0)
0049     , _root(n)
0050     , _id(id)
0051     , _compare(cmp)
0052     , _child(n)
0053     ,
0054 #if defined(BOOST_MSVC) || defined(__ICL) // need a new macro?
0055         new_roots(size_type(log(float(n))) + 5)
0056     {
0057     }
0058 #else
0059         new_roots(size_type(std::log(float(n))) + 5)
0060     {
0061     }
0062 #endif
0063
0064     // 33
0065     void push(const T& d)
0066     {
0067         ++_n;
0068         size_type v = get(_id, d);
0069         _key[v] = d;
0070         _p[v] = nil();
0071         _degree[v] = 0;
0072         _mark[v] = false;
0073         _child[v] = nil();
0074         if (_root == nil())
0075         {
0076             _root = _left[v] = _right[v] = v;
0077             // std::cout << "root added" << std::endl;
0078         }
0079         else
0080         {
0081             size_type u = _left[_root];
0082             _left[v] = u;
0083             _right[v] = _root;
0084             _left[_root] = _right[u] = v;
0085             if (_compare(d, _key[_root]))
0086                 _root = v;
0087             // std::cout << "non-root node added" << std::endl;
0088         }
0089     }
0090     T& top() { return _key[_root]; }
0091     const T& top() const { return _key[_root]; }
0092
0093     // 38
0094     void pop()
0095     {
0096         --_n;
0097         int h = -1;
0098         size_type v, w;
0099         if (_root != nil())
0100         {
0101             if (_degree[_root] == 0)
0102             {
0103                 v = _right[_root];
0104             }
0105             else
0106             {
0107                 w = _child[_root];
0108                 v = _right[w];
0109                 _right[w] = _right[_root];
0110                 for (w = v; w != _right[_root]; w = _right[w])
0111                     _p[w] = nil();
0112             }
0113             while (v != _root)
0114             {
0115                 w = _right[v];
0116                 add_tree_to_new_roots(v, new_roots.begin(), h);
0117                 v = w;
0118             }
0119             rebuild_root_list(new_roots.begin(), h);
0120         }
0121     }
0122     // 39
0123     inline void add_tree_to_new_roots(size_type v, LinkIter new_roots, int& h)
0124     {
0125         int r;
0126         size_type u;
0127         r = _degree[v];
0128         while (1)
0129         {
0130             if (h < r)
0131             {
0132                 do
0133                 {
0134                     ++h;
0135                     new_roots[h] = (h == r ? v : nil());
0136                 } while (h < r);
0137                 break;
0138             }
0139             if (new_roots[r] == nil())
0140             {
0141                 new_roots[r] = v;
0142                 break;
0143             }
0144             u = new_roots[r];
0145             new_roots[r] = nil();
0146             if (_compare(_key[u], _key[v]))
0147             {
0148                 _degree[v] = r;
0149                 _mark[v] = false;
0150                 std::swap(u, v);
0151             }
0152             make_child(u, v, r);
0153             ++r;
0154         }
0155         _degree[v] = r;
0156         _mark[v] = false;
0157     }
0158     // 40
0159     void make_child(size_type u, size_type v, size_type r)
0160     {
0161         if (r == 0)
0162         {
0163             _child[v] = u;
0164             _left[u] = u;
0165             _right[u] = u;
0166         }
0167         else
0168         {
0169             size_type t = _child[v];
0170             _right[u] = _right[t];
0171             _left[u] = t;
0172             _right[t] = u;
0173             _left[_right[u]] = u;
0174         }
0175         _p[u] = v;
0176     }
0177     // 41
0178     inline void rebuild_root_list(LinkIter new_roots, int& h)
0179     {
0180         size_type u, v, w;
0181         if (h < 0)
0182             _root = nil();
0183         else
0184         {
0185             T d;
0186             u = v = new_roots[h];
0187             d = _key[u];
0188             _root = u;
0189             for (h--; h >= 0; --h)
0190                 if (new_roots[h] != nil())
0191                 {
0192                     w = new_roots[h];
0193                     _left[w] = v;
0194                     _right[v] = w;
0195                     if (_compare(_key[w], d))
0196                     {
0197                         _root = w;
0198                         d = _key[w];
0199                     }
0200                     v = w;
0201                 }
0202             _right[v] = u;
0203             _left[u] = v;
0204         }
0205     }
0206
0207     // 34
0208     void update(const T& d)
0209     {
0210         size_type v = get(_id, d);
0211         assert(!_compare(_key[v], d));
0212         _key[v] = d;
0213         size_type p = _p[v];
0214         if (p == nil())
0215         {
0216             if (_compare(d, _key[_root]))
0217                 _root = v;
0218         }
0219         else if (_compare(d, _key[p]))
0220             while (1)
0221             {
0222                 size_type r = _degree[p];
0223                 if (r >= 2)
0224                     remove_from_family(v, p);
0225                 insert_into_forest(v, d);
0226                 size_type pp = _p[p];
0227                 if (pp == nil())
0228                 {
0229                     --_degree[p];
0230                     break;
0231                 }
0232                 if (_mark[p] == false)
0233                 {
0234                     _mark[p] = true;
0235                     --_degree[p];
0236                     break;
0237                 }
0238                 else
0239                     --_degree[p];
0240                 v = p;
0241                 p = pp;
0242             }
0243     }
0244
0245     inline size_type size() const { return _n; }
0246     inline bool empty() const { return _n == 0; }
0247
0248     void print(std::ostream& os)
0249     {
0250         if (_root != nil())
0251         {
0252             size_type i = _root;
0253             do
0254             {
0255                 print_recur(i, os);
0256                 os << std::endl;
0257                 i = _right[i];
0258             } while (i != _root);
0259         }
0260     }
0261
0262 protected:
0263     // 35
0264     inline void remove_from_family(size_type v, size_type p)
0265     {
0266         size_type u = _left[v];
0267         size_type w = _right[v];
0268         _right[u] = w;
0269         _left[w] = u;
0270         if (_child[p] == v)
0271             _child[p] = w;
0272     }
0273     // 36
0274     inline void insert_into_forest(size_type v, const T& d)
0275     {
0276         _p[v] = nil();
0277         size_type u = _left[_root];
0278         _left[v] = u;
0279         _right[v] = _root;
0280         _left[_root] = _right[u] = v;
0281         if (_compare(d, _key[_root]))
0282             _root = v;
0283     }
0284
0285     void print_recur(size_type x, std::ostream& os)
0286     {
0287         if (x != nil())
0288         {
0289             os << x;
0290             if (_degree[x] > 0)
0291             {
0292                 os << "(";
0293                 size_type i = _child[x];
0294                 do
0295                 {
0296                     print_recur(i, os);
0297                     os << " ";
0298                     i = _right[i];
0299                 } while (i != _child[x]);
0300                 os << ")";
0301             }
0302         }
0303     }
0304
0305     size_type nil() const { return _left.size(); }
0306
0307     std::vector< T > _key;
0308     LinkVec _left, _right, _p;
0309     std::vector< bool > _mark;
0310     LinkVec _degree;
0311     size_type _n, _root;
0312     ID _id;
0313     Compare _compare;
0314     LinkVec _child;
0315     LinkVec new_roots;
0316 };
0317
0318 } // namespace boost
0319
0320 #endif // BOOST_FIBONACCI_HEAP_HPP