using namespace std;

#include <cassert>

#include "treemap.h"

/**
 * Constructs an empty map.
 */

TreeMap::TreeMap()
{
  root = NULL;
  numItems = 0;
}

/**
 * pre: none
 * post: destroys this map
 */

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

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

int TreeMap::getSize() const
{
  return numItems;
}

/**
 * pre: the given item is in the map
 * post: the value associated with the given item is returned
 */

TreeMap::ValueType TreeMap::getValue(const ItemType& i) const
{
  return getValue(root, i);
}

/**
 * pre: tree points to the root of a tree containing the given item
 * post: the value associated with that key is returned
 */

TreeMap::ValueType TreeMap::getValue(const Node *tree, const ItemType& i)
{
  assert(tree != NULL);

  if (i == tree->info)
    {
      return tree->value;
    }
  else if (i < tree->info)
    return getValue(tree->left, i);
  else
    return getValue(tree->right, i);
}

/**
 * pre: none
 * post: returns true iff the given item is in this map
 */

bool TreeMap::contains(const ItemType& i) const
{
  return contains(root, i);
}

/**
 * pre: tree is NULL or points to the root of a BST
 * post: returns true iff the given item is in the subtree rooted at tree
 */

bool TreeMap::contains(const Node *tree, const ItemType& i)
{
  if (tree == NULL)
    return false;
  else if (i == tree->info)
    return true;
  else if (i < tree->info)
    return contains(tree->left, i);
  else
    return contains(tree->right, i);
}

/**
 * pre: none
 * post: this map is empty
 */

void TreeMap::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 TreeMap::makeEmpty(Node*& tree)
{
  if (tree != NULL)
    {
      makeEmpty(tree->left);
      makeEmpty(tree->right);
      delete tree;
      tree = NULL;
    }
}

/**
 * pre: the given item isn't already in the map and the map isn't full
 * post: item toAdd has been added to the TreeMap and associated with
 * the given value
 */

void TreeMap::addItem(const ItemType& toAdd, const ValueType& val)
{
  addItem(root, toAdd, val);
  numItems++;
}

/**
 * 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 (associated with
 * the value given by int parameter)
 */

void TreeMap::addItem(Node*& tree, const ItemType& toAdd, const ValueType& val)
{
  if (tree == NULL)
    {
      tree = new Node;
      tree->left = NULL;
      tree->right = NULL;
      tree->info = toAdd;
      tree->value = val;
    }
  else if (toAdd < tree->info)
    addItem(tree->left, toAdd, val);
  else
    addItem(tree->right, toAdd, val);
}