l Burgener – Section Informatique Résumé : Programmation II

Raphaël Burgener – Section Informatique

Résumé : Programmation II

Cours 2 : Exceptions

Lorsqu’une erreur est détectée, les exceptions permettent de :

• transférer le contrôle à un gestionnaire d’exception (exception handler)

• de passer une valeur quelconque décrivant l’erreur (p.ex. sa raison)

Lorsqu’on programme au moyen des exceptions, on peut effectuer deux actions :

• installer un gestionnaire d’exception, qui sera activé si une exception d’un certain type se produit, et ignoré sinon

• lever une exception, ce qui transfère immédiatement le contrôle au gestionnaire d’exception du bon type installé le plus récemment, ou à défaut termine l’exécution

En Java, on utilise l’énoncé try…catch pour installer un gestionnaire d’exceptions, et l’énoncé throw pour lever une exception. Les exceptions sont des objets comme les autres, à un détail près : ils doivent être des instances d’une sousclasse de Throwable.

La classe Throwable possède quelques méthodes intéressantes :

• getMessage – fournit le message d’erreur

• getCause – fournit la cause de l’exception

• printStackTrace – affiche la pile d’appels

L'interpréteur cherche un bloc catch(){} à partir de l'endroit où l'exception a été créée en cherchant vers le bas. S'il ne trouve aucun bloc catch{}, l'exception est lancée dans le bloc de niveau supérieur, ainsi de suite jusqu'au bloc de la classe qui par défaut enverra l'exception au handler de l'interpréteur.

Gestionnaire qui s’applique à toutes les exceptions :

try { … } catch (Throwable e) { … }

Gestionnaire qui s’applique uniquement aux erreurs d’entréessorties :

try { … } catch (IOException e) { … }

1


L’énoncé try…finally permet de s’assurer qu’un morceau de code sera exécuté, même enprésence d’exceptions, et même en cas de retour explicite de la fonction ! (return...)

La gestion des exceptions est obligatoire sauf dans deux cas : les sousclasses de Error et de RuntimeException.

Il est possible de chaîner les exceptions. Pour ce faire, toute exception possède une cause, qui est soit une autre exception, soit null. Le chaînage permet d’éviter que les exceptions ne détruisent l’abstraction.

Exemple :

Bloc try...finally :

private static int countLines(String fileName) throws IOException //avertit la JVM que la fonction peut lever une IOException//pas besoin de mettre un catch, quand on utilisera la fonction//on sera obligé de try{}catch{} la fonction, autrement erreur

{BufferedReader reader = new BufferedReader(new FileReader(fileName));try {int count = 0;while (reader.readLine() != null)++count;return count;} finally {reader.close();}

}

Bloc try...catch :

public static void main(String[] args) {if (args.length != 1) {System.out.println("Usage: count <filename>");System.exit(1);} try {String name = args[0];int lines = countLines(name);System.out.println("Le fichier "+name +" contient "+lines+" lignes");} catch (IOException e) {//exécute le code suivant si le bloc try lève une IOException //ou une autre exception « extends » à celleci, autrement//passe le relais à l'interpréteurSystem.out.println("Erreur E/S:\n"+e.getMessage());

2


}}

Sousclasse d'Exception :

public class DateFormatException extends Exception {public DateFormatException(String message) {super(message);}

public DateFormatException(String message, Throwable cause) {super(message, cause);}

}

Installer un gestionnaire d'exception / Lever une exception :

if (s.length() != 10 || s.charAt(2) != ’/’ || s.charAt(5) != ’/’)throw new DateFormatException("invalid date " + s);try {return new Date(Integer.parseInt(s.substring(0,2)),Integer.parseInt(s.substring(3,5)),Integer.parseInt(s.substring(6,10)));} catch (NumberFormatException e) {throw new DateFormatException("invalid date " + s, e);}

Utiliser la méthode printStackTrace/getMessage :

static int [] j = new int [5];

public static void main(String[] args) {try {mult(1);} catch (ArrayIndexOutOfBoundsException e) {System.out.println(" err: " + e.getMessage());System.out.println(" cause: " + e.getCause());System.out.println(" printStackTrace: "); e.printStackTrace();}}

public static int mult(int i) {j[i] = i;return mult(i + 1);}

Ce code renvoie :

err: 5 cause: null

3


printStackTrace: java.lang.ArrayIndexOutOfBoundsException: 5

at Exception.mult(Exception.java:19) ... // quelques lignes effacées

Si à la place de ArrayIndexOutOfBoundsException, nous avions mis une autre exception qui ne se serait pas lever, la JVM aurait pris le relais (en affichant le printstacktrace).

Cours 3 : Généricité

class Pair<F,S> {public final F fst;public final S snd;

public Pair(F f, S s) {fst = f; snd = s;

}}

Pair est une classe générique possédant deux paramètres de type, nommés ici F et S.

Désormais, le compilateur signale une erreur lors d’une utilisation incorrecte de la paire.

Pour utiliser une classe générique comme Pair, il faut spécifier quels types utiliser pour ses paramètres de type F et S. Par exemple, le type des paires composées d’une chaîne et d’un entier se note : Pair<String,Integer>.

On appelle un tel type une instanciation de la classe générique Pair. Plusieurs instanciations d’un même type générique ne sont jamais soustype l’une de l’autre.

Le type Cell<?> est celui des cellules dont l’élément est de type inconnu, donc quelconque. Le compilateur n’accepte le code que s’il est certain qu’il pourra s’exécuter sans problème quelque soit le type qui remplace le joker.

On dit que le type Object est la borne supérieure (upper bound) du joker, car c’est le type le plus haut dans la hiérarchie qui pourrait s’y substituer. Object est la borne supérieure attribuée par défaut aux jokers, mais il est possible d’en spécifier une autre explicitement, p.ex. : <? extends Number>

Nous pouvons également spécifier une borne inférieure (lower bound), p. ex. : <? super Number>

Les méthodes peuvent également être génériques.

Notez que lorsqu’on appelle une méthode générique, il ne faut pas spécifier les paramètres de type. Ils sont inférés par le compilateur. Exemple : <integer> cell2pair(new Cell<Integer>(42))

4


Les exceptions ne peuvent pas être génériques.

Exemple :

Méthode générique / à argument générique :

public class Exemple1 {private static <E> void rotateRight(ArrayList<E> array) {// ^ paramêtre de type, obligatoirearray.add(0, array.remove(array.size() 1));}

public static void main(String[] args) {ArrayList<Integer> a = new

ArrayList<Integer>(Arrays.asList(1,2,3,4));System.out.println(a);for (int i = 0; i < a.size(); ++i) {rotateRight(a);System.out.println(a);}

}}

Méthode générique avec joker :

public class Exemple2 {private static double average(ArrayList<? extends Number> array) {

double sum = 0.0;for (int i = 0; i < array.size(); ++i)sum += array.get(i).doubleValue();return array.isEmpty() ? 0.0 : sum / array.size();

}

public static void main(String[] args) {ArrayList<Integer> a1 =new ArrayList<Integer>(Arrays.asList(1,2,3,4));ArrayList<Double> a2 =new ArrayList<Double>(Arrays.asList(1.0,2.0,3.0,4.0));}

}

Cours 4 : Introduction aux structures de données

Le paquetage java.util définit trois genres de structures de données : les listes, les ensembles et les tables associatives. A chaque genre de structure de données correspond une interface. Chaque interface est implémentée par une ou plusieurs classes, qui mettent en oeuvre la structure de données d’une certaine manière.

5


L’interface List<E> représente le concept de liste d’éléments de type E. Les opérations définies par cette interface permettent d’ajouter et de supprimer des éléments, de les parcourir, etc.

Deux classes implémentent cette interface :

• ArrayList qui stocke les éléments dans un tableau

• LinkedList, qui chaîne les éléments

Hiérarchisation :

ArrayList List (listes) LinkedList

TreeSet Collection Set (ensembles) HashSet

LinkedHashSet

TreeMap Map (tables associatives) HashMap

LinkedHashMap

Les tableaux sont la seule structure de données intégrée au langage Java luimême.

Point fort : accès à et modification d’un élément quelconque en O(1).

Points faibles : pas moyen de modifier la taille du tableau une fois celuici créé ; limitations liées à la généricité (aucune info supplémentaire...).

L'arrayList est une structure de donnée permettant d’accéder à un élément quelconque en un temps constant – comme un tableau – tout en étant extensible.

class ArrayList<E> {private E[] array = (E[])new Object[1];private int size;

int size() {return size;}

E get(int index) {return array[index];}

6


void add(int index, E elem) {if (size == array.length) {E[] a2 = (E[])new Object[array.length*2];System.arraycopy(array, 0, a2, 0, index);System.arraycopy(array, index, a2, index+1, size-index);array = a2;} else {System.arraycopy(array, index, array, index+1, size-index); array[index] = elem; ++size;}}

}

infos : System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

Les listes chaînées ( linked list )

Principe : chaque élément est lié à son successeur direct (et évt. son prédécesseur), et on garde une référence vers le premier élément.

Point fort : insertion et suppression d’un élément en tête en O(1).

Point faible : accès à l’élément d’indice n en O(n).

La classe LinkedList est conçue pour pouvoir être utilisée comme une pile ou une queue. Elle dispose pour ce faire des méthodes addFirst, addLast, removeFirst et removeLast qui permettent l’ajout et la suppression d’éléments aux extrémités en untemps constant.

class LinkedList<E> {private Node<E> head;// référence vers le premier élément// ... méthodes

}

class Node<E> {public final E elem;public Node<E> next;

public Node(E elem, Node<E> next) {this.elem = elem;this.next = next;}

7


E get(int index) {Node<E> node = head;for (int i = 0; i < index; ++i)node = node.next;return node.elem;}

void add(int index, E elem) {if (index == 0)head = new Node<E>(elem, head);else {

Node<E> pred = head;for (int i = 1; i < index; ++i)pred = pred.next;pred.next = new Node<E>(elem, pred.next);

}}

}

Equivalent API : java.util.List<E>, java.util.LinkedList<E>, java.util.ArrayList<E>.

Pour parcourir les éléments d’une collection, on utilise un itérateur. Un itérateur est un objet qui désigne un élément d’une collection, et qui peut être déplacé de cet élément à son successeur (évt. Prédécesseur). Les deux opérations principales d’un itérateur permettent d’obtenir l’élément suivant de la collection (ou null s’il n’y en a plus) et de savoir si l’élément courant a un successeur.

L’interface java.util.Iterator définit les itérateurs Java. Sa définition ressemble à ceci :

interface Iterator<E> {boolean hasNext();E next();}

Son Utilisation :

List<String> l = …;

for (Iterator<String> it = l.iterator(); it.hasNext();) {String e = it.next();System.out.println(e);}

ou équivalent :

for (String e: l)System.out.println(e);

8


Cours 6 : les ensembles (I)

Un ensemble est une collection d’éléments dans laquelle tout élément apparaît au plus une fois. Les opérations principales sont :

• l’ajout et la suppression d’éléments

• le test d’appartenance

Pour trouver si un élément donné est présent dans un tableau trié, on peut utiliser la recherche dichotomique. L’idée est de séparer le tableau en deux moitiés égales, puis de regarder dans quelle moitié l’élément recherché devrait être. Ensuite, on recommence la recherche dans cette moitié, jusqu’à tomber sur un tableau à un élément – ou vide si l’élément n’est pas présent. Le test d’appartenance est en O(log n).

Un arbre binaire de recherche (binary search tree) est un arbre composé de noeuds – qui ont chacun deux fils – deux noeuds ou deux feuilles. A chaque noeud est associé un élément, et l’arbre est organisé de manière à ce que tous les éléments du sousarbre gauche d’un noeud soient plus petits que celui du noeud, et tous les éléments du sousarbre droite soient plus grands.

abstract class Tree {abstract boolean contains(int e);abstract boolean isLeaf();abstract int min();abstract Tree remove(int e);

}

class Leaf extends Tree {boolean contains(int e){ return false; }

Tree insert(int e) {//à mettre en relation avec la fonction du même nom de la //classe Nodereturn new Node(e, new Leaf(), new Leaf());}

boolean isLeaf() { return true; }

int min() { throw new Error(); }

Tree remove(int e) { return this; }}

class Node extends Tree {private Tree s, g;private final int v;

9


public Node(int v, Tree s, Tree g){ this.v = v; this.s = s; this.g = g; }

public boolean contains(int e) {if (e < v)return s.contains(e);else if(e > v) return g.contains(e);else if (e == v) return true;elsereturn false;}

Tree insert(int e) {if (e < v) s = s.insert(e);else if (v < e) g = g.insert(e);return this;}

boolean isLeaf() { return false; }

int min() {return s.isLeaf() ? v : s.min();}

Tree remove(int e) {if (e < v) { s = s.remove(e);return this;} else if (v < e) { g = g.remove(e);return this;} else {

if (s.isLeaf()) return g;else if (g.isLeaf()) return s;else {int r = g.min();return new Node(r, s, g.remove(r));}

}}

}

La suppression d’un élément dans un arbre de recherche est légèrement plus complexe que les autres opérations. On peut distinguer trois cas :

1. le noeud n’a aucun fils – on le supprime

2. le noeud a un fils unique – on le remplace par ce fils

10


3. le noeud a deux fils – cas plus complexe détaillé ciaprès

Pour supprimer un élément e qui a deux fils, il faut trouver par quel autre élément le remplacer. Deux candidats s’imposent rapidement :

1. l’élément qui précède directement e, càd le plus grand élément de son fils gauche

2. l’élément qui suit directement e, càd le plus petit élément de son fils droite.

Pour généraliser la relation d’ordre, on peut penser à deux solutions :

1. on admet que les objets stockés dans l’ensemble « savent » se comparer entre eux (ordre intrinsèque)

Solution : définir une interface contenant la méthode de comparaison, et s’assurer ensuite que les éléments de l’ensemble implémentent cette interface.

interface Comparable<T> {public int compareTo(T that);}

Equivalent API : java.lang.Comparable<T>

2. on trouve un moyen de représenter la relation d’ordre et on la passe en argumentau moment de la création de l’ensemble (comparateur)

L’autre manière de spécifier la relation d’ordre est de la représenter de manière explicite et de la passer en argument lors de la création de l’ensemble. Pour représenter cette relation, on peut très naturellement utiliser un objet doté d’une méthode permettant de comparer deux éléments.

Pour définir l’interface des comparateurs, on utilise une technique similaire à celle utilisée précédemment : l’interface est générique, et le paramètre de type T représente le type des objets que le comparateur sait comparer.

interface Comparator<T> { int compare(T obj1, T obj2);}

Extrait du code du labyrinthe :

public Maze (int width, int height, Tiling pavage) {this.width = width; //...this.pavage = pavage; // méthode passée en argument

11


}

Utilisation :

xLongueur = pavage.xLength(xLongueur);

Equivalent API : java.util.Comparator<T>

L’ordre intrinsèque (ou naturel) est plus léger, dans le sens où il n’est pas nécessaire de passer explicitement la relation d’ordre. Les comparateurs sont plus flexibles, dans le sens où il est possible d’en définir plusieurs pour un seul type d’éléments.

Cours 7 : les ensembles (II)

Dans un arbre de recherche, les opérations de base ont une complexité proportionnelle à la hauteur de l’arbre. Si un arbre de taille n est équilibré, sa hauteur est de l’ordre de log2(n), donc les opérations de base ont une complexité en O(log n).Si un arbre de taille n a dégénéré en liste, sa hauteur est n, donc les opérations de base ont une complexité en O(n).

Un arbre binaire de taille n est complètement équilibré s’il est de hauteur Log2 n arrondi à l'entier inférieur. La taille d’un arbre est son nombre de noeuds. La hauteur d’un arbre est la longueur de sa plus longue branche. Si un arbre est complètement équilibré, sa hauteur est minimale !

Les arbres AVL (AVL trees) sont une forme d’arbres de recherche partiellement équilibrés. Ces arbres ont la particularité d’avoir une hauteur qui est toujours de l’ordre de log n. Ils peuvent ainsi offrir les opérations de base – ajout, suppression et recherche – en O(log n).

Pour quantifier le degré d’équilibrage d’un arbre, on peut définir la fonction δ suivante : δ(noeud(fils gauche, fils droit)) = hauteur(fils gauche) – hauteur(fils droit)

Un arbre binaire est dit Héquilibré si, pour chacun de ses noeuds, δ vaut 1, 0 ou 1. Les arbres AVL sont des arbres binaires de recherche Héquilibrés.Réalisées naïvement, les opérations d’ajout et de suppression dans un arbre AVL peuvent perturber l’équilibre des arbres. Il faut donc prendre garde à rétablir l’équilibre lors de ces opérations, ce qui se fait au moyen d’opérations de rotation.

Il y a trois cas à considérer :

1. h’ = h : dans ce cas, δ = δ’, il n’y a donc rien à faire,

2. h’ = h+1 et δ < 1 : dans ce cas, δ’ vaut 0 ou 1, et il n’y a de nouveau rien à faire

12


3. h’ = h+1 et δ = 1 : dans ce cas il faut utiliser une rotation pour conserver le Héquilibre sans quoi δ’ vaudrait 2. Le type de rotation à effectuer dépend de l’équilibre du sous arbre s’, càd de la valeur de δ s’ qui peut être soit 1, soit +1.

Les arbres rougenoir ou bicolores (redblack trees) sont une autre forme d’arbres binaires de recherche partiellement équilibrés. Comme les arbres AVL, ces arbres ont une hauteur qui est toujours de l’ordre de log n. Ils offrent aussi les opérations de base en O(log n). Les deux invariants suivants sur les couleurs doivent être respectés pour qu’un arbre rougenoir soit valide :

1. aucun noeud rouge n’a un fils rouge

2. tout chemin de la racine à une feuille contient le même nombre de noeuds noirs

Ils garantissent que le plus long chemin est au plus deux fois plus long que le plus court. Comme pour les arbres AVL, les arbres rougenoir peuvent devenir invalides – càd qu’un des deux invariants peut être violé – lors d’opérations d’ajout ou de suppression. Une fois encore, la solution consiste à reéquilibrer les arbres invalides au moyen de rotations après chaque modification. Les rotations utilisées pour les arbres rougenoir sont différentes de celles utilisées pour les AVL.

Equivalent API : java.util.TreeSet<E>

Cours 8 : les ensembles (III)

Le but d’une fonction de hachage est de transformer une valeur d’un certain type en un entier. En se basant sur ces fonctions, on peut stocker des ensembles de valeurs dans des tableaux.

Une table de hachage est un tableau contenant un ensembles d’éléments, dont la position est déterminée au moyen d’une fonction de hachage.

La possibilité de déterminer la position d’un élément en lui appliquant la fonction de hachage permet – sous certaines conditions – de fournir les opérations de base sur l’ensemble de valeurs en O(1).

Une fonction de hachage h(x) est dite parfaite si elle retourne un entier différent pour tous les éléments auxquels on peut l’appliquer. Dans les – rares – cas où l’on connaît à l’avance la totalité des valeurs à hacher, il est possible de trouver et d’utiliser une fonction de hachage parfaite. Dans les autres cas, il faut trouver un moyen pour gérer les collisions de hachage, c’est à dire les cas où plusieurs éléments différents ont la même valeur de hachage. Une solution simple pour gérer ces collisions consiste à stocker des listes de valeurs dans la table, p.ex. des listes chaînées.

13


La mise en oeuvre des tables de hachage est simple :

• on représente la table par un tableau de listes chaînées

• pour rechercher, ajouter ou supprimer un élément, on calcule sa valeur de hachage h puis on recherche, ajoute ou supprime l’élément dans la he liste chaînée

Pour mettre en oeuvre les tables de hachage en Java, il faut pouvoir effectuer deux opérations sur les éléments qu’on y stocke :

1. obtenir la valeur de hachage d’un élément

2. tester si deux éléments sont égaux.

Cela est extrêmement simple, puisque la classe Object possède deux méthodes – hashCode et equals – permettant de le faire. Par défaut, la méthode equals vérifie si deux objets sont physiquement les mêmes – càd s’ils résultent du même new. La méthode hashCode fournit une valeur qui dépend de l’identité de l’objet. Cela signifie que deux objets résultant de deux new différents auront en général une valeur de hachage différente, même si leur contenu est identique !

class MyHashSet<E> {private Node<E>[] table = (Node<E>[])new Node[5];

public boolean contains(E elem) {int h = Math.abs(elem.hashCode()% table.length);for (Node<E> n = table[h]; n != null; n = n.next) {

if (n.elem.equals(elem))return true;

}return false;}

public void remove(E elem) {int h = Math.abs(elem.hashCode() %table.length);Node<E> prev = null, n = table[h];while (n != null && !n.elem.equals(elem)) {prev = n; n = n.next;}if (n != null) {

if (prev == null) table[h] = n.next;else prev.next = n.next;}

}}

14


class Node<E> { public final E elem;public Node<E> next;public Node(E elem, Node<E> next) {this.elem = elem;this.next = next;}

}

Une table de hachage est efficace ssi :

• le tableau n’est pas « plein de trous », sans quoi de la mémoire est gaspillée

• les listes chaînées sont aussi courtes que possible

Pour assurer ces propriétés, il faut s’assurer que le tableau soit toujours de « bonne » dimension. Un tableau de taille fixe tel que nous l’avons utilisé jusqu’à présent ne saurait convenir ! Lorsque le nombre d’éléments présents dans la table atteint un certain seuil, il faut le redimensionner et redistribuer les éléments, afin de s’assurer que les listes chaînées gardent une taille raisonnable. Cette opération s’appelle rehachage. Pour savoir quand faire un rehachage, on définit la notion de facteur de charge (load factor). Le facteur de charge d’une table de hachage est le rapport entre le nombre d’éléments qu’elle contient et sa capacité – càd la taille du tableau sousjacent. Par exemple, une table ayant une capacité de 100 et contenant 75 éléments a un facteur de charge de 0,75.

Equivalent API : java.util.HashSet<E>

Cours 9 : tables associatives

Une table associative ou dictionnaire (map, dictionary) est une structure de données associant des valeurs à des clefs.

Listes associatives :

class Entry<K,V> {public final K key;public V value;public Entry(K key, V value) {this.key = key;this.value = value;}

}

import java.util.*;

15


class MyAList<K,V> implements MyMap<K,V> {private List<Entry<K,V>> list = new LinkedList<Entry<K,V>>();

public V get(K key) {for (Entry<K,V> p : list)if (key.equals(p.key))return p.value;return null;}

public void put(K k, V v) {//...}

public void remove(K k) {//...}

}

Arbres de recherche :

En gras, les modifications par rapport à la version nongénérique et non « table associative » vue précédemment.

class MyTreeMap<K extends Comparable<K>,V> implements MyMap<K,V> {private Tree<K,V> root = new Leaf<K,V>();

public V get(K key) { return root.get(key); }

public void put(K key, V value) {root = root.put(key, value);}

public void remove(K key) {root = root.remove(key);}

}

abstract class Tree<K extends Comparable<K>,V> {abstract V get(K key);abstract Tree<K,V> put(K key, V value);abstract Tree<K,V> remove(K key);abstract Pair<K,V> min();abstract boolean isLeaf();

}

class Leaf<K extends Comparable<K>,V> extends Tree<K,V> {

16


V get(K key) { return null; }

Tree<K,V> put(K key, V value) {return new Node<K,V>(key, value,new Leaf<K,V>(),new Leaf<K,V>());}

Tree<K,V> remove(K key) { return this; }

Pair<K,V> min() { throw new Error(); }

boolean isLeaf() { return true; }}

class Node<K extends Comparable<K>,V> extends Tree<K,V> {private final K k;private V v;private Tree<K,V> s, g;public Node(K k, V v, Tree<K,V> s, Tree<K,V> g) {this.k = k; this.v = v;this.s = s; this.g = g;}

V get(K key) {int comp = key.compareTo(k);if (comp > 0)return s.get(key);else if (comp > 0)return g.get(key);elsereturn v;}

Tree<K,V> put(K key, V value) {int comp = key.compareTo(k);if (comp < 0)s = s.put(key, value);else if (comp > 0)g = g.put(key, value);else v = value;return this;}

Tree<K,V> remove(K key) {int comp = key.compareTo(k);if (comp < 0) {s = s.remove(key);return this;} else if (comp > 0) {

17


g = g.remove(key);return this;} else {if (g.isleaf()) return s;else if (s.isleaf()) return g;else {Pair<K,V> min = g.min();return new Node<K,V>(min.fst,min.snd,s,g.remove(min.fst));}

Pair<K,V> min() {return s.isLeaf() ? new Pair<K,V>(k,v) : s.min();}

boolean isLeaf() { return false; }}

Tables de hachage :

class MyHashMap<K,V> implements MyMap<K,V> {private MyAList<K,V>[] table = (MyAList<K,V>[])new MyAList[10];

public V get(K key) {int h = Math.abs(key.hashCode())% table.length;MyAList<K,V> l = table[h];return l == null ? null : table[h].get(key);}

//Etrangement, la méthode contains a disparu et les méthodes//put et remove sont sensiblement différentespublic void put(K key, V value) {int n = Math.abs(key.hashCode())%table.length;MyAList<K,V> l = table[n];if (l == null)table[n] = (l = new MyAList<K,V>());l.put(key,value);}

public void remove (K key) {int n = Math.abs(key.hashCode())%table.length;if (table[n] == null)table[n].remove(key);}

}

Equivalent API : java.util.Map<K,V>,java.util.TreeMap, java.util.HashMap.

18


Utilisation de hashMap :

class Date {final int year, month, day;public Date(int year, int month, int day) {this.year=year; this.month=month; this.day=day;}

@Override public boolean equals(Object that) {//En ajoutant @Override devant une déclaration de méthode //

vous indiquez que celle-ci est censée surcharger une //méthode parente. Si aucune super méthode correspondante ne //peut être trouvée, une erreur de compilation est lancée.

return that instanceof Date && ((Date)that).year == year && ((Date)that).month == month && ((Date)that).day == day;}

@Override public int hashCode() {return (((year << 4) | (month << 5) | day;// | : Retourne 1 si l'un ou l'autre des deux bits de même //poids est à 1 (ou les deux) // << : Décale les bits vers la gauche (multiplie par 2 à //

chaque décalage). Les bits qui sortent à gauche sont //perdus, tandis que des zéros sont insérés à droite

}}

Map<Date,String> diary = new HashMap<Date,String>();diary.put(new Date(2006,5,3), "Cours Prog. II");diary.put(new Date(2006,5,25), "Ascension");diary.put(new Date(2006,12,25), "Noël");// retourne "Ascension"diary.get(new Date(2006,5,25));// retourne nulldiary.get(new Date(2006,2,12));

Utilisation de TreeMap (ordre naturel):

class Person implements Comparable<Person> {public final String fName, lName;public Person(String fName, String lName) {this.fName = fName; this.lName = lName;}

public int compareTo(Person that) {int lNameComp = lName.compareTo(that.lName);return lNameComp == 0 ? fName.compareTo(that.fName) : lNameComp;

19


}}

Map<Person,String> dir = new TreeMap<Person,String>();dir.put(new Person("Jean","Dupond"), "079 132 57 92");dir.put(new Person("Jeanne","Dupond"), "079 225 54 78");dir.put(new Person("Jean","Durand"), "079 228 44 48");// retourne "079 225 54 78"dir.get(new Person("Jeanne","Dupond"))// retourne nulldir.get(new Person("Maurice","Rapin"))

Utilisation de TreeMap (comparateur) :

class PartialDate {public final int year, month;public PartialDate(int year, int month) {this.year = year;this.month = month;}

}

class PDComp implements Comparator<PartialDate> {public int compare(PartialDate d1,PartialDate d2) {if (d1.year < d2.year) return -1;else if (d1.year > d2.year) return 1;else {if (d1.month < d2.month) return -1;else if (d1.month > d2.month) return 1;else return 0;}}

}

Map<PartialDate,String> history = new TreeMap<PartialDate,String>(new PDComp());history.put(new PartialDate(1791, 12),"Naissance de Charles Babbage");history.put(new PartialDate(1969, 7), "Premier atterrissage sur la lune");history.put(new PartialDate(1977, 6),"Vente des premiers Apple II");// retourne "Naissance de Charles Babbage"history.get(new PartialDate(1791, 12));

Cours 11 : modèles de conception (I)

20


Iterator :

Illustration : Une classe représentant une liste d’éléments doit fournir un moyen de parcourir ces éléments les uns après les autres.

Solution : Pour permettre le parcours des éléments d’une liste sans exposer sa représentation interne, on peut utiliser un objet qui désigne à tout moment un élément de la liste. Cet objet possède des opérations permettant d’obtenir l’élément désigné et de passer à l’élément suivant, voire au précédent.

class MyLinkedList<E> {private Node<E> head;

public void add(int index, E elem) { … }public E get(int index) { … }public void remove(int index) { … }

public MyIterator<E> iterator() {return new MyLLIterator<E>(head);}

}

class Node<E> {public final E elem;public Node<E> next;public Node(E elem, Node<E> next) { … }

}

interface MyIterator<E> {boolean hasNext();E next();

}

class MyLLIterator<E> implements MyIterator<E> {private Node<E> next;public MyLLIterator(Node<E> first) {next = first;}

public boolean hasNext() {return next != null;}

public E next() {next = next.next;return next;

21


}}

MyLinkedList<Integer> l = new MyLinkedList<Integer>();l.add(0,2);l.add(1,3);l.add(2,5);MyIterator<Integer> it = l.iterator();while (it.hasNext()) {System.out.println(it.next());}

Singleton :

Illustration : Dans un jeu, on trouve habituellement une table des meilleurs scores obtenus (high scores). Pour représenter cette table, il est probable qu’un programmeur décide de définir une classe HighScores. Or il est capital de garantir qu’il n’existe qu’une seule instance de cette classe à l’exécution, sans quoi les résultats sont faussés.

Solution : En Java, une manière propre de garantir qu’il n’existe qu’une seule instance d’une classe consiste à :

• déclarer le constructeur de la classe comme étant privé, ce qui interdit la création d’instances depuis l’extérieur de celleci

• fournir une méthode statique qui retourne l’instance unique, en la créant au besoin.

public class HighScores {// l’instance unique, créée paresseusementprivate static HighScores instance = null;

// interdit les instanciations externesprivate HighScores() { }

// retourne l’instance unique, en la créant au besoinpublic static HighScores getInstance() {if (instance == null)instance = new HighScores();return instance;}

public void addScore(String playerName, int score) {// ...}

}

22


Pour utiliser la table des scores, tous les clients sont obligés de passer par la méthode fournissant l’instance unique :

HighScores hs = HighScores.getInstance();hs.addScore(playerName, playerScore);

Cours 12 : modèles de conception (II)

Adapter :

Illustration : Admettons que nous disposons d’une méthode permettant de mélanger une liste d’éléments : void shuffleList(List<?> list) { … }Estil possible d’utiliser cette méthode pour mélanger un tableau Java ?

Solution : Pour permettre l’utilisation d’un tableau Java là où une liste est attendue, il suffit d’écrire une classe qui adapte le tableau en le présentant comme une liste. Cette classe doit implémenter l’interface List de java.util et effectuer les opérations de cette interface directement sur le tableau qu’elle adapte.

import java.util.List;class ArrayAdapter<E> implements List<E> {

private E[] array;public ArrayAdapter(E[] array) {this.array = array;}

public E get(int index) {return array[index];}

// ... les 22 autres méthodes de List}

void shuffleList(List<?> list) { … }String[] array = …;List<String> adaptedArray = new ArrayAdapter<String>(array);// « convertit » le tableau en listeshuffleList(adaptedArray);// mélange les éléments de array.

Equivalent API : asList (java.util.Arrays, transforme le tableau pour qu'il puisse être utilisé comme une liste)

Interlude – la classe AbstractList :

Dans la bibliothèque Java, on trouve des interfaces qui définissent des méthodes

23


documentées comme correspondant à des opérations optionnelles. Ces méthodes ont la particularité suivante : une classe implémentant l’interface qui les définit « a le droit » de leur faire simplement lever l’exception UnsupportedOperationException.

Dans la bibliothèque Java, les méthodes qui modifient les structures de données sont en général optionnelles. Cela permet la définition de structures de données non modifiables. Ainsi, la méthode remove de l’interface Iterator est optionnelle, de même que les méthodes add, addAll, clear, remove, removeAll, retainAll et set de l’interface List.

L’interface List possède plusieurs méthodes qui sont facilement exprimables en fonction de méthodes « de base ».

Par exemple, au moyen de la méthode size il est trivial de fournir la méthode isEmpty :

public boolean isEmpty() {return size() == 0;}

La classe AbstractList nous permet d’écrire beaucoup plus simplement notre adaptateur pour tableaux. Au lieu de définir les 23 méthodes de l’interface List, il nous suffit d’hériter d’AbstractList et de définir les trois méthodes de base requises : get, set et size. C’est tout !

Factory Method :

Illustration : Plusieurs jeux récents sont extensibles par programmation : l’utilisateur a la possibilité de modifier ou améliorer certains de leurs aspects en écrivant du code. Dans un langage orientéobjets, une manière naturelle de permettre ce genre d’extensions consiste à laisser l’utilisateur définir ses propres sousclasses des classes principales du jeu.Pour rendre le problème plus concret, imaginons un jeu dans lequel chaque joueur possède un bateau, modélisé par une classe Ship. Afin d’étendre le jeu, un utilisateur pourrait définir sa propre sousclasse de Ship, p.ex. MagicShip. Une question se pose alors : comment s’assurer que tous les bateaux créés lors du jeu soient des instances de MagicShip et pas de Ship ?

Solution : Afin de résoudre ce problème, une solution est de définir une méthode dans la classe Game pour créer un nouveau bateau, puis de l’utiliser systématiquement à la place de l’opérateur new. Cette méthode peut être redéfinie dans une sousclasse afin de créer un autre type de bateau. Une telle méthode est appelée une méthode fabrique (factory method) ou constructeur virtuel (virtual constructor).

class Game {Ship newShip() { return new Ship(); }

public Game(int pCount) {Player[] players = new Player[pCount];

24


Ship[] ships = new Ship[pCount];for (int i = 0; i < pCount; ++i) {players[i] = new Player();ships[i] = newShip();ships[i].setPosition(...);ships[i].setOwner(players[i]);}// ... initialisation complète du jeu}

}class MagicShip extends Ship {// ...}class MyGame extends Game {

@Override Ship newShip() {return new MagicShip();}

public MyGame(int playersCount) {super(playersCount);}

}

Abstract Factory :

Illustration : Continuons avec notre exemple de jeu extensible, mais en imaginant une situation plus complexe. Plutôt que de n’avoir que la seule classe Ship qui soit extensible par l’utilisateur, imaginons que nous en ayons trois: Ship, Treasure et Island. Posonsnous la même question qu’avant : comment s’assurer que chaque fois qu’un bateau, trésor ou île est créé, la bonne classe est utilisée ?

Solution : Une solution consiste bien entendu à définir trois méthodes fabriques dans la classe Game. Toutefois, lorsque le nombre de méthodes fabriques commence à devenir important, il peut devenir préférable de les extraire de la classe Game pour les mettre dans une interface séparée. Une telle interface, qui ne contient que des méthodes fabriques, est appelée fabrique abstraite (abstract factory)

Pour notre exemple, la fabrique abstraite se présente ainsi :

interface GameFactory {//fabrique abstraiteShip newShip();Island newIsland();Treasure newTreasure();

}

class Game {

25


private final Ship[] ships;private final Island[] islands;private final Treasure[] treasures;public Game(GameFactory factory) {ships = new Ship[] {factory.newShip(), … };islands = new Island[] {factory.newIsland(), … };treasures = new Treasure[] {factory.newTreasure(), … };}

}

class MagicShip extends Ship { … }class MagicIsland extends Island { … }class MagicTreasure extends Treasure { … }class MagicGameFactory implements GameFactory {

public Ship newShip(){ return new MagicShip(); }

public Island newIsland(){ return new MagicIsland(); }

public Treasure newTreasure(){ return new MagicTreasure(); }}

Pour obtenir une version magique du jeu, il suffit de créer une instance de la classe Game en lui passant la fabrique correspondante :

// Classe principale de la version magique du jeu.class MagicGameMain {

public static void main(String[] args) {// crée et démarre le jeunew Game(new MagicGameFactory());}

}

Interlude – classes imbriquées :

La classe MagicGameFactory de notre exemple n’est utilisée qu’une seule fois dans tout le programme – lors de la création d’une de ses instances, passée au constructeur de Game : new Game(new MagicGameFactory()). Il peut sembler superflu de rendre une telle classe visible à l’ensemble du programme. Pour éviter de rendre MagicGameFactory visible à tous, on peut l’imbriquer dans Main :

class Main {private static class MagicGameFactory implements GameFactory

{// ... comme avant}

public static void main(String[] args) {new Game(new MagicGameFactory());

26


}}

Cours 13 : modèles de conception (III)

Strategy :

Illustration : Admettons que nous désirions écrire une méthode de tri permettant de trier des listes d’éléments quelconques : <E> void sort(List<E> list).

Pour que cette méthode soit flexible, il faut que l’utilisateur puisse spécifier l’ordre à utiliser pour le tri. En effet, même pour un type comme les chaînes de caractères il existe plusieurs ordres possibles.

Solution : La solution consiste bien entendu à utiliser un comparateur pour spécifier l’ordre de tri. Pour ce faire, il suffit d’ajouter un paramètre représentant ce comparateur à notre méthode : <E> void sort(List<E> list, Comparator<E> comparator)

Chaque fois que la méthode de tri doit comparer deux éléments, elle utilise le comparateur.

class StringLengthFirstComparator implements Comparator<String> {public int compare(String s1, String s2){int d = s1.length() - s2.length();return d != 0 ? d : s1.compareTo(s2);}

}

Chaque fois qu’une partie d’un algorithme doit être interchangeable, il est possible de la représenter au moyen d’un objet. Dans notre exemple, la comparaison de deux objets était la partie variable de l’algorithme de tri, et le comparateur était l’objet la représentant.

Decorator :

Illustration : Comme nous venons de le voir, la méthode sort de la bibliothèque Java permet de trier une liste selon un ordre spécifié par un comparateur. Cette méthode trie la liste dans l’ordre croissant. Toutefois, il peut être parfois utile de la trier par ordre décroissant. Etant donnés une liste et un comparateur pour les éléments de cette liste, comment peuton trier la liste par ordre décroissant ?

Solution : Pour trier la liste par ordre décroissant selon un comparateur C, il suffit de passer à la méthode sort un comparateur qui soit l’inverse de C. Nous dirons que deux comparateurs C1 et C2 sont inverses l’un de l’autre si C1 retourne une valeur positive quand C2 en retourne une négative, et inversement. Peuton programmer une méthode qui, étant donné un comparateur, retourne son inverse ? Pour pouvoir définir une telle méthode, la première chose à faire est de définir un nouveau type de comparateur, qui se

27


comporte comme l’inverse d’un autre comparateur. Cela s’avère assez simple : la méthode de comparaison de notre inverseur de comparateur doit appeler celle du comparateur d’origine en échangeant les arguments.

class InvComparator<E> implements Comparator<E> {private Comparator<E> c;public InvComparator(Comparator<E> c) {this.c = c;}

public int compare(E s1, E s2) {return c.compare(s2, s1);}

}

<E> Comparator<E> inv(Comparator<E> c) {return new InvComparator<E>(c);}

Pour trier une liste par ordre décroissant, on peut alors définir la méthode suivante :

<E> void invSort(List<E> l, Comparator<E> c) {Collections.sort(l, inv(c));}

Cette méthode utilise la méthode de tri de la bibliothèque Java, en inversant au préalable le comparateur passé en argument.

Interlude Entrée/Sortie :

Java distingue deux genres de flots, en fonction du type de données qu’ils transportent : les flots de caractères et les flots d’octets. Les flots de caractères sont représentés par les classes Reader (entrée) et Writer (sortie) et leurs sousclasses. Les flots d’octets sont représentés par les classes InputStream (entrée) et OutputStream (sortie), ainsi que leurs sousclasses.

// Détermine si un fichier est un fichier classe Javapublic static void main(String[] args) {

try {FileInputStream s = new FileInputStream(args[0]);byte[] b = new byte[4];int read = s.read(b); //met chaque bit dans une celluleboolean isClassFile = (read == b.length && b[0] == (byte)0xCA && b[1] == (byte)0xFE && b[2] == (byte)0xBA && b[3] == (byte)0xBE); //compare bit à bitSystem.out.println(isClassFile);s.close();

28


} catch (IOException e) {e.printStackTrace();}

}

// Création d’un fichier compressé contenant 100000 nombres // aléatoires.FileOutputStream fos = new FileOutputStream("rand.gz");GZIPOutputStream zos = new GZIPOutputStream(fos);BufferedOutputStream bos = new BufferedOutputStream(zos);PrintStream ps = new PrintStream(bos);Random r = new Random();for (int i = 0; i < 100000; ++i)ps.println(r.nextInt());ps.close();

Composite :

Illustration : Dans un programme de gestion de base de données, il est fréquent de laisser l’utilisateur spécifier un ordre pour trier les données. Cet ordre peut généralement comporter plusieurs critères. Par exemple, on peut vouloir d’abord trier par nom de famille, puis par prénom. En interne, un ordre simple peut être représenté par un comparateur. Mais comment représenter les ordres composés de plusieurs critères ?

Solution : Une solution consiste à définir une classe pour représenter un « macrocomparateur » composé de deux comparateurs C1 et C2 à appliquer en séquence. Si le C1 déclare que les objets à comparer sont différents, on utilise son résultat, sinon on utilise celui de C2. Pour qu’un tel macrocomparateur soit utilisable comme les autres, il faut qu’il implémente l’interface Comparator.

class SeqComparator<E> implements Comparator<E> {private final Comparator<E> c1, c2;public SeqComparator(Comparator<E> c1,Comparator<E> c2) {this.c1 = c1; this.c2 = c2;}

public int compare(E e1, E e2) {int c = c1.compare(e1, e2);return c != 0 ? c : c2.compare(e1, e2);}

}

class StringLengthComparator implements Comparator<String> {public int compare(String s1, String s2){return s1.length() - s2.length();}

29


}

class StringLexicalComparator implements Comparator<String> {public int compare(String s1, String s2){return s1.compareTo(s2);}

}

Comparator<String> c1 = new StringLengthComparator();Comparator<String> c2 = new StringLexicalComparator();Comparator<String> c = new SeqComparator<String>(c1, c2);

Cours 14 : modèles de conception (IV)

Observer :

Illustration : Le contenu d’une cellule contenant une formule doit être mis à jour dès que le contenu d’une cellule dont elle dépend change. Comment organiser le programme pour garantir que la mise à jour soit faite ?

Solution : Une solution consiste à permettre aux cellules d’en observer d’autres. Lorsque la valeur d’une cellule change, toutes les cellules qui l’observent sont informées du changement. Une cellule contenant une formule observe la ou les cellules dont elle dépend – càd celles qui apparaissent dans sa formule. Lorsqu’elle est informée du changement d’une d’entreelles, elle met à jour sa propre valeur.

interface Observer {void update(Subject s);

}

import java.util.*;

class Subject {private Set<Observer> observers = new HashSet<Observer>();

public void addObserver(Observer o){ observers.add(o); }public void removeObserver(Observer o){ observers.remove(o); }

protected void notifyObservers() {for (Observer o: observers)o.update(this);}

}

30


class Cell extends Subject {private double value = 0.0;

public double getValue() {return value;}

public void setValue(double newValue) {if (newValue != value) {value = newValue;notifyObservers();}}

}

class SumCell extends Cell implements Observer {private Cell c1, c2;

public SumCell(Cell c1, Cell c2) {this.c1 = c1; this.c2 = c2;c1.addObserver(this);c2.addObserver(this);setValue(c1.getValue()+c2.getValue());}

public void update(Subject s) {setValue(c1.getValue()+c2.getValue());}

}

class SpreadSheet implements Observer {public SpreadSheet() {Cell A1 = new Cell(), A2 = new Cell();A1.addObserver(this); // ... A2Cell A3 = new SumCell(A1, A2);A3.addObserver(this); // ... B1-B3, C3A1.setValue(10); // ...}

public void update(Subject s) {Cell c = (Cell)s;System.out.println("nouvelle valeur " + "pour " + c + ":" + c.getValue());

}}

Swing :

31


public class SwingExample2 extends JFrame {//modèle observerprivate static class QuitListener implements ActionListener {

public void actionPerformed(ActionEvent event) {System.exit(0);}

}

public SwingExample2() {setDefaultCloseOperation(EXIT_ON_CLOSE);//modèle strategyJPanel mainPanel = new JPanel();mainPanel.setLayout(new BoxLayout(mainPanel, BoxLayout.PAGE_AXIS));JLabel helloLabel = new JLabel("Bonjour tout le monde !");//modèle factoryBorder out = BorderFactory.createEmptyBorder(3,3,3,3);Border in = BorderFactory.createRaisedBevelBorder();Border border = BorderFactory.createCompoundBorder(out, in);helloLabel.setBorder(border);mainPanel.add(helloLabel);//modèle observerJButton quitButton = new JButton("Quitter");quitButton.addActionListener(new QuitListener());//modèle compositemainPanel.add(quitButton);setContentPane(mainPanel);

getContentPane().add(quitButton);pack();setVisible(true);

}

public static void main(String[] args) {new SwingExample2();}

}

interlude classes anonymes :

Java offre la notion de classe anonyme (anonymous class), classe sans nom, définie dans le contexte d’un énoncé new. Une telle classe est définie en spécifiant le nom de sa superclasse (ou interface), les paramètres du constructeur de cette classe, et son corps.

quitButton.addActionListener(new ActionListener() {public void actionPerformed(ActionEvent event) {System.exit(0);}

32


});

Cours 15 : techniques de développement

conception de contrat :

Toutes les méthodes d’un programme font des hypothèses concernant leurs arguments – y compris l’argument implicite this. Ces hypothèses concernant les valeurs avant un appel sont appelées préconditions.

Les utilisateurs d’une méthode font des hypothèses sur la valeur de retour ou l’état de l’objet après l’appel.Ces hypothèses concernant les valeurs après un appel sont appelées postconditions.

Certaines propriétés sont supposées vraies pendant une période donnée – p.ex. Durant l’exécution d’une boucle, voire de tout le programme. On appelle invariants de telles conditions.

L’idée d’annoter les programmes avec de telles hypothèses (pré et postcondition) se nomme conception par contrats.

Les annotations – pré et postconditions,invariants – attachées aux éléments d’unprogramme ont deux intérêts majeurs :

1. elles constituent un contrat entre la personne qui écrit une partie de programme – classe, méthode, etc. – et celle qui l’utilise

2. elles peuvent automatiquement être vérifiées à l’exécution, et une erreur signalée dès que l’une d’elles est violée.

Java ne gère pas la conception par contrat.

Une assertion est une hypothèse concernant les valeurs du programme, exprimée sous la forme d’une expression booléenne qui doit être vraie. Par exemple, l’hypothèse que l’argument de la factorielle est un entier positif s’exprime ainsi :

int fact(int x) {assert x >= 0;return (x == 0) ? 1 : x * fact(x - 1);}

Lorsqu’on le demande explicitement – au moyen de l’option enableassertions – Java vérifie lors de l’exécution que toutes les assertions sont vraies. Si l’une d’elle ne l’est pas, l’exception java.lang.AssertionError est levée.

33


Lorsque la vérification des assertions n’est pas demandée, Java les ignore tout simplement. Cela peut être utile si l’on désire que le programme s’exécute aussi rapidement que possible.

Il est possible d’associer un message à une assertion. En cas de violation, ce message est attaché à l’exception AssertionError, et apparaît ainsi à l’écran.

assert x >= 0 : "paramètre négatif: "+x;

Test par Unité :

Tout programme conséquent est composé de plusieurs unités, qui doivent idéalement être aussi indépendantes que possible les unes des autres. Une unité est composée d’un petit nombre de classes indissociables.

Par exemple, dans le projet Labyrinthe on peut distinguer plusieurs unités : la classe de mélange, la classe représentant les ensembles disjoints, etc. L’idée du test par unité (unit testing) consiste à écrire de petits programmes s’assurant que chaque unité se comporte comme elle le devrait.

JUnit (http://junit.org/) est une bibliothèque Java facilitant l’écriture de tests d’unité. Elle fournit des méthodes pour tester que certaines conditions sont satisfaites, et signaler une erreur dans le cas contraire. Pour tester une unité à l’aide de JUnit, il convient de définir une classe de test contenant un certain nombre de méthodes de test. Une telle méthode se reconnaît à l’attribut @Test qu’on lui attache. La méthode de test se doit normalement d’utiliser une ou plusieurs méthodes fournies par Junit, vérifiant qu’une condition est vraie ou fausse.

public class Shuffler {public Shuffler(Random rand);public <E> void shuffle(ArrayList<E> a);}Définissons un ensemble de tests pour cette classe...

1. le tableau mélangé doit toujours être une permutation du tableau original,

import java.util.*;import org.junit.Test;import static org.junit.Assert.*;

@Test public void producesSomePermutation() {Shuffler shuffler = new Shuffler(new Random());String[] arr = new String[] {"Jean", "Marie", "Marc", "Louise", "Marcel", "Sylvie"};

34


ArrayList<String> original =new ArrayList<String>(Arrays.asList(arr));ArrayList<String> shuffled =new ArrayList<String>(Arrays.asList(arr));shuffler.shuffle(shuffled);Collections.sort(original);Collections.sort(shuffled);assertEquals("does not produce a permutation",original, shuffled);}

2. toutes les permutations possibles du tableau doivent apparaître avec une probabilité égale.

Import //blablabla...

@Test public void producesAllPermutations() {Shuffler shuffler = new Shuffler(new Random());boolean gotId = false, gotInv = false;

for (int i = 0; i < 10000 && !(gotId && gotInv); ++i) {ArrayList<Integer> a =new ArrayList<Integer>(Arrays.asList(1,2));shuffler.shuffle(a);

//controle si après mélange le tableau de base est égale au //nouveau tableauif (a.get(0) == 1 && a.get(1) == 2)gotId = true;

//controle si après mélange le tableau de basee est l'inverse du //nouveau tableauelse if (a.get(0) == 2 && a.get(1) == 1)gotInv = true;

}

assertTrue("identity permutation not produced", gotId);assertTrue("reverse permutation not produced", gotInv);}

Pour effectuer les tests, on peut soit utiliser l’interface à JUnit contenue dans certains environnements de programmation comme Eclipse, soit passer par le terminal :

> java org.junit.runner.JUnitCore ShufflerTest JUnit version 4.1..Time: 0.068OK (2 tests)

35


On ne peut pas prouver qu'un programme n'a pas de bugs.

Refactorisation :

Il est souvent utile de transformer un programme afin d’améliorer sa structure interne, sans toutefois modifier son comportement. Ces transformations ont pour but de rendre le programme plus facile à lire ou à modifier par la suite. Ce processus se nomme refactorisation (refactoring).

Un exemple trivial de refactorisation est le renommage d’une entité – classe, méthode,variable, paramètre, etc.

Mêmes lorsqu’elles sont en principe triviales, certaines transformations sont parfois difficiles à effectuer en pratique sur un gros programme. Par exemple, renommer une méthode est rendu pénible par le fait qu’il faut trouver tous les endroits où cette méthode est utilisée – càd appelée ou redéfinie. Cela est particulièrement difficile lorsque la méthode porte un nom commun, p.ex. Get.

Récemment, plusieurs environnement de programmation ont commencé à offrir des outils de refactorisation qui « comprennent » le programme édité.

Il est important néanmoins d'avoir conscience que les programmes peuvent refactoriser de façon fausse. Il est donc nécessaire de vérifier le travail effectué après coup.

36

Documents

l Burgener – Section Informatique Résumé : Programmation II