//
// Binary Tree ADT implementation
//

#ifndef __TREE
#define __TREE

#include "stack.h"

template <class T>
class __TreeNode {
 public:
  T key;
  __TreeNode<T> *left, *right;
  __TreeNode<T> (T k, __TreeNode<T> *l, __TreeNode<T> *r)
    { key = k; left = l; right = r; }
};

template <class T>
class BTree {

 protected:
  __TreeNode<T> *Root;

 public:
  BTree () { Root = NULL; }
  BTree (T& item);
  BTree (T& item, BTree* l, BTree* r);
  BTree (T& item, BTree& l, BTree& r);

  BTree (const BTree& t);
  ~BTree ();

 void operator = (BTree<T>& l) { this->Root = dup (l.Root); }

 protected:
  __TreeNode<T>* dup (__TreeNode<T>* ptr);
  int height (__TreeNode<T>* ptr) const;
  bool Destroy (__TreeNode<T>* ptr);
  
 public:
  virtual bool AddLeft (T&);
  virtual bool AddLeft (BTree*);
  virtual bool DeleteLeft ();

  virtual bool AddRight (T&);
  virtual bool AddRight (BTree*);
  virtual bool DeleteRight ();

 public:
  virtual int Height () const { return height (Root); }

 private:
  // Private recursive helpers for internal tree structure traversal
  void inorder (__TreeNode<T>* ptr, void (*Visit) (T&, int), int d) const;
  void preorder (__TreeNode<T>* ptr, void (*Visit) (T&, int), int d) const;
  void postorder (__TreeNode<T>* ptr, void (*Visit) (T&, int), int d) const;

 public:
  // Recursive solutions for internal tree structure traversals
  void Inorder (void (*Visit) (T&, int)) const
    { inorder (Root, Visit, 0); }
  void Preorder (void (*Visit) (T&, int)) const
    { preorder (Root, Visit, 0); }
  void Postorder (void (*Visit) (T&, int)) const
    { postorder (Root, Visit, 0); }

  // Iterative solutions for internal tree structure traversals using a stack
  void iInorder (void (*Visit) (T&)) const;
  void iPreorder (void (*Visit) (T&)) const;
  void iPostorder (void (*Visit) (T&)) const;

  // Recursive search of an item
  virtual bool Search (T& i) const { return Search (Root, i); }

  // Friendly operator for outputing a tree 
  friend ostream& operator << <> (ostream& out, BTree<T>& t);

  // 
  void operator = (BTree& t)
  {
    this->Root = dup (t.Root);
  }

  // Iterators
  template<class X> friend class BTreeIter;

 private:
  void Print (__TreeNode<T>* R, ostream& out, int d)
    {
      for (int i = 4*d; i > 0; i--) cout << " "; 
      if (R != NULL)
	{
	  out << R->key << endl;
	  Print (R->left, out, d+1);
	  Print (R->right, out, d+1);
	}
      else
      	out << "NULL" << endl;
    }
  bool Search (__TreeNode<T>*, T&) const;

};

template <class T> 
BTree<T>::BTree (T& item) 
{ 
  Root = new __TreeNode<T> (item, NULL, NULL); 
}

template <class T> 
BTree<T>::BTree (T& item, BTree* l, BTree* r) 
{ 
  Root = new __TreeNode<T> (item, l ? dup (l->Root) : NULL, 
		                r ? dup (r->Root) : NULL); 
}
 
template <class T> 
BTree<T>::BTree (T& item, BTree& l, BTree& r) 
{ 
  Root = new __TreeNode<T> (item, dup (l.Root), dup (r.Root)); 
}

template <class T>
BTree<T>::BTree (const BTree& t)
{
  Root = dup (t.Root);
}

template <class T> 
BTree<T>::~BTree () 
{ 
  Destroy (Root); 
  Root = NULL; 
}

// Recursive implementation for deallocating the internal tree structure
template <class T> 
bool BTree<T>::Destroy (__TreeNode<T>* ptr) 
{
  if (ptr != NULL)
    {
      Destroy (ptr->left);
      Destroy (ptr->right);
      delete ptr;
      return true;
    }
  return false;
}

// Recursive implementation for duplicating an internal tree structure
template<class T> 
__TreeNode<T>* BTree<T>::dup (__TreeNode<T>* ptr)
{
  __TreeNode<T>* crt = NULL;
  if (ptr != NULL)
    crt = new __TreeNode<T> (ptr->key, dup (ptr->left), dup (ptr->right));
  return crt;
}
  
template <class T> 
bool BTree<T>::AddLeft (T& item) 
{ 
  if (Root->left != NULL)
    return false;
  Root->left = new __TreeNode<T> (item, NULL, NULL);
  return true;
}

template <class T> 
bool BTree<T>::AddLeft (BTree* sl) 
{ 
  if (Root->left != NULL)
    return false;
  Root->left = dup (sl->Root);
  return true;
}

template <class T> 
bool BTree<T>::DeleteLeft () 
{ 
  Destroy (Root->left);
  Root->left = NULL;
}

template <class T> 
bool BTree<T>::AddRight (T& item) 
{ 
  if (Root->right != NULL)
    return false;
  Root->right = new __TreeNode<T> (item, NULL, NULL);
  return true;
}

template <class T> 
bool BTree<T>::AddRight (BTree* sr) 
{ 
  if (Root->right != NULL) 
    return false;
  Root->right = dup (sr->Root);
  return true;
}

template <class T> 
bool BTree<T>::DeleteRight () 
{ 
  Destroy (Root->right);
  Root->right = NULL;
}

template <class T> 
int BTree<T>::height (__TreeNode<T>* ptr) const
{
  if (ptr == NULL)
    return 0;
  int sd = height (ptr->right);
  int sl = height (ptr->left);
  return 1 + (sd > sl ? sd : sl);
}

template <class T> 
void BTree<T>::inorder (__TreeNode<T>* ptr, 
			void (*Visit) (T&, int), int d) const
{
  if (ptr != NULL)
    {
      inorder (ptr->left, Visit, d+1);
      if (Visit) 
        Visit (ptr->key, d);
      else
        cout << ptr->key << " ";
      inorder (ptr->right, Visit, d+1);
    }
}

template <class T> 
void BTree<T>::preorder (__TreeNode<T>* ptr, 
			 void (*Visit) (T&, int), int d) const
{
  if (ptr != NULL)
    {
      if (Visit)
        Visit (ptr->key, d);
      else
        cout << ptr->key << " ";
      preorder (ptr->left, Visit, d+1);
      preorder (ptr->right, Visit, d+1);
    }
}

template <class T> 
void BTree<T>::postorder (__TreeNode<T>* ptr, 
			  void (*Visit) (T&, int), int d) const
{
  if (ptr != NULL)
    {
      postorder (ptr->left, Visit, d+1);
      postorder (ptr->right, Visit, d+1);
      if (Visit)
        Visit (ptr->key, d);
      else
        cout << ptr->key << " ";
    }
}

// Iterative solutions for internal tree structure traversals
// using stack
template <class T> 
void BTree<T>::iInorder (void (*Visit) (T&)) const
{ 
  bool Done = false;
  __TreeNode<T>* crt = Root;
  Stack<__TreeNode<T>*> st;
  
  while (Done != true)
    {
      if (crt != NULL)
	{
	  st.Push (crt);
	  crt = crt->left;
	}
      else if (!st.isEmpty ())
	{
	  st.Pop (crt);
	  Visit (crt->key);
	  crt = crt->right;
	}
      else Done = true;
    }
}

template <class T> 
void BTree<T>::iPreorder (void (*Visit) (T&)) const
{ 
  __TreeNode<T>* crt;
  Stack<__TreeNode<T>*> st;
  
  st.Push (Root);
  while (!st.isEmpty ())
    {
      st.Pop (crt);
      if (crt != NULL)
	{
	  Visit (crt->key);
	  st.Push (crt->right);
	  st.Push (crt->left);
	}
    }      
}

// HW
template <class T> 
void BTree<T>::iPostorder (void (*Visit) (T&)) const
{ 
  
}


template <class T>
bool BTree<T>::Search (__TreeNode<T>* ptr, T& i) const
{
  if (ptr == NULL)
    return false;
  if (i == ptr->key)
    return true;
  return Search (ptr->left, i) || Search (ptr->right, i);
}

template<class T>
ostream& operator << (ostream& out, BTree<T>& t)
{ 
  t.Print (t.Root, out, 0); 
  return out; 
}

//
// Iterator Class Implementation
//
template <class T>
class BTreeIter {
  Stack< __TreeNode<T>* > st;

 public:
  BTreeIter (BTree<T>& t) 
    { 
      if (t.Root) 
	st.Push (t.Root); 
    }
  ~BTreeIter () { }

  bool Step ();
  bool Finished ();
  T& Get ();
};

template <class T>
bool BTreeIter<T>::Step ()
{
  __TreeNode<T>* crt;

  if (st.Pop (crt))
    {
      if (crt->right)
	st.Push (crt->right);
      if (crt->left)
	st.Push (crt->left);
      return true;
    }
  else
    {
      return false;
    }
}

template <class T>
bool BTreeIter<T>::Finished () 
{
  __TreeNode<T>* crt;

  return st.Top (crt) ? false : true;
}

template <class T>
T& BTreeIter<T>::Get () 
{
  __TreeNode<T>* crt = NULL;

  st.Top (crt);
  return crt->key;
}

#endif