/*
 *
 * Minimal Binary Tree Implementation
 *
 * Author: Gamblers doth Idyl blog
 *
 * From my blog posts about brushing up on some old techniques
 * This is not intended to be a full implementation, just an example to 
 * demonstrate some basic principles, in particular, enough to do breadth and
 * depth first searches.
 *
 *
 *
 * Changes and Additions
 *
 * 0.2 Apr 28 2008
 * Addition of an "STL style" iterator
 *
 * 0.1 Apr 26 2008
 *
 *
 * Do with this code what you like.
 * I place this in the public domain. No warranty expressed or implied.
 * 
 *
 */


#ifndef _BINTREE_H_
#define _BINTREE_H_

#include <iostream>
#include <cassert>

#include "queue.h"

using namespace std;

typedef enum Child {LEFT, RIGHT}; 

template <class T> 
struct TreeItem {
	
	TreeItem(T data_) {
		data = data_;
		child_left = NULL;
		child_right = NULL;
		visited = false;
	}
	
	T data;
	TreeItem *child_left, *child_right;
	bool visited; 
};

template <class T>
struct BinTree {
	
	BinTree() {
		num_items = 0;
	}
	
	TreeItem<T>* create_node_and_link(TreeItem<T>* node, Child left_or_right, T data ) {
			
		assert(node);
	
		TreeItem<T>* new_node = new TreeItem<T>(data);
		
		if (num_items > 0) {
			
			// create a new node and tack it on either left or right
			
			assert(new_node);
			
			if (left_or_right == LEFT)
				node->child_left = new_node;
			else
				node->child_right = new_node;
		} else {
			
			// the tree is empty - instantiate the root node
			root = new_node;
		}
		
		num_items++;
		
		return new_node;
	}
	
	// Recursive depth first traverse 
	void dft(TreeItem<T>* iter) {
		
		if (!iter)
			return;
		
		cout << iter->data << " ";
		
		if (iter->child_left)
			dft(iter->child_left);
		
		if (iter->child_right)
			dft(iter->child_right);
	}
	
	void bfs(TreeItem<T>* iter) {
	
		Queue<TreeItem<T>*> q;
		
		q.push_back(iter);
		
		while (q.pop(iter)) {
		
			cout << iter->data << " ";
			
			if (iter->child_left) 
				q.push_back(iter->child_left);
			if (iter->child_right) 
				q.push_back(iter->child_right);
	
			
		} 
	}
	
	class bft_iterator;
	bft_iterator begin() { return bft_iterator(root); }
	bft_iterator end() { return bft_iterator(NULL); }
	
	private:
	
	TreeItem<T>* root; //right_deepest, rightmost
	unsigned long num_items;
};


template <class T>
struct BinTree<T>::bft_iterator
{
	bft_iterator(TreeItem<T>* node) {
		pointer = node;
		if (node) {
			q.push_back(node);
			step();
		}
	}
	
	bool operator==(const bft_iterator& rhs) {
		return (pointer == rhs.pointer);
	}
	
	bool operator!=(const bft_iterator& rhs) {
		return (pointer != rhs.pointer);
	}
	
	void operator++(int) {
	
		step();
	}
	
	T operator*() {
		
		if (pointer)
			return pointer->data;
		else 
			return T();
	}
	
	private:
	
	void step() {
		if (q.pop(pointer) && pointer && !pointer->visited) {
			pointer->visited = true;
			if (pointer->child_left) 
				q.push_back(pointer->child_left);
			if (pointer->child_right) 
				q.push_back(pointer->child_right);
		} else {
			pointer = NULL;
		}
	}
	
	TreeItem<T> 	*pointer; 	// current position in the tree 
			
	Queue<TreeItem<T>*> q;
};



#endif