rb_tree.c

将HTML转换为TXT文件的程序

/* ------------------------------------------------------------------------- */

/*
 * Copyright (c) 1999
 *      GMRS Software GmbH, Innsbrucker Ring 159, 81669 Munich, Germany.
 *      http://www.gmrs.de
 *      All rights reserved.
 *      Author: Arno Unkrig ([e-mail])
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by GMRS Software GmbH.
 * 4. The name of GMRS Software GmbH may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY GMRS SOFTWARE GMBH ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL GMRS SOFTWARE GMBH BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */

/* ------------------------------------------------------------------------- */

#ident "$Id: rb_tree.C,v 1.2 1999/11/17 21:57:41 arno Exp $"

#include <iostream.h>

#include "rb_tree.h"

#define ASSERT(x) if (!(x)) cerr << __FILE__ << ":" << __LINE__ << ": Assertion failed: " << #x << endl; else

/* ------------------------------------------------------------------------- */

rb_tree::rb_tree(
  const node_type *from,
  const node_type *to,
  node_type       *(*node_copier)(const node_type *)
)
{
  while (from && from != to) {
    insert(node_copier(from));
    from = successor(from);
  }
}

/*
 * Returns "end()" if tree is empty.
 */
rb_tree::node_type *
rb_tree::begin()
{
  node_type *n = end();
  while (n->left) n = n->left;
  return n;
}

const rb_tree::node_type *
rb_tree::begin() const
{
  const node_type *n = end();
  while (n->left) n = n->left;
  return n;
}

/*
 * Finds the first node that matches.
 * Returns "end()" if key cannot be found.
 */
rb_tree::node_type *
rb_tree::find_first(value_pointer vp)
{
  node_type *n = lower_bound(vp);
  return n == end() || node_less_than(vp, n) ? end() : n;
} 

/*
 * Finds any of the nodes that match.
 * Returns "end()" if key cannot be found.
 * Notice that this function is faster than "find_first()".
 */
rb_tree::node_type *
rb_tree::find_any(value_pointer vp)
{
  node_type *n = root;

  while (n) {
    if (node_less_than(vp, n)) {
      n = n->left;
    } else
    if (node_less_than(n, vp)) {
      n = n->right;
    } else {
      return n;
    }
  }

  return end();
} 

/*static*/ rb_tree::size_type
rb_tree::size(const node_type *n)
{
  return (
    (n->left  ? size(n->left ) : 0) +
    1 +
    (n->right ? size(n->right) : 0)
  );
}

rb_tree::size_type
rb_tree::count(value_pointer vp, const node_type *n) const
{
  if (node_less_than(n, vp)) return n->right ? count(vp, n->right) : 0;
  if (node_less_than(vp, n)) return n->left  ? count(vp, n->left ) : 0;
  return (
    1 +
    (n->left  ? count(vp, n->left ) : 0) +
    (n->right ? count(vp, n->right) : 0)
  );
}

/*
 * Returns "end()" if tree is less than the tree.
 */
rb_tree::node_type *
rb_tree::lower_bound(value_pointer vp)
{
  if (!root) return end();

  node_type *n = root;
  node_type *res = end();

  for (;;) {
    while (node_less_than(n, vp)) {
      n = n->right;
      if (!n) return res;
    }
    for (;;) {
      if (!n->left) return n;
      if (node_less_than(n->left, vp)) {
        res = n;
        n = n->left;
        break;
      }
      n = n->left;
    }
  }
}

rb_tree::node_type *
rb_tree::upper_bound(value_pointer vp)
{
  if (!root) return end();

  node_type *n = root;
  node_type *res = end();

  for (;;) {
    while (!node_less_than(vp, n)) {
      n = n->right;
      if (!n) return res;
    }
    for (;;) {
      if (!n->left) return n;
      if (!node_less_than(vp, n->left)) {
        res = n;
        n = n->left;
        break;
      }
      n = n->left;
    }
  }
}

void
rb_tree::check(
  int             *depth_return,
  int             *black_depth_return,
  int             *count_in_out,
  const node_type *n,
  ostream         &os
) const
{
  if (!n) { *depth_return = *black_depth_return = 0; return; }

  if (n->parent == end()) {
    if (root != n) os << "Inconsistent root pointer" << endl;
    if (n->color != node_type::BLACK) os << "Top node is not black" << endl;
  }

  // "n->parent->left == n" should also be true for the top node!
  if (n->parent->left != n && n->parent->right != n) {
    os << "Node is not child of its parent" << endl;
  }

  (*count_in_out)++;

  int ld, rd, lbd, rbd;

  if (n->left) {
    if (n->color == node_type::RED && n->left->color == node_type::RED) {
      os << "Red node has red left child" << endl;
    }
    check(&ld, &lbd, count_in_out, n->left, os);
  } else {
    ld = 0;
  }
  if (n->right) {
    if (n->color == node_type::RED && n->right->color == node_type::RED) {
      os << "Red node has red right child" << endl;
    }
    check(&rd, &rbd, count_in_out, n->right, os);
  } else {
    rd = 0;
  }
  *depth_return = 1 + (ld > rd ? ld : rd);
  if (n->left && n->right && lbd != rbd) {
    os << "Inconsistent black depth" << endl;
  }
  *black_depth_return = (
    (n->color == node_type::BLACK) +
    (n->left ? lbd : n->right ? rbd : 0)
  );
}

/*
 * This function has two modes of operation:
 *
 * (A) indent == -1:
 *        Print like
 *
 *                nodevalue1, nodevalue2, nodevalue3
 *
 *        Notice the ascending order.
 *        Notice that only the node *values* are printed, not the other node
 *        members like "left", "right", "parent", "color".
 *
 * (B) indent >= 0:
 *        Print a tree-like structure; one line per node, like:
 *
 *                    node1
 *                  node2
 *                    node3
 *                node4
 *                    node5
 *                  node6
 *                    node7
 *
 *        Notice that the entire nodes are printed, i.e. "left", "right",
 *        "parent", "color", "value".
 *        Notice that this only yields nice results if "operator<<(os, value)"
 *        does not generate any newline characters.
 */
void
rb_tree::print_subtree(
  const node_type *n,
  ostream         &os,
  int             indent,
  void            *closure
) const
{
  ASSERT(n);
  if (indent == -1) {
    if (n->left) { print_subtree(n->left, os, -1, closure); os << ", "; }
    print_node_value(*n, os, closure);
    if (n->right) { os << ", "; print_subtree(n->right, os, -1, closure); }
  } else {
    if (n->left) print_subtree(n->left, os, indent + 1, closure);
    for (int i = 0; i < indent; ++i) os << "  ";
    print_node(*n, os, closure); os << endl;
    if (n->right) print_subtree(n->right, os, indent + 1, closure);
  }
}

/*
 * Warning: Calls pure virtual method "copy_node()".
 */
rb_tree::node_type *
rb_tree::copy_subtree(const node_type *n1, node_type *pa) const
{
  ASSERT(n1);
  node_type *n2 = copy_node(n1);
  n2->left   = n1->left  ? copy_subtree(n1->left,  n2) : 0;
  n2->right  = n1->right ? copy_subtree(n1->right, n2) : 0;
  n2->parent = pa;
  n2->color  = n1->color;
  return n2;
}

/*
 * Warning: Calls pure virtual method "delete_node()".
 * Notice: Does not invalidate the "n->parent"'s reference to "n".
 */
void
rb_tree::delete_subtree(node_type *n)
{
  if (n->left ) delete_subtree(n->left );
  if (n->right) delete_subtree(n->right);
  delete_node(n);
}

/*
 * May be called from the destructor, because no pure virtual functions are
 * called.
 * Notice: Does not invalidate the "n->parent"'s reference to "n".
 */
/*static*/ void
rb_tree::delete_subtree(node_type *n, void (*node_deletor)(node_type *))
{
  if (n->left ) delete_subtree(n->left,  node_deletor);
  if (n->right) delete_subtree(n->right, node_deletor);
  node_deletor(n);
}

/*
 * Only "node_less_than()" must work for "x", i.e. "x"'s value must be set;
 * all other member are explicitly set here.
 */

/*
 * Case 1:
 *
 *        BLACK              x-> RED        (Continue with new "x".)
 *        /   \                 /   \
 *      RED   RED    ===>   BLACK   BLACK
 *       |                    |
 *  x-> RED                  RED
 *
 * --------------------------------------------------------------------
 *
 * Case 2:
 *
 *             F-BLACK                         D-BLACK      (Done.)
 *            /       \                        /     \
 *       B-RED     G-BLACK-opt   ===>     B-RED       F-RED
 *      /     \                           /   \       /   \
 *   A-opt     D-RED <-x               A-opt C-opt E-opt G-BLACK-opt
 *             /   \
 *          C-opt E-opt
 *
 * --------------------------------------------------------------------
 *
 * Case 3:
 *
 *              F-BLACK                        D-BLACK      (Done.)
 *              /     \                        /     \
 *          D-RED     G-BLACK-opt ===>    B-RED       F-RED
 *          /   \                         /   \       /   \
 *  x-> B-RED   E-opt                  A-opt C-opt E-opt G-BLACK-opt
 *      /   \
 *   A-opt C-opt
 *
 * (These cases apply for "parent(x) == left_child(grandparent(x))"; otherwise
 * mirror the diagrams.)
 */

rb_tree::node_type *
rb_tree::insert(node_type *x)
{
  x->left  = 0;
  x->right = 0;

  if (empty()) {
    x->parent = end();
    x->color = node_type::BLACK;
    root = x;
    return x;
  }

  x->color = node_type::RED;
  node_type *y = root;
  for (;;) {
    if (node_less_than(x, y)) {
      if (!y->left) { y->left = x; x->parent = y; break; }
      y = y->left;
    } else {
      if (!y->right) { y->right = x; x->parent = y; break; }
      y = y->right;
    }
  }

  node_type *saved_x = x;

  /*
   * Rebalance the tree from "x" to "root".
   */
  while (x->parent->color == node_type::RED) {
    ASSERT(x);
    ASSERT(x != end());
    ASSERT(x->color == node_type::RED);
    ASSERT(x->parent != end());
    ASSERT(x->parent->color == node_type::RED);
    ASSERT(x->parent->parent != end());
    ASSERT(x->parent->parent->color == node_type::BLACK);

    node_type *pa = x->parent;