package net.beadsproject.touch.surface;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import net.beadsproject.touch.old.VoronoiSurface;
import net.beadsproject.touch.old.VoronoiSurface.PNPnt;
import net.beadsproject.touch.perform.PerformNode;
import net.beadsproject.touch.perform.PerformTree;


/**
 * Factory for generating surfaces.
 * 
 * @author ben
 */
public class SurfaceGenerator {

	
	/**
	 * Generates a voronoi surface using a uniform distribution of nodes from the perform tree.
	 * 
	 * @param pt
	 * @return
	 */
	static public VoronoiSurfaceTwo UniformVoronoiTwo(PerformTree pt)
	{
		VoronoiSurfaceTwo vs = new VoronoiSurfaceTwo();
		if (pt==null || pt.getRoot()==null) return vs;
		PerformNode root = pt.getRoot();
		
		// first randomly scatter all the points uniformly
		RV_addPNAndChildrenWithParentTwo(vs,root);
		vs.buildVoronoi();		
		return vs;
	}	
	
	static public void findBetterConfiguration(float energy, int numiters, VoronoiSurfaceTwo vs)
	{
		ArrayList<VoronoiSurfaceTwo.PNPnt> points = new ArrayList<VoronoiSurfaceTwo.PNPnt>(vs.getPoints());
		Random r = new Random();
		for(int i=0;i<numiters;i++)
		{
			VoronoiSurfaceTwo.PNPnt a = points.get(r.nextInt(points.size()));
			VoronoiSurfaceTwo.PNPnt b = points.get(r.nextInt(points.size()));
			VoronoiSurfaceTwo.PNPnt c = points.get(r.nextInt(points.size()));
			if (a==b || a==c || b==c) continue;
						
			// else, compute treedist
			PerformNode pa = a.pn();
			PerformNode pb = b.pn();
			PerformNode pc = c.pn();
			
			// get the dist from c to a and b and swap it with the one that brings it closer
			int ab = PerformNode.getTreeDistance(pa,pb);
			int ac = PerformNode.getTreeDistance(pc,pb);
			float abdist = (float) VoronoiSurfaceTwo.sqdistance(a,b);
			float bcdist = (float) VoronoiSurfaceTwo.sqdistance(b,c);
	
			//System.out.printf("%d %d\n",ab,ac);
			
			if (bcdist<abdist && ab<ac) // || (!swapCloser && ab >= ac)) 
			{
				if (Math.random() < energy && Math.random()*energy>abdist)
				{
					vs.swapPoints(a, c);
				}
			}
		}		
	}
	
	/**
	 * Generates a voronoi surface using a uniform distribution of nodes from the perform tree.
	 * 
	 * @param pt
	 * @return
	 */
	static public VoronoiSurface UniformVoronoi(PerformTree pt)
	{
		VoronoiSurface vs = new VoronoiSurface();
		if (pt==null || pt.getRoot()==null) return vs;
		PerformNode root = pt.getRoot();
		
		// first randomly scatter all the points uniformly
		RV_addPNAndChildrenWithParent(vs,root);
		
		/*
		 * define treedist(a,b) = numnodesbetween(a,c)+numnodesbetween(b,c) where c is the common ancestor of a and b
		 * 
		 * special cases of this:
		 * treedist(a,a) = 0
		 * treedist(a,sibling of a) = 2
		 * treedist(a,direct parent of a) = 1
		 */
		
		/*
		 * algorithm 1.
		 * pick a point, a
		 * pick another point b,
		 * find the N nearest neighbours to b N(b)
		 * forall n in N(b):
		 *   if treedist(a,b) < treedist(a,n): swap(a,n) and break the loop
		 */
		
		/*
		 * algorithm 2. (rougher, quicker)
		 * pick a point, a
		 * pick a point, b
		 * pick a 3rd point, c
		 * if treedist(a,b)<treedist(a,c) then swap a and c
		 */
		
		final int NUM_ITERATIONS = 100*vs.numPoints()*vs.numPoints();
		ArrayList<VoronoiSurface.PNPnt> points = new ArrayList<VoronoiSurface.PNPnt>(vs.getPoints());
		Random r = new Random();
		for(int i=0;i<NUM_ITERATIONS;i++)
		{
			VoronoiSurface.PNPnt a = points.get(r.nextInt(points.size()));
			VoronoiSurface.PNPnt b = points.get(r.nextInt(points.size()));
			VoronoiSurface.PNPnt c = points.get(r.nextInt(points.size()));
			if (a==b || a==c || b==c) continue;
						
			// else, compute treedist
			PerformNode pa = a.pn();
			PerformNode pb = b.pn();
			PerformNode pc = c.pn();
			
			// get the dist from c to a and b and swap it with the one that brings it closer
			int ab = PerformNode.getTreeDistance(pa,pb);
			int ac = PerformNode.getTreeDistance(pc,pb);
			
			if (ab < ac) 
			{
				// swap the perform nodes
				a.pn = pc;
				c.pn = pa;
			}
		}
		
		return vs;
	}	
	
	static public VoronoiSurface RandomVoronoi(PerformTree pt)
	{
		VoronoiSurface vs = new VoronoiSurface();
		if (pt==null || pt.getRoot()==null) return vs;
		PerformNode root = pt.getRoot();
		RV_addPNAndChildren(vs,root);		
		return vs;		
	}
	
	static public VoronoiSurface BasicRecursiveVoronoi(PerformTree pt)
	{
		VoronoiSurface vs = new VoronoiSurface();
		if (pt==null) return vs;		
		PerformNode root = pt.getRoot();
		if (root==null) return vs;
		BRV_addPNAndChildren(vs,root,.5f,.5f,.5f);
		//vs.buildPointsAndTheirPolys();
		return vs;
	}

	static public CircleSurface RandomCircles(PerformTree pt)
	{
		CircleSurface cs = new CircleSurface();
		if (pt==null || pt.getRoot()==null) return cs;
		PerformNode root = pt.getRoot();
		RC_addPNAndChildren(cs,root);		
		return cs;
	}

	static public CircleSurface BasicRecursiveCircles(PerformTree pt) 
	{
		CircleSurface cs = new CircleSurface();
		if (pt==null) return cs;		
		// generate a circle surface given a perform tree
		PerformNode root = pt.getRoot();
		if (root==null) return cs;
	
		CircleSurface.Circle rootC = new CircleSurface.Circle(.5,.5,.5,root,0);
		cs.addCircle(rootC);
		SurfaceGenerator.BRC_addPNChildren(cs,root,rootC,0);
		return cs;
	}

	static private void BRV_addPNAndChildren(VoronoiSurface vs, PerformNode pn, double x, double y, double r)
	{
		List<PerformNode> children = pn.getChildren();
		int num = children.size();
		// add self 
		vs.addPerformNode(pn,x,y);
		if (num==0)
		{
	
		}
		if (num==1)
		{
			// add sole child just above it
			PerformNode child = children.get(0);
			BRV_addPNAndChildren(vs, child, x, y+r/2, (float) (r*0.8));
		}
		else
		{
			// distribute the circles equally around the center
			double dtheta = 2.0*Math.PI/num;
			double theta = 0;
			double distFromCenter = r * .5;
	
			// compute the maximum radius the subcircles can be
			double radius = Math.min(r-distFromCenter,distFromCenter*Math.sin(dtheta/2));
			for(PerformNode child: children)
			{
				double cx = distFromCenter*Math.cos(theta) + x;
				double cy = distFromCenter*Math.sin(theta) + y;
				theta += dtheta;	
	
				BRV_addPNAndChildren(vs,child, cx, cy, radius);				
			}			
		}		
	}
	
	static private void RV_addPNAndChildren(VoronoiSurface vs, PerformNode pn)
	{
		if (pn.getChildren().isEmpty())
		{
			// add this node
			double x = Math.random();
			double y = Math.random();
			vs.addPerformNode(pn,x,y);
		}
		else
		{
			// add all the children
			for(PerformNode child: pn.getChildren())
			{
				RV_addPNAndChildren(vs,child);
			}
		}
	}
	
	static private void RV_addPNAndChildrenWithParent(VoronoiSurface vs, PerformNode pn)
	{
		// add this node
		double x = Math.random();
		double y = Math.random();
		vs.addPerformNode(pn,x,y);
		
		// add all the children
		for(PerformNode child: pn.getChildren())
		{
			RV_addPNAndChildrenWithParent(vs,child);
		}
	}
	
	static private void RV_addPNAndChildrenWithParentTwo(VoronoiSurfaceTwo vs, PerformNode pn)
	{
		// add this node
		float x = (float) Math.random();
		float y = (float) Math.random();
		vs.addPerformNode(pn,x,y);
		
		// add all the children
		for(PerformNode child: pn.getChildren())
		{
			RV_addPNAndChildrenWithParentTwo(vs,child);
		}
	}

	static private void RC_addPNAndChildren(CircleSurface cs, PerformNode pn)
	{
		if (pn.getChildren().isEmpty())
		{
			// add this node
			double r = 0.2;
			while(true)
			{
				double x = Math.random();
				double y = Math.random();
				CircleSurface.Circle ctry = new CircleSurface.Circle(x,y,r,pn,0);
				boolean fine = true;
				for(CircleSurface.Circle circ: cs.circles)
				{
					if (CircleSurface.Circle.overlaps(circ,ctry))
					{
						fine = false;
						break;
					}					
				}

				if (fine)
				{
					cs.addCircle(ctry);
					break;
				}
				else
					r = Math.max(r*.9, 0.001);
			}
		}
		else
		{
			// add all the children
			for(PerformNode child: pn.getChildren())
			{
				RC_addPNAndChildren(cs,child);
			}
		}
	}


	static private void BRC_addPNChildren(CircleSurface cs, PerformNode pn, CircleSurface.Circle c, int depth)
	{
		List<PerformNode> children = pn.getChildren();
		int num = children.size();
		if (num==0) return;
		if (num==1)
		{
			PerformNode child = children.get(0);
			CircleSurface.Circle childc = new CircleSurface.Circle(c.x,c.y,c.r*0.75,child,depth+1);
			cs.addCircle(childc);
			BRC_addPNChildren(cs, child,childc,depth+1);
		}
		else
		{
			// distribute the circles equally around the center
			double dtheta = 2.0*Math.PI/num;
			double theta = 0;
			double distFromCenter = c.r * .5;

			// compute the maximum radius the subcircles can be
			double radius = Math.min(c.r-distFromCenter,distFromCenter*Math.sin(dtheta/2));			
			for(PerformNode child: children)
			{
				double x = distFromCenter*Math.cos(theta) + c.x;
				double y = distFromCenter*Math.sin(theta) + c.y;
				theta += dtheta;

				CircleSurface.Circle childc = new CircleSurface.Circle(x,y,radius,child,depth+1);
				cs.addCircle(childc);
				BRC_addPNChildren(cs,child,childc,depth+1);				
			}			
		}

	}

}