// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- // 
// C++ Source Code File Name: rbtreeb.cpp
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced By: Doug Gaer 
// File Creation Date: 01/23/1997 
// Date Last Modified: 07/28/1998
// Copyright (c) 1997 Douglas M. Gaer
// ----------------------------------------------------------- // 
// ------------- Program Description and Details ------------- // 
// ----------------------------------------------------------- // 
/*
The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
All those who put this code or its derivatives in a commercial
product MUST mention this copyright in their documentation for
users of the products in which this code or its derivative
classes are used. Otherwise, you have the freedom to redistribute
verbatim copies of this source code, adapt it to your specific
needs, or improve the code and release your improvements to the
public provided that the modified files carry prominent notices
stating that you changed the files and the date of any change.

THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

(R)ed (B)lack (T)ree node data independent functions. 
*/
// ----------------------------------------------------------- //   
#include "rbtreeb.hpp"
#include "rbtree.hpp"

// Convenience macros
#define T  (pp.t)  // The current node
#define P  (pp.p)  // Parent 
#define G  (pp.g)  // Grandparent 
#define GG (pp.gg) // Great Grandparent
#define S  (pp.s)  // Sibling 
#define RS (pp.rs) // Right children of s 
#define LS (pp.ls) // Left children of s
#define M  (pp.m)  // Matching node 
#define PM (pp.pm) // Parent of matching node

RBNodeBase *InsBalance(RBNodeBase *Root, PtrPack &pp)
// Balance adjusting for top down insertions. Eliminates
// both P and T from being red by doing rotations and
// color changes. G, P, and T assumed not null coming in. 
// GG may be null. At the end of this routine, only Tree 
// and P will be valid with each other. G and GG may 
// not reflect the proper ordering.
{
  RBNodeBase *cofgg; // New child of great-grandparent
  int side;

  side = GG && GG->Right == G;

  if (G->Left == P) {
     if (P->Right == T) { // Do double rotate
        G->Left = T->Right;
        T->Right = G;
        P->Right = T->Left;
        T->Left = P;
        P = GG;
        cofgg = T;
     }
     else { // Do single rotate Right
        G->Left = P->Right;
        P->Right = G;
        cofgg = P;
     }
  }
  else { // G->Right == P
    if (P->Left == T) {  // Do double rotate
       G->Right = T->Left;
       T->Left = G;
       P->Left = T->Right;
       T->Right = P;
       P = GG;
       cofgg = T;
    }
    else { // Do single rotate Left
       G->Right = P->Left;
       P->Left = G;
       cofgg = P;
    }
  }
 
  cofgg->color = BlackNode;
  G->color = RedNode;

  if (GG) {
     if (side) GG->Right = cofgg; else GG->Left = cofgg;
  }
  else Root = cofgg;

  return Root;
}

RBNodeBase *DelBalance(RBNodeBase *Root, PtrPack &pp)
// Balancing code during top down deletion
{
  if ((T == 0 || T->color == BlackNode) && S && S->color == RedNode) {

     // Case: T is black, S red. T might be null,
     // but S and P must not be.

     // Fix G child to be S. Also S may become P of M
     if (G) {
        if (G->Left == P) G->Left = S; else G->Right = S;
     }
     else Root = S;
     if (P == M) PM = S;
     // Finish rotating
     if (P->Left == T) {
        // RotateLeft(P);
        P->Right = LS;
        S->Left = P;
        G = S;
        S = LS;
     }
     else {
        // RotateRight(P);
        P->Left = RS;
        S->Right = P;
        G = S;
        S = RS;
     }

     // Fixup children of S
     if (S) { LS = S->GetLeft(); RS = S->GetRight(); }
     // Fixup colors
     P->color = RedNode; G->color = BlackNode;
  }

  if (T && T->color == BlackNode &&
      (T->Left == 0 || T->GetLeft()->color == BlackNode) &&
      (T->Right == 0 || T->GetRight()->color == BlackNode)) {

     // Case: T is a single binary node with two black children.
     if (S && S->color == BlackNode &&
         (S->Left == 0 || S->GetLeft()->color == BlackNode) &&
         (S->Right == 0 || S->GetRight()->color == BlackNode)) {

       // Case: T and S are single binary nodes with two black children..
       P->color = BlackNode; T->color = RedNode; S->color = RedNode;

     }
     else if (LS && LS->color == RedNode) {

       // Case: Tree is a single binary node with two black children.
       // S is pair of binary nodes-one red, one black or S is a set
       // of three binary nodes with a black parent and red child nodes.
       // LS is red or RS might be red.

       if (P->Left == T) {
          // Fix colors
          LS->color = P->color; P->color = BlackNode; T->color = RedNode;
          // Fix G child to be LS. ALSo LS may become P of M
          if (G) {
             if (G->Left == P) G->Left = LS; else G->Right = LS;
          }
          else Root = LS;
          if (P == M) PM = LS;
          // Finish: DoubleRotateLeft(S, P);
          P->Right = LS->Left;
          LS->Left = P;
          S->Left = LS->Right;
          LS->Right = S;
          G = LS;
          // Do not fix S or LS since they get reassigned
          // at the top of next loop
       }
       else {
          // Fix colors
          S->color = P->color; LS->color = BlackNode;
          P->color = BlackNode; T->color = RedNode;
          // Fix G child to be S. Also S may become P of M
          if (G) {
             if (G->Left == P) G->Left = S; else G->Right = S;
          }
          else Root = S;
          if (P == M) PM = S;
          // Finish: RotateRight(P);
          P->Left = RS;
          S->Right = P;
          G = S;
          // Do not fix S or LS since they get reassigned
          // at the top of next loop
       }

     }
     else if (RS && RS->color == RedNode) {

       // Case: T is a single binary node with two black children.
       // S is a pair of binary nodes-one red, one black.
       // LS is black, RS is red.   

       if (P->Left == T) {
          // Fix colors
          RS->color = BlackNode; S->color = P->color;
          P->color = BlackNode; T->color = RedNode;
          // Fix G child to be S. Also, S may become P of M
          if (G) {
             if (G->Left == P) G->Left = S; else G->Right = S;
          }
          else Root = S;
          if (P == M) PM = S;
          // Finish: RotateLeft(P);
          P->Right = LS;
          S->Left = P;
          G = S;
          // Do not fix S or LS since they get reassigned
          // at the top of next loop
       }
       else {
          // Fix colors
          RS->color = P->color; P->color = BlackNode; T->color = RedNode;
          // Fix G child to become RS. ALSo, RS may become P of M.
          if (G) {
             if (G->Left == P) G->Left = RS; else G->Right = RS;
          }
          else Root = RS;
          if (P == M) PM = RS;
          // Finish: DoubleRotateRight(S, P);
          P->Left = RS->Right;
          RS->Right = P;
          S->Right = RS->Left;
          RS->Left = S;
          G = RS;
          // Do not fix S or LS since they get reassigned
          // at the top of next loop
       }

     }
  }

  return Root;
}

RBNodeBase *DoReplacement(RBNodeBase *Root, PtrPack &pp)
// Swaps the node data in the matching node's successor with the
// node data of the matching node to be deleted. Then the successor
// node with no data is deleted. If the matching node has no successor
// the parent node will equal the matching node and the replacement
// node becomes the non-null child of the matching node.
{
  // At this point, M is the node to delete, PM is it's parent,
  // P is the replacement node, G is it's parent. If M has no
  // successor, P will = M, and replacement is the non-null
  // child of M.

  if (M) { // Matching node was found
    if (P == M || M->Left == 0 || M->Right == 0) {
       // No successor, and/or at least one child null
       // Get non-null child, if any, else P will be null
       P = (M->Left) ? M->GetLeft() : M->GetRight();
    }
    else { // M has a successor to use as a replacement
       if (G != M) {
         // Successor is not immediate child of M, so detach
         // from where it is, attach to where M is
         G->Left = P->Right;
         P->Right = M->Right;
       }
       // Finish attaching where M is.
       P->Left = M->Left;
    }
    // P should have same color as M since it's going where M was
    if (P) P->color = M->color;
  }

  // Fixup PM child link to be P
  if (M) {
     if (PM) {
        if (PM->Left == M) PM->Left = P; else PM->Right = P;
     }
     else Root = P; // New Root, possibly null
  }

  return Root;
}

RBNodeBase *DetachMinMax(RBNodeBase *&Root, int mx)
// Detach the smallest node in the tree (the node all the way to the left)
// or the largest node in the tree (the node all the way to the right)
// if mx is true.
{
  struct PtrPack pp;

  if (Root == 0) return 0;

  T = Root; P = 0; G = 0;
  M = 0; PM = 0;

  while (T) {

    // Pretend we're on the matching node
    M = T; PM = P;

    // Update ancestor pointers
    G = P; P = T;

    // Then go all the way Left or Right
    if (mx) {
       T = P->GetRight(); S = P->GetLeft();
    }
    else {
       T = P->GetLeft(); S = P->GetRight();
    }

    if (S) {
       LS = S->GetLeft(); RS = S->GetRight();
    }
    else {
       LS = 0; RS = 0;
    }

    Root = DelBalance(Root, pp);

  } // end of while loop

  Root = DoReplacement(Root, pp);

  if (Root) Root->color = BlackNode;

  return M; // Node to delete
}
// ----------------------------------------------------------- // 
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //
