import java.io.Reader;
import java.io.Writer;
import java.util.Vector;
import java.util.Stack;
import java.io.IOException;


/**
 * Storage class for per-agent information neccessary to perform formation
 * morphing.
 */

public class MorphSpecStoredVals implements IMorphSpec 
{

	class SingleVal {
		public double [] m_arrLfUvFinal;
		public int m_nTopoLastVisit;
		public int m_nTopoFirstVisit;
		public int m_nTopoDepth;
		public int m_nTopoNumChildren;

		public boolean m_bVisited;
		public boolean m_bFinalized;

		public SingleVal() {
			m_bVisited = false;
			m_bFinalized = false;
			m_nTopoNumChildren = 0;
			m_arrLfUvFinal = new double[2];
		}
	}

	SingleVal m_arrVals[];



	class LocAndParent {
		public double [] m_arrLfLoc;
		public int m_nParent;


		public LocAndParent() {
			m_arrLfLoc = new double[2];
			m_nParent = -1;
		}

		public LocAndParent(double arrLfLoc[], int nParent) {
			m_arrLfLoc = new double[2];
			m_arrLfLoc[0] = arrLfLoc[0];
			m_arrLfLoc[1] = arrLfLoc[1];
			m_nParent = nParent;
		}

		public LocAndParent(LocAndParent src) {
			copyFrom(src);
		}

		public LocAndParent copyFrom(LocAndParent src) {
			m_arrLfLoc = new double[2];
			m_arrLfLoc[0] = src.m_arrLfLoc[0];
			m_arrLfLoc[1] = src.m_arrLfLoc[1];
			m_nParent = src.m_nParent;
			return this;
		}
	}

	LocAndParent m_arrIniVals[];
	
	int m_nMaxDepth;

	int m_nSetTo;

	boolean m_bVerbose;

	boolean m_bParentFrame;

	public MorphSpecStoredVals() {
		m_bParentFrame = false;
		m_bVerbose = false;
		m_arrVals = null;
		m_arrIniVals = null;
		setSize(10);
		m_nSetTo = 0;
	}

	public MorphSpecStoredVals(int nSize) {
		m_bParentFrame = false;
		m_bVerbose = false;
		m_arrVals = null;
		m_arrIniVals = null;
		setSize(nSize);
	}

    /**
     * Make this more then a stub later
     */
    public void dump(Writer writeTo) 
    {
    	for(int nNum = 0; nNum < m_arrVals.length; ++nNum) {
			Double objLfVal1 = new Double(m_arrVals[nNum].m_arrLfUvFinal[0]);
			Double objLfVal2 = new Double(m_arrVals[nNum].m_arrLfUvFinal[1]);
			try {
				writeTo.write(objLfVal1.toString() + "\t" + 
						objLfVal2.toString()+"\t(" + 
						m_arrVals[nNum].m_nTopoDepth +"," +
						m_arrVals[nNum].m_nTopoFirstVisit+","+
						m_arrVals[nNum].m_nTopoLastVisit+","
						+"\n");
			} catch (IOException e) {
				
			}
		}
    }
    
    /**
     * Make this more then a stub later
     */
    public void load(Reader readFrom) {
    }	
	
	/**
	 * Sets number of agents.
	 */
	 public void setSize(int nStartSize) {
		 m_nSetTo = 0;
		 m_arrIniVals = new LocAndParent[nStartSize];
	 }

	 void doubleIniValArr() {
		 LocAndParent arrNextVals[] = new LocAndParent[2*m_arrIniVals.length];
		 for(int i = 0; i < m_nSetTo; ++i) {
			 arrNextVals[i] = new LocAndParent(m_arrIniVals[i]);
		 }
		 m_arrIniVals = arrNextVals;
		 // garbage collection cleans up spare array
	 }

	 /**
	  * Adds an agent.  Doubles storage array if 
	  * neccessary
	  */
	 public void addAgent(double arrLfPos[], int nParent) {

		 if(m_arrIniVals.length-1 <= m_nSetTo) {
			 doubleIniValArr();
		 }
		 m_arrIniVals[m_nSetTo] = new LocAndParent(arrLfPos, nParent);
		 ++m_nSetTo;
	 }

	 /**
	  * Converts position and parent information into
	  * morph spec information.
	  */
	 public void convertVals() {
		 m_nMaxDepth = 0;
		 
		 m_arrVals = new SingleVal[m_nSetTo];
		 Vector<Vector<Integer> > adjList = 
			 new Vector<Vector<Integer> >(m_nSetTo);

		 for(int i = 0; i < m_nSetTo; ++i) {
			 adjList.add(i,new Vector<Integer>());
			 m_arrVals[i] = new SingleVal();
			 m_arrVals[i].m_bVisited = false;
		 }

		 for(int i = 0; i < m_nSetTo; ++i) {
			 adjList.get(m_arrIniVals[i].m_nParent).add(new Integer(i));
		 }

		 Stack<Integer> dfsStack = new Stack<Integer>();
		 dfsStack.push(new Integer(0));
		 int nCnt = 0;
		 int nDep = 0;
		 while(!dfsStack.empty()) {
			 Integer poppedVal = 
				 (Integer)dfsStack.pop();
			 if(m_bVerbose) {
				 System.out.println("Stack size == "+dfsStack.size());
				 System.out.println("Just popped "+poppedVal.intValue()+
						 "depth is "+nDep+", cnt is "+nCnt);
			 }
			 int nVal = poppedVal.intValue();
			 if(m_arrVals[nVal].m_bFinalized == true) 
			 {
				 if(m_bVerbose) {
					 System.out.println("Node is finalized\n");
				 }
			 } else if(m_arrVals[nVal].m_bVisited == true) 
			 {
				 m_arrVals[nVal].m_nTopoLastVisit = nCnt;
				 m_arrVals[nVal].m_bFinalized = true;
				 --nDep;

			 } else {
				 m_arrVals[nVal].m_bVisited = true;
				 m_arrVals[nVal].m_nTopoFirstVisit = nCnt;
				 m_arrVals[nVal].m_nTopoLastVisit = -1;
				 m_arrVals[nVal].m_nTopoDepth = nDep;
				 
				 if(nDep > m_nMaxDepth) {
					 m_nMaxDepth = nDep;
				 }
				 
				 dfsStack.push(new Integer(nVal));
				 ++nDep;
				 dfsStack.addAll(adjList.get(nVal));

				 if(m_bVerbose) {
					 System.out.println("Adding "+adjList.get(nVal).size()+
							 " items : Stack size is now "+
							 dfsStack.size());
					 System.out.println("Stack is "+dfsStack);
				 }

				 m_arrVals[nVal].m_nTopoNumChildren = 
					 adjList.get(nVal).size();

				 if(nVal == 0) {
					 m_arrVals[nVal].m_arrLfUvFinal[0] = 0.0;
					 m_arrVals[nVal].m_arrLfUvFinal[1] = 0.0;
				 } else {
					 if(m_bParentFrame == true) {
						 if(m_arrIniVals[nVal].m_nParent == 0) {
							 m_arrVals[nVal].m_arrLfUvFinal[0] = 
								 m_arrIniVals[nVal].m_arrLfLoc[0] - 
								 m_arrIniVals[0].m_arrLfLoc[0];
							 m_arrVals[nVal].m_arrLfUvFinal[1] = 
								 m_arrIniVals[nVal].m_arrLfLoc[1] - 
								 m_arrIniVals[0].m_arrLfLoc[1];
						 } else {
							 int nParent = m_arrIniVals[nVal].m_nParent;
							 int nPParent = m_arrIniVals[nParent].m_nParent;
							 double lfFrame[][] = new double[2][2];
							 lfFrame[0][0] = 
								 m_arrIniVals[nPParent].m_arrLfLoc[0] -
								 m_arrIniVals[nParent].m_arrLfLoc[0];
							 lfFrame[0][1] = 
								 m_arrIniVals[nPParent].m_arrLfLoc[1] -
								 m_arrIniVals[nParent].m_arrLfLoc[1];
							 double lfScale = 
								 Math.sqrt(lfFrame[0][0]*lfFrame[0][0]+
										 lfFrame[0][1]*lfFrame[0][1]
								 );
							 if(lfScale > 0.0) {
								 lfScale = 1.0/lfScale;
							 }
							 lfFrame[0][0] *= lfScale;
							 lfFrame[0][1] *= lfScale;
							 lfFrame[1][0] = lfFrame[0][1];
							 lfFrame[1][1] = -lfFrame[0][0];

							 double lfRelVec[] = new double[2];
							 lfRelVec[0] = 
								 m_arrIniVals[nVal].m_arrLfLoc[0] -
								 m_arrIniVals[nParent].m_arrLfLoc[0];

							 lfRelVec[1] = 
								 m_arrIniVals[nVal].m_arrLfLoc[1] -
								 m_arrIniVals[nParent].m_arrLfLoc[1];

							 m_arrVals[nVal].m_arrLfUvFinal[0] = 
								 lfRelVec[0]*lfFrame[0][0] +
								 lfRelVec[1]*lfFrame[0][1];

							 m_arrVals[nVal].m_arrLfUvFinal[1] = 
								 lfRelVec[0]*lfFrame[1][0] +
								 lfRelVec[1]*lfFrame[1][1];


						 } // if parent==0 else ...
					 } else {
						 m_arrVals[nVal].m_arrLfUvFinal[0] = 
							 m_arrIniVals[nVal].m_arrLfLoc[0];
						 m_arrVals[nVal].m_arrLfUvFinal[1] = 
							 m_arrIniVals[nVal].m_arrLfLoc[1];
					 } // if (m_bParentFrame == true) ... else
				 } // if val == 0 else ...

			 } // if lastVisit < firstVisit ... else ...
			 ++nCnt;
		 } // loop

	 } // function

	 public double [] getFinalUv(int nAgentId) {
		 return m_arrVals[nAgentId].m_arrLfUvFinal;
	 }

	 public int getTopoLastVisit(int nAgentId) {
		 return m_arrVals[nAgentId].m_nTopoLastVisit;
	 }

	 public int getTopoFirstVisit(int nAgentId) {
		 return m_arrVals[nAgentId].m_nTopoFirstVisit;
	 }

	 public int getTopoDepth(int nAgentId) {
		 return m_arrVals[nAgentId].m_nTopoDepth;
	 }

	 public int getNumChildren(int nAgentId) {
		 return m_arrVals[nAgentId].m_nTopoNumChildren;
	 }
	 
	 public int getMaxDepth() { return m_nMaxDepth; }
}