import java.time.Duration;
import java.time.Instant;

/* TD8. Tri fusion en place et généricité
 * Ce fichier contient 5 classes:
 *  - Singly<E> : listes chaînées génériques,
 *  - MergeSortString : algorithme merge-sort pour les listes (chaînées) de chaînes de caractères,
 *  - Occurrence : comptage des mots d'un texte,
 *  - MergeSort : algorithme merge-sort générique (on remplace le type «String» par le type générique «E»),
 *  - Median : calcul de la médiane d'un ensemble de valeurs numériques
 */

/* Remarque : ne sont declarées «public» que les constructeurs, ainsi que les méthodes dont la
 * visibilité ne peut pas être réduite, ici toString et compareTo.
 */

// SINGLY

class Singly<E> {
    E element;
    Singly<E> next;

    // On choisit de représenter la liste vide par null, les deux constructeurs qui suivent ne
    // peuvent donc pas construire de liste vide.

    // Cree une liste a un element.

    public Singly(E element, Singly<E> next) {
        this.element = element;
        this.next = next;
    }

    // Crée une liste à partir d'un tableau non vide.

    public Singly(E[] data) {
        assert (data.length > 0) : "\nLe constructeur Singly(E[] data) ne peut pas être utilisé avec un tableau vide"
                + "\ncar on ne peut pas construire une liste non vide sans données.";
        this.element = data[0];
        this.next = null;
        Singly<E> cursor = this;
        for (int i = 1; i < data.length; i++) {
            cursor.next = new Singly<E>(data[i], null);
            cursor = cursor.next;
        }
        ;
    }

    // Copie physique d'une liste (pour les tests uniquement)

    static <E> Singly<E> copy(Singly<E> l) {
        if (l == null)
            return null;
        Singly<E> res = new Singly<E>(l.element, l.next);
        Singly<E> cursor = res;
        while (l.next != null) {
            l = l.next;
            cursor.next = new Singly<E>(l.element, l.next);
            cursor = cursor.next;
        }
        return res;
    }

    // Test l'égalite de deux chaînes.

    static <E> boolean areEqual(Singly<E> chain1, Singly<E> chain2) {
        while (chain1 != null && chain2 != null) {
            if (!chain1.element.equals(chain2.element))
                return false;
            chain1 = chain1.next;
            chain2 = chain2.next;
        }
        return chain1 == chain2;
    }

    // Crée une chaîne de caractères à partir d'une liste chaînée (nécessaire à l'affichage).

    public String toString() {
        Singly<E> cursor = this;
        String answer = "[ ";
        while (cursor != null) {
            answer = answer + (cursor.element).toString() + " ";
            cursor = cursor.next;
        }
        answer = answer + "]";
        return answer;
    }

    // Question 1
    // Longueur d'une chaîne. Implémentation itérative pour éviter les
    // débordements de pile («stack overflow»).

    static<E> int length(Singly<E> l) {
        if (l==null) return 0;
        Singly<E> i = l;
        int count = 1;
        while(i.next != null) {
            count += 1;
            i = i.next;
        }
        return count;
    }

    // Question 1
    // Coupe la seconde moitié de la chaîne passée en argument,
    // la partie supprimée est renvoyée.
    // La méthode split modifie donc la liste passée en argument.

    static<E> Singly<E> split(Singly<E> l) {
        if (l==null) return null;
        int splt = (length(l)-1)/2;
        Singly<E> i = l;
        for (int j = 0; j <splt;j++) {
            i = i.next;
        }
        Singly<E> k = i.next;
        i.next = null;
        return k;
    }
}

/* MERGE_SORT_STRING */

class MergeSortString {

    // Question 2.2
    // Réalise la fusion des chaînes passées en argument, renvoie la chaîne obtenue.
    // Les deux chaînes passées en arguments sont détruites puisque l'opération
    // se fait «en place».

    static Singly<String> merge(Singly<String> l1, Singly<String> l2) {
        if (l1==null) return l2;
        if (l2==null) return l1;
        Singly<String> i1, i2;
        i1 = l1;
        i2 =l2;
        Singly<String> accu;
        if (l1.element.compareTo(l2.element) <= 0) {
            i1 = l1.next;
            accu = l1;
            accu.next = null;
        }
        else {
            i2 = l2.next;
            accu = l2;
            accu.next = null;
        }
        Singly<String> last = accu;
        for (int i = 0; i < Singly.length(l1) +Singly.length(l2); i++) {
            if (i1==null) {
                last.next = i2;
                return accu;
            }
            if (i2==null) {
                last.next = i1;
                return accu;
            }
            if (i1.element.compareTo(i2.element) <= 0) {
                last.next = i1;
                last = i1;
                i1 = i1.next;
                last.next = null;
            }
            else {
                last.next = i2;
                last = i2;
                i2 = i2.next;
                last.next = null;
            }
        }
        return accu;
    }

    // Question 2.2
    // Trie (récursivement) la liste passée en argument en triant chacune de ses deux
    // moitiés séparement avant de fusionner les deux moitiés triées.
    // La liste passée en argument est détruite au cours de l'opération.

    static Singly<String> sort(Singly<String> l) {
        if (l==null) return null;
        if(l.next == null) return l;
        Singly<String> l1 = Singly.split(l);
        return merge(sort(l1), sort(l));
    }

}

/* OCCURRENCE */

class Occurrence implements Comparable<Occurrence> {
    String word;
    int count;

    Occurrence(String word, int count) {
        this.word = word;
        this.count = count;
    }

    public String toString() {
        return word;
    }

    // Question 2.3
    // Renvoie une liste dont chaque maillon contient un mot présent
    // dans la liste de mots passée en argument, avec sa multiplicité.
    // La liste passée en argument peut être détruite.

    static Singly<Occurrence> count(Singly<String> l) {
        if (l==null) return null;
        Instant start = Instant.now();
        Singly<String> i = MergeSortString.sort(l);
        Instant end = Instant.now();
        System.out.println(Duration.between(start, end));
        int count = 1;
        while(i.next.element.compareTo(i.element) == 0) {
            count++;
            i = i.next;

        }
        Singly<Occurrence> res = new Singly<Occurrence>(new Occurrence(i.element, count), null);
        count = 1;
        Singly<Occurrence> last = res;
        i = i.next;
            while(i != null) {
                if (i.next == null) {
                    last.next = new Singly<Occurrence>(new Occurrence(i.element, count), null);
                    return res;
                }
                count = 1;
                while(i.next.element.compareTo(i.element) == 0) {
                    count++;
                    i = i.next;
                    if (i.next == null) {
                        last.next = new Singly<Occurrence>(new Occurrence(i.element, count), null);
                        return res;
                    }
                }
                last.next = new Singly<Occurrence>(new Occurrence(i.element, count), null);
                last = last.next;
                i = i.next;
            }
            return res;
    }

    // Question 3.2
    // Méthode de comparaison nécessaire a l'utilisation de l'algorithme de tri

    public int compareTo(Occurrence that) {
        if (this.count < that.count || (this.count == that.count && this.word.compareTo(that.word) > 0)) return 1;
        else if (this.count == that.count && this.word.compareTo(that.word) == 0) return 0;
        else return -1;
    }

    // Question 3.2
    // Identique à la méthode count(Singly<String> l) excepté que la liste renvoyée
    // est triée par ordre décroissant de multiplicité.

    static Singly<Occurrence> sortedCount(Singly<String> l) {
        Singly<Occurrence> res = count(l);
        return MergeSort.sort(res);
    }
}

/* MERGE_SORT */

// Version générique de MergeSortString
// On remplace le type «String» par le type générique «E» dans l'implémentation de MergeSort

class MergeSort {

    // Question 3.1
    // Identique à merge(Singly<String> l1, Singly<String> l2) avec «E» au lieu de «String»

    static<E extends Comparable<E>> Singly<E> merge(Singly<E> l1, Singly<E> l2) {
        if (l1==null) return l2;
        if (l2==null) return l1;
        Singly<E> i1, i2;
        i1 = l1;
        i2 =l2;
        Singly<E> accu;
        if (l1.element.compareTo(l2.element) <= 0) {
            i1 = l1.next;
            accu = l1;
            accu.next = null;
        }
        else {
            i2 = l2.next;
            accu = l2;
            accu.next = null;
        }
        Singly<E> last = accu;
        for (int i = 0; i < Singly.length(l1) +Singly.length(l2); i++) {
            if (i1==null) {
                last.next = i2;
                return accu;
            }
            if (i2==null) {
                last.next = i1;
                return accu;
            }
            if (i1.element.compareTo(i2.element) <= 0) {
                last.next = i1;
                last = i1;
                i1 = i1.next;
                last.next = null;
            }
            else {
                last.next = i2;
                last = i2;
                i2 = i2.next;
                last.next = null;
            }
        }
        return accu;
    }

    // Question 3.1
    // Identique à sort(Singly<String> l) avec «E» au lieu de «String»

    static<E extends Comparable<E>> Singly<E> sort(Singly<E> l) {
        if (l==null) return null;
        if(l.next == null) return l;
        Singly<E> l1 = Singly.split(l);
        return merge(sort(l1), sort(l));
    }
}

/* MEDIAN */

    class Median {

    // Question 3.3
    // Renvoie une médiane de l'ensemble de valeurs numériques passé en argument
    // sous la forme d'une liste chaînée.

    static Pair<Double> median (Singly<Double> data) {
        throw new Error("Méthode median (Singly<Double> data) à remplir (Question 3.3)");
    }
}