// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- //
// C++ Header File Name: bstree.h
// 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: 03/15/1999
// Copyright (c) 1997 Douglas M. Gaer
// ----------------------------------------------------------- // 
// ---------- Include File 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.

This is a generic (R)ed (B)lack binary search (T)ree. The
RBTree class maintains binary search tree properties, by
allowing nodes to have no more then two children, but it
ensures the tree will be balanced by assigning links the
colors RED and BLACK. A black parent link is referred to as
a black node and a red parent link is referred to as a red
node.

Changes: 
================================================================
03/20/1998 - Removed duplicate definition of the FreeNode()
function.
Changed by: Doug Gaer
================================================================
*/
// ----------------------------------------------------------- //   
#ifndef __RBTREE_HPP
#define __RBTREE_HPP

#include "rbnode.h"
#include "bstreeb.h"
#include "rbtreeb.h"
#include "twalk.h"

template<class TYPE>
class RBTree
{
public:
  RBTree() { Root = 0; }
  virtual ~RBTree();
  RBTree(const RBTree<TYPE> &t) { Root = 0; Copy(t); }
  void operator=(const RBTree<TYPE> &t) { if (this != &t) Copy(t); }

public:
  int Copy(const RBTree<TYPE> &t);
  int Copy(const RBTree<TYPE> &t, WalkOrder w);
  void Clear() { DelTree(Root); Root = 0; }
  RBNode<TYPE> *GetMember(const TYPE &X);
  const RBNode<TYPE> *GetMember(const TYPE &X) const {
    return ((RBTree<TYPE> *)this)->GetMember(X); }
  RBNode<TYPE> *Add(const TYPE &X, int &existed);
  RBNode<TYPE> *Add(const TYPE &X) { int dmy; return Add(X, dmy); }
  RBNode<TYPE> *Detach(const TYPE &X);
  RBNode<TYPE> *DetachMin() {
    return (RBNode<TYPE> *)DetachMinMax((RBNodeBase *&)Root, 0); }
  RBNode<TYPE> *DetachMax() {
    return (RBNode<TYPE> *)DetachMinMax((RBNodeBase *&)Root, 1); }
  int Delete(const TYPE &X);
  void DeleteMin() { FreeNode(DetachMin()); }
  void DeleteMax() { FreeNode(DetachMax()); }
  RBNode<TYPE> *GetRoot() { return Root; }
  RBNode<TYPE> *GetMin() { return (RBNode<TYPE> *)Minimum(Root); }
  RBNode<TYPE> *GetMax() { return (RBNode<TYPE> *)Maximum(Root); }
  int IsEmpty() const { return Root == 0; }

protected:
  // Allocates a new RBNode<TYPE> node.
  virtual RBNode<TYPE> *AllocNode
  (const TYPE &X, char c=1, RBNode<TYPE> *l=0, RBNode<TYPE> *r=0);
    
  RBNode<TYPE> *DupTree(RBNode<TYPE> *t);
  void FreeNode(RBNode<TYPE> *n);
  void DelTree(RBNode<TYPE> *t);

protected:
  RBNode<TYPE> *Root;
};

template<class TYPE>
RBTree<TYPE>::~RBTree()
{
  Clear();
}

template<class TYPE>
RBNode<TYPE> *RBTree<TYPE>::
AllocNode(const TYPE &X, char c, RBNode<TYPE> *l, RBNode<TYPE> *r)
{
  return new RBNode<TYPE>(X, c, l, r);
}

template<class TYPE>
void RBTree<TYPE>::FreeNode(RBNode<TYPE> *n)
{
  delete n;
}

template<class TYPE>
RBNode<TYPE> *RBTree<TYPE>::GetMember(const TYPE &X)
// Returns pointer to node containing data X if there is
// such a node in the tree t, otherwise, a 0 is returned.
// Assumes TYPE has '<' and '==' defined.
{
  RBNode<TYPE> *t = Root;
  while (t) {
    if (X == t->Data) break;
    t = (X < t->Data) ? t->GetLeft() : t->GetRight();
  }
  return t;
}

template<class TYPE>
RBNode<TYPE> *RBTree<TYPE>::Add(const TYPE &X, int &exists)
{
  PtrPack pp;
  int side;

  exists = 1;
  pp.t = Root; pp.p = 0; pp.g = 0; pp.gg = 0;

  while(pp.t && X != ((RBNode<TYPE> *)(pp.t))->Data) {
    // If on a set of three binary nodes with a black
    // parent node and red child nodes, split it into
    // two single binary nodes with two black children.
    if ((pp.t->Left && pp.t->GetLeft()->color == RedNode) &&
        (pp.t->Right && pp.t->GetRight()->color == RedNode)) {
       pp.t->color = RedNode;
       pp.t->GetLeft()->color = BlackNode;
       pp.t->GetRight()->color = BlackNode;
       // Check for two reds in a row, and adjust if so
       if (pp.p && pp.p->color == RedNode)
          Root = (RBNode<TYPE> *)InsBalance(Root, pp);
    }
    pp.gg = pp.g; pp.g = pp.p; pp.p = pp.t;
    if (X < ((RBNode<TYPE> *)(pp.t))->Data) {
       pp.t = pp.t->GetLeft(); side = 0;
    }
    else {
       pp.t = pp.t->GetRight(); side = 1;
    }
  }

  // Reached the bottom, with no matching node
  if (pp.t == 0) {
     exists = 0;
     pp.t = AllocNode(X, RedNode);
     if (pp.t == 0) return 0; // Couldn't add
     if (pp.p) {
        if (side) pp.p->Right = pp.t; else pp.p->Left = pp.t;
     }
     else Root = (RBNode<TYPE> *)(pp.t);
     // Check for two reds in a row, and adjust if so
     if (pp.p && pp.p->color == RedNode)
        Root = (RBNode<TYPE> *)InsBalance(Root, pp);
  }

  Root->color = BlackNode; // Root always made black

  return (RBNode<TYPE> *)(pp.t);
}

template<class TYPE>
RBNode<TYPE> *RBTree<TYPE>::Detach(const TYPE &X)
{
  struct PtrPack pp;

  if (Root == 0) return 0;

  pp.t = Root; pp.p = 0; pp.g = 0;
  pp.m = 0; pp.pm = 0;

  while (pp.t) {
    // Go down the tree one level, searching for node to delete
    if ( ((RBNode<TYPE> *)(pp.t))->Data == X ) {
       pp.m = pp.t;  // Record matching node
       pp.pm = pp.p; // And it's parent
    }

    // Update ancestor pointers
    pp.g = pp.p; pp.p = pp.t;

    if (X < ((RBNode<TYPE> *)(pp.t))->Data) {
       pp.t = pp.p->GetLeft(); pp.s = pp.p->GetRight();
    }
    else { // Walk down even if t matches, to look for successor
       pp.t = pp.p->GetRight(); pp.s = pp.p->GetLeft();
    }

    if (pp.s) {
       pp.ls = pp.s->GetLeft(); pp.rs = pp.s->GetRight();
    }
    else {
       pp.ls = 0; pp.rs = 0;
    }

    Root = (RBNode<TYPE> *)DelBalance(Root, pp);

  } 

  Root = (RBNode<TYPE> *)DoReplacement(Root, pp);

  if (Root) Root->color = BlackNode;

  return (RBNode<TYPE> *)pp.m; // Node to delete

}

template<class TYPE>
int RBTree<TYPE>::Delete(const TYPE &X)
{
  RBNode<TYPE> *n = Detach(X);

  if (n) {
     FreeNode(n);
     return 1;
  }
  else return 0;
}

template<class TYPE>
void RBTree<TYPE>::DelTree(RBNode<TYPE> *t)
// Recursively deletes tree t, using post-order traversal
{
  if (t == 0) return;
  DelTree(t->GetLeft());
  DelTree(t->GetRight());
  FreeNode(t);
}

template<class TYPE>
RBNode<TYPE> *RBTree<TYPE>::DupTree(RBNode<TYPE> *t)
// Duplicates all of the nodes of tree t using a post-order
// traversal. Returns root of copy, or 0 if couldn't
// allocate root.
{
  if (t == 0) return 0;
  RBNode<TYPE> *l = DupTree(t->GetLeft());
  RBNode<TYPE> *r = DupTree(t->GetRight());
  return AllocNode(t->Data, t->color, l, r);
}


template<class TYPE>
int RBTree<TYPE>::Copy(const RBTree<TYPE> &t)
// Copies the nodes in tree t by using a recursive node
// duplication process. Clears this tree first.
{
  Clear();
  RBNode<TYPE> *r = DupTree(t.Root);
  if (r) {
     Root = r;
     return 1;
  }
  else return 0;
}

template<class TYPE>
int RBTree<TYPE>::Copy(const RBTree<TYPE> &t, WalkOrder w)
// Copies the nodes of tree t by walking t during a w-type
// traversal, and adding the nodes to this tree using the
// normal binary insertion process.
{
  Clear();
  TreeWalker< RBNode<TYPE> > tw(t.Root, w);
  RBNode<TYPE> *nxt;
  while(1) {
    nxt = tw.Next();
    if (nxt == 0) break;
    Add(nxt->Data);
  }
  return 1;
}

#endif // __RBTREE_HPP
// ----------------------------------------------------------- // 
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //
