package ML;

import javafx.util.Pair;

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
    // write your code here
        int K;
        System.out.println("Dati numarul de clustere : ");
        Scanner s1 = new Scanner(System.in);
        K = s1.nextInt();

        BufferedReader br = new BufferedReader(new FileReader("dset500.csv"));

        try {
            BufferedWriter bw = new BufferedWriter(new FileWriter("KMeansOut.txt"));
        } catch (IOException e) {
            e.printStackTrace();
        }

        //adding points - reading csv
        ArrayList<Point> points = new ArrayList<Point>();
        String line;
        ArrayList<ArrayList<Point>> adjList= new ArrayList<>();
        ArrayList<Boolean> vizList = new ArrayList<Boolean>();
        double x, y;
        try {
            while((line = br.readLine()) != null)
            {
                String[] lines = line.split(",");
                x = Double.parseDouble(lines[0]);
                y = Double.parseDouble(lines[1]);
                Point pointy = new Point(x,y);
                //System.out.println("(" + x + ", " + y + ")");
                points.add(pointy);
                adjList.add(new ArrayList<Point>());
                vizList.add(false);
            }
        }
        catch (IOException e) {
            e.printStackTrace();
        }

        System.out.println("Avem "+points.size()+" puncte.");
        System.out.println();
        System.out.println();

        Collections.sort(points, new PointComparator());
        //System.out.println(vizList.size());
        //Acum avem o ordine pentru a ne putea referi la adjList si vizList


        //let's make some edges

        ArrayList<Pair<Edge, Pair<Integer, Integer>>> allEdges =  new ArrayList<>();
        for(int i=0; i<points.size()-1; ++i){
            for(int j=i+1; j<points.size(); ++j){
                Pair<Integer, Integer> auxPair = new Pair<>(i, j);
                Pair<Edge, Pair<Integer, Integer>> auxEdgePair = new Pair<>(new Edge(points.get(i), points.get(j)), auxPair);
                allEdges.add(auxEdgePair);
               // System.out.println("("+auxEdgePair.getKey().getSquareLength() + ", " + points.get(auxEdgePair.getValue().getKey()).getX() + ", " + points.get(auxEdgePair.getValue().getKey()).getY() + ", " + points.get(auxEdgePair.getValue().getValue()).getX() + ", " + points.get(auxEdgePair.getValue().getValue()).getY());
            }
        }
     //   System.out.println(new Point(4.63982706567831,2.65349724511111).getSqDist(new Point(4.75194435915857,3.00555353562793)));
            Collections.sort(allEdges, new Comparator<Pair<Edge, Pair<Integer, Integer>>> () {
            @Override
            public int compare(final Pair<Edge, Pair<Integer, Integer>> o1, final Pair<Edge, Pair<Integer, Integer>> o2) {
                // TODO: implement your logic here
                double i1 = o1.getKey().getSquareLength();
                double i2 = o2.getKey().getSquareLength();
                if(i1>i2) return 1;
                else if (i2>i1) return -1;
                else return 0;
            }
        });

        /*for(int i=0; i<allEdges.size();++i){
            System.out.println("("+allEdges.get(i).getKey().getSquareLength() + ", " + points.get(allEdges.get(i).getValue().getKey()).getX() + ", " + points.get(allEdges.get(i).getValue().getKey()).getY() + ", " + points.get(allEdges.get(i).getValue().getValue()).getX() + ", " + points.get(allEdges.get(i).getValue().getValue()).getY());
        }*/

        //Sorted edges. Time to Kruskal.



        ArrayList<Pair<Edge, Pair<Integer, Integer>>> MST =  new ArrayList<>();

        MST.clear();
        for(int i=0; i<vizList.size(); ++i){
            vizList.set(i, false);
        }
        ArrayList<Set<Integer>> disjointSets = new ArrayList<>();
        for(int i=0; i<allEdges.size();++i){
            //easy add

            //if 2 points are not visited, we add the edge; since they are not visited, they are in no disjoint set
            if(!vizList.get(allEdges.get(i).getValue().getKey()) && !vizList.get(allEdges.get(i).getValue().getValue())){
                MST.add(allEdges.get(i));
                vizList.set(allEdges.get(i).getValue().getKey(), true);
                vizList.set(allEdges.get(i).getValue().getValue(), true);
                Set<Integer> newSet = new HashSet<>();
                newSet.add(allEdges.get(i).getValue().getValue());
                newSet.add(allEdges.get(i).getValue().getValue());
                disjointSets.add(newSet);
            }
            //if 1 point is visited, we have to find its disjoint set and add the next; since an if clause can't tell which is visited, we need 2 \
            else if(vizList.get(allEdges.get(i).getValue().getKey()) && !vizList.get(allEdges.get(i).getValue().getValue())){
                for(int j = 0; j<disjointSets.size(); ++j){
                    if(disjointSets.get(j).contains(allEdges.get(i).getValue().getKey())){
                        disjointSets.get(j).add(allEdges.get(i).getValue().getValue());
                        MST.add(allEdges.get(i));
                        vizList.set(allEdges.get(i).getValue().getValue(), true);
                        break;
                    }
                }
            }
            else if(vizList.get(allEdges.get(i).getValue().getValue()) && !vizList.get(allEdges.get(i).getValue().getKey())){
                for(int j = 0; j<disjointSets.size(); ++j){
                    if(disjointSets.get(j).contains(allEdges.get(i).getValue().getValue())){
                        disjointSets.get(j).add(allEdges.get(i).getValue().getKey());
                        MST.add(allEdges.get(i));
                        vizList.set(allEdges.get(i).getValue().getKey(), true);
                        break;
                    }
                }
            }
            //both visited remain; we must either merge the 2 sets or continue if both are in the same set
            else{
                int foundFirst = -1;
                int foundSecond = -1;
                for(int j=0; j<disjointSets.size(); ++j){
                    if(disjointSets.get(j).contains(allEdges.get(i).getValue().getValue())){
                        foundSecond=j;
                    }
                    if(disjointSets.get(j).contains(allEdges.get(i).getValue().getKey())){
                        foundFirst=j;
                    }
                }
               /* if (foundFirst == foundSecond) {
                    System.out.println(foundFirst + " == " + foundSecond);
                }
                else{
                    System.out.println(foundFirst + " != " + foundSecond);
                }*/
               if(foundFirst!=-1 && foundSecond!=-1){
                   Set<Integer> aux = disjointSets.get(foundFirst);
                   aux.addAll(disjointSets.get(foundSecond));

                   disjointSets.remove(foundFirst);
                   disjointSets.remove(foundSecond);
                   disjointSets.add(aux);
               }
            }
            }


        for(int i=0; i<MST.size(); ++i){
        //    System.out.println("("+MST.get(i).getKey().getSquareLength() + ", " + points.get(MST.get(i).getValue().getKey()).getX() + ", " + points.get(MST.get(i).getValue().getKey()).getY() + ", " + points.get(MST.get(i).getValue().getValue()).getX() + ", " + points.get(MST.get(i).getValue().getValue()).getY() + ")");
        }

        for(int i=0; i<disjointSets.size();++i){
                System.out.println(disjointSets.get(i));
        }
        System.out.println(MST.size() + " " + allEdges.size());

    }


}

public class Point{
    private double x;
    private double y;
    public Point(double px, double py) {
        this.x = px;
        this.y = py;
    }

    public double getX() {
        return x;
    }
    public double getY(){
        return y;
    }

    public double getSqDist(Point p){
        return (this.y-p.y)*(this.y-p.y)+(this.x-p.x)*(this.x-p.x);
    }


    public void addPoint(Point p){
        this.x+=p.x;
        this.y+=p.y;
    }

    public void divCoord(int n){
        this.x = x/(double)n;
        this.y = y/(double)n;
    }
}

public class Edge {
    private Point x;
    private Point y;
    private double squareLength;

    public Edge(Point px, Point py){
        this.x=px;
        this.y=py;
        this.squareLength = x.getSqDist(y);
    }

    public double getSquareLength(){
        return this.squareLength;
    }
}

import java.util.Comparator;

public class PointComparator implements Comparator<Point> {
    @Override
    public int compare(Point o1, Point o2) {
        double i1 = o1.getSqDist(new Point(0,0));
        double i2 = o2.getSqDist(new Point(0,0));
        if(i1>i2) return 1;
        else if (i2>i1) return -1;
        else return 0;
    }
}