//  BST.cpp
//
//  Chris Nevison
//  March 13, 1997
//
//  Modified, Chris Nevison
//  May 2, 2000
//
//	Modified, G. Volger
//	March 13, 2001
//
//  Modification adds a function that returns contents in order 
//  in an apvector. 5-2-2000
//
//  This file provides the implementation for a map or directory 
//  structure which stores items which can be looked up using one
//  part of the item stored, the key.  When the item is stored, the key 
//  under which it is stored is specified separately.
//  Each item in the directory must have a unique key.  If
//  an item is inserted with the same key as an item already in the
//  directory, then the old item is removed (overwritten) by the new.
//
//  The directory is written as a template for two types, the type of
//  the key and the type of the items stored.  The key type must have the
//  operators ==, !=, <, and >, and assignment (=) defined.

template <class ItemType, class KeyType>
Directory<ItemType, KeyType>::Directory()
	:  myRoot(NULL)
{}

template <class ItemType, class KeyType>
Directory<ItemType, KeyType>::~Directory()
{
  FreeTree(myRoot);
}

////////////////  Accessors  ////////////////////

template <class ItemType, class KeyType>
bool Directory<ItemType, KeyType>::Lookup(const KeyType & key, 
                                          ItemType & item) const
// post: if there is an item which matches the key in the directory,
//       Lookup returns it as item and returns true, otherwise
//       item is unchanged and Lookup returns false
{
  return LookHelp(key, myRoot, item);
}

template <class ItemType, class KeyType>
apqueue<ItemType> Directory<ItemType, KeyType>::InorderList() const
{
	apqueue<ItemType> itemList;
	InorderHelp(itemList, myRoot);
	return itemList;
}


template <class ItemType, class KeyType>
void Directory<ItemType, KeyType>::Display() const
// post: Outputs the contents of the directory in order
{
}



//////////  Modifiers  ////////////

template <class ItemType, class KeyType>
void  Directory<ItemType, KeyType>::Insert(const ItemType & item,
                                           const  KeyType & key)
// post: item has been inserted into the directory
{
	InsHelp(myRoot, item, key);
}

template <class ItemType, class KeyType>
void Directory<ItemType, KeyType>::Remove(const KeyType & key)
// post: key has removed from the directory if possible
{
	RemHelp(myRoot, key);
}

//////////////////// Helper functions /////////////////

template <class ItemType, class KeyType>
void Directory<ItemType, KeyType>::FreeTree(TNode * T)
// pre:  T is a binary search tree
// post: the memory for all nodes below T in the tree has been deallocated
//       and the memory for the node pointed to by T has been deallocated
{
}

template <class ItemType, class KeyType>
void Directory<ItemType, KeyType>::InsHelp(TNode * & T, 
                                           const ItemType & item,
                                           const  KeyType & key) 
// pre:  T is a non-empty binary search tree 
// post: if any item in the tree had the same key as the given item,
//       that item has been replaced by the given item, otherwise a
//       node has been added to the tree containing the given item
//       so as to preserve the binary search tree ordering.
{
}

template <class ItemType, class KeyType>
bool Directory<ItemType, KeyType>::LookHelp(const KeyType & key, 
                                            TNode * T,
                                            ItemType & item) const
// pre:  T is a binary search tree
// post: if any item in the tree matches the given key,
//       that item is returned as item and LookHelp returns true,
//       otherwise LookHelp returns false.
{
}

template <class ItemType, class KeyType>
void Directory<ItemType, KeyType>::RemHelp(TNode * & root, 
                                           const KeyType & key)
// pre:  T is a binary search tree
// post: The key node is removed from the tree if it is found
//       If key is not found then the tree is not altered
{
}

template <class ItemType, class KeyType>
void Directory<ItemType, KeyType>::InorderHelp(apqueue<ItemType> & list,
                                               TNode * T) const
// pre:  T is a binary search tree
// post: Stores in the nodes in the BST in the queue using an Inorder traversal
{
}


template <class ItemType, class KeyType>
void  Directory<ItemType, KeyType>::DisplayHelp(TNode * T) const
// Preorder traversal for debugging only
{
}