import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import Jcg.viewer.old.Fenetre;
import Jcg.geometry.Point_;
import Jcg.geometry.Point_2;
import Jcg.triangulations2D.Delaunay_2;
import Jcg.triangulations2D.HalfedgeHandle;
import Jcg.triangulations2D.TriangulationDSFace_2;
import Jcg.triangulations2D.TriangulationDSVertex_2;

/**
 * Class for comparing (half-)edges according to their euclidean length
 */
class HalfedgeHandleLengthComparator implements Comparator<HalfedgeHandle<Point_2>> {
	public int compare (HalfedgeHandle<Point_2> e1, HalfedgeHandle<Point_2> e2) {
		double d1 = e1.getVertex(0).getPoint().distanceFrom(e1.getVertex(1).getPoint()).doubleValue();
		double d2 = e2.getVertex(0).getPoint().distanceFrom(e2.getVertex(1).getPoint()).doubleValue();
		if (d1 < d2)
			return -1;
		else if (d1 > d2)
			return 1;
		else
			return 0;
	}
}

/**
 * Solve TSP to compute curve reconstruction (using Christophides algorithm)
 *
 */
public class TSP_2D {

	private Collection<Point_> nuage; // store the input point cloud P
	private Delaunay_2 del; // store the 2d Delaunay triangulation of P
	
	
	/**
	 * MST is stored as a suggraph of the Delaunay graph
	 *
	 */
	public TSP_2D (String filename) {
		nuage = IO.readPointCloud(filename);
		del = new Delaunay_2();
		for (Point_ p : nuage)
			del.insert(new Point_2(p));
	}
	
	/**
	 * MST is stored as a suggraph of the Delaunay graph
	 * (a' completer)
	 */
	public void computeMST () {
		// retrieve triangulation edges
		
		// sort them by increasing length
		
		// initialize union-find data structure
		
		// iterate over edges (ordered according to their length)
	}

	/**
	 * Computes degree of a vertex in MST
	 * (a' completer)
	 */
	int degree (TriangulationDSVertex_2<Point_2> v) {
		throw new Error("To be completed");
	}
	

	/**
	 * Computes an eulerian tour starting from an arbitrary leaf of the MST
	 *
	 */
	public List<HalfedgeHandle<Point_2>> computeEulerianTour () {
		throw new Error("To be completed");
	}

	/**
	 * Trims the Eulerian tour.
	 */
	public List<Point_2[]> trim (List<HalfedgeHandle<Point_2>> tour) {
		throw new Error("To be completed");
	}
 	
	/**
	 * Reconstructs closed curve from point cloud using TSP
	 */
	public List<Point_2[]> reconstruct() {
		throw new Error("To be completed");
	}
	
	
	
	public static void test (String filename) {
		TSP_2D tsp = new TSP_2D(filename);

		// compute MST
		tsp.computeMST();
			
		// Get list of constraint edges
		Collection<HalfedgeHandle<Point_2>> cEdgesDel = tsp.del.constraintEdges();
		Collection<Point_2[]> segments = new LinkedList<Point_2[]> ();
		for (HalfedgeHandle<Point_2> q : cEdgesDel)
			segments.add(new Point_2[] {q.getVertex(0).getPoint(), q.getVertex(1).getPoint()});

		// Show triangulation and MST in window
		Fenetre f1 = new Fenetre(false);
		Collection<TriangulationDSFace_2<Point_2>> facesDel = tsp.del.finiteFaces();
		LinkedList<Point_2[]> trianglesDel = new LinkedList<Point_2[]>();
		for (TriangulationDSFace_2<Point_2> fd : facesDel)
			trianglesDel.add(new Point_2[]{fd.vertex(0).getPoint(), fd.vertex(1).getPoint(), fd.vertex(2).getPoint()});

		f1.addTriangles(trianglesDel);
		f1.addFatSegments(segments);
		f1.setVisible();
			
		// re-initialize data structure
		tsp = new TSP_2D (filename);
			
		// compute TSP-based reconstruction
		List<Point_2[]> recons = tsp.reconstruct();

		// Show triangulation and MST in window
		Fenetre f2 = new Fenetre(false);
		f2.addTriangles(trianglesDel);
		f2.addFatSegments(recons);
		f2.setVisible();
		
		System.out.println("done.");
	}
		
	public static void main (String[] args) {
		if (args.length != 1) {
			System.out.println("Usage : java TSP_2D <filename>");
			System.exit(0);
		}
		test(args[0]);
	}
}