import java.awt.*;
import java.util.Vector;

class MMmdata {

    // unmodified source and data 
    protected MMdata source, target;
    protected MMdata current; 
    // between 0 and 100 percentage
    protected float percentage;
    // morphable normals (start, end, current angle fixed weight)
    protected MMmnormal[] mnormals;
    protected MMnormal[] sorted;
    protected float lambda, sigma;
    protected double maxWeightDiff;
    
    MMmdata (MMdata source, MMdata target, float lambda, float sigma) {

	this.lambda = lambda;
	this.sigma = sigma;
	// maximum weight difference between the two files
	this.maxWeightDiff = Math.max(source.getMaxweight()-target.getMinweight(), target.getMaxweight()-source.getMinweight());

	//maximum weight difference between two files, assumingn some weights are zero
//	maxWeightDiff = Math.max(source.getMaxweight(), target.getMaxweight());

	double[][] weights = new double[source.size()][target.size()];
	double[] sourceSum = new double[source.size()];
	double[] targetSum = new double[target.size()];

	mnormals = new MMmnormal[source.size()*target.size()]; 
	sorted = new MMnormal[source.size()*target.size()]; 
	this.source = source;
	this.target = target;

	// individual weights 
	for (int i = 0; i < source.size(); i++) 
	    for (int j = 0; j < target.size(); j++) {
		double dAngle = angleUnitDist(source.normalAt(i), target.normalAt(j));
		double dWeight = weightUnitDist(source.normalAt(i), target.normalAt(j));
		double thingToExp = - sigma*(lambda*angleUnitDist(source.normalAt(i), target.normalAt(j))+
					           weightUnitDist(source.normalAt(i), target.normalAt(j)));
		weights[i][j] = Math.exp(thingToExp);
		//		System.out.println("i = "+i+" j = "+j+" thingToExponentiate = "+thingToExp+" and weight = "+weights[i][j]);
	    }
	//	System.out.println("");

	// inverted source sums
	for (int i = 0; i < source.size(); i++) {
	    sourceSum[i] = 0;
	    for (int j=0; j < target.size(); j++) 
		sourceSum[i] += weights[i][j];
	    sourceSum[i] = 1/sourceSum[i];
	}
	
	// inverted target sums
	for (int j = 0; j < target.size(); j++) {
	    targetSum[j] = 0;
	    for (int i=0; i < source.size(); i++) 
		targetSum[j] += weights[i][j];
	    targetSum[j] = 1/targetSum[j];
	}
	
	// create all pairs (m*n of 'em)
	for (int i = 0; i < source.size(); i++) 
	    for (int j = 0; j  < target.size(); j++)
		mnormals[i*target.size()+j] = new MMmnormal(source.normalAt(i).multBy(weights[i][j] * sourceSum[i]), 
							    target.normalAt(j).multBy(weights[i][j] * targetSum[j]));
    }
    
    private double angleDist(MMnormal m, MMnormal n) {
	return ((m.getAngle()>n.getAngle())?Math.min(m.getAngle()-n.getAngle(), 2*Math.PI+n.getAngle()-m.getAngle()):
				  Math.min(n.getAngle()-m.getAngle(), 2*Math.PI+m.getAngle()-n.getAngle())); 
    }
    
    private double weightDist(MMnormal m, MMnormal n) {
	return (Math.abs(m.getWeight() - n.getWeight()));
    }

    private double angleUnitDist(MMnormal m, MMnormal n) {
	return ((m.getAngle()>n.getAngle())?Math.min(m.getAngle()-n.getAngle(), 2*Math.PI+n.getAngle()-m.getAngle()):
					    Math.min(n.getAngle()-m.getAngle(), 2*Math.PI+m.getAngle()-n.getAngle()))
		/ (Math.PI); // max angle difference is pi since we're going both ways
    }
    
    private double weightUnitDist(MMnormal m, MMnormal n) {
	return (Math.abs(m.getWeight() - n.getWeight()))
		/ maxWeightDiff;
    }

    private double weightAvg(MMnormal m, MMnormal n) {
	return (m.getWeight() + n.getWeight());
    }
    
    public MMdata morphAt(float percentage) {
	// first create the array to sort
	for (int i = 0; i < mnormals.length; i++) {
	    sorted[i] = mnormals[i].normalWhen(percentage);
//	    System.out.println (i+": angle = "+current.normalAt(i).getAngle()+" weight = "+current.normalAt(i).getWeight());
//	    System.out.println("Current current size is "+current.size());
//	    System.out.println(current.toString());
	} 

	// see what array looks like before sorting
//	System.out.println("Before sorting the array is: ");
//	for (int i = 0; i < sorted.length; i++) 
//	    System.out.println(i+": angle="+sorted[i].getAngle()+" weight="+sorted[i].getWeight()+" x="+sorted[i].x+" y="+sorted[i].y+" cosa="+sorted[i].getCosa()+" sina="+sorted[i].getSina());

	// quick sort by angle
	quickSort(0, sorted.length-1);

	// complain if any angle is smaller than the previous one
/*	float prev;
	if (sorted.length !=0) prev = sorted[0].getAngle();
	for (int i = 1; i < sorted.length; i++) {
	    System.out.println("Checked elements "+(i-1)+" and "+i);
	    if (prev > sorted[i].getAngle()) {
		System.out.println("ALERT!! Array is not really sorted: Check elements "+(i-1)+" and "+i); 
		for (int j = 0; j < sorted.length; j++) 
		    System.out.println(j+": angle="+sorted[j].getAngle()+" weight="+sorted[j].getWeight()+" x="+sorted[j].x+" y="+sorted[j].y+" cosa="+sorted[j].getCosa()+" sina="+sorted[j].getSina());
	    }
	    prev = sorted[i].getAngle();
	}

*/
	// see what it looks like after sorting
//	System.out.println("After sorting the array is: ");
//	for (int i = 0; i < sorted.length; i++) 
//	    System.out.println(i+": angle="+sorted[i].getAngle()+" weight="+sorted[i].getWeight()+" x="+sorted[i].x+" y="+sorted[i].y+" cosa="+sorted[i].getCosa()+" sina="+sorted[i].getSina());

	// from sorted list create MMdata 
	current = new MMdata(mnormals.length);
	current.addFirstNormal(new MMpoint (0, 0), sorted[0]);
	for (int i = 1; i < mnormals.length-1 ; i++) {
	    current.addNormal(sorted[i]);
	}
//	System.out.println("Still need to addFinalNormal in MMmdata.java line 121");
	current.addFinalNormal();
	//	System.out.println("Last normal was w="+sorted[sorted.length-1].getWeight()+" a="+sorted[sorted.length-1].getAngle()+" but is w="+current.normalAt(current.size()-1).getWeight()+" a="+current.normalAt(current.size()-1).getAngle());
	
//	System.out.println("Scaling the damn bastard; it was (x,y,weight,angle,cosa,sina) = "+current.normalAt(current.size()-1)+")");
	current.normalAt(current.size()-1).scaleBy(-1);

	/*	// calculate center of mass
	double sum = 0, sumx = 0, sumy = 0, sumw = 0;
	for (int i=0; i<sorted.length; i++) {
		sum += sorted[i].getWeight() * sorted[i].getAngle();
		sumw += sorted[i].getWeight();
		sumx += sorted[i].getWeight() * Math.cos(sorted[i].getAngle()); 
		sumy += sorted[i].getWeight() * Math.sin(sorted[i].getAngle());
	}
	//	System.out.println("(di*wi)/sumw="+sum/sumw+" ECI center ("+sumx+", "+sumy+")");
	*/
//	System.out.println("Also after sorting, the MMdata current is:\n"+current);
		
//	current.addNormal(new MMnormal(sorted[mnormals.length-1], new MMpoint(0,0)));
	
	//	System.out.println("Size of current is "+Integer.toString(current.size()));
	//	System.out.println("Current current size is "+Integer.toString(current.size()));
	//	System.out.println(current.toString());

//	System.out.println("Final current size is "+Integer.toString(current.size()));
//	System.out.println(current.toString());
//	System.out.println("Done bugging"); 
	return current;
    }
    
    // quick sort procedure for sorting matchlists
    private void quickSort(int p, int r) {
	if (p >= r) return;
	int q = quickPartition(p, r);
	quickSort (p, q);
	quickSort (q+1, r);
    }
    
    // partition sub procedure of quick sort for sorting match lists
    private int quickPartition(int p, int q) {
	
	// improvements: randomizer to choose x = m[ random(p, q) ]
	MMnormal temp;
	MMnormal pointer; 
	MMnormal x = sorted[p];
	int i = p-1;
	int j = q+1;
	while (true) {
	    while (true) {
		j--;
		if (sorted[j].getAngle()<=x.getAngle()) break;
	    }
	    while (true) {
		i++;
		if (sorted[i].getAngle()>=x.getAngle()) break;
	    }
	    if (i<j) {
		// exchange elements i and j (exchange pointers)
	      //		System.out.println("About to exchange "+i+" with "+j+" coz angle(i) = "+sorted[i].getAngle()+" and angle(j) = "+sorted[j].getAngle());
		pointer = sorted[i];
		sorted[i] = sorted[j];
		sorted[j] = pointer;
	    } else {
//		System.out.println("Didn't exchange "+i+" with "+j+" coz angle(i) = "+sorted[i].getAngle()+" and angle(j) = "+sorted[j].getAngle());
		return j;
	    }
	}
    }
    
}