package tsp.shortestpath;

import java.util.ArrayList;
import java.util.List;

public class DisjointSets {

    private ArrayList<Location> sets;
    private int[] parents;

    DisjointSets(ArrayList<Location> locations){
        this.sets = locations;
        this.parents = new int[sets.size()];
        for (int i = 0; i < this.parents.length; i++){
            this.parents[i] = i;
            locations.get(i).setPositionHeap(i);
        }
    }

    public int findRepresentative(Location location){
        int index = location.getPositionHeap();
        while (parents[index] != index){
            index = parents[index];
        }
        return index;
    }

    public boolean haveSameRepresentatives(Location l1, Location l2) {
        int representative1 = this.findRepresentative(l1);
        int representative2 = this.findRepresentative(l2);
        return representative1 == representative2;
    }

    public void union(Location l1, Location l2) {
        int representative1 = this.findRepresentative(l1);
        int representative2 = this.findRepresentative(l2);
        if (representative1 != representative2){
            parents[representative1] = representative2;
        }
    }

    @Override
    public String toString() {
        // StringBuilder is more effective than a String concatenation
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < this.parents.length; i++){
            res.append(this.sets.get(i).toString()).append("\t").append(this.findRepresentative(this.sets.get(i)))
                    .append("\n");
        }
        return res.toString();
    }

    public static void main(String[] args) {
        Location evry = new Location("Evry", 48.629828, 2.4417819999999892);
        Location paris = new Location("Paris", 48.85661400000001, 2.3522219000000177);
        Location lemans = new Location("Le Mans", 48.00611000000001, 0.1995560000000296);
        Location orleans = new Location("Orléans", 47.902964, 1.9092510000000402);
        Location angers = new Location("Angers", 47.478419, -0.5631660000000238);
        ArrayList<Location> locations = new ArrayList<>(List.of(new Location[]{evry, paris, lemans, orleans, angers}));
        DisjointSets ds = new DisjointSets(locations);
        System.out.println(ds);
        ds.union(evry, paris);
        ds.union(orleans, angers);
        ds.union(orleans, evry);
        System.out.println(ds);
    }
}