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

Revision 857, 17.2 KB checked in by igarcia, 19 years ago (diff)
Line 
1// Copyright 2004 The Trustees of Indiana University.
2
3// Use, modification and distribution is subject to the Boost Software
4// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7//  Authors: Douglas Gregor
8//           Andrew Lumsdaine
9#ifndef BOOST_RELAXED_HEAP_HEADER
10#define BOOST_RELAXED_HEAP_HEADER
11
12#include <functional>
13#include <boost/property_map.hpp>
14#include <boost/optional.hpp>
15#include <vector>
16
17#ifdef BOOST_RELAXED_HEAP_DEBUG
18#  include <iostream>
19#endif // BOOST_RELAXED_HEAP_DEBUG
20
21#if defined(BOOST_MSVC)
22#  pragma warning(push)
23#  pragma warning(disable:4355) // complaint about using 'this' to
24#endif                          // initialize a member
25
26namespace boost {
27
28template<typename IndexedType,
29         typename Compare = std::less<IndexedType>,
30         typename ID = identity_property_map>
31class relaxed_heap
32{
33  struct group;
34
35  typedef relaxed_heap self_type;
36  typedef std::size_t  rank_type;
37
38public:
39  typedef IndexedType  value_type;
40  typedef rank_type    size_type;
41
42private:
43  /**
44   * The kind of key that a group has. The actual values are discussed
45   * in-depth in the documentation of the @c kind field of the @c group
46   * structure. Note that the order of the enumerators *IS* important
47   * and must not be changed.
48   */
49  enum group_key_kind { smallest_key, stored_key, largest_key };
50
51  struct group {
52    explicit group(group_key_kind kind = largest_key)
53      : kind(kind), parent(this), rank(0) { }
54
55    /** The value associated with this group. This value is only valid
56     *  when @c kind!=largest_key (which indicates a deleted
57     *  element). Note that the use of boost::optional increases the
58     *  memory requirements slightly but does not result in extraneous
59     *  memory allocations or deallocations. The optional could be
60     *  eliminated when @c value_type is a model of
61     *  DefaultConstructible.
62     */
63    ::boost::optional<value_type> value;
64
65    /**
66     * The kind of key stored at this group. This may be @c
67     * smallest_key, which indicates that the key is infinitely small;
68     * @c largest_key, which indicates that the key is infinitely
69     * large; or @c stored_key, which means that the key is unknown,
70     * but its relationship to other keys can be determined via the
71     * comparison function object.
72     */
73    group_key_kind        kind;
74
75    /// The parent of this group. Will only be NULL for the dummy root group
76    group*                parent;
77
78    /// The rank of this group. Equivalent to the number of children in
79    /// the group.
80    rank_type            rank;
81
82    /** The children of this group. For the dummy root group, these are
83     * the roots. This is an array of length log n containing pointers
84     * to the child groups.
85     */
86    group**               children;
87  };
88
89  size_type log2(size_type n)
90  {
91    size_type leading_zeroes = 0;
92    do {
93      size_type next = n << 1;
94      if (n == (next >> 1)) {
95        ++leading_zeroes;
96        n = next;
97      } else {
98        break;
99      }
100    } while (true);
101    return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1;
102  }
103
104public:
105  relaxed_heap(size_type n, const Compare& compare = Compare(),
106               const ID& id = ID())
107    : compare(compare), id(id), root(smallest_key), groups(n),
108      smallest_value(0)
109  {
110    if (n == 0) {
111      root.children = new group*[1];
112      return;
113    }
114
115    log_n = log2(n);
116
117    if (log_n == 0) log_n = 1;
118    size_type g = n / log_n;
119    if (n % log_n > 0) ++g;
120    size_type log_g = log2(g);
121    size_type r = log_g;
122
123    // Reserve an appropriate amount of space for data structures, so
124    // that we do not need to expand them.
125    index_to_group.resize(g);
126    A.resize(r + 1, 0);
127    root.rank = r + 1;
128    root.children = new group*[(log_g + 1) * (g + 1)];
129    for (rank_type i = 0; i < r+1; ++i) root.children[i] = 0;
130
131    // Build initial heap
132    size_type idx = 0;
133    while (idx < g) {
134      root.children[r] = &index_to_group[idx];
135      idx = build_tree(root, idx, r, log_g + 1);
136      if (idx != g)
137        r = static_cast<size_type>(log2(g-idx));
138    }
139  }
140
141  ~relaxed_heap() { delete [] root.children; }
142
143  void push(const value_type& x)
144  {
145    groups[get(id, x)] = x;
146    update(x);
147  }
148
149  void update(const value_type& x)
150  {
151    group* a = &index_to_group[get(id, x) / log_n];
152    if (!a->value
153        || *a->value == x
154        || compare(x, *a->value)) {
155      if (a != smallest_value) smallest_value = 0;
156      a->kind = stored_key;
157      a->value = x;
158      promote(a);
159    }
160  }
161
162  void remove(const value_type& x)
163  {
164    group* a = &index_to_group[get(id, x) / log_n];
165    assert(groups[get(id, x)] != 0);
166    a->value = x;
167    a->kind = smallest_key;
168    promote(a);
169    smallest_value = a;
170    pop();
171  }
172
173  value_type& top()
174  {
175    find_smallest();
176    assert(smallest_value->value != 0);
177    return *smallest_value->value;
178  }
179
180  const value_type& top() const
181  {
182    find_smallest();
183    assert(smallest_value->value != 0);
184    return *smallest_value->value;
185  }
186
187  bool empty() const
188  {
189    find_smallest();
190    return !smallest_value || (smallest_value->kind == largest_key);
191  }
192
193  bool contains(const value_type& x) const { return groups[get(id, x)]; }
194
195  void pop()
196  {
197    // Fill in smallest_value. This is the group x.
198    find_smallest();
199    group* x = smallest_value;
200    smallest_value = 0;
201
202    // Make x a leaf, giving it the smallest value within its group
203    rank_type r = x->rank;
204    group* p = x->parent;
205    {
206      assert(x->value != 0);
207
208      // Find x's group
209      size_type start = get(id, *x->value) - get(id, *x->value) % log_n;
210      size_type end = start + log_n;
211      if (end > groups.size()) end = groups.size();
212
213      // Remove the smallest value from the group, and find the new
214      // smallest value.
215      groups[get(id, *x->value)].reset();
216      x->value.reset();
217      x->kind = largest_key;
218      for (size_type i = start; i < end; ++i) {
219        if (groups[i] && (!x->value || compare(*groups[i], *x->value))) {
220          x->kind = stored_key;
221          x->value = groups[i];
222        }
223      }
224    }
225    x->rank = 0;
226
227    // Combine prior children of x with x
228    group* y = x;
229    for (size_type c = 0; c < r; ++c) {
230      group* child = x->children[c];
231      if (A[c] == child) A[c] = 0;
232      y = combine(y, child);
233    }
234
235    // If we got back something other than x, let y take x's place
236    if (y != x) {
237      y->parent = p;
238      p->children[r] = y;
239
240      assert(r == y->rank);
241      if (A[y->rank] == x)
242        A[y->rank] = do_compare(y, p)? y : 0;
243    }
244  }
245
246#ifdef BOOST_RELAXED_HEAP_DEBUG
247  /*************************************************************************
248   * Debugging support                                                     *
249   *************************************************************************/
250  void dump_tree() { dump_tree(std::cout); }
251  void dump_tree(std::ostream& out) { dump_tree(out, &root); }
252
253  void dump_tree(std::ostream& out, group* p, bool in_progress = false)
254  {
255    if (!in_progress) {
256      out << "digraph heap {\n"
257          << "  edge[dir=\"back\"];\n";
258    }
259
260    size_type p_index = 0;
261    if (p != &root) while (&index_to_group[p_index] != p) ++p_index;
262
263    for (size_type i = 0; i < p->rank; ++i) {
264      group* c = p->children[i];
265      if (c) {
266        size_type c_index = 0;
267        if (c != &root) while (&index_to_group[c_index] != c) ++c_index;
268
269        out << "  ";
270        if (p == &root) out << 'p'; else out << p_index;
271        out << " -> ";
272        if (c == &root) out << 'p'; else out << c_index;
273        if (A[c->rank] == c) out << " [style=\"dotted\"]";
274        out << ";\n";
275        dump_tree(out, c, true);
276
277        // Emit node information
278        out << "  ";
279        if (c == &root) out << 'p'; else out << c_index;
280        out << " [label=\"";
281        if (c == &root) out << 'p'; else out << c_index;
282        out << ":";
283        size_type start = c_index * log_n;
284        size_type end = start + log_n;
285        if (end > groups.size()) end = groups.size();
286        while (start != end) {
287          if (groups[start]) {
288            out << " " << get(id, *groups[start]);
289            if (*groups[start] == *c->value) out << "(*)";
290          }
291          ++start;
292        }
293        out << '"';
294
295        if (do_compare(c, p)) {
296          out << "  ";
297          if (c == &root) out << 'p'; else out << c_index;
298          out << ", style=\"filled\", fillcolor=\"gray\"";
299        }
300        out << "];\n";
301      } else {
302        assert(p->parent == p);
303      }
304    }
305    if (!in_progress) out << "}\n";
306  }
307
308  bool valid()
309  {
310    // Check that the ranks in the A array match the ranks of the
311    // groups stored there. Also, the active groups must be the last
312    // child of their parent.
313    for (size_type r = 0; r < A.size(); ++r) {
314      if (A[r] && A[r]->rank != r) return false;
315
316      if (A[r] && A[r]->parent->children[A[r]->parent->rank-1] != A[r])
317        return false;
318    }
319
320    // The root must have no value and a key of -Infinity
321    if (root.kind != smallest_key) return false;
322
323    return valid(&root);
324  }
325
326  bool valid(group* p)
327  {
328    for (size_type i = 0; i < p->rank; ++i) {
329      group* c = p->children[i];
330      if (c) {
331        // Check link structure
332        if (c->parent != p) return false;
333        if (c->rank != i) return false;
334
335        // A bad group must be active
336        if (do_compare(c, p) && A[i] != c) return false;
337
338        // Check recursively
339        if (!valid(c)) return false;
340      } else {
341        // Only the root may
342        if (p != &root) return false;
343      }
344    }
345    return true;
346  }
347
348#endif // BOOST_RELAXED_HEAP_DEBUG
349
350private:
351  size_type
352  build_tree(group& parent, size_type idx, size_type r, size_type max_rank)
353  {
354    group& this_group = index_to_group[idx];
355    this_group.parent = &parent;
356    ++idx;
357
358    this_group.children = root.children + (idx * max_rank);
359    this_group.rank = r;
360    for (size_type i = 0; i < r; ++i) {
361      this_group.children[i] = &index_to_group[idx];
362      idx = build_tree(this_group, idx, i, max_rank);
363    }
364    return idx;
365  }
366
367  void find_smallest() const
368  {
369    group** roots = root.children;
370
371    if (!smallest_value) {
372      std::size_t i;
373      for (i = 0; i < root.rank; ++i) {
374        if (roots[i] &&
375            (!smallest_value || do_compare(roots[i], smallest_value))) {
376          smallest_value = roots[i];
377        }
378      }
379      for (i = 0; i < A.size(); ++i) {
380        if (A[i] && (!smallest_value || do_compare(A[i], smallest_value)))
381          smallest_value = A[i];
382      }
383    }
384  }
385
386  bool do_compare(group* x, group* y) const
387  {
388    return (x->kind < y->kind
389            || (x->kind == y->kind
390                && x->kind == stored_key
391                && compare(*x->value, *y->value)));
392  }
393
394  void promote(group* a)
395  {
396    assert(a != 0);
397    rank_type r = a->rank;
398    group* p = a->parent;
399    assert(p != 0);
400    if (do_compare(a, p)) {
401      // s is the rank + 1 sibling
402      group* s = p->rank > r + 1? p->children[r + 1] : 0;
403
404      // If a is the last child of p
405      if (r == p->rank - 1) {
406        if (!A[r]) A[r] = a;
407        else if (A[r] != a) pair_transform(a);
408      } else {
409        assert(s != 0);
410        if (A[r + 1] == s) active_sibling_transform(a, s);
411        else good_sibling_transform(a, s);
412      }
413    }
414  }
415
416  group* combine(group* a1, group* a2)
417  {
418    assert(a1->rank == a2->rank);
419    if (do_compare(a2, a1)) do_swap(a1, a2);
420    a1->children[a1->rank++] = a2;
421    a2->parent = a1;
422    clean(a1);
423    return a1;
424  }
425
426  void clean(group* q)
427  {
428    if (2 > q->rank) return;
429    group* qp = q->children[q->rank-1];
430    rank_type s = q->rank - 2;
431    group* x = q->children[s];
432    group* xp = qp->children[s];
433    assert(s == x->rank);
434
435    // If x is active, swap x and xp
436    if (A[s] == x) {
437      q->children[s] = xp;
438      xp->parent = q;
439      qp->children[s] = x;
440      x->parent = qp;
441    }
442  }
443
444  void pair_transform(group* a)
445  {
446#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
447    std::cerr << "- pair transform\n";
448#endif
449    rank_type r = a->rank;
450
451    // p is a's parent
452    group* p = a->parent;
453    assert(p != 0);
454
455    // g is p's parent (a's grandparent)
456    group* g = p->parent;
457    assert(g != 0);
458
459    // a' <- A(r)
460    assert(A[r] != 0);
461    group* ap = A[r];
462    assert(ap != 0);
463
464    // A(r) <- nil
465    A[r] = 0;
466
467    // let a' have parent p'
468    group* pp = ap->parent;
469    assert(pp != 0);
470
471    // let a' have grandparent g'
472    group* gp = pp->parent;
473    assert(gp != 0);
474
475    // Remove a and a' from their parents
476    assert(ap == pp->children[pp->rank-1]); // Guaranteed because ap is active
477    --pp->rank;
478
479    // Guaranteed by caller
480    assert(a == p->children[p->rank-1]);
481    --p->rank;
482
483    // Note: a, ap, p, pp all have rank r
484    if (do_compare(pp, p)) {
485      do_swap(a, ap);
486      do_swap(p, pp);
487      do_swap(g, gp);
488    }
489
490    // Assuming k(p) <= k(p')
491    // make p' the rank r child of p
492    assert(r == p->rank);
493    p->children[p->rank++] = pp;
494    pp->parent = p;
495
496    // Combine a, ap into a rank r+1 group c
497    group* c = combine(a, ap);
498
499    // make c the rank r+1 child of g'
500    assert(gp->rank > r+1);
501    gp->children[r+1] = c;
502    c->parent = gp;
503
504#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
505    std::cerr << "After pair transform...\n";
506    dump_tree();
507#endif
508
509    if (A[r+1] == pp) A[r+1] = c;
510    else promote(c);
511  }
512
513  void active_sibling_transform(group* a, group* s)
514  {
515#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
516    std::cerr << "- active sibling transform\n";
517#endif
518    group* p = a->parent;
519    group* g = p->parent;
520
521    // remove a, s from their parents
522    assert(s->parent == p);
523    assert(p->children[p->rank-1] == s);
524    --p->rank;
525    assert(p->children[p->rank-1] == a);
526    --p->rank;
527
528    rank_type r = a->rank;
529    A[r+1] = 0;
530    a = combine(p, a);
531    group* c = combine(a, s);
532
533    // make c the rank r+2 child of g
534    assert(g->children[r+2] == p);
535    g->children[r+2] = c;
536    c->parent = g;
537    if (A[r+2] == p) A[r+2] = c;
538    else promote(c);
539  }
540
541  void good_sibling_transform(group* a, group* s)
542  {
543#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
544    std::cerr << "- good sibling transform\n";
545#endif
546    rank_type r = a->rank;
547    group* c = s->children[s->rank-1];
548    assert(c->rank == r);
549    if (A[r] == c) {
550#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
551      std::cerr << "- good sibling pair transform\n";
552#endif
553      A[r] = 0;
554      group* p = a->parent;
555
556      // Remove c from its parent
557      --s->rank;
558
559      // Make s the rank r child of p
560      s->parent = p;
561      p->children[r] = s;
562
563      // combine a, c and let the result by the rank r+1 child of p
564      assert(p->rank > r+1);
565      group* x = combine(a, c);
566      x->parent = p;
567      p->children[r+1] = x;
568
569      if (A[r+1] == s) A[r+1] = x;
570      else promote(x);
571
572#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
573      dump_tree(std::cerr);
574#endif
575      //      pair_transform(a);
576    } else {
577      // Clean operation
578      group* p = a->parent;
579      s->children[r] = a;
580      a->parent = s;
581      p->children[r] = c;
582      c->parent = p;
583
584      promote(a);
585    }
586  }
587
588  static void do_swap(group*& x, group*& y)
589  {
590    group* tmp = x;
591    x = y;
592    y = tmp;
593  }
594
595  /// Function object that compares two values in the heap
596  Compare compare;
597
598  /// Mapping from values to indices in the range [0, n).
599  ID id;
600
601  /** The root group of the queue. This group is special because it will
602   *  never store a value, but it acts as a parent to all of the
603   *  roots. Thus, its list of children is the list of roots.
604   */
605  group root;
606
607  /** Mapping from the group index of a value to the group associated
608   *  with that value. If a value is not in the queue, then the "value"
609   *  field will be empty.
610   */
611  std::vector<group> index_to_group;
612
613  /** Flat data structure containing the values in each of the
614   *  groups. It will be indexed via the id of the values. The groups
615   *  are each log_n long, with the last group potentially being
616   *  smaller.
617   */
618  std::vector< ::boost::optional<value_type> > groups;
619
620  /** The list of active groups, indexed by rank. When A[r] is null,
621   *  there is no active group of rank r. Otherwise, A[r] is the active
622   *  group of rank r.
623   */
624  std::vector<group*> A;
625
626  /** The group containing the smallest value in the queue, which must
627   *  be either a root or an active group. If this group is null, then we
628   *  will need to search for this group when it is needed.
629   */
630  mutable group* smallest_value;
631
632  /// Cached value log2(n)
633  size_type log_n;
634};
635
636
637} // end namespace boost
638
639#if defined(BOOST_MSVC)
640#  pragma warning(pop)
641#endif
642
643#endif // BOOST_RELAXED_HEAP_HEADER
Note: See TracBrowser for help on using the repository browser.