#include <iostream>
#include <string>

using namespace std;
/* Node class for Interval tree */
class IntervalTreeNode
{
	string lo;
	string hi;
	IntervalTreeNode *left;
	IntervalTreeNode *right;
	string max_subtree_hi_val;
	bool lo_included;
	bool hi_included;
public:
	string getlo()
	{
		return lo;
	}
	
	string gethi()
	{
		return hi;
	}
	
	IntervalTreeNode* getleft()
	{
		return left;
	}
	
	IntervalTreeNode* getright()
	{
		return right;
	}

        IntervalTreeNode* setleft(IntervalTreeNode *value)
        {
	  left = value;
	}

        IntervalTreeNode* setRight(IntervalTreeNode *value)
        {
	  right = value;
	}
	
	string getmaxhi()
	{
		return max_subtree_hi_val;
	}
	
	IntervalTreeNode(string lo, string hi, bool lo_included, bool hi_included)
	{
		this->lo = lo;
		this->hi = hi;
		this->lo_included = lo_included;
		this->hi_included = hi_included;
		
		left = NULL;
		right = NULL;
	}

	IntervalTreeNode* search(string key, bool &isFound);
	void insertInterval(string lo, string hi, bool lo_included, bool hi_included);
        bool searchInterval(string lo, string hi);
};

class IntervalTree
{
public:
        IntervalTreeNode *root;

        IntervalTree()
        {
	  root = NULL;
	}

	bool isKeyPresent(string key);
	void addInterval(string lo, string hi, bool lo_included, bool hi_included);
	void deleteInterval(string lo, string hi);
        void deleteNode(string lo);
};

/* Search if given interval overlaps with the interval in the current node */
bool IntervalTreeNode::searchInterval(string lo, string hi)
{

  if (lo <= this->hi && this->lo <= hi)
        return true;

  return false;
}

/* Node deletion with given key */
void IntervalTree::deleteNode(string deletelo)
{
  IntervalTreeNode *traverse = root;
  IntervalTreeNode *parent_pointer = NULL;

  if (root == NULL)
    return;

  while (traverse != NULL && (traverse->getlo()) != deletelo)
  {
    parent_pointer = traverse;

    if ((traverse->getlo()) > deletelo)
    {
      traverse = traverse->getleft();
    }
    else
    {
      traverse = traverse->getright();
    }

  }

  /* Check if the key wasnt found in the tree */
  if (traverse == NULL)
    return;

  /* Check if only a left child exists. */
  if ((traverse->getright()) == NULL)
  {
    if ((parent_pointer->getleft()) == traverse)
    {
      parent_pointer->setleft(traverse->getleft());
    }
    else
    {
      parent_pointer->setright(traverse->getleft());

    }


    
	

IntervalTreeNode* IntervalTreeNode::search(string key, bool &isFound)
{

	//pthread_mutex_lock( &mutex_node );
	isFound = false;

	if (lo_included && key == lo)
	{
		isFound = true;
		//pthread_mutex_unlock( &mutex_node );
		return this;
	}

	if (hi_included && key == hi)
	{
		isFound = true;
		//pthread_mutex_unlock( &mutex_node );
		return this;
	}


	if (lo < key && hi > key)
	{
		isFound = true;
		//pthread_mutex_unlock( &mutex_node );
		return this;
	}

	if (left != NULL && (left->getmaxhi()) > key)
	{
		//pthread_mutex_unlock( &mutex_node );
		return left;
	}

	//pthread_mutex_unlock( &mutex_node );
	return right;
}
bool IntervalTree::isKeyPresent(string key)
{
	IntervalTreeNode *traverse = root;
	IntervalTreeNode *temp = NULL;
	bool isFound = false;

	/* While the value is not found and we still have nodes to search */
	while (traverse != NULL && isFound != true)
	{
		temp = traverse->search(key, isFound);
		traverse = temp;
	}

	return isFound;
}

void IntervalTreeNode::insertInterval(string insertlo, string inserthi, bool lo_included, bool hi_included)
{
	IntervalTreeNode *new_node = NULL;
	
	cout<<"in insertInterval"<<" "<<insertlo<<" "<<lo<<endl;

	/* Since the BST is built only on the lo values of the intervals as key, we shall only take lo values into account here */
	if (insertlo == lo) /* Key already exists in interval tree */
	{
		cout<<"case1"<<endl;
		/* need to check if hi value needs to updated for the current interval */
		if (inserthi > hi)
		{
		        cout<<"value updated1"<<endl;
			hi = inserthi;
			cout<<"value after updating1"<<" "<<hi<<endl;

		}
	}
	else if (insertlo < lo)
	{
		cout<<"case2"<<endl;
		/* Insertion in left subtree */
		if (left == NULL)
		{
			new_node = new IntervalTreeNode(insertlo, inserthi, lo_included, hi_included);
			left = new_node;
		}
		else
		{
			left->insertInterval(insertlo, inserthi, lo_included, hi_included);
		}
	}
	else if(insertlo > lo)
	{
		cout<<"case3"<<endl;
		/* Insertion in right subtree */
		if (right == NULL)
		{
			new_node = new IntervalTreeNode(insertlo, inserthi, lo_included, hi_included);
			right = new_node;
		}
		else
		{
			right->insertInterval(insertlo, inserthi, lo_included, hi_included);
		}
	}

	/* Check if max hi val needs to be updated for the current node */
	if (inserthi > max_subtree_hi_val)
	{
		max_subtree_hi_val = inserthi;
	}

}	

	 
void IntervalTree::addInterval(string insertlo, string inserthi, bool lo_included, bool hi_included)
{
	IntervalTreeNode *traverse = root;
	bool isInserted = false;
	IntervalTreeNode *new_node = NULL;

	if (inserthi <= insertlo)
	{
		cout<<"Erratical range"<<endl;
		return;
	}

	if (root == NULL)
	{
		new_node = new IntervalTreeNode(insertlo, inserthi, lo_included, hi_included);
		root = new_node;
		return;
	}

	cout<<"inserting2"<<" "<<insertlo<<endl;
	root->insertInterval(insertlo, inserthi, lo_included, hi_included);
}

int main()
{
	IntervalTree tree1;
	bool return_val = false;
	
	tree1.addInterval("AAA", "BaB", true, true);
	
	return_val = tree1.isKeyPresent("Aaab");
	
	if (return_val == true)
	{
		cout<<"true1"<<endl;
	}
	else
	{
		cout<<"false1"<<endl;
	}
	
	//tree1.addInterval("DD", "Df", true, true);
	tree1.addInterval("BBB", "DDD", true, true);
	
	return_val = tree1.isKeyPresent("CD");
	
	if (return_val == true)
	{
		cout<<"true2"<<endl;
	}
	else
	{
		cout<<"false2"<<endl;
	}

	return_val = tree1.root->searchInterval("EEE", "FFF");

	if (return_val == true)
	{
		cout<<"true3"<<endl;
	}
	else
	{
		cout<<"false3"<<endl;
	}

	//tree1.addInterval("AAA","CCC", true, true);

	cout<<((tree1.root)->getmaxhi())<<endl;
}