using namespace std;

#include <cassert>

#include "list.h"

/**
 * Constructs an empty list.
 */

List::List()
{
  root = NULL;
}

/**
 * Destroys this list
 */

List::~List()
{
  makeEmpty();
}

/**
 * pre: none
 * post: returns true iff the list is full.
 */

bool List::isFull() const
{
  return false;
}

/**
 * pre: none
 * post: returns the number of items on the list.
 */

int List::getLength() const
{
  return countNodes(root);
}

/**
 * pre: tree is NULL or a pointer to a node in a BST
 * post: returns the number of nodes in the subtree rooted at tree
 */

int List::countNodes(const Node *tree)
{
  if (tree == NULL)
    return 0;
  else
    return 1 + countNodes(tree->left) + countNodes(tree->right);
}

/**
 * pre: none
 * post: if item with same key as i is on the list, then that item is
 * copied into i and found = true, otherwise i is unchanged and i = false
 */

void List::retrieveItem(ItemType& i, bool& found) const
{
  retrieveItem(root, i, found);
}

/**
 * pre: tree is NULL or points to a node in a BST
 * post: if item with same key as i is on the list, then that item is
 * copied into i and found = true, otherwise i is unchanged and i = false
 */

void List::retrieveItem(const Node *tree, ItemType& i, bool& found)
{
  if (tree == NULL)
    found = false;
  else if (i.compareTo(tree->info) == 0)
    {
      found = true;
      i = tree->info;
    }
  else if (i.compareTo(tree->info) < 0)
    retrieveItem(tree->left, i, found);
  else
    retrieveItem(tree->right, i, found);
}

/**
 * pre: none
 * post: the list is empty
 */

void List::makeEmpty()
{
  makeEmpty(root);
}

/**
 * pre: tree is NULL or points to a node in a BST
 * post: all nodes in subtree rooted at tree are deleted and tree = NULL
 */

void List::makeEmpty(Node*& tree)
{
  if (tree != NULL)
    {
      makeEmpty(tree->left);
      makeEmpty(tree->right);
      delete tree;
      tree = NULL;
    }
}

/**
 * pre: no item with same key as toAdd is on the list and the list isn't full
 * post: item toAdd has been added to the list and items sorted by key
 */

void List::addItem(const ItemType& toAdd)
{
  addItem(root, toAdd);
}

/**
 * pre: tree is NULL or points to a node in a BST and no item with same key
 * as toAdd is in BST rooted at tree
 * post: tree points to root of a BST containing toAdd and all items
 * in original tree
 */

void List::addItem(Node*& tree, const ItemType& toAdd)
{
  if (tree == NULL)
    {
      tree = new Node;
      tree->left = NULL;
      tree->right = NULL;
      tree->info = toAdd;
    }
  else if (toAdd.compareTo(tree->info) < 0)
    addItem(tree->left, toAdd);
  else
    addItem(tree->right, toAdd);
}

/**
 * pre: an item with same key as toDelete is on the list
 * post: that item is no longer on the list and the current point is set to
 * the beginning of the list and items still sorted by key
 */

void List::deleteItem(const ItemType& toDelete)
{
  deleteItem(root, toDelete);
}

/**
 * pre: an item with same key as toDelete is in BST rooted at tree
 * post: that item is no longer in the BST
 */

void List::deleteItem(Node*& tree, const ItemType& toDelete)
{
  assert(tree != NULL);
  
  if (toDelete.compareTo(tree->info) < 0)
    deleteItem(tree->left, toDelete);
  else if (toDelete.compareTo(tree->info) > 0)
    deleteItem(tree->right, toDelete);
  else
    {
      if (tree->left == NULL && tree->right == NULL) // no children
	{
	  delete tree;
	  tree = NULL;
	}
      else if (tree->left == NULL) // only right child
	{
	  Node *deadNode = tree;
	  tree = deadNode->right;
	  delete deadNode;
	}
      else if (tree->right == NULL) // only left child
	{
	  Node *deadNode = tree;
	  tree = deadNode->left;
	  delete deadNode;
	}
      else if (tree->left->right == NULL) // two kids, child is max in left ST
	{
	  Node *deadNode = tree;
	  tree = deadNode->left;
	  tree->right = deadNode->right;
	  delete deadNode;
	}
      else // two kids, max in left subtree is somewhere down the tree
	{
	  Node *deadNode = tree;

	  // find the max in left subtree
	  Node *parentMax = deadNode->left;
	  Node *max = deadNode->left->right;
	  
	  while (max->right != NULL)
	    {
	      parentMax = max;
	      max = max->right;
	    }
	  
	  // now max is the largest node in the dead node's left subtree and
	  // parentMax is its parent
	  
	  tree = max;
	  parentMax->right = max->left;
	  max->left = deadNode->left;
	  max->right = deadNode->right;
	}
    }
}

/**
 * pre: none
 * post: the current position in the list is the beginning of the list
 */

void List::resetCurrent()
{
  inorder.makeEmpty();
  traverse(root, inorder);
}

/**
 * pre: tree is NULL or points to a node in a BST
 * post: pointers to nodes in BST rooted at tree are added to q in order
 * of data contained in them
 */

void List::traverse(Node *tree, Queue& q)
{
  if (tree != NULL)
    {
      traverse(tree->left, q);
      q.enqueue(tree);
      traverse(tree->right, q);
    }
}

/**
 * pre: there is a next item on the list
 * post: the current position is advanced one spot and the item moved over
 * is copied to nextItem
 */

void List::getNextItem(ItemType& nextItem)
{
  void *dummy;
  Node *currentNode;

  inorder.dequeue(dummy);

  // dequeue returns a generic (void) pointer; must cast it to correct type
  currentNode = (Node*)dummy;

  nextItem = currentNode->info;
}