/*search_tree class interface
Make a search_tree
If passed a value, (start of game tree) make a node with that value
Also, be able to append nodes to another node:
	-Search for the node, if not found return NULL
	-If found, add a new successor node containing value


*/


#include "d_node.h"



template <class Entry>
class search_tree {
public:
   search_tree();  //constructor
   //Post: An empty game tree has been created.
	search_tree(Entry x);
   bool empty() const;
   //Post: A result of true is returned if the binary tree is empty.
   //Otherwise, false is returned.
	
   d_node<Entry> *depth_search(Entry value);
	//start depth_search at root, pass templated function to do what you want

private:

	d_node<Entry> *recursive_depth_search(deque<d_node<Entry> > *&search_queue, Entry value);
	   
	   d_node<Entry> *root;
	  
};





template <class Entry>
search_tree<Entry>::search_tree()
{
	root=new d_node<Entry>;
	root=NULL;
	if (debug > 0) cout << "\nEmpty tree created.";
}

template <class Entry>
search_tree<Entry>::search_tree(Entry x)
{
	
	root = new d_node<Entry>;
	root->data = x;
	if (debug > 0) cout << "\nEmpty tree created.";
}


/*Use a queue to implement depth first search of our tree.
 - Push the root node on, then call recursive depth_search
*/
template <class Entry>
d_node<Entry> *search_tree<Entry>::depth_search(Entry value)
{
	 deque<d_node<Entry> > *search_queue;
	 search_queue = new deque<d_node<Entry> >;
	 search_queue->push_front(*root);
	return recursive_depth_search(search_queue, value);
}

/*Takes a deque of nodes, returns a node if value is found, otherwise, NULL
1. Make temp node called state
2. 
*/
template <class Entry>
d_node<Entry> *search_tree<Entry>::recursive_depth_search(deque<d_node<Entry> > *&search_queue, Entry value)
{
	d_node<Entry> *state = new d_node<Entry>;
	while(!search_queue->empty())
	{	
	
		state = search_queue->front();
	
		if (state->data == value) return state;   //If thats what we want, return that node
		else search_queue->pop_front();  //Else dump it, then 
	
		//add its successors to queue
		deque<d_node<Entry> >::iterator iter = state->leaves.begin();
		while ((iter != state->leaves.end()) && (search_queue->push_front(iter))) iter++;  //I think this will run both conditions.  so it will work on the last node.
		//then rerun search
		recursive_depth_search(search_queue, value);
	}
	return null;

	
}