package prim;

import java.util.*;

public class Prim {

    PriorityQueue<Solmu> keko;
    ArrayList<Solmu>[] vieruslista;
    int[] etaisyys;
    Solmu[] vanhempi;
    int[][] painot;
    boolean[] onkoPuussa;
    Solmu[] verkko;
    int n;

    int maara;
    int laskuri;
    HashSet<Kaari> kaaret;

    public Prim(int n) {
        this.keko = new PriorityQueue<>();
        this.vieruslista = new ArrayList[n+1];
        this.etaisyys = new int[n+1];
        this.vanhempi = new Solmu[n+1];
        this.painot = new int[n+1][n+1];
        this.onkoPuussa = new boolean[n+1];
        this.verkko = new Solmu[n+1];
        this.n = n;

        this.maara = 0;
        this.laskuri = 0;
        this.kaaret = new HashSet<>();

        for (int i = 1; i <= n; i++) {
            vieruslista[i] = new ArrayList();
        }

        onkoPuussa[1] = true;

        etaisyys[1] = 0;

        for (int i = 2; i <= n; i++) {
            etaisyys[i] = Integer.MAX_VALUE;
        }

    }

    public class Solmu implements Comparable {
        public int numero, etaisyys;

        public Solmu(int solmu) {
            this.numero = solmu;
            this.etaisyys = Integer.MAX_VALUE;
        }

        @Override
        public int compareTo(Object o) {
            Solmu toinen = (Solmu) o;
            return this.etaisyys - toinen.etaisyys;
        }
    }

    public class Kaari implements Comparable {
        public int alku, loppu, paino;

        public Kaari(int alku, int loppu, int paino) {
            this.alku = alku;
            this.loppu = loppu;
            this.paino = paino;
        }

        @Override
        public int compareTo(Object t) {
            Kaari toinen = (Kaari) t;
            return this.paino - toinen.paino;
        }
    }

    public void lisaaTie(int a, int b, int x) {

        if (painot[a][b] > 0 && painot[a][b] < x) return;

        Solmu solmuA = new Solmu(a);
        Solmu solmuB = new Solmu(b);

        painot[a][b] = x;
        painot[b][a] = x;

        vieruslista[a].add(solmuB);
        vieruslista[b].add(solmuA);
    }

    public int laske() {

        Solmu eka = new Solmu(1);
        eka.etaisyys = 0;
        keko.add(eka);
        verkko[1] = eka;

        for (int i = 2; i <= n; i++) {
            Solmu uusi = new Solmu(i);
            verkko[i] = uusi;
            keko.add(uusi);
        }

        int paino = 0;
        Solmu solmu;

        while (!keko.isEmpty()) {

            solmu = keko.poll();

            if (vanhempi[solmu.numero] != null) {
                laskuri++;
                paino = paino + painot[vanhempi[solmu.numero].numero][solmu.numero];

                int u = solmu.numero;
                int uv = vanhempi[solmu.numero].numero;

                kaaret.add(new Kaari(uv, u, painot[u][uv]));

                onkoPuussa[solmu.numero] = true;
            }

            for (int i = 0; i < vieruslista[solmu.numero].size(); i++) {

                Solmu v = vieruslista[solmu.numero].get(i);

                if (!onkoPuussa[v.numero] && painot[solmu.numero][v.numero] < etaisyys[v.numero]) {
                    vanhempi[v.numero] = solmu;
                    etaisyys[v.numero] = painot[solmu.numero][v.numero];
                    verkko[v.numero].etaisyys = etaisyys[v.numero];
                    keko.add(keko.poll());
                }
            }
        }


        for (int i = 0; i < onkoPuussa.length; i++) {
            if (onkoPuussa[i]) maara++;
        }

        return paino;
    }

    public static void main(String[] args) {

        HashSet<Integer> solmut = new HashSet<>();

        int n = 5000;
        int m = 100000;

        Prim k = new Prim(n);

        Random r = new Random(1337);
        for (int i = 1; i <= m; i++) {
            int a = r.nextInt(n)+1;
            int b = r.nextInt(n)+1;
            int x = r.nextInt(1000)+1;
            k.lisaaTie(a,b,x);

            solmut.add(a);
            solmut.add(b);
        }

        long alku = System.nanoTime();

        System.out.println(k.laske());

        long loppu = System.nanoTime();

        int pieninPainoKaarista = 0;
        for (Kaari kaari : k.kaaret) {
            pieninPainoKaarista += kaari.paino;
        }
        System.out.println("pienin paino kaarista laskettuna on "+pieninPainoKaarista);
        System.out.println("Kaarien määrä: " + k.kaaret.size());
        System.out.println("Kuinka monta kertaa päästään if-lauseeseen: " + k.laskuri);

        System.out.println("Virittävässä puussa solmuja: " + k.maara);

        System.out.println("Solmuja on: " + solmut.size());

        System.out.println("Aikaa kului "+((loppu-alku)/1e9)+" s");
    }

}