/***********************************************************
     Copyright 2003 Rick Miller - Pulp Free Press 
     
     This source code accompanies the text C++ For Artists
     and is provided for instructional purposes only. No 
     warranty concerning the quality of the code is expressed
     or implied.

	 You are free to use this code in your programs so long
	 as this copyright notice is included in its entirety.

**********************************************************/

#ifndef BTREE_H
#define BTREE_H

#include "node.h"
#include "stack.h"
#include <iostream.h>

template<class T>
class BTree{
	public:
		BTree();
		~BTree();
		void Insert(T item);
		void List_PreOrder();
		void List_InOrder();
		void List_PostOrder();
	private:
		bool r,l;
		Node<T> *root;
		Stack<Node<T> *> its_stack;
		int node_count;
		void Insert(T item, Node<T> *tree, Node<T> *parent);
		void List_PreOrder(Node<T> *tree, Node<T> *parent);
		void List_InOrder(Node<T> *tree, Node<T> *parent);
		void List_PostOrder(Node<T> *tree, Node<T> *parent);
		void Delete_Tree(Node<T> *tree);
		void Visit(Node<T> *the_node);
		void List_PreOrder(Node<T> *tree);
		void List_InOrder(Node<T> *tree);
		void List_PostOrder(Node<T> *tree);

};

template<class T>
BTree<T>::BTree():node_count(0), root(NULL){}

template<class T>
BTree<T>::~BTree(){
	Delete_Tree(root);
}


template<class T>
void BTree<T>::Delete_Tree(Node<T> *tree){
	
	if(tree){
		its_stack.Push(tree);
		
	}
	while(!its_stack.IsEmpty()){
	
	if(tree->left_child)
			its_stack.Push(tree->left_child);
		
		
	if(tree->right_child)
			its_stack.Push(tree->right_child);
	tree = its_stack.Pop();
	delete tree;	
	}
}


template<class T>
void BTree<T>::Insert(T item){
	Insert(item, root, root);
}


template<class T>
void BTree<T>::Insert(T item, Node<T> *tree, Node<T> *parent){
	if(node_count == 0){
		root = new Node<T>(parent);
		root->item = item;
		root->number_of_items++;
		node_count++;    
	
		}
		else if(!tree){
		     tree = new Node<T>(parent);
			 tree->item = item;
			 tree->number_of_items++;
			 if(r) parent->right_child = tree;
			   else if(l) parent->left_child = tree;
		     node_count++;
		    }
	
	      else if(item == tree->item)
			tree->number_of_items++;
		     else if(item < tree->item){
		     	r = false;
		     	l = true;
		    	Insert(item, tree->left_child, tree);
		    	}
			       else if(item > tree->item){
			         r = true;
			         l = false;
				     Insert(item, tree->right_child, tree);
				     }
}

template<class T>
void BTree<T>::Visit(Node<T> *the_node){
	cout<<the_node->item;
}


template<class T>
void BTree<T>::List_PreOrder(){
	List_PreOrder(root);
}

template<class T>
void BTree<T>::List_InOrder(){
	List_InOrder(root);
}


template<class T>
void BTree<T>::List_PostOrder(){
	List_PostOrder(root);
}

template<class T>
void BTree<T>::List_PreOrder(Node<T> *tree){
	
	if(tree)
		its_stack.Push(tree);
	
	
	while(!its_stack.IsEmpty()){
		tree = its_stack.Pop();
		Visit(tree);
		if(tree->right_child)
			its_stack.Push(tree->right_child);
		if(tree->left_child)
			its_stack.Push(tree->left_child);
	}
}

template<class T>
void BTree<T>::List_InOrder(Node<T> *tree){
	
	if(tree){
		its_stack.Push(tree->left_child);
		
	}
	while(!its_stack.IsEmpty()){
	
	tree = its_stack.Pop();
	Visit(tree);
	
	if(tree->right_child)
			its_stack.Push(tree->right_child);
			
	if(tree)
			its_stack.Push(tree);
		
	}
}

template<class T>
void BTree<T>::List_PostOrder(Node<T> *tree){
	
	if(tree){
		its_stack.Push(tree->left_child);
		
	}
	while(!its_stack.IsEmpty()){
	tree = its_stack.Pop();
	Visit(tree);
	if(tree)
			its_stack.Push(tree);
		
		
	if(tree->right_child)
			its_stack.Push(tree->right_child);
		
	}
}

		



#endif