//
// SimpleTreeNode.h
//
// Author: 
//    Michael A. Redmond based on work by T. Budd as revised by J. Turk
//
// Date Written:
//    04/24/00
//
//

#ifndef SIMPLETREENODE_H
#define SIMPLETREENODE_H

#include <iostream>
#include <assert.h>
using namespace std;

// SimpleTreeNode is a template class designed to handle simple binary trees
// using inOrder traversal, with no attempt to balance the tree
// SimpleTreeNode is simpler than Budd's in that it only does inOrder traversal and no balancing
//   which allows us to define it as a single template class rather than a whole bunch 
//   (Budd's program has a template class for node, which is also a base class for AVL tree (balanced) nodes,
//    and another template class for searchTree, which is also the base class for AVL trees. In addition, there
//    also is a class to create iterators for in order traversal (which could then be supplemented with 
//    classes for preorder and postorder traversal iterators
// (of course all of this makes Budd's program more general)
// Note that SimpleTreeNode is really a node in a tree - which gives us access to the 
//    whole tree from there on out because of pointers to children and
//    parent
template <class T> class SimpleTreeNode {
	public:
		// constructors
		// basic constructor - takes only one value (no empty tree)
		SimpleTreeNode (T val);
		//full constructor 
		SimpleTreeNode (T val, SimpleTreeNode<T> * lPtr, SimpleTreeNode<T> * rPtr,
			SimpleTreeNode<T> * pPtr);

		// basic inspector - returns value in a node
		T  GetValue() {
			return value;
		}


		// Copy a tree rooted at this node
		SimpleTreeNode * copy() const;

		// release entire tree started at this node
		// intentionally not a destructor to give us more control over 
		// when tree goes away
		void release();

		// accessing and changing child nodes
		SimpleTreeNode * left() const;
		void     left(SimpleTreeNode * lef);

		SimpleTreeNode * right() const;
		void     right(SimpleTreeNode * rgt);

		// accessing and changing parent node
		SimpleTreeNode * parent() const;
		void     parent(SimpleTreeNode * par);

		// common tree functions
		// add a new node to the tree in the correct place (no balancing)
		void     add(T val);
		// display tree rooted in current node
		void     displayTree ();
		// version to allow recursively displaying tree using same function
		void     displayTree (int level);

		// student assigned code
		T     FindMax();
		int   CountNodes() const;
		// returns whether a tree rooted at the current node includes the given value
		//bool     includes (T val);
		int      includes (T val);


	protected:

		T value;                     // holds the data itself
		SimpleTreeNode * parentPtr;
		SimpleTreeNode * leftChildPtr;
		SimpleTreeNode * rightChildPtr;

		// used for displaying tree
		int level;
};

// template class member-functions MUST
//  1) be written in the same .h file as the template class definition
//  2) be written in template form so that they can be used by multiple classes
//  3) be written with parameterized class template name as the scope

// basic constructor - uses base member initialization list syntax
//         (each datamembername(value) is equivalent to normal datamembername = value
//          but the way C++ works, this way is more efficient at run time
template <class T> SimpleTreeNode<T>::SimpleTreeNode( T val) : value(val),
leftChildPtr(0), rightChildPtr(0),parentPtr(0),level(0) {
	// no further initialization needed
}


//full constructor 
template <class T> SimpleTreeNode<T>::SimpleTreeNode (T val, SimpleTreeNode<T> * lPtr, SimpleTreeNode<T> * rPtr,
			SimpleTreeNode<T> * pPtr) : value(val),
leftChildPtr(lPtr), rightChildPtr(rPtr),parentPtr(pPtr),level(0) {
	// no further initialization needed
	// well - might should do something about level - if pPtr is not null
	// the level should be 1 greater than the parent pointer-> level
}



		
// Copy a tree rooted at this node
// copy constructor could probably use this when written?
template <class T> 
SimpleTreeNode<T> * SimpleTreeNode<T>::copy() const {
	// prepare pointers to hold sub-trees
	SimpleTreeNode<T> * newLeftPtr;
	SimpleTreeNode<T> * newRightPtr;
	// if there is a left child - duplicate left sub-tree
	if (leftChildPtr != 0) {
		// point to copy of subtree
		newLeftPtr = leftChildPtr->copy();
	}
	else {
		newLeftPtr = 0;
	}
	// if there is a right child - duplicate rigth sub-tree
	if (rightChildPtr != 0) {
		// point to copy of subtree
		newRightPtr = rightChildPtr->copy();
	}
	else {
		newRightPtr = 0;
	}


	// duplicate node
	SimpleTreeNode<T> * newPtr = new SimpleTreeNode<T> (value,newLeftPtr,newRightPtr,0);
	//check that allocation was successful
	// assert function crashes the program immediately if the condition evaluates to false
	// assert is generally used in debugging team project
	//    but here we can't really go on if memory is exhausted so I can live with assert here  (MAR)

	assert (newPtr != 0);

	
	// MAR seemed to be a slip-up by Budd - parent never set
	// set children's parent to current node
	if (newPtr->leftChildPtr != 0) {
		newPtr->leftChildPtr->parentPtr = newPtr;
	}
	// set children's parent to current node
	if (newPtr->rightChildPtr != 0) {
		newPtr->rightChildPtr->parentPtr = newPtr;
	}

	// return new top
	return newPtr;
}


// release memory for a tree rooted at this node
// Budd's works a little different - look at if can't delete this
template <class T> 
void SimpleTreeNode<T>::release()  {
	// release memory for children then come back for node itslef
	if (leftChildPtr != 0) {
		leftChildPtr->release();
		leftChildPtr = 0;
	}
	if (rightChildPtr != 0) {
		rightChildPtr->release();
		rightChildPtr = 0;
	}
	delete this;

}

// for accessing left child
template <class T>
SimpleTreeNode<T> * SimpleTreeNode<T>::left() const {
	// return the pointer to the left child
	return leftChildPtr;
}

// for changing the left child
template <class T>
void SimpleTreeNode<T>::left(SimpleTreeNode<T> * lPtr) {
	// set the left child
	leftChildPtr = lPtr;
	return;
}


// for accessing right child
template <class T>
SimpleTreeNode<T> * SimpleTreeNode<T>::right() const {
	// return the pointer to the right child
	return rightChildPtr;
}

// for changing the right child
template <class T>
void SimpleTreeNode<T>::right(SimpleTreeNode<T> * rPtr) {
	// set the right child
	rightChildPtr = rPtr;
	return;
}


// for accessing parent
template <class T>
SimpleTreeNode<T> * SimpleTreeNode<T>::parent() const {
	// return the pointer to the parent
	return parentPtr;
}

// for changing the parent
template <class T>
void SimpleTreeNode<T>::parent(SimpleTreeNode<T> * pPtr) {
	// set the parent
	parentPtr = pPtr;
	return;
}


// add a new node to the tree in the correct place (no balancing)
// assume that there is a root to the tree
template <class T>
void     SimpleTreeNode<T>::add(T val) {
	// set current pointer to current node
	SimpleTreeNode * currPtr = this;
	// prepare place to keep track of child
	SimpleTreeNode * childPtr;
	// loop until find a place - at leaf of search tree
	while (currPtr != 0) {
		if (currPtr->GetValue() < val) {
			// ok - here we're going high to the right
			childPtr = currPtr->right();
			// if we dont find a node then we've found the place to insert
			if (childPtr == 0) {
				// create a new node
				SimpleTreeNode * newPtr = new SimpleTreeNode<T> (val);
				// put correct level in 
				newPtr->level = currPtr->level + 1;
				// stick it in the right child position
				currPtr->right(newPtr);
				// set parent back to current node
				newPtr->parentPtr = currPtr;
				// bail out of function - we've done it
				return;
			}
		} // end outer if
		else {
			// value less than current - look to the left
			childPtr = currPtr->left();
			// if we dont find a node then we've found the place to insert
			if (childPtr == 0) {
				// create a new node
				SimpleTreeNode * newPtr = new SimpleTreeNode<T> (val);
				// put correct level in 
				newPtr->level = currPtr->level + 1;
				// stick it in the left child position
				currPtr->left(newPtr);
				// set parent back to current node
				newPtr->parentPtr = currPtr;
				// bail out of function - we've done it
				return;
			}
		} // end else
		// if we get here it is because we didn't find a place yet - need to go deeper
		currPtr = childPtr;
	} // end while
	return;
}






// display tree rooted in current node
template <class T>
void     SimpleTreeNode<T>::displayTree () {
	cout << endl << "Tree: " << endl;
	if (leftChildPtr != 0) {
		leftChildPtr->displayTree(level+1);
	}
	// space over
	for (int cnt = 0; cnt < level; cnt++) {
		cout << "    ";
	}
	cout << GetValue() << endl;
	if (rightChildPtr != 0) {
		rightChildPtr->displayTree(level+1);
	}
	return;
}


// version to allow recursively displaying tree using same function
template <class T>
void     SimpleTreeNode<T>::displayTree (int lev) { 
	if (leftChildPtr != 0) {
		leftChildPtr->displayTree(level+1);
	}
	// space over
	//for (int cnt = 0; cnt < level; cnt++) {
	for (int cnt = 0; cnt < lev; cnt++) {
		cout << "    ";
	}
	cout << GetValue() << endl;
	if (rightChildPtr != 0) {
		rightChildPtr->displayTree(level+1);
	}
	return;
}


#endif