//v0.2.2 15/11/21 (PM) (0.2..2 : modification (mineure) des parties à compléter)

import java.nio.file.Paths;
import java.nio.file.Files;
import java.nio.file.LinkOption;
import java.io.IOException;
import java.io.FileNotFoundException;
import java.util.concurrent.ExecutionException;

import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;

import java.util.concurrent.Future;
import java.util.concurrent.Callable;
import java.util.concurrent.Executors;
import java.util.concurrent.ExecutorService;

import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;

class TriLocal implements Callable<int[]> {
    // pool fixe
    private int début;
    private int fin;
    private int[] tableau;
    private int[] résultat;

    TriLocal(int[] t, int d, int f) {
        début = d;
        fin = f;
        tableau = t;
    }

    @Override
    public int[] call() {
        return TF.traiterTronçon(tableau, début, fin);
    }
}

class TraiterFragment extends RecursiveTask<int[]> {
    // pool fork-join
    private int début;
    private int fin;
    private int[] tableau;
    int[] resTri = null;

    private int max = 0;

    TraiterFragment(int[] t, int d, int f) {
        début = d;
        fin = f;
        tableau = t;
    }

    @Override
    protected int[] compute() {
        int resteAFaire = this.fin - this.début;
        // System.out.print(resteAFaire + " ");
        if (resteAFaire > 1) {
            TraiterFragment sp1 = new TraiterFragment(tableau, début, début + resteAFaire / 2);
            TraiterFragment sp2 = new TraiterFragment(tableau, début + resteAFaire / 2, fin);

            sp1.fork();
            sp2.fork();

            return TF.fusion(sp1.join(), sp2.join());
        } else {
            return tableau;
        }
    }
}

public class TF {
    static int seuil;

    static int[] fusion(int[] t1, int[] t2) {
        // fusionne les tableaux triés t1 et t2 en un seul tableau trié (résultat)
        int[] résultat = new int[t1.length + t2.length];
        int i1 = 0;
        int i2 = 0;
        int iR = 0;

        while ((iR < résultat.length) && (i1 < t1.length) && (i2 < t2.length)) {
            if (t1[i1] < t2[i2]) {
                résultat[iR] = t1[i1];
                i1++;
            } else {
                résultat[iR] = t2[i2];
                i2++;
            }
            iR++;
        }
        while (i1 < t1.length) {
            résultat[iR] = t1[i1];
            i1++;
            iR++;
        }
        while (i2 < t2.length) {
            résultat[iR] = t2[i2];
            i2++;
            iR++;
        }
        return résultat;
    }

    static int[] traiterTronçon(int[] t, int début, int fin) {
        int taille;
        int[] resTri;
        // si le fragment est trop gros, on le décompose en 2
        if ((fin - début + 1) > TF.seuil) {
            taille = (fin - début + 1) / 2;
            return TF.fusion(traiterTronçon(t, début, début + taille - 1), traiterTronçon(t, début + taille, fin));
        } else { // traitement direct : quicksort
            resTri = Arrays.copyOfRange(t, début, fin + 1);
            Arrays.sort(resTri);
            return resTri;
        }
    }

    // --------- Mono
    static int[] TFMono(int[] t) {
        return traiterTronçon(t, 0, t.length - 1);
    }

    // -------- Pool Fixe
    static int[] TFPool(ExecutorService xs, int[] t, int nbT) throws InterruptedException, ExecutionException {

        List<Future<int[]>> résultats = new ArrayList<Future<int[]>>(nbT);
        int grain = Math.max(1, t.length / nbT); /*
                                                  * taille d'une recherche locale = taille du tableau/nombre de tâches
                                                  * soumises (ou 1 dans le cas (aberrant) où il y a plus de tâches que
                                                  * d'éléments du tableau)
                                                  */

        int[] résultat = new int[t.length];

        TriLocal[] workers = new TriLocal[nbT];
        for (int i = 0; i < workers.length; i++) {
            workers[i] = new TriLocal(t, i * grain, (i + 1) * grain);
        }

        // soumettre les tâches
        for (int i = 0; i < workers.length; i++) {
            résultats.add(xs.submit(workers[i]));
        }

        // récupérer les résultats
        for (int i = 0; i < workers.length; i++) {
            résultat = fusion(résultat, résultats.get(i).get());
        }
        return résultat;
    }

    // -------- Pool ForkJoin
    static int[] TFForkJoin(ForkJoinPool f, int[] t) {
        TraiterFragment tout = new TraiterFragment(t, 0, t.length - 1);
        return tout.compute();
    }

    // -------- main
    public static void main(String[] args)
            throws InterruptedException, ExecutionException, IOException, FileNotFoundException {

        int nbOuvriersPool = 0; // nb ouvriers du pool fixe. Bonne valeur : nb de processeurs disponibles
        int nbEssais = 0;
        int nbTâches = 0;
        int tailleSeuil = 0; // nombre d'éléments du tableau en dessous duquel on effectue un tri directement
        String chemin = "";
        int[] tableau;
        long départ, fin;
        int[] resTri;

        long[] tempsMono, tempsPool, tempsForkJoin;

        if (args.length == 5) { // analyse des paramètres
            chemin = args[0];
            try {
                nbEssais = Integer.parseInt(args[1]);
                nbTâches = Integer.parseInt(args[2]);
                tailleSeuil = Integer.parseInt(args[3]);
                nbOuvriersPool = Integer.parseInt(args[4]);
            } catch (NumberFormatException nfx) {
                throw new IllegalArgumentException("\nUsage : TF <fichier> <nb essais> " + " <nb tâches (pool)> <seuil>"
                        + " <nb ouvriers du pool (pool)>\n" + " * <nb tâches (pool)> = nb de fragments à traiter \n"
                        + " * <seuil> = taille pour tri direct \n");
            }
        }

        if ((nbEssais < 1) || (nbTâches < 1) || (tailleSeuil < 1) || (nbOuvriersPool < 1)
                || !Files.isRegularFile(Paths.get(chemin), LinkOption.NOFOLLOW_LINKS))
            throw new IllegalArgumentException("\nUsage : TF <fichier> <nb essais> " + " <nb tâches (pool)> <seuil>"
                    + " <nb ouvriers du pool (pool)>\n" + " * <nb tâches (pool)> = nb de fragments à traiter \n"
                    + " * <seuil> = taille pour tri direct \n");
        // l'appel est correct
        tempsMono = new long[nbEssais];
        tempsPool = new long[nbEssais];
        tempsForkJoin = new long[nbEssais];
        tableau = TableauxDisque.charger(chemin);
        TF.seuil = tailleSeuil;

        System.out.println(Runtime.getRuntime().availableProcessors() + " processeurs disponibles pour la JVM");

        // créer un pool avec un nombre fixe d'ouvriers
        ExecutorService poule = Executors.newFixedThreadPool(nbOuvriersPool);

        // créer un pool ForkJoin
        ForkJoinPool fjp = new ForkJoinPool();

        for (int i = 0; i < nbEssais; i++) {
            départ = System.nanoTime();
            resTri = TFMono(tableau);
            fin = System.nanoTime();
            tempsMono[i] = (fin - départ);
            TableauxDisque.sauver(chemin + "triéMono", resTri);
            System.out.println("Essai [" + i + "] : durée (mono) " + tempsMono[i] / 1_000 + "µs");
        }
        System.out.println("--------------------");

        for (int i = 0; i < nbEssais; i++) {
            départ = System.nanoTime();
            resTri = TFPool(poule, tableau, nbTâches);
            fin = System.nanoTime();
            tempsPool[i] = (fin - départ);
            TableauxDisque.sauver(chemin + "triéPF", resTri);
            System.out.println("Essai [" + i + "] : durée (PF) " + tempsPool[i] / 1_000 + "µs");
        }
        poule.shutdown();
        System.out.println("--------------------");

        for (int i = 0; i < nbEssais; i++) {
            départ = System.nanoTime();
            resTri = TFForkJoin(fjp, tableau);
            fin = System.nanoTime();
            tempsForkJoin[i] = (fin - départ);
            TableauxDisque.sauver(chemin + "triéFJ", resTri);
            System.out.println("Essai [" + i + "] : durée (FJ) " + tempsForkJoin[i] / 1_000 + "µs");
        }
        System.out.println("--------------------");
    }
}