rb_tree.c

将HTML转换为TXT文件的程序

    node_type *gp = pa->parent;

    ASSERT(x ->color == node_type::RED);
    ASSERT(pa->color == node_type::RED);
    ASSERT(gp->color == node_type::BLACK);

    node_type *uncle;
    if (pa == gp->left) {

      /*
       * Parent is left child of grandparent.
       */
      uncle = gp->right;               // May be 0
      if (!uncle || uncle->color == node_type::BLACK) {
        if (pa->right == x) {

          /*
           * X is right child of parent.
           */
          if (x->left) x->left->parent = pa;          // Case 2
          pa->right = x->left;
          x->left = pa;
          pa->parent = x;
          pa = x;
        }
        if (pa->right) pa->right->parent = gp;        // Case 3
        pa->parent = gp->parent;
        if (gp == gp->parent->left) {
          gp->parent->left = pa;
        } else {
          gp->parent->right = pa;
        }
        gp->parent = pa;
        gp->left = pa->right;
        pa->right = gp;
        pa->color = node_type::BLACK;
        gp->color = node_type::RED;
        break;
      }
    } else {

      /*
       * Parent is right child of grandparent.
       */
      uncle = gp->left;               // May be 0
      if (!uncle || uncle->color == node_type::BLACK) {
        if (pa->left == x) {

          /*
           * X is left child of parent.
           */
          if (x->right) x->right->parent = pa;        // Case 2
          pa->left = x->right;
          x->right = pa;
          pa->parent = x;
          pa = x;
        }
        if (pa->left) pa->left->parent = gp;          // Case 3
        pa->parent = gp->parent;
        if (gp == gp->parent->left) {
          gp->parent->left = pa;
        } else {
          gp->parent->right = pa;
        }
        gp->parent = pa;
        gp->right = pa->left;
        pa->left = gp;
        pa->color = node_type::BLACK;
        gp->color = node_type::RED;
        break;
      }
    }

    pa   ->color = node_type::BLACK;                  // Case 1
    uncle->color = node_type::BLACK;

    if (gp == root) break;

    gp->color = node_type::RED;
    x = gp;
  }

  return saved_x;
}

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

/*
 * Erase all matching nodes. Return number of nodes erased.
 */
rb_tree::size_type
rb_tree::erase_all(value_pointer vp)
{
  size_type count = 0;

  for (
    node_type *z = lower_bound(vp);
    z != end() && !node_less_than(vp, z);
    z = erase(z), ++count
  );
  return count;
}

/*
 * Erase one of the matching nodes. Return "false" if no node matches.
 */
bool
rb_tree::erase_one(value_pointer vp)
{
  node_type *z = find_any(vp);
  if (z == end()) return false;
  erase(z);
  return true;
}

rb_tree::node_type *
rb_tree::erase(node_type *z)
{
  if (z == end()) return end();

  ASSERT(z);
  ASSERT(z != end());

  node_type *succ = successor(z);               // May be "end()"
  node_type *y = z->left && z->right ? succ : z;

  ASSERT(y);
  ASSERT(y != end());
  ASSERT(!(y->left && y->right));

  node_type *x = y->left ? y->left : y->right;  // May be 0.
  node_type *x_parent = y->parent;              // May be "end()"

  /*
   * Isolate "y".
   */
  if (x) x->parent = x_parent;

  if (x_parent->left == y) {
    x_parent->left = x;
  } else {
    x_parent->right = x;
  }
  node_type::color_type old_color = y->color;

  /*
   * Implant "y" in place of "z"; this isolates "z".
   */
  if (y != z) {

    /*
     * Instead of copying the value, change all the links.
     */
    y->parent = z->parent;
    y->left   = z->left;
    y->right  = z->right;
    y->color  = z->color;
    if (z->parent->left == z) {
      z->parent->left = y;
    } else {
      z->parent->right = y;
    }
    if (z->left) z->left->parent = y;
    if (z->right) z->right->parent = y;
    if (x_parent == z) x_parent = y;
  }

  delete_node(z);

  /*
   * Check if fixup is necessary...
   */
  if (old_color == node_type::RED) return succ;

  while (x != root && (!x || x->color == node_type::BLACK)) {
    ASSERT(x_parent != end());
    if (x == x_parent->left) {
      node_type *sibling = x_parent->right;
      ASSERT(sibling);
      if (sibling->color == node_type::RED) {               // Case 1
        sibling->color = node_type::BLACK;
        x_parent->color = node_type::RED;
        left_rotate(x_parent);
        ASSERT(x_parent);
        ASSERT(x_parent != end());
        sibling = x_parent->right;
      }
      ASSERT(sibling);
      ASSERT(sibling != end());
      if (
        (!sibling->left || sibling->left->color == node_type::BLACK) &&
        (!sibling->right || sibling->right->color == node_type::BLACK)
      ) {                                                   // Case 2
        sibling->color = node_type::RED;
        x = x_parent;
        ASSERT(x_parent);
        ASSERT(x_parent != end());
        x_parent = x_parent->parent;
      } else {
        if (
          !sibling->right ||
          sibling->right->color == node_type::BLACK
        ) {                                                 // Case 3
          ASSERT(sibling);
          ASSERT(sibling != end());
          ASSERT(sibling->left);
          /*if (sibling->left)*/ sibling->left->color = node_type::BLACK;
          sibling->color = node_type::RED;
          right_rotate(sibling);
          ASSERT(x_parent);
          ASSERT(x_parent != end());
          sibling = x_parent->right;
        }
        ASSERT(x_parent);
        ASSERT(x_parent != end());
        sibling->color = x_parent->color;                   // Case 4
        x_parent->color = node_type::BLACK;
        ASSERT(sibling);
        ASSERT(sibling->right);
        /*if (sibling->right)*/ sibling->right->color = node_type::BLACK;
        left_rotate(x_parent);
        break;
      }
    } else {     // x->parent()->right == x
      node_type *sibling = x_parent->left;
      ASSERT(sibling);
      if (sibling->color == node_type::RED) {               // Case 1
        sibling->color = node_type::BLACK;
        x_parent->color = node_type::RED;
        right_rotate(x_parent);
        ASSERT(x_parent);
        ASSERT(x_parent != end());
        sibling = x_parent->left;
      }
      ASSERT(sibling);
      if (
        (!sibling->right || sibling->right->color == node_type::BLACK) &&
        (!sibling->left || sibling->left->color == node_type::BLACK)
      ) {                                                   // Case 2
        sibling->color = node_type::RED;
        x = x_parent;
        ASSERT(x_parent);
        ASSERT(x_parent != end());
        x_parent = x_parent->parent;
      } else {
        ASSERT(sibling);
        ASSERT(sibling != end());
        if (
          !sibling->left ||
          sibling->left->color == node_type::BLACK
        ) {                                                 // Case 3
          ASSERT(sibling->right);
          /*if (sibling->right)*/ sibling->right->color = node_type::BLACK;
          sibling->color = node_type::RED;
          left_rotate(sibling);
          ASSERT(x_parent);
          ASSERT(x_parent != end());
          sibling = x_parent->left;
        }
        ASSERT(x_parent);
        ASSERT(x_parent != end());
        sibling->color = x_parent->color;                   // Case 4
        x_parent->color = node_type::BLACK;
        ASSERT(sibling);
        ASSERT(sibling != end());
        ASSERT(sibling->left);
        /*if (sibling->left)*/ sibling->left->color = node_type::BLACK;
        right_rotate(x_parent);
        break;
      }
    }
  }

  ASSERT(x != end());
  if (x) x->color = node_type::BLACK;
  return succ;
}

/*
 * Erase all nodes from "n1" (inclusive) to "n2" (exclusive). "n1" may only be
 * "end()" if "n2" is also "end()".
 */
rb_tree::node_type *
rb_tree::erase(node_type *n1, node_type *n2)
{
  while (n1 != n2) n1 = erase(n1);
  return n1;
}

void
rb_tree::swap(rb_tree &x)
{

  /*
   * Swap pointers to root node.
   */
  node_type *tmp = root;
  root = x.root;
  x.root = tmp;

  /*
   * Fix up parent pointers of root nodes.
   */
  if (root) root->parent = end();
  if (x.root) x.root->parent = x.end();
}

/*
 * Returns "end()" if "x" was the last node.
 */
/*static*/ const rb_tree::node_type *
rb_tree::successor(const node_type *x)
{
  if (x->right) {
    x = x->right;
    while (x->left) x = x->left;
    return x;
  } else {
    for (;;) {
      if (x == x->parent->left) return x->parent;
      x = x->parent;
    }
  }
}

void
rb_tree::print(ostream &os, void *closure) const
{
  if (root) {
    os << "{ "; print_subtree(root, os, -1, closure); os << " }";
  } else {
    os << "{}";
  }
}

void
rb_tree::debug_print(ostream &os, void *closure) const
{
  if (root) print_subtree(root, os, 0, closure);
}


// "x" must have a right child, but not necessarily a parent.
void
rb_tree::left_rotate(node_type *x)
{
  ASSERT(x);
  ASSERT(x->right);

  node_type *y = x->right;          // set temporary y

  x->right = y->left;               // y's left is x's right
  if (y->left) y->left->parent = x; // link y->left's parent to x
  y->parent = x->parent;            // link x's parent to y
  if (x == x->parent->left) {
    x->parent->left = y;
  } else {
    x->parent->right = y;
  }
  y->left = x;                      // x is left child of y
  x->parent = y; 
}

// "x" must have a left child, but not necessarily a parent.
void
rb_tree::right_rotate(node_type *x)
{
  ASSERT(x);
  ASSERT(x->left);

  node_type* y = x->left;             // set temporary y

  x->left = y->right;                 // x's left is y's right
  if (y->right) y->right->parent = x; // link y->right's parent to x
  y->parent = x->parent;              // link y's parent to x
  if (x == x->parent->left) {
    x->parent->left = y;
  } else {
    x->parent->right = y;
  }
  y->right = x;                       // x is right child of y
  x->parent = y;
} 

/*virtual*/ void
rb_tree::print_node(const node_type &n, ostream &os, void *closure) const
{
  os << "value=";
  print_node_value(n, os, closure);
  os << ", left=";
  if (n.left) { print_node_value(*n.left, os, closure); } else { os << "0"; }
  os << ", right=";
  if (n.right) { print_node_value(*n.right, os, closure); } else { os << "0"; }

  os << ", color=" << (n.color == node_type::RED ? "RED" : "BLACK");
  os << ", parent=";
  if (n.parent == end()) {
    os << "TOP";
  } else {
    print_node_value(*n.parent, os, closure);
  }
}

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