package clothSimulator;

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

import annas.graph.UndirectedGraph;

/**
 * The constraint graph
 * @author ben
 */
public class ConstraintGraph {
	
	/** The graph */
	public List<ConstraintGraphNode> theNodeList= new LinkedList<ConstraintGraphNode>();
	
	
	/** here we use the annas package to have many graph methods.  theGraph is the construction of a graph where we have stated that
	 * the nodes are particles and the edges are constraints...now isn't that nice.  To use this we just had to say that Constraints class extends
	 * the arc class
	 */
	public UndirectedGraph<Particle, Constraint> theAnnasGraph= new UndirectedGraph<Particle, Constraint>();
	
	
	/** an empty constructor */
	public ConstraintGraph(){
		//do nothing
	}
	
	/** 
	 * Builds the graphs from a constraint list and a aparticle list 
	 * @param theCList 
	 * @param theParticles */
	public ConstraintGraph(ConstraintList theCList, List<Particle> theParticles){
		//upon calling the constructor, we build the graph
		buildNodeList(theCList, theParticles);
		setNeighbours(theCList, this);
		buildEdgeList(theCList);
	}
	
	/** this builds the edge list*/
	private void buildEdgeList(@SuppressWarnings("unused") ConstraintList theCList){
		// do nothing
	}
	
	
	ConstraintGraphNode tempNode;
	/** just puts the particles into a node list*/
	private void buildNodeList(ConstraintList theCList,  List<Particle> theParticles){
		for(Particle p: theParticles){
			tempNode=new ConstraintGraphNode(p, theCList);
			theNodeList.add(tempNode);
			p.CGraphIndex=theNodeList.indexOf(tempNode);
		}

	}
	
	/** sets the neighbours of each node in the node list*/
	private void setNeighbours(ConstraintList theCList,ConstraintGraph theGraph){
		for(ConstraintGraphNode n1: theGraph.theNodeList){
			for(int constLoc: n1.CListLocations){
				for(Particle p1: theCList.theConstraints.get(constLoc).ParticleList()){
					if(p1!=n1.p && !n1.neighbours.contains(theNodeList.get(n1.p.CGraphIndex))){
						n1.neighbours.add(theNodeList.get(p1.CGraphIndex));
					}
				}
			}
		}
	}
	

	/** to execute Prim's algorithm, we use a priority queue */
	private PriorityQueue<ConstraintGraphNode> theQueue;
	/** which requires a comparator*/
	private ConstraintEdgeComparator theComparator;
	private int theQueueCapacity;
	/** the root node */
	public ConstraintGraphNode root;
	//we may in the future, want to create an MST as an actual MST object rather than as a ConstrGrph.  
//	private ConstraintGraph theMST;
	
	/**
	 * Computes the minimum spanning tree using Prim's algorithm
	 * it is an implementation of Prim's algorithm
	 * @param rootParticle 
	 * @param theCList 
	 */
	public void mstByPrim(Particle rootParticle, ConstraintList theCList){
	    ConstraintGraphNode u = null;
		//take in a particle and use it to find that node which refers to that particle
		for(ConstraintGraphNode n: this.theNodeList){
			if(n.p==rootParticle){
				root=n;
				break;
			}
		}
		//we may in the future, want to create an MST as an actual MST object rather than as a ConstrGrph.  
		//theMST=new ConstraintGraph();
		theQueueCapacity = theNodeList.size();
		theComparator = new ConstraintEdgeComparator();
		theQueue = new PriorityQueue<ConstraintGraphNode>(theQueueCapacity, theComparator);
		for (ConstraintGraphNode cGN: theNodeList){
			cGN.primKey = Double.POSITIVE_INFINITY;
			if ( cGN == root ) cGN.primKey = 0D;
			cGN.parent = null;
			cGN.children = new LinkedList<ConstraintGraphNode>();
			theQueue.add( cGN );
			cGN.isInQ = true;
		}
//		root.primKey = 0D;
//		theQueue.remove(root);
//		theQueue.add(root);
		
		while ( !theQueue.isEmpty() ){
			//we may in the future, want to create an MST as an actual MST object rather than as a ConstrGrph.  To do that, we need
			//to create an tree
			u = theQueue.poll();
			u.isInQ = false;
			for ( ConstraintGraphNode v : u.neighbours ) {
				//next we return the weight which is the negative of the constraint value between u and v
			    // PGK: is this expensive???
				double wUV = v.getSharedConstraintValue(u, theCList);
				if ( v.isInQ && wUV < v.primKey ){
					if ( v.parent != null ){
						//sometimes the parent relation gets changed so we have to clear out the children
						v.parent.children.remove(v);
					}
					v.parent = u;
					//child cannot be a single node, it has to be a list 
					u.children.add(v);					
					theQueue.remove(v);
					v.primKey = (Double)wUV;
					theQueue.add(v);
				}
			}
		}		
//		theMST.parentsToNeighbours();
//		return theMST;
	}
	


	


	/**this method takes a larval MST with no neighbours, just parents and then builds the neighbour list */
	@SuppressWarnings("unused")
    private void parentsToNeighbours(){
		for(ConstraintGraphNode n: this.theNodeList){
			if(n!=root){
				// get the parent and turn it into a neighbour for n and a neighbour for the parent
				n.neighbours.add(n.parent);
				n.parent.neighbours.add(n);
			}

		}
	}

	
	/** 
	 * this method takes a constraint list correspondng to a Kruskal tree, and reconstructs the tree on the bigGraph 
	 * @param kTree 
	 */	
	public void graphFromKruskal(List<Constraint> kTree){
		
		//find the root in the constraint list
		for(Constraint c: kTree){
			for(Particle p: c.ParticleList()){
				if(p==root.p){
					//set the parents and children
					this.root.children.add(nodeFromParticle(p));
					traverseCLTree(c, kTree);
				}
			}
		}
		
	}
	
	/** 
	 * @param thePart 
	 * @return the node in the graph corresponding to the given particle 
	 */
	public ConstraintGraphNode nodeFromParticle(Particle thePart){
		for(ConstraintGraphNode cgn: this.theNodeList){
			if(cgn.p==thePart){
				return cgn;
			}
		}
		return null;
	}
	
	/** a recursive method to traverse the Kruskal tree */
	private void traverseCLTree(@SuppressWarnings("unused") Constraint c, @SuppressWarnings("unused") List<Constraint>kTree){		
		// do nothing, just yet!  TODO: finish me...
	}
	
	
	
//	/**Here we take the prim MST and turn it into a list of constraints
//	 * @param theRoot
//	 * @param kruskalTree
//	 */
//	/** this is a helper method to make a constraint list out of the prim child relations.  It essentially
//	 * allows you to walk a graph depth first.
//	 */
//	ConstraintGraphNode nextNode;
//	ConstraintGraphNode currNode;
//	public List<Constraint> listFromPrim(ConstraintList theCList){
//		currNode=root;
//		while(currNode.children.size()!=0){
//			if(currNode.children.size()>1){
//				for(ConstraintGraphNode cgn: currNode.children){
//					cgn.nextDepthFirst();
//				}
//			}else{
//				for(int clListLoc: currNode.CListLocations){
//					if()
//				}
//			}
//		}
//		return nextNode;
//	}
	

}
