#include <vector>
#include <iostream>
using namespace std;

#include "rtsDTGrid1D.h"

#ifndef _RTS_DTGRID2D_H
#define _RTS_DTGRID2D_H

struct IndexPair
{
	//int toValue;
	int toConn;
	int numConn;
};

#include "ColumnUnion.h"

struct Coord2D
{
	int x1;
	int x2;
};



template<typename T>
class rtsDTGrid2D
{
private:
	//main arrays
	vector<T> value;
	vector<ConnectedComponent> conn;
	rtsDTGrid1D<IndexPair> proj1D;
	bool randomIndex(rtsDTGrid1D<IndexPair>::iterator &iter1D, int &v_i, int &c_i, int x1, int x2);

	

	//variables to keep track of insertion
	int max_coord;
	bool grid_insertion_started;
	bool column_insertion_started;


public:
	rtsDTGrid2D<T>()
	{
		grid_insertion_started = false;
		column_insertion_started = false;
		proj1D.background.toConn = -1;
		max_coord = 0;
	}

	bool push(int x1, int x2, T v);
	T random(int x1, int x2);
	T& back();
	T background;
	void print();

	friend class ColumnUnion;
	void dilate(int H);
	void insert(rtsDTGrid2D<T> toInsert);
	void operator=(T rhs);
	void getBounds(int &min_x1, int &min_x2, int &max_x1, int &max_x2);

	void dumpValue();
	void dumpConn();

	//iterator
	class iterator;
	friend class iterator;
	class stencil_iterator;
	iterator randomIterator(int x1, int x2);
	iterator begin();
	iterator before();
	iterator end();
	iterator after();
};

/**********ITERATOR***********************/
template<typename T>
class rtsDTGrid2D<T>::iterator
{
	friend class rtsDTGrid2D;
	rtsDTGrid2D<T>* parent;
	rtsDTGrid1D<IndexPair>::iterator loc1D;
	int iv;
	int ic;
	int x2;

public:
	

	T Value(){return parent->value[iv];}
	int X1(){return loc1D.X1();}
	int X2(){return x2;}
	iterator(){parent = NULL;}
	void SetValue(T value){parent->value[iv] = value;}
	

	void increment()
	{
		//increment the value
		iv++;
		//if this exceeds the length of the value array, we are at the end of the grid
		if(iv == parent->value.size())
		{
			(*this) = parent->after();
			return;
		}

		//increment the current coordinate
		x2++;
		//if we are outside of the current connected component
		if(x2 > parent->conn[ic].coordMax)
		{
			//move to the next connected component
			ic++;
			//if this is the last connected component in the column
			if(ic == loc1D.Value().toConn + loc1D.Value().numConn)
				loc1D++;
			//if there are no more connected components
			if(ic == parent->conn.size())
			{
				//we're at the end, return end
				(*this) = parent->end();
				return;
			}
			x2 = parent->conn[ic].coordMin;
		}
	}


	//boolean operators for comparing iterators
	bool operator==(iterator rhs)
	{
		if(parent == rhs.parent && iv == rhs.iv)
			return true;
		return false;
	}
	bool operator!=(iterator rhs){return !((*this) == rhs);}

	friend bool operator<(iterator &left, iterator &right)
	{
		if(left.iv < right.iv)
			return true;
		return false;
	}
	friend bool operator<=(iterator &left, iterator &right)
	{
		if(left.iv <= right.iv)
			return true;
		return false;
	}
	void operator++(){increment();}
	void increment_until(int p1, int p2)
	{
		while((*this) != parent->end())
		{
			if(X1() > p1)
				return;
			else if(X1() == p1 && X2() >= p2)
				return;

			increment();
		}
	}
};

/********STENCIL ITERATOR*****************/
template<typename T>
class rtsDTGrid2D<T>::stencil_iterator : public iterator
{
private:
	//list of iterators that make up the template
	vector<iterator> iterator_list;
	//iterator positions (relative to the position of the stencil iterator)
	vector<Coord2D> position_list;
	//list containing the values for each position in the stencil
	vector<T> value_list;

	void refresh_iterators();
	void set_values();
	void increment_all();

public:
	typename rtsDTGrid2D<T>::stencil_iterator operator=(const iterator rhs);
	void addPosition(int p1, int p2);
	void increment();
	void operator++()
	{
		increment();
	}
	T getValue(int id){return value_list[id];}
	bool exists(int id);
	
};

template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::increment_all()
{
	//run through each iterator and increment to the correct position
	int i;
	Coord2D dest;
	for(i=0; i<iterator_list.size(); i++)
	{
		//determine the appropriate position for the iterator
		dest.x1 = X1() + position_list[i].x1;
		dest.x2 = X2() + position_list[i].x2;
		//iterate until that position is reached
		iterator_list[i].increment_until(dest.x1, dest.x2);
	}
	set_values();

}

template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::increment()
{
	//increment the current position
	rtsDTGrid2D<T>::iterator::increment();

	increment_all();
}

template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::refresh_iterators()
{
	//make sure that the iterator position has been set
	if(parent == NULL)
	{
		cout<<"Iterator location not set."<<endl;
		return;
	}
	
	//initialize all of the other iterators
	int i;
	for(i=0; i<iterator_list.size(); i++)
	{
		//for each iterator, set the iterator to the beginning of the grid
		//iterator_list[i] = parent->begin();
		iterator_list[i] = parent->randomIterator(X1() + position_list[i].x1,
												  X2() + position_list[i].x2);
	}
	//increment_all();
	//set the values for all of the iterators
	set_values();
}

template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::set_values()
{
	int i;
	Coord2D dest;
	for(i=0; i<iterator_list.size(); i++)
	{
		//determine the appropriate position for the iterator
		dest.x1 = X1() + position_list[i].x1;
		dest.x2 = X2() + position_list[i].x2;
		//now add the value to the value list
		if(iterator_list[i].X1() == dest.x1 && iterator_list[i].X2() == dest.x2)
			value_list[i] = iterator_list[i].Value();
		else
			value_list[i] = parent->background;
	}


}

template<typename T>
typename rtsDTGrid2D<T>::stencil_iterator rtsDTGrid2D<T>::stencil_iterator::operator=(const iterator rhs)
{
	parent = rhs.parent;
	loc1D = rhs.loc1D;
	iv = rhs.iv;
	ic = rhs.ic;
	x2 = rhs.x2;

	refresh_iterators();

	return (*this);
}

template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::addPosition(int p1, int p2)
{
	//add a position to the position list and add a new iterator to the iterator list
	Coord2D p;
	p.x1 = p1;
	p.x2 = p2;
	position_list.push_back(p);
	rtsDTGrid2D<T>::iterator new_iter;


	iterator_list.push_back(new_iter);
	T empty;
	value_list.push_back(empty);
}

template<typename T>
bool rtsDTGrid2D<T>::stencil_iterator::exists(int id)
{
	int i;
	Coord2D dest;

	//determine the appropriate position for the iterator
	dest.x1 = X1() + position_list[id].x1;
	dest.x2 = X2() + position_list[id].x2;
	//now add the value to the value list
	if(iterator_list[id].X1() == dest.x1 && iterator_list[id].X2() == dest.x2)
		return true;
	else
		return false;
	
}

/**************ITERATOR METHODS IN DT GRID*******************/
template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::begin()
{
	//if the grid is empty, return an iterator to "after"
	if(value.size() == 0)
		return after();

	iterator result;
	result.parent = this;
	result.ic = 0;
	result.iv = 0;
	result.x2 = conn[0].coordMin;
	result.loc1D = proj1D.begin();

	return result;
}
template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::before()
{
	if(value.size() == 0)
		return after();

	iterator result;
	result.parent = this;
	result.ic = 0;
	result.iv = -1;
	//result.x2 = conn[0].coordMin;
	result.loc1D = proj1D.before();

	return result;
}

template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::end()
{
	//if the grid is empty, return after()
	if(value.size() == 0)
		return after();
	iterator result;
	result.parent = this;
	result.ic = conn.size() - 1;
	result.iv = value.size() - 1;
	result.x2 = conn[result.ic].coordMax;
	result.loc1D = proj1D.end();
	return result;
}

template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::randomIterator(int x1, int x2)
{
	rtsDTGrid2D<T>::iterator result;
	result.parent = this;

	//perform the random search
	int v_i, c_i;
	rtsDTGrid1D<IndexPair>::iterator iter1D;

	//if the value exists in the grid, create the iterator and return
	if(randomIndex(iter1D, v_i, c_i, x1, x2))
	{
		result.loc1D = iter1D;
		result.iv = v_i;
		result.ic = c_i;
		int offset = v_i - conn[c_i].toValue;
		result.x2 = conn[c_i].coordMin + offset;
	}
	//if the value doesn't exist
	else
	{
		//if the 1D iterator is at the end of the grid, return after()
		if(iter1D == proj1D.after())
			return after();
		
		//if the value lies before the current column
		if(x1 < iter1D.X1() || (x1 == iter1D.X1() && x2 < conn[c_i].coordMin) )
		{
			result.ic = c_i;
		}
		//else if the value lies after the current column
		else
		{
			//increment the 1D iterator
			iter1D++;
			//if this is the last connected component
			if(c_i >= conn.size() - 1)
				return after();
			else
			{
				c_i++;
				result.ic = c_i;
			}
		}
		

		result.loc1D = iter1D;
		result.iv = conn[c_i].toValue;
		result.x2 = conn[c_i].coordMin;
	}
	return result;


}
template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::after()
{
	iterator result;
	result.parent = this;
	result.ic = conn.size() - 1;
	result.iv = value.size();
	//result.x2 = conn[result.ic].coordMax;
	result.loc1D = proj1D.after();
	return result;
}

/**************DT GRID**************************/
template<typename T>
bool rtsDTGrid2D<T>::push(int x1, int x2, T v)
{
	//run this code if we have to start a new column in X1.  This happens when:
	//(a) we have just inserted the first value into the grid
	//(b) the value of x1 is greater than the last value of x1	
	if(grid_insertion_started == false || x1 != proj1D.getMaxX1())
	{
		//assume that a new column is being created
		//create the column in proj1D
		IndexPair newPair;
		newPair.toConn = conn.size();
		//newPair.toValue = value.size();
		newPair.numConn = 0;

		//if this insertion throws an error, the value was inserted incorrectly
		//the error will get thrown by DTGrid1D, so just return
		if(!proj1D.push(x1, newPair))
		{
			cout<<"Out-of-order insertion in D = 2: X1 = "<<x1<<" X2 = "<<x2<<endl;
			return false;
		}

		column_insertion_started = false;
		grid_insertion_started = true;
	}
	//If there is no new column, we still have to check to make sure the value is inserted
	//in the correct order in X2:
	else
	{
		if(column_insertion_started && x2 <= max_coord)
		{
			cout<<"Out-of-order insertion in D = 2: X1 = "<<x1<<" X2 = "<<x2<<endl;
			return false;
		}
	}
	

	//run this code if we have to start a new connected component.  This happens when:
	//(a) We insert the first value into the column
	//(b) There is empty space between the last insertion and this one
	if(column_insertion_started == false || x2 > (max_coord + 1))
	{
		//start a new connected component
		ConnectedComponent new_conn;
		new_conn.toValue = value.size();
		new_conn.coordMin = x2;
		new_conn.coordMax = x2;
		conn.push_back(new_conn);
		//increment the number of connected components for the column in X1
		proj1D.back().numConn++;
		column_insertion_started = true;
	}

	//insert the value into the grid:
	//(a) Insert the value at the end of the coord array
	//(b) Increment the coordMax value of the current connected component
	//(c) Change the maximum inserted coordinate to the new value
	value.push_back(v);
	conn[conn.size() - 1].coordMax = x2;
	//change max_coord to the new coordinate
	max_coord = x2;
	return true;
}

template<typename T>
bool rtsDTGrid2D<T>::randomIndex(rtsDTGrid1D<IndexPair>::iterator &iter1D, int &v_i, int &c_i, int x1, int x2)
{
	//search along the first dimension
	//get an iterator
	iter1D = proj1D.randomIterator(x1);

	//if the after() iterator is returned, exit
	if(iter1D == proj1D.after())
	{
		c_i = conn.size();
		v_i = value.size();
		return false;
	}

	IndexPair i = iter1D.Value();

	//if the 1D column does not exist
	if(iter1D.X1() != x1)
	{
		//get the appropriate values from the 1D iterator
		//(which points to the next valid column)
		c_i = i.toConn;
		v_i = conn[c_i].toValue;
		return false;
	}
	

	int high, low, mid;
	low = i.toConn;
	high = i.toConn + i.numConn - 1;

	do
	{
		mid = low + (high - low)/2;
		if(x2 > conn[mid].coordMax)
			low = mid + 1;
		else if(x2 < conn[mid].coordMin)
			high = mid - 1;
		else break;
	}
	while(low <= high);

	//at this point, mid is either at the appropriate connected component,
	//or x2 is not in the grid
	if(x2 >= conn[mid].coordMin && x2 <= conn[mid].coordMax)
	{
		int offset = x2 - conn[mid].coordMin;
		c_i = mid;
		v_i = conn[mid].toValue + offset;
		return true;
	}
	else
	{
		c_i = mid;
		v_i = conn[c_i].toValue;
		return false;
	}
}

template<typename T>
T rtsDTGrid2D<T>::random(int x1, int x2)
{
	int v_i, c_i;
	rtsDTGrid1D<IndexPair>::iterator iter1D;
	if(randomIndex(iter1D, v_i, c_i, x1, x2))
		return value[v_i];
	else
		return background;
}

template<typename T>
T& rtsDTGrid2D<T>::back()
{
	return value[value.size()-1];
}

template<typename T>
void rtsDTGrid2D<T>::dilate(int H)
{
	//if the grid is empty, return unchanged
	if(value.size() == 0)
		return;

	ColumnUnion CUqueue;
	CUqueue.ConnectToGrid(&conn);


	//dilate the N-1 DT-Grid constituent
	rtsDTGrid1D<IndexPair> dilated_proj1D = proj1D;
	
	//an empty pair has a number of connected components equal to zero
	//this should not happen in reality and can therefore be used to check for new columns
	IndexPair empty_pair;
	empty_pair.numConn = 0;

	//set the background node to the empty node and dilate the 1D projection
	dilated_proj1D.background = empty_pair;
	dilated_proj1D.dilate(H);

	//create a new DT Grid that will replace this one
	rtsDTGrid2D<T> new_grid;
	new_grid.proj1D = dilated_proj1D;
	new_grid.proj1D.background.toConn = -1;

	//create iteratorDilate that iterates along the dilated N-1 grid
	rtsDTGrid1D<IndexPair>::stencil_iterator iteratorDilate;
	iteratorDilate.addPosition(-H);
	iteratorDilate.addPosition(H);

	//create an iterator to set the new proj1D values
	rtsDTGrid1D<IndexPair>::iterator iteratorNew;


	//variables for each iteration
	IndexPair new_pair;
	vector<ConnectedComponent>::iterator ccIterator;
	unsigned int numValues = 0;
	for(iteratorNew = new_grid.proj1D.begin(),
		iteratorDilate = dilated_proj1D.begin();
		iteratorDilate != dilated_proj1D.after();
		iteratorNew++,
		iteratorDilate++)
		{
			//cout<<"1D position: "<<iteratorNew.X1()<<endl;
			//if a column is entering the stencil
			if(iteratorDilate.getValue(1).numConn)
				CUqueue.InsertColumn(iteratorDilate.getValue(1));
			
			//compute the union of all columns in the queue
			vector<ConnectedComponent> result = CUqueue.ComputeUnion(H);

			//compute the new IndexPair representing the column
			new_pair.toConn = new_grid.conn.size();
			new_pair.numConn = result.size();
			//store the index pair
			iteratorNew.SetValue(new_pair);

			//insert each of the connected components
			for(ccIterator = result.begin(); ccIterator!=result.end(); ccIterator++)
			{
				new_grid.conn.push_back(*ccIterator);
				new_grid.conn.back().toValue = numValues;
				numValues += (*ccIterator).coordMax - (*ccIterator).coordMin + 1;
			}

			//if a column is leaving the stencil
			if(iteratorDilate.getValue(0).numConn)
				CUqueue.RemoveColumn();
		}

	//allocate space for the new value array
	new_grid.value.resize(numValues, background);

	//copy the data from this grid into the new grid
	new_grid.insert(*this);

	//replace this grid with the new grid
	conn = new_grid.conn;
	value = new_grid.value;
	proj1D = new_grid.proj1D;

	
}

template<typename T>
void rtsDTGrid2D<T>::insert(rtsDTGrid2D<T> toInsert)
{
	//create source and destination iterators
	rtsDTGrid2D<T>::iterator source = toInsert.begin();
	rtsDTGrid2D<T>::iterator dest = begin();

	for(source = toInsert.begin(); source != toInsert.after(); source++)
	{
		//move the destination iterator to the current source position
		dest.increment_until(source.X1(), source.X2());
		//cout<<"source: "<<source.X1()<<" "<<source.X2()<<": "<<source.Value()<<endl;
		//cout<<"dest: "<<dest.X1()<<" "<<dest.X2()<<": "<<dest.Value()<<endl;
		//if the position exists in dest
		if(dest.X1() == source.X1() && dest.X2() == source.X2())
			dest.SetValue(source.Value());
		//cout<<"dest: "<<dest.X1()<<" "<<dest.X2()<<": "<<dest.Value()<<endl;
	}

}

template<typename T>
void rtsDTGrid2D<T>::getBounds(int &min_x1, int &min_x2, int &max_x1, int &max_x2)
{
	//if the grid is empty, return an empty bounding volume
	if(value.size() == 0)
	{
		min_x1 = min_x2 = max_x1 = max_x2 = 0;
		return;
	}

	//get the min and max values for the 1D grid (x1 coordinate)
	proj1D.getBounds(min_x1, max_x1);

	//initialize the min and max values
	min_x2 = conn[0].coordMin;
	max_x2 = conn.back().coordMax;

	//iterate through all columns finding the smallest and largest coordinate values
	rtsDTGrid1D<IndexPair>::iterator i;
	IndexPair col;
	for(i=proj1D.begin(); i!=proj1D.after(); i++)
	{
		col = i.Value();
		if(conn[col.toConn].coordMin < min_x2)
			min_x2 = conn[col.toConn].coordMin;
		if(conn[col.toConn + col.numConn - 1].coordMax > max_x2)
			max_x2 = conn[col.toConn + col.numConn - 1].coordMax;
	}
		

}
template<typename T>
void rtsDTGrid2D<T>::operator =(T rhs)
{
	for(int i=0; i<value.size(); i++)
		value[i] = rhs;
}


template<typename T>
void rtsDTGrid2D<T>::dumpValue()
{
	for(int i=0; i<value.size(); i++)
		cout<<value[i]<<endl;
}

template<typename T>
void rtsDTGrid2D<T>::dumpConn()
{
	for(int i=0; i<conn.size(); i++)
		cout<<conn[i].toValue<<","<<conn[i].coordMin<<","<<conn[i].coordMax<<endl;


}

#endif