// GuestRegister.C

#include "GuestRegister.h"

GuestRegister::GuestRegister()
  : theTree() { }

void GuestRegister::Insert(
               const GuestInfo & g)
  // PRE: no record with g.name is in theTree
  // && theTree is a binary search Tree
  // MODIFIES: theTree
  // POST: theTree has g added to it
  // && theTree is still a binary search tree
{
  if (theTree.Root() == NULL) {
    theTree.BuildRoot(g);
  } else {

    NodePtr prevPtr = theTree.Root();
    NodePtr probePtr = prevPtr;

    // INV: prevPtr != NULL
    // && probePtr != theTree.Root()
    // --> prevPtr points to the parent of probePtr
    while (probePtr != NULL) {
      prevPtr = probePtr;
      if (g.name < Data(probePtr).name) {
	probePtr = LChild(probePtr);
      } else {
	// ASSERT: g.name > Data(probePtr).name
	probePtr = RChild(probePtr);
      }
    }
    
    // ASSERT: probePtr == NULL && prevPtr != NULL
    // && g.name < Data(prevPtr).name --> LChild(prevPtr) == NULL
    // && g.name > Data(prevPtr).name --> RChild(prevPtr) == NULL
    
    if (g.name < Data(prevPtr).name) {
      AppendLeft(prevPtr, g);
    } else {
      AppendRight(prevPtr, g);
    }
  }
}

NodePtr removeTop(NodePtr top)
  // PRE: top != NULL
  // MODIFIES: the subtree starting at top
  // POST: FCTVALpoints to the root node of the subtree
  // formed by removing top from the subtree top<entry>
  // && top is now a leaf node
  // NOTE: the node *top hasn't been returned to the free store yet.
{
  NodePtr left = LChild(top);
  NodePtr right = RChild(top);

  if (left == NULL) {
    // ASSERT: top may be a leaf, and has no left child
    SetRight(top, NULL);
    return right;
  }

  if (right == NULL) {
    // ASSERT: top has no right child
    SetLeft(top, NULL);
    return left;
  }

  SetLeft(top, NULL);
  SetRight(top, NULL);
  // ASSERT: left != NULL && right != NULL
  // && top is a leaf node

  NodePtr nr = LChild(right);

  if (nr == NULL) {
    // Make right new root.
    SetLeft(right, left);
    return right;
  }

  // ASSERT: left != NULL && right != NULL
  // && nr != NULL

  // Find a node just greater than top,
  // by following the left branch of nr.

  NodePtr parent = right;
  // INV: parent is the parent of nr
  while (LChild(nr) != NULL) {
    parent = nr;
    nr = LChild(nr);
  }

  // ASSERT: left != NULL && right != NULL
  // && nr != NULL && LChild(nr) == NULL
  // && parent is the parent of nr

  // Make nr the root of the returned tree.
  SetLeft(parent, RChild(nr));
  SetLeft(nr, left);
  SetRight(nr, right);
  return nr;
}

void GuestRegister::Delete(
			   const String & name,
			   Boolean & found)
{
  if (theTree.Root() == NULL) {
    found = FALSE;
    return;
  }

  NodePtr root = theTree.Root();
  if (Data(root).name == name) {
    found = TRUE;
    NodePtr newRoot = removeTop(root);
    DeleteLeaf(root);
    theTree.SetRoot(newRoot);
    return;
  }

  found = FALSE;
  NodePtr parent = root;
  // INV: parent != NULL -->
  // (Data(parent).name != name
  // && if name is in the subtree starting at root,
  //    then it's in the subtree starting at parent)
  // && (parent == NULL --> name is not in the tree starting at root)
  while (parent != NULL) {
    NodePtr child;
    if (name < Data(parent).name) {
	child = LChild(parent);
	if (child != NULL && (Data(child).name == name)) {
	  found = TRUE;
	  SetLeft(parent, removeTop(child));
	  DeleteLeaf(child);
	  return;
	}
      } else {
	// ASSERT: Data(parent).name < name
	child = RChild(parent);
	if (child != NULL && (Data(child).name == name)) {
	  found = TRUE;
	  SetRight(parent, removeTop(child));
	  DeleteLeaf(child);
	  return;
	}
      }
    parent = child;
  }
}

void GuestRegister::SearchFor(
			      const String & name,
			      Boolean & found,
			      GuestInfo& g) const
{
  if (theTree.Root() == NULL) {
    found = FALSE;
  } else {
    NodePtr probePtr = theTree.Root();

    // INV: (probePtr != NULL && a record with name field name is in theTree)
    // --> a record with name field name is in the tree with root probePtr.
    while (probePtr != NULL && Data(probePtr).name != name) {
      if (name < Data(probePtr).name) {
	probePtr = LChild(probePtr);
      } else {
	// ASSERT: name > Data(probePtr).name
	probePtr = RChild(probePtr);
      }
    }
    
    // ASSERT: probePtr == NULL || Data(probePtr).name == name
    
    if (probePtr == NULL) {
      found = FALSE;
    } else {
      found = TRUE;
      g = Data(probePtr);
    }
  }
}

void GuestRegister::InOrderPrint() const
{
  PrintInOrder(theTree.Root());
}