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