/** * Trieuse.java * * * Created: Sun Apr 04 16:49:06 1999 * * @author P.Genoud * @version */ import java.util.*; interface Comparable { /** * comparaison de deux éléments. * @param o objet avec le quel le recepteur du message doit se comparer. * @return true si this (le recepteur du message) et o sont * de même classe et si this est plus petit que o selon * la relation de comparaison définie pour * la classe de this. false sinon * @exception NonComparableException si this et o ne * sont pas de même classe. */ public boolean plusPetitQue(Object o) throws NonComparableException; } /** * Classe d'exception lancées lorsqu'il y a problème avec l'interface Comparable */ class NonComparableException extends Exception { public NonComparableException(String message) { super(message); } } /** * Des entiers comparables. */ class IntComparable implements Comparable { private int val; /** * Création d'un entier comprable * @param la valeur de l'entier Comparable */ public IntComparable(int v) { val = v; } /** * implémentation de l'interface Comparable */ public boolean plusPetitQue(Object v) throws NonComparableException { if ( v.getClass() != this.getClass()) throw new NonComparableException( "impossible de comparer objet de classe IntComparable avec un objet de classe " + v.getClass().getName()); return ( val < ((IntComparable)v).val ); } /** * renvoie sous forme de chaîne de caractères la valeur de l'entier. * @return la châine représentant l'entier */ public String toString() { return ""+val; } /** * renvoie la valeur de l'entier * @return la valeur de l'entier. */ public int getVal() { return val; } } /** * Classe implémentant un algorithme de tri par insertion */ public class Trieuse { /** * effectue le trie par insertion d'une liste d'éléments comparables. * @param v la liste à trier * @return une liste triée par ordre croissant * @exception NonComparableException si v contient un élément de type * non Comparable * ou si v contient deux élements de type (classe) différents */ public static List triInsertion(List v) throws NonComparableException,InstantiationException, IllegalAccessException { List res = (List) (v.getClass().newInstance()); // la liste résultat int i; // indice pour le parcours de v int p; // indice pour la position d'insertion dans res for (i=0; i < v.size(); i++) { // on verifie que l'élément i de v est bien un // élémenent Comparable // si ce n'est pas le cas, envoi d'une exception if (! (v.get(i) instanceof Comparable)) throw new NonComparableException("element " + i + "de la liste n'est pas un Comparable"); Comparable elti = (Comparable) v.get(i); // recherche de la position p du i ème élement //de v dans le vecteur resultat for (p = 0; p < res.size(); p++) if (elti.plusPetitQue(res.get(p))) break; // insertion du i ème élement de v à la position p // dans le vecteur resultat res.add(p,elti); } return res; } /** * programme de test. * - création d'une liste de 20 entier comparables dont la valeur est tirée * au hasard.
* - trie de la liste
* - affichage de la liste triée
* Le type de l'implémentation pour la liste peut être fixé au lancement du programme * en passant celui-ci en argument de la ligne de commandes. * Par défaut une implémentation sous forme d'ArrayList est choisie. */ public static void main(String[] args) throws NonComparableException, InstantiationException, IllegalAccessException { List v = null; if (args.length > 0) if (args[0].equals("ArrayList")) v = new ArrayList(); else if (args[0].equals("LinkedList")) v = new LinkedList(); else if (args[0].equals("Vector")) v = new Vector(); else { System.out.println("il n'existe pas de listes de type : " + args[0]); System.exit(1); } else // par défaut une ArrayList v = new ArrayList(); for (int i = 0; i < 20; i++) v.add(new IntComparable((int) (Math.random()*100))); System.out.println("La liste non triée"); for (int i = 0; i < v.size(); i++) System.out.print(v.get(i) + " "); // au lieu de la boucle ci-dessus // on aurait pu tout simplement écrire : System.out.println(v); System.out.println(); List vtrie = Trieuse.triInsertion(v); System.out.println("La Liste triée"); for (int i = 0; i < vtrie.size(); i++) System.out.print(vtrie.get(i) + " "); // idem au lieu de la boucle ci-dessus // on aurait pu tout simplement écrire : System.out.println(vtrie); // M.L. 20/7/2001 dans le cas où la ligne // "System.out.println(vtrie);" // est présente, retirez celle qui suit: System.out.println(); } } // Trieuse