/*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

1.  First we must add searching, so that we can then add items to nodes.
    
*/


#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. If search queue is not empty
3. See if the first node in the queue contains our search term
4. If not, add it's successors to back of list, then recurse
*/
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();  //Here's our ERROR ***********************
	
		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;

}


/*

state = search_queue->front();

At the line above I get errors:
z:\Backup\User\My Documents\Prog1\search_tree.h(82): error C2440: '=' : cannot convert from 'std::allocator<_Ty>::value_type' to 'd_node<Entry> *'
        with
        [
            _Ty=d_node<char>
        ]
        and
        [
            Entry=char
        ]





*/