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

#ifndef _RTS_DTGRID1D_H
#define _RTS_DTGRID1D_H

struct ConnectedComponent
{
	int toValue;
	int coordMin;
	int coordMax;
};




template<typename T>
class rtsDTGrid1D
{
	
private:
	//main arrays
	vector<T> value;
	vector<ConnectedComponent> conn;

	//variables to keep track of insertion
	int max_coord;
	bool insertion_started;
	bool randomIndex(int &v, int &c, int x1);


public:
	T background;
	rtsDTGrid1D<T>()
	{
		insertion_started = false;
		max_coord = 0;
	}
	int getMaxX1(){return max_coord;}
	
	T random(int x1);
	T& back();
	bool push(int x1, T value);
	void insert(rtsDTGrid1D<T> toInsert);
	void getBounds(int &min_x1, int &max_x1);
	void dilate(int H);
	template<typename P> rtsDTGrid1D<P> getStorage()
	{
		//create the resulting grid
		rtsDTGrid1D<P> result;
		//create an iterator to run over the existing grid
		P* new_value = (P*)calloc(1, sizeof(P));		
		for(iterator i = begin(); i!=end(); i.increment())
		{
			result.push(i.X1(), *new_value);
		}
		return result;
		
	}
	void operator=(T rhs);
	void print();

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

};

/***************ITERATOR*************************/
template<typename T>
class rtsDTGrid1D<T>::iterator
{
	friend class rtsDTGrid1D;
	

protected:
	rtsDTGrid1D<T>* parent;
	int iv;
	int ic;
	int x1;

public:
	T Value(){return parent->value[iv];}
	int X1(){return x1;}
	void SetValue(T val){parent->value[iv] = val;}

	iterator(){parent = NULL;}

	void increment()
	{
		//increment the current coordinate and value
		x1++;
		iv++;
		//if we are outside of the current connected component
		if(x1 > parent->conn[ic].coordMax)
		{
			//if this is the last connected component, set the iterator to END and return
			if(ic == parent->conn.size() - 1)
			{
				(*this) = parent->after();
				return;
			}
			//otherwise move to the next connected component and update the coordinate
			ic++;
			x1 = 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 pos)
	{
		while(x1 < pos && (*this) != parent->after())
		{
			p();
		}
	}
};


/************STENCIL ITERATOR********************/
template<typename T>
class rtsDTGrid1D<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<int> 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 rtsDTGrid1D<T>::stencil_iterator operator=(const iterator rhs);
	void addPosition(int p);
	void operator++(){p();}
	void p();
	T getValue(int id){return value_list[id];}
	bool exists(int id);
	
};

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

}

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

	increment_all();
}

template<typename T>
void rtsDTGrid1D<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();
	}
	increment_all();
	//set the values for all of the iterators
	set_values();
}

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


}

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

	refresh_iterators();

	return (*this);
}

template<typename T>
void rtsDTGrid1D<T>::stencil_iterator::addPosition(int p)
{
	position_list.push_back(p);
	rtsDTGrid1D<T>::iterator new_iter;
	/*If the parent variable is valid (the current iterator is assigned to
	a grid), assign the position just added to the same grid.
	If the parent isn't set, all iterators are assigned to the appropriate grid
	later on when the operator= is used to assign the grid to the stencil.
	*/
	if(parent != NULL)
	{
		new_iter = parent->begin();
		refresh_iterators();
	}

	iterator_list.push_back(new_iter);
	value_list.resize(value_list.size() + 1);
}

template<typename T>
bool rtsDTGrid1D<T>::stencil_iterator::exists(int id)
{
	//returns true if the iterator defined by id points to an actual grid node
	
	//determine the appropriate position for the iterator
	int dest = x1 + position_list[id];

	if(iterator_list[id].X1() == dest)
		return true;
	else
		return false;

}


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

	iterator result;
	result.parent = this;
	result.ic = 0;
	result.iv = 0;
	result.x1 = conn[0].coordMin;
	return result;
}
template<typename T>
typename rtsDTGrid1D<T>::iterator rtsDTGrid1D<T>::before()
{
	//if the grid is empty, return after()
	if(value.size() == 0)
		return after();

	iterator result;
	result.parent = this;
	result.ic = 0;
	result.iv = -1;
	//result.x1 = conn[0].coordMin;
	return result;
}

template<typename T>
typename rtsDTGrid1D<T>::iterator rtsDTGrid1D<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.x1 = conn[result.ic].coordMax;
	return result;
}
template<typename T>
typename rtsDTGrid1D<T>::iterator rtsDTGrid1D<T>::after()
{
	iterator result;
	result.parent = this;
	result.ic = conn.size() - 1;
	result.iv = value.size();
	//result.x1 = conn[result.ic].coordMax;
	return result;
}




template<typename T>
typename rtsDTGrid1D<T>::iterator rtsDTGrid1D<T>::randomIterator(int x1)
{
	//if the grid is empty return a "after" iterator
	if(value.size() == 0)
		return after();

	rtsDTGrid1D<T>::iterator result;
	result.parent = this;
	int v_i, c_i;

	//if the value exists in the grid, create the iterator and return
	if(randomIndex(v_i, c_i, x1))
	{
		result.iv = v_i;
		result.ic = c_i;
		int offset = v_i - conn[c_i].toValue;
		result.x1 = conn[c_i].coordMin + offset;
	}
	//if the value doesn't exist
	else
	{
		//if the value lies before the current column
		if(x1 < conn[c_i].coordMin)
		{
			result.ic = c_i;

		}
		else
		{
			//if this is the last connected component
			if(c_i >= conn.size() - 1)
				return after();
			else
			{
				c_i++;
				result.ic = c_i;
			}
		}
		result.iv = conn[c_i].toValue;
		result.x1 = conn[c_i].coordMin;
	}
	return result;

}
template<typename T>
void rtsDTGrid1D<T>::print()
{
	rtsDTGrid1D<T>::iterator i;
	i = begin();
	while(i != after())
	{
		cout<<i.X1()<<":"<<i.Value()<<endl;
		i++;
	}
	

}

/**************DT GRID**************************/
template<typename T>
bool rtsDTGrid1D<T>::push(int x1, T v)
{
	//test to make sure the insertion is happening in the right order
	if(insertion_started && x1 <= max_coord)
	{
		cout<<"Out-of-order insertion in D = 1: X1 = "<<x1<<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 grid
	//(b) There is empty space between the last insertion and this one
	if(insertion_started == false || x1 > (max_coord + 1))
	{
		//start a new connected component
		ConnectedComponent new_conn;
		new_conn.toValue = value.size();
		new_conn.coordMin = x1;
		new_conn.coordMax = x1;
		conn.push_back(new_conn);
		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 = x1;
	//change max_coord to the new coordinate
	max_coord = x1;
	return true;
}

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

	while(source != toInsert.after())
	{
		//move the destination iterator to the current source position
		dest.increment_until(source.X1());
		//if the position exists in dest
		if(dest.X1() == source.X1())
			dest.SetValue(source.Value());
		source++;
	}

}

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

	//get the minimum and maximum coordinates
	min_x1 = conn[0].coordMin;
	max_x1 = conn.back().coordMax;
}
template<typename T>
void rtsDTGrid1D<T>::dilate(int H)
{
	//this function creates a new DT grid dilated by H and copies
	//the original grid into the new grid

	//create a new grid
	rtsDTGrid1D<T> new_grid;

	//determine the dilated values for the first connected component
	int numValues = 0;
	int start = conn[0].coordMin - H;
	int end = conn[0].coordMax + H;

	//run through each remaining connected component
	for(int i=1; i<conn.size(); i++)
	{
		//if the new component and the i'th ones overlap, combine them
		//cout<<conn[i].coordMin - H<<endl;
		if(conn[i].coordMin - H <= end)
			end = conn[i].coordMax + H;
		else
		{
			//store the dilated connected component
			ConnectedComponent cc;
			cc.coordMin = start;
			cc.coordMax = end;
			cc.toValue = numValues;
			numValues += end - start + 1;
			new_grid.conn.push_back(cc);

			//start a new dilated connected component
			start = conn[i].coordMin - H;
			end = conn[i].coordMax + H;
		}
	}
	//add the last dilated connected component
	ConnectedComponent cc;
	cc.coordMin = start;
	cc.coordMax = end;
	cc.toValue = numValues;
	numValues += end - start + 1;
	new_grid.conn.push_back(cc);
	//allocate space in the value array, fill it with the background value
	new_grid.value.resize(numValues, background);

	//insert this grid into the new one
	new_grid.insert(*this);
	
	//copy the new grid to this grid
	conn = new_grid.conn;
	value = new_grid.value;
}

template<typename T>
bool rtsDTGrid1D<T>::randomIndex(int &v, int &c, int x1)
{
	//if the grid is empty return false
	if(value.size() == 0)
		return false;

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

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

template<typename T>
void rtsDTGrid1D<T>::operator=(T rhs)
{
	for(int i=0; i<value.size(); i++)
		value[i] = rhs;
}
template<typename T>
T& rtsDTGrid1D<T>::back()
{
	return value[value.size()-1];
}

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


#endif