Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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)");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement