/**
* 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