Alex239

Untitled

Oct 23rd, 2020
899
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.time.Duration;
  2. import java.time.Instant;
  3.  
  4. /* TD8. Tri fusion en place et généricité
  5.  * Ce fichier contient 5 classes:
  6.  *  - Singly<E> : listes chaînées génériques,
  7.  *  - MergeSortString : algorithme merge-sort pour les listes (chaînées) de chaînes de caractères,
  8.  *  - Occurrence : comptage des mots d'un texte,
  9.  *  - MergeSort : algorithme merge-sort générique (on remplace le type «String» par le type générique «E»),
  10.  *  - Median : calcul de la médiane d'un ensemble de valeurs numériques
  11.  */
  12.  
  13. /* Remarque : ne sont declarées «public» que les constructeurs, ainsi que les méthodes dont la
  14.  * visibilité ne peut pas être réduite, ici toString et compareTo.
  15.  */
  16.  
  17. // SINGLY
  18.  
  19. class Singly<E> {
  20.     E element;
  21.     Singly<E> next;
  22.  
  23.     // On choisit de représenter la liste vide par null, les deux constructeurs qui suivent ne
  24.     // peuvent donc pas construire de liste vide.
  25.  
  26.     // Cree une liste a un element.
  27.    
  28.     public Singly(E element, Singly<E> next) {
  29.         this.element = element;
  30.         this.next = next;
  31.     }
  32.  
  33.     // Crée une liste à partir d'un tableau non vide.
  34.    
  35.     public Singly(E[] data) {
  36.         assert (data.length > 0) : "\nLe constructeur Singly(E[] data) ne peut pas être utilisé avec un tableau vide"
  37.                 + "\ncar on ne peut pas construire une liste non vide sans données.";
  38.         this.element = data[0];
  39.         this.next = null;
  40.         Singly<E> cursor = this;
  41.         for (int i = 1; i < data.length; i++) {
  42.             cursor.next = new Singly<E>(data[i], null);
  43.             cursor = cursor.next;
  44.         }
  45.         ;
  46.     }
  47.  
  48.     // Copie physique d'une liste (pour les tests uniquement)
  49.    
  50.     static <E> Singly<E> copy(Singly<E> l) {
  51.         if (l == null)
  52.             return null;
  53.         Singly<E> res = new Singly<E>(l.element, l.next);
  54.         Singly<E> cursor = res;
  55.         while (l.next != null) {
  56.             l = l.next;
  57.             cursor.next = new Singly<E>(l.element, l.next);
  58.             cursor = cursor.next;
  59.         }
  60.         return res;
  61.     }
  62.  
  63.     // Test l'égalite de deux chaînes.
  64.    
  65.     static <E> boolean areEqual(Singly<E> chain1, Singly<E> chain2) {
  66.         while (chain1 != null && chain2 != null) {
  67.             if (!chain1.element.equals(chain2.element))
  68.                 return false;
  69.             chain1 = chain1.next;
  70.             chain2 = chain2.next;
  71.         }
  72.         return chain1 == chain2;
  73.     }
  74.    
  75.     // Crée une chaîne de caractères à partir d'une liste chaînée (nécessaire à l'affichage).
  76.    
  77.     public String toString() {
  78.         Singly<E> cursor = this;
  79.         String answer = "[ ";
  80.         while (cursor != null) {
  81.             answer = answer + (cursor.element).toString() + " ";
  82.             cursor = cursor.next;
  83.         }
  84.         answer = answer + "]";
  85.         return answer;
  86.     }
  87.  
  88.     // Question 1
  89.     // Longueur d'une chaîne. Implémentation itérative pour éviter les
  90.     // débordements de pile («stack overflow»).
  91.    
  92.     static<E> int length(Singly<E> l) {
  93.         if (l==null) return 0;
  94.         Singly<E> i = l;
  95.         int count = 1;
  96.         while(i.next != null) {
  97.             count += 1;
  98.             i = i.next;
  99.         }
  100.         return count;
  101.     }
  102.    
  103.     // Question 1
  104.     // Coupe la seconde moitié de la chaîne passée en argument,
  105.     // la partie supprimée est renvoyée.
  106.     // La méthode split modifie donc la liste passée en argument.
  107.    
  108.     static<E> Singly<E> split(Singly<E> l) {
  109.         if (l==null) return null;
  110.         int splt = (length(l)-1)/2;
  111.         Singly<E> i = l;
  112.         for (int j = 0; j <splt;j++) {
  113.             i = i.next;
  114.         }
  115.         Singly<E> k = i.next;
  116.         i.next = null;
  117.         return k;
  118.     }
  119. }
  120.  
  121. /* MERGE_SORT_STRING */
  122.  
  123. class MergeSortString {
  124.  
  125.     // Question 2.2
  126.     // Réalise la fusion des chaînes passées en argument, renvoie la chaîne obtenue.
  127.     // Les deux chaînes passées en arguments sont détruites puisque l'opération
  128.     // se fait «en place».
  129.    
  130.     static Singly<String> merge(Singly<String> l1, Singly<String> l2) {
  131.         if (l1==null) return l2;
  132.         if (l2==null) return l1;
  133.         Singly<String> i1, i2;
  134.         i1 = l1;
  135.         i2 =l2;
  136.         Singly<String> accu;
  137.         if (l1.element.compareTo(l2.element) <= 0) {
  138.             i1 = l1.next;
  139.             accu = l1;
  140.             accu.next = null;
  141.         }
  142.         else {
  143.             i2 = l2.next;
  144.             accu = l2;
  145.             accu.next = null;
  146.         }
  147.         Singly<String> last = accu;
  148.         for (int i = 0; i < Singly.length(l1) +Singly.length(l2); i++) {
  149.             if (i1==null) {
  150.                 last.next = i2;
  151.                 return accu;
  152.             }
  153.             if (i2==null) {
  154.                 last.next = i1;
  155.                 return accu;
  156.             }
  157.             if (i1.element.compareTo(i2.element) <= 0) {
  158.                 last.next = i1;
  159.                 last = i1;
  160.                 i1 = i1.next;  
  161.                 last.next = null;
  162.             }
  163.             else {
  164.                 last.next = i2;
  165.                 last = i2;
  166.                 i2 = i2.next;  
  167.                 last.next = null;
  168.             }
  169.         }
  170.         return accu;
  171.     }
  172.  
  173.     // Question 2.2
  174.     // Trie (récursivement) la liste passée en argument en triant chacune de ses deux  
  175.     // moitiés séparement avant de fusionner les deux moitiés triées.  
  176.     // La liste passée en argument est détruite au cours de l'opération.
  177.    
  178.     static Singly<String> sort(Singly<String> l) {
  179.         if (l==null) return null;
  180.         if(l.next == null) return l;
  181.         Singly<String> l1 = Singly.split(l);
  182.         return merge(sort(l1), sort(l));
  183.     }
  184.  
  185. }
  186.  
  187. /* OCCURRENCE */
  188.  
  189. class Occurrence implements Comparable<Occurrence> {
  190.     String word;
  191.     int count;
  192.  
  193.     Occurrence(String word, int count) {
  194.         this.word = word;
  195.         this.count = count;
  196.     }
  197.    
  198.     public String toString() {
  199.         return word;
  200.     }
  201.    
  202.     // Question 2.3
  203.     // Renvoie une liste dont chaque maillon contient un mot présent
  204.     // dans la liste de mots passée en argument, avec sa multiplicité.  
  205.     // La liste passée en argument peut être détruite.
  206.    
  207.     static Singly<Occurrence> count(Singly<String> l) {
  208.         if (l==null) return null;
  209.         Instant start = Instant.now();
  210.         Singly<String> i = MergeSortString.sort(l);
  211.         Instant end = Instant.now();
  212.         System.out.println(Duration.between(start, end));
  213.         int count = 1;
  214.         while(i.next.element.compareTo(i.element) == 0) {
  215.             count++;
  216.             i = i.next;
  217.            
  218.         }
  219.         Singly<Occurrence> res = new Singly<Occurrence>(new Occurrence(i.element, count), null);
  220.         count = 1;
  221.         Singly<Occurrence> last = res;
  222.         i = i.next;
  223.             while(i != null) {
  224.                 if (i.next == null) {
  225.                     last.next = new Singly<Occurrence>(new Occurrence(i.element, count), null);
  226.                     return res;
  227.                 }
  228.                 count = 1;
  229.                 while(i.next.element.compareTo(i.element) == 0) {
  230.                     count++;
  231.                     i = i.next;
  232.                     if (i.next == null) {
  233.                         last.next = new Singly<Occurrence>(new Occurrence(i.element, count), null);
  234.                         return res;
  235.                     }
  236.                 }
  237.                 last.next = new Singly<Occurrence>(new Occurrence(i.element, count), null);
  238.                 last = last.next;
  239.                 i = i.next;
  240.             }
  241.             return res;
  242.     }
  243.    
  244.     // Question 3.2
  245.     // Méthode de comparaison nécessaire a l'utilisation de l'algorithme de tri
  246.    
  247.     public int compareTo(Occurrence that) {
  248.         if (this.count < that.count || (this.count == that.count && this.word.compareTo(that.word) > 0)) return 1;
  249.         else if (this.count == that.count && this.word.compareTo(that.word) == 0) return 0;
  250.         else return -1;
  251.     }
  252.  
  253.     // Question 3.2
  254.     // Identique à la méthode count(Singly<String> l) excepté que la liste renvoyée
  255.     // est triée par ordre décroissant de multiplicité.
  256.    
  257.     static Singly<Occurrence> sortedCount(Singly<String> l) {
  258.         Singly<Occurrence> res = count(l);
  259.         return MergeSort.sort(res);
  260.     }
  261. }
  262.  
  263. /* MERGE_SORT */
  264.  
  265. // Version générique de MergeSortString
  266. // On remplace le type «String» par le type générique «E» dans l'implémentation de MergeSort
  267.  
  268. class MergeSort {
  269.    
  270.     // Question 3.1
  271.     // Identique à merge(Singly<String> l1, Singly<String> l2) avec «E» au lieu de «String»
  272.    
  273.     static<E extends Comparable<E>> Singly<E> merge(Singly<E> l1, Singly<E> l2) {
  274.         if (l1==null) return l2;
  275.         if (l2==null) return l1;
  276.         Singly<E> i1, i2;
  277.         i1 = l1;
  278.         i2 =l2;
  279.         Singly<E> accu;
  280.         if (l1.element.compareTo(l2.element) <= 0) {
  281.             i1 = l1.next;
  282.             accu = l1;
  283.             accu.next = null;
  284.         }
  285.         else {
  286.             i2 = l2.next;
  287.             accu = l2;
  288.             accu.next = null;
  289.         }
  290.         Singly<E> last = accu;
  291.         for (int i = 0; i < Singly.length(l1) +Singly.length(l2); i++) {
  292.             if (i1==null) {
  293.                 last.next = i2;
  294.                 return accu;
  295.             }
  296.             if (i2==null) {
  297.                 last.next = i1;
  298.                 return accu;
  299.             }
  300.             if (i1.element.compareTo(i2.element) <= 0) {
  301.                 last.next = i1;
  302.                 last = i1;
  303.                 i1 = i1.next;  
  304.                 last.next = null;
  305.             }
  306.             else {
  307.                 last.next = i2;
  308.                 last = i2;
  309.                 i2 = i2.next;  
  310.                 last.next = null;
  311.             }
  312.         }
  313.         return accu;
  314.     }
  315.  
  316.     // Question 3.1
  317.     // Identique à sort(Singly<String> l) avec «E» au lieu de «String»
  318.    
  319.     static<E extends Comparable<E>> Singly<E> sort(Singly<E> l) {
  320.         if (l==null) return null;
  321.         if(l.next == null) return l;
  322.         Singly<E> l1 = Singly.split(l);
  323.         return merge(sort(l1), sort(l));
  324.     }
  325. }
  326.  
  327. /* MEDIAN */
  328.  
  329.     class Median {
  330.  
  331.     // Question 3.3
  332.     // Renvoie une médiane de l'ensemble de valeurs numériques passé en argument
  333.     // sous la forme d'une liste chaînée.
  334.    
  335.     static Pair<Double> median (Singly<Double> data) {
  336.         throw new Error("Méthode median (Singly<Double> data) à remplir (Question 3.3)");
  337.     }
  338. }
  339.  
RAW Paste Data