#include <iostream>
#include <cstdlib>
#include "tbb/task_scheduler_init.h"
#include "tbb/parallel_do.h"
#include "tbb/concurrent_queue.h"

#define N 10

using namespace std;
using namespace tbb;

class Node {
	public:
		int data;
		Node *left;
		Node *right;

		Node() : left(NULL), right (NULL) {}
};

class BST {
	private:
		Node *head;
		int sX; // we shall search this number
		concurrent_queue<bool> *CQ;

	public:
		BST(int x);

		void ins(int x);

		bool trav_find(BST &bst, int x);

		typedef Node *argument_type;

		void operator()( argument_type c_Node, parallel_do_feeder<argument_type> &append_task ) const
		{
			if ( c_Node == NULL ) {
				return;
			}

			if ( c_Node->data == sX ) {
				printf ("		 %p\n", (void *) c_Node);
				if ( (*CQ).empty() ) {
					(*CQ).push(true);
				}
			}

			append_task.add( c_Node->left );
			append_task.add( c_Node->right );
		}

};

BST::BST(int x)
{
	head = new Node;
	head->data = x;
	head->left = NULL;
	head->right = NULL;

	CQ = new concurrent_queue<bool>;

	printf("New BST (head = %p, data = %d)\n", (void *) head, x);
}

void BST::ins(int x)
{
	Node *c_Node = head;

	bool inserted = false;

	while ( ! inserted ) {
		if (x <= c_Node->data) {
			if ( c_Node->left == NULL ) {
				Node *n_Node = new Node;
				n_Node->data = x;
				c_Node->left = n_Node;
				printf ("   %d is left  of %d @ %p\n", x,c_Node->data,n_Node);
				inserted = true;
			} else {
				c_Node = c_Node->left;
			}
		} else {
			if ( c_Node->right == NULL ) {
				Node *n_Node = new Node;
				n_Node->data = x;
				c_Node->right = n_Node;
				printf ("   %d is right of %d @ %p\n", x,c_Node->data,n_Node);
				inserted = true;
			} else {
				c_Node = c_Node->right;
			}
		}
	}
}

bool BST::trav_find(BST &bst, int x)
{
	sX = x; // sets the value to be searched
	(*CQ).clear(); // if this is not empty, then at least once the element was found

	Node *ary[] = { head };

	parallel_do(ary, ary+1, BST(bst));

	return (! (*CQ).empty());
}

int main()
{
	task_scheduler_init init(4);

	BST my_tree(N/2);

	for (unsigned int i=0; i<N; i++) {
		my_tree.ins( rand() % N );
	}
	cout << endl;

	for ( int i=0; i<10; i++ ) {
		if ( my_tree.trav_find(my_tree, i) ) {
			printf ("   %3d : present\n\n", i);
		} else {
			printf ("   %3d : absent\n\n", i);
		}
	}

	return 0;
}