relaxed_heap.hpp

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

// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine
#ifndef BOOST_RELAXED_HEAP_HEADER
#define BOOST_RELAXED_HEAP_HEADER

#include <functional>
#include <boost/property_map.hpp>
#include <boost/optional.hpp>
#include <vector>

#ifdef BOOST_RELAXED_HEAP_DEBUG
#  include <iostream>
#endif // BOOST_RELAXED_HEAP_DEBUG

#if defined(BOOST_MSVC)
#  pragma warning(push)
#  pragma warning(disable:4355) // complaint about using 'this' to
#endif                          // initialize a member

namespace boost {

template<typename IndexedType,
         typename Compare = std::less<IndexedType>,
         typename ID = identity_property_map>
class relaxed_heap
{
  struct group;

  typedef relaxed_heap self_type;
  typedef std::size_t  rank_type;

public:
  typedef IndexedType  value_type;
  typedef rank_type    size_type;

private:
  /**
   * The kind of key that a group has. The actual values are discussed
   * in-depth in the documentation of the @c kind field of the @c group
   * structure. Note that the order of the enumerators *IS* important
   * and must not be changed.
   */
  enum group_key_kind { smallest_key, stored_key, largest_key };

  struct group {
    explicit group(group_key_kind kind = largest_key)
      : kind(kind), parent(this), rank(0) { }

    /** The value associated with this group. This value is only valid
     *  when @c kind!=largest_key (which indicates a deleted
     *  element). Note that the use of boost::optional increases the
     *  memory requirements slightly but does not result in extraneous
     *  memory allocations or deallocations. The optional could be
     *  eliminated when @c value_type is a model of
     *  DefaultConstructible.
     */
    ::boost::optional<value_type> value;

    /**
     * The kind of key stored at this group. This may be @c
     * smallest_key, which indicates that the key is infinitely small;
     * @c largest_key, which indicates that the key is infinitely
     * large; or @c stored_key, which means that the key is unknown,
     * but its relationship to other keys can be determined via the
     * comparison function object.
     */
    group_key_kind        kind;

    /// The parent of this group. Will only be NULL for the dummy root group
    group*                parent;

    /// The rank of this group. Equivalent to the number of children in
    /// the group.
    rank_type            rank;

    /** The children of this group. For the dummy root group, these are
     * the roots. This is an array of length log n containing pointers
     * to the child groups.
     */
    group**               children;
  };

  size_type log_base_2(size_type n) // log2 is a macro on some platforms
  {
    size_type leading_zeroes = 0;
    do {
      size_type next = n << 1;
      if (n == (next >> 1)) {
        ++leading_zeroes;
        n = next;
      } else {
        break;
      }
    } while (true);
    return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1;
  }

public:
  relaxed_heap(size_type n, const Compare& compare = Compare(),
               const ID& id = ID())
    : compare(compare), id(id), root(smallest_key), groups(n),
      smallest_value(0)
  {
    if (n == 0) {
      root.children = new group*[1];
      return;
    }

    log_n = log_base_2(n);
    if (log_n == 0) log_n = 1;
    size_type g = n / log_n;
    if (n % log_n > 0) ++g;
    size_type log_g = log_base_2(g);
    size_type r = log_g;

    // Reserve an appropriate amount of space for data structures, so
    // that we do not need to expand them.
    index_to_group.resize(g);
    A.resize(r + 1, 0);
    root.rank = r + 1;
    root.children = new group*[(log_g + 1) * (g + 1)];
    for (rank_type i = 0; i < r+1; ++i) root.children[i] = 0;

    // Build initial heap
    size_type idx = 0;
    while (idx < g) {
      root.children[r] = &index_to_group[idx];
      idx = build_tree(root, idx, r, log_g + 1);
      if (idx != g)
        r = static_cast<size_type>(log_base_2(g-idx));
    }
  }

  ~relaxed_heap() { delete [] root.children; }

  void push(const value_type& x)
  {
    groups[get(id, x)] = x;
    update(x);
  }

  void update(const value_type& x)
  {
    group* a = &index_to_group[get(id, x) / log_n];
    if (!a->value
        || *a->value == x
        || compare(x, *a->value)) {
      if (a != smallest_value) smallest_value = 0;
      a->kind = stored_key;
      a->value = x;
      promote(a);
    }
  }

  void remove(const value_type& x)
  {
    group* a = &index_to_group[get(id, x) / log_n];
    assert(groups[get(id, x)] != 0);
    a->value = x;
    a->kind = smallest_key;
    promote(a);
    smallest_value = a;
    pop();
  }

  value_type& top()
  {
    find_smallest();
    assert(smallest_value->value != 0);
    return *smallest_value->value;
  }

  const value_type& top() const
  {
    find_smallest();
    assert(smallest_value->value != 0);
    return *smallest_value->value;
  }

  bool empty() const
  {
    find_smallest();
    return !smallest_value || (smallest_value->kind == largest_key);
  }

  bool contains(const value_type& x) const { return groups[get(id, x)]; }

  void pop()
  {
    // Fill in smallest_value. This is the group x.
    find_smallest();
    group* x = smallest_value;
    smallest_value = 0;

    // Make x a leaf, giving it the smallest value within its group
    rank_type r = x->rank;
    group* p = x->parent;
    {
      assert(x->value != 0);

      // Find x's group
      size_type start = get(id, *x->value) - get(id, *x->value) % log_n;
      size_type end = start + log_n;
      if (end > groups.size()) end = groups.size();

      // Remove the smallest value from the group, and find the new
      // smallest value.
      groups[get(id, *x->value)].reset();
      x->value.reset();
      x->kind = largest_key;
      for (size_type i = start; i < end; ++i) {
        if (groups[i] && (!x->value || compare(*groups[i], *x->value))) {
          x->kind = stored_key;
          x->value = groups[i];
        }
      }
    }
    x->rank = 0;

    // Combine prior children of x with x
    group* y = x;
    for (size_type c = 0; c < r; ++c) {
      group* child = x->children[c];
      if (A[c] == child) A[c] = 0;
      y = combine(y, child);
    }

    // If we got back something other than x, let y take x's place
    if (y != x) {
      y->parent = p;
      p->children[r] = y;

      assert(r == y->rank);
      if (A[y->rank] == x)
        A[y->rank] = do_compare(y, p)? y : 0;
    }
  }

#ifdef BOOST_RELAXED_HEAP_DEBUG
  /*************************************************************************
   * Debugging support                                                     *
   *************************************************************************/
  void dump_tree() { dump_tree(std::cout); }
  void dump_tree(std::ostream& out) { dump_tree(out, &root); }

  void dump_tree(std::ostream& out, group* p, bool in_progress = false)
  {
    if (!in_progress) {
      out << "digraph heap {\n"
          << "  edge[dir=\"back\"];\n";
    }

    size_type p_index = 0;
    if (p != &root) while (&index_to_group[p_index] != p) ++p_index;

    for (size_type i = 0; i < p->rank; ++i) {
      group* c = p->children[i];
      if (c) {
        size_type c_index = 0;
        if (c != &root) while (&index_to_group[c_index] != c) ++c_index;

        out << "  ";
        if (p == &root) out << 'p'; else out << p_index;
        out << " -> ";
        if (c == &root) out << 'p'; else out << c_index;
        if (A[c->rank] == c) out << " [style=\"dotted\"]";
        out << ";\n";
        dump_tree(out, c, true);

        // Emit node information
        out << "  ";
        if (c == &root) out << 'p'; else out << c_index;
        out << " [label=\"";
        if (c == &root) out << 'p'; else out << c_index;
        out << ":";
        size_type start = c_index * log_n;
        size_type end = start + log_n;
        if (end > groups.size()) end = groups.size();
        while (start != end) {
          if (groups[start]) {
            out << " " << get(id, *groups[start]);
            if (*groups[start] == *c->value) out << "(*)";
          }
          ++start;
        }
        out << '"';

        if (do_compare(c, p)) {
          out << "  ";
          if (c == &root) out << 'p'; else out << c_index;
          out << ", style=\"filled\", fillcolor=\"gray\"";
        }
        out << "];\n";
      } else {
        assert(p->parent == p);
      }
    }
    if (!in_progress) out << "}\n";
  }

  bool valid()
  {
    // Check that the ranks in the A array match the ranks of the
    // groups stored there. Also, the active groups must be the last
    // child of their parent.
    for (size_type r = 0; r < A.size(); ++r) {
      if (A[r] && A[r]->rank != r) return false;

      if (A[r] && A[r]->parent->children[A[r]->parent->rank-1] != A[r])
        return false;
    }

    // The root must have no value and a key of -Infinity
    if (root.kind != smallest_key) return false;

    return valid(&root);