relaxed_heap.hpp

来自「support vector clustering for vc++」· HPP 代码 · 共 643 行 · 第 1/2 页

  }

  bool valid(group* p)
  {
    for (size_type i = 0; i < p->rank; ++i) {
      group* c = p->children[i];
      if (c) {
        // Check link structure
        if (c->parent != p) return false;
        if (c->rank != i) return false;

        // A bad group must be active
        if (do_compare(c, p) && A[i] != c) return false;

        // Check recursively
        if (!valid(c)) return false;
      } else {
        // Only the root may
        if (p != &root) return false;
      }
    }
    return true;
  }

#endif // BOOST_RELAXED_HEAP_DEBUG

private:
  size_type
  build_tree(group& parent, size_type idx, size_type r, size_type max_rank)
  {
    group& this_group = index_to_group[idx];
    this_group.parent = &parent;
    ++idx;

    this_group.children = root.children + (idx * max_rank);
    this_group.rank = r;
    for (size_type i = 0; i < r; ++i) {
      this_group.children[i] = &index_to_group[idx];
      idx = build_tree(this_group, idx, i, max_rank);
    }
    return idx;
  }

  void find_smallest() const
  {
    group** roots = root.children;

    if (!smallest_value) {
      std::size_t i;
      for (i = 0; i < root.rank; ++i) {
        if (roots[i] &&
            (!smallest_value || do_compare(roots[i], smallest_value))) {
          smallest_value = roots[i];
        }
      }
      for (i = 0; i < A.size(); ++i) {
        if (A[i] && (!smallest_value || do_compare(A[i], smallest_value)))
          smallest_value = A[i];
      }
    }
  }

  bool do_compare(group* x, group* y) const
  {
    return (x->kind < y->kind
            || (x->kind == y->kind
                && x->kind == stored_key
                && compare(*x->value, *y->value)));
  }

  void promote(group* a)
  {
    assert(a != 0);
    rank_type r = a->rank;
    group* p = a->parent;
    assert(p != 0);
    if (do_compare(a, p)) {
      // s is the rank + 1 sibling
      group* s = p->rank > r + 1? p->children[r + 1] : 0;

      // If a is the last child of p
      if (r == p->rank - 1) {
        if (!A[r]) A[r] = a;
        else if (A[r] != a) pair_transform(a);
      } else {
        assert(s != 0);
        if (A[r + 1] == s) active_sibling_transform(a, s);
        else good_sibling_transform(a, s);
      }
    }
  }

  group* combine(group* a1, group* a2)
  {
    assert(a1->rank == a2->rank);
    if (do_compare(a2, a1)) do_swap(a1, a2);
    a1->children[a1->rank++] = a2;
    a2->parent = a1;
    clean(a1);
    return a1;
  }

  void clean(group* q)
  {
    if (2 > q->rank) return;
    group* qp = q->children[q->rank-1];
    rank_type s = q->rank - 2;
    group* x = q->children[s];
    group* xp = qp->children[s];
    assert(s == x->rank);

    // If x is active, swap x and xp
    if (A[s] == x) {
      q->children[s] = xp;
      xp->parent = q;
      qp->children[s] = x;
      x->parent = qp;
    }
  }

  void pair_transform(group* a)
  {
#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
    std::cerr << "- pair transform\n";
#endif
    rank_type r = a->rank;

    // p is a's parent
    group* p = a->parent;
    assert(p != 0);

    // g is p's parent (a's grandparent)
    group* g = p->parent;
    assert(g != 0);

    // a' <- A(r)
    assert(A[r] != 0);
    group* ap = A[r];
    assert(ap != 0);

    // A(r) <- nil
    A[r] = 0;

    // let a' have parent p'
    group* pp = ap->parent;
    assert(pp != 0);

    // let a' have grandparent g'
    group* gp = pp->parent;
    assert(gp != 0);

    // Remove a and a' from their parents
    assert(ap == pp->children[pp->rank-1]); // Guaranteed because ap is active
    --pp->rank;

    // Guaranteed by caller
    assert(a == p->children[p->rank-1]);
    --p->rank;

    // Note: a, ap, p, pp all have rank r
    if (do_compare(pp, p)) {
      do_swap(a, ap);
      do_swap(p, pp);
      do_swap(g, gp);
    }

    // Assuming k(p) <= k(p')
    // make p' the rank r child of p
    assert(r == p->rank);
    p->children[p->rank++] = pp;
    pp->parent = p;

    // Combine a, ap into a rank r+1 group c
    group* c = combine(a, ap);

    // make c the rank r+1 child of g'
    assert(gp->rank > r+1);
    gp->children[r+1] = c;
    c->parent = gp;

#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
    std::cerr << "After pair transform...\n";
    dump_tree();
#endif

    if (A[r+1] == pp) A[r+1] = c;
    else promote(c);
  }

  void active_sibling_transform(group* a, group* s)
  {
#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
    std::cerr << "- active sibling transform\n";
#endif
    group* p = a->parent;
    group* g = p->parent;

    // remove a, s from their parents
    assert(s->parent == p);
    assert(p->children[p->rank-1] == s);
    --p->rank;
    assert(p->children[p->rank-1] == a);
    --p->rank;

    rank_type r = a->rank;
    A[r+1] = 0;
    a = combine(p, a);
    group* c = combine(a, s);

    // make c the rank r+2 child of g
    assert(g->children[r+2] == p);
    g->children[r+2] = c;
    c->parent = g;
    if (A[r+2] == p) A[r+2] = c;
    else promote(c);
  }

  void good_sibling_transform(group* a, group* s)
  {
#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
    std::cerr << "- good sibling transform\n";
#endif
    rank_type r = a->rank;
    group* c = s->children[s->rank-1];
    assert(c->rank == r);
    if (A[r] == c) {
#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
      std::cerr << "- good sibling pair transform\n";
#endif
      A[r] = 0;
      group* p = a->parent;

      // Remove c from its parent
      --s->rank;

      // Make s the rank r child of p
      s->parent = p;
      p->children[r] = s;

      // combine a, c and let the result by the rank r+1 child of p
      assert(p->rank > r+1);
      group* x = combine(a, c);
      x->parent = p;
      p->children[r+1] = x;

      if (A[r+1] == s) A[r+1] = x;
      else promote(x);

#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
      dump_tree(std::cerr);
#endif
      //      pair_transform(a);
    } else {
      // Clean operation
      group* p = a->parent;
      s->children[r] = a;
      a->parent = s;
      p->children[r] = c;
      c->parent = p;

      promote(a);
    }
  }

  static void do_swap(group*& x, group*& y)
  {
    group* tmp = x;
    x = y;
    y = tmp;
  }

  /// Function object that compares two values in the heap
  Compare compare;

  /// Mapping from values to indices in the range [0, n).
  ID id;

  /** The root group of the queue. This group is special because it will
   *  never store a value, but it acts as a parent to all of the
   *  roots. Thus, its list of children is the list of roots.
   */
  group root;

  /** Mapping from the group index of a value to the group associated
   *  with that value. If a value is not in the queue, then the "value"
   *  field will be empty.
   */
  std::vector<group> index_to_group;

  /** Flat data structure containing the values in each of the
   *  groups. It will be indexed via the id of the values. The groups
   *  are each log_n long, with the last group potentially being
   *  smaller.
   */
  std::vector< ::boost::optional<value_type> > groups;

  /** The list of active groups, indexed by rank. When A[r] is null,
   *  there is no active group of rank r. Otherwise, A[r] is the active
   *  group of rank r.
   */
  std::vector<group*> A;

  /** The group containing the smallest value in the queue, which must
   *  be either a root or an active group. If this group is null, then we
   *  will need to search for this group when it is needed.
   */
  mutable group* smallest_value;

  /// Cached value log_base_2(n)
  size_type log_n;
};


} // end namespace boost

#if defined(BOOST_MSVC)
#  pragma warning(pop)
#endif

#endif // BOOST_RELAXED_HEAP_HEADER