Interface collectionsinter

Conception par Conception par Objet et Objet et

Programmation Programmation JavaJava

1

Plan du coursPlan du coursSéance

sChapitres

1 Introduction à Java

2 Classe et objet

3 Encapsulation

4 Héritage

5 Polymorphisme

6 Exceptions

7 Interface et collection8 Interface graphique

2

Contenu du coursContenu du coursLes interfacesGénéralités sur les collectionsCollections

– classe la plus utilisée : ArrayList<E>

– interface Iterator<E> (énumérer les éléments d’une collection) et Iterable<E>

Maps– classe la plus utilisée : HashMap<K,V>

Utilitaires : trier une collection et rechercher une information dans une liste triée

3

Rappel sur l’héritageRappel sur l’héritageProgrammation objet réutilisation

du code héritage

Avec l'héritage multiple, une classe peut hériter en même temps de plusieurs super classes.

!!Ce mécanisme n'existe pas en Java!!

◦Solution : les interfaces

5

Les interfaces Les interfaces Déclaration d’une Déclaration d’une interface :interface :

• Une interface est un ensemble d'opérations utilisé pour spécifier unservice offert par une classe.

• Une interface est un ensemble de constantes et de déclarations de méthodes correspondant un peu à une classe abstraite.

import java.awt.*;public interface Dessinable { public void dessiner(Graphics g); void effacer(Graphics g);}

• Toutes les méthodes sont implicitement abstraites et publiques

• Possibilité de définir des attributs à condition qu’il s’agisse d ’attributs de type primitif

• Ces attributs sont implicitement déclarés comme static final(Constante)Dessinable.java

Opérations abstraites

Interfaces«interface»

Dessinabledessiner(g : Graphics)effacer(g: Graphics)

6

Les interfaces Les interfaces « réalisation » d’une « réalisation » d’une interfaceinterface•C'est une sorte de standard auquel une classe peut répondre. Tous les

objets qui se conforment à cette interface (qui implémentent cette interface) possèdent les méthodes et les constantes déclaréees dans celle-ci. Plusieurs interfaces peuvent être implémentées dans une même classe.

7

Les interfaces Les interfaces « réalisation » d’une « réalisation » d’une interfaceinterface

• De la même manière qu'une classe étend sa super-classe elle peut de manière optionnelle implémenter une ou plusieurs interfaces

dans la définition de la classe, après la clause extends nomSuperClasse, faire apparaître explicitement le mot clé implements suivi du nom de l'interface implémentée

class RectangleDessinable extends Rectangle implements Dessinable {

public void dessiner(Graphics g){g.drawRect((int) x, (int) y, (int) largeur, (int)

hauteur);}public void effacer(Graphics g){

g.clearRect((int) x, (int) y, (int)largeur, (int) hauteur);

}}

si la classe est une classe concrète elle doit fournir une implémentation (un corps) à chacune des méthodes abstraites définies dans l'interface (qui doivent être déclarées publiques)

8

Les interfaces Les interfaces « réalisation » d’une « réalisation » d’une interfaceinterface

• Une classe JAVA peut implémenter simultanément plusieurs interfaces

Pour cela la liste des noms des interfaces à implémenter séparés par des virgules doitsuivre le mot clé implements

class RectangleDessinable extends Rectangle implements Dessinable,Comparable {

public void dessiner(Graphics g){g.drawRect((int) x, (int) y, (int) largeur, (int) hauteur);

}public void effacer(Graphics g){

g.clearRect((int) x, (int) y, (int)largeur, (int) hauteur);}public int compareTo(Object o) {

if (o instanceof Rectangle)...

}}

Méthodes de l’interfaceComparable

Méthodes de l ’interfaceDessinable

9

Les interfaces Les interfaces Interface et Interface et polymorphismepolymorphisme

• Une interface peut être utilisée comme un type

- A des variables (références) dont le type est une interface il est possible d'affecter des instances de toute classe implémentant l'interface, ou toute sous-classe d'une telle classe.public class Fenetre {

private nbFigures; private Dessinable[] figures; ... public void ajouter(Dessinable d){ ... } public void supprimer(Dessinable o){ ... } public void dessiner() { for (int i = 0; i < nbFigures; i++) figures[i].dessiner(g); }}

Dessinable d;…d = new RectangleDessinable(…);...d.dessiner(g);d.surface();

permet de s’intéresser uniquement àcertaines caractéristiques d’un objet

règles du polymorphisme s’appliquent dela même manière que pour les classes :• vérification statique du code• liaison dynamique

10

Les interfaces Les interfaces Héritage d’interfaceHéritage d’interface

De la même manière qu'une classe peut avoir des sous-classes, une interface peut avoir des "sous-interfaces" Une sous interface

- hérite de toutes les méthodes abstraites et des constantes de sa "super-interface"

- peut définir de nouvelles constantes et méthodes abstraites

interface Set extends Collection{...}

Une classe qui implémente une interface doit implémenter toutes les méthodesabstraites définies dans l'interface et dans les interfaces dont elle hérite.

11

Les interfaces Les interfaces Héritage d’interfaceHéritage d’interface

A la différence des classes une interface peut étendre plus d'une interface à la fois

représente une connexion ouverte vers une entité telle qu’un dipositif hardware, un fichier, une “socket” réseau, ou tout composant logiciel capable de réaliser une ou plusieurs opérations d’entrée/sortie.

package java.nio;interface ByteChannel extends ReadableByteChanel, WriteableByteChanel {}

12

Les interfaces Les interfaces InterêtInterêt

• Les interfaces permettent de s ’affranchir d ’éventuelles contraintesd’héritage.

- Lorsqu’on examine une classe implémentant une ou plusieursinterfaces, on est sûr que le code d’implémentation est dans le

corps de la classe. Excellente localisation du code (défaut de l’héritage multiple, sauf si on hérite de classes purement abstraites).

Permet une grande évolutivité du modèle objet

Les interfaces Les interfaces

13

abstract class Animal { ... abstract void talk();}

class Dog extends Animal { ... void talk() { System.out.println("Woof!"); }}

class Bird extends Animal { ... void talk() { System.out.println("Weet"); }}

class Cat extends Animal { ... void talk() { System.out.println(« Miaw!"); }}

Polymorphisme signifie qu’une référence d’untype (classe) donné peut désigner un objet den’importe quelle sous classe et selon nature decet objet produire un comportement différent

Animal animal = new Dog();...animal = new Cat();

animal peut être un Chien, un Chat oun’importe quelle sous classe d ’Animal

En JAVA le polymorphisme est rendu possiblepar la liaison dynamique (dynamic binding)

class Interrogator { static void makeItTalk(Animal subject) { subject.talk(); }}

JVM décide à l’exécution (runtime) quelle méthodeinvoquer en se basant sur la classe de l’objet

Exemple :Exemple :

14

Les interfaces Les interfaces Exemple :Exemple :

Comment utiliser Interrogator pour faire parler aussi un CuckooClock ?abstract class Animal { ... abstract void talk();}




abstract class Robot{ ...

}

class Humanoïde{ ... void talk() { System.out.println(« cuckoo »); }}

Pas d’héritage multiple

Faire passer CuckooClock

dans la hiérarchie d’animal?


class HumanoîdeInterrogator { static void makeItTalk(Humanoïde subject) { subject.talk(); }}

Se passer du polymorphisme

?

15

Les interfaces Les interfaces Exemple :Exemple :

abstract class Animal implements Talkative { ... abstract void talk();}




abstract class Robot{ ...

}

class Humanoïde implements Talkative {void talk() { System.out.println(« cuckoo »); }}


interface Talkative { public void talk();}

Association de ce type à différentes classes de la hiérarchie d’héritage

Tolkative

Utilisation de ce type abstrait

Définition d’un type abstrait (interface)

Les interfaces permettent plus de polymorphisme car avec les interfaces il n’est pas nécessaire de tout faire rentrer dans une seule famille (hiérarchie) de classe

16

Les collections Les collections IntroductionIntroduction

• Collection :objet (conteneur) qui regroupe de multiples éléments dans une

seule structure.

• Utilisation de collections pour- stocker, rechercher et manipuler des données- transmettre des données d ’une méthode à une autre

Exemples :- un dossier de courrier : collection de mails- un répertoire téléphonique : collection d ’associations noms/ numéros de téléphone.

• Par exemple, un tableau est une collection

• Le JDK fournit d’autres types de collections sous la forme de classes et d’interfaces

• Ces classes et interfaces sont dans le paquetage java.util

Rappel : Tableaux Exemple

Static final int DIM = 10;

String[] tableau;

tableau = newString[DIM];

int i;

for(i=0; i < tableau.length ; i++) {

System.out.println (tableau[i]);

}

La dimension d’un tableau est stockée dans un champ spécifique length

Les éléments d’un tableau sont indicés de 0 à length - 1 Si l’indice n’est pas compris entre 0 et length-1, une

exception de type IndexOutOfBoundsException est levée

Les collectionsCollections = structures de données

ListesEnsemblesTableauxArbresTables de hashage ...

Ces structures sont complexes à implanter ( ⇒Efficacité)Ordonnées ou nonDoublons ou nonAccès aux données indexé ou nonRechercheTris

Les collections en Java

• Les collections Java contiennent des éléments de type Object

Quelques structures de données classiquesVector :implante un tableau redimensionnable

dynamiquement; les éléments sont indexables

ArrayList :Liste ordonnée implantée sous la forme d’un tableau

HashSet :Ensemble d’éléments; non ordonné; sans doublons; opérations d’unionetd’intersection

Hashtable : implante une table de hashage; élements = clef→valeur

21

Les collections Les collections GénéricitéGénéricité

• Avant le JDK 5.0, les collections peuvent contenir des objets de n’importe quel type

• A partir du JDK 5.0, on peut indiquer le type des objets contenus dans une collection grâce à la généricité

• On privilégie ici l’API du JDK 5.0.

22

Les collections Les collections Les interfacesLes interfaces

• Des interfaces dans 2 hiérarchies principales :- Collection<E>- Map<K,V>

• Collection correspond aux interfaces des collections proprement dites

• Map correspond aux collections indexées par des clés ; un élément de type V d’une map est retrouvé rapidement si on connaît sa clé de

type K (comme les entrées d’un dictionnaire ou les entrées de l’index d’un livre)

23

Les collections Les collections Hiérarchie des interfacesHiérarchie des interfaces

Collections

Iterable <E>

Collection <E>

Set <E>

List <E>

Queue <E>

SortedSet <E>

24

Les collections Les collections Hiérarchie des interfacesHiérarchie des interfaces

Maps

Map<K, V>

SortedMap <K, V>

25

Les collections Les collections Les classesLes classes

• Classes abstraites : AbstractCollection<E>, AbstractList<E>, AbstractMap<K,V>,…qui implantent les méthodes de base communesaux collections (ou map)

• Classes concrètes : ArrayList<E>,LinkedList<E>, HashSet<E>, TreeSet<E>,HashMap<K,V>, TreeMap<K,V>,…qui héritent des classes abstraites ; ellesimplantent, en particulier, les méthodes d’accèsaux données (get, put, add,…)

26

Les collections Les collections Classes concrètes d'implantation des Classes concrètes d'implantation des interfacesinterfaces

27

Les collections Les collections Classes étudiéesClasses étudiées

• Nous étudierons essentiellement les classesArrayList et HashMap comme classesd'implémentation de List et de Map

• Elles permettront d'introduire des conceptset informations qui sont aussi valables

pour les autres classes d'implantation

28

Les collections Les collections Les classes utilitairesLes classes utilitaires

• Collections (avec un s final) fournit des méthodes static pour, en particulier,

– trier une collection– faire des recherches rapides dans une collection triée

• Arrays fournit des méthodes static pour, en particulier,

– trier– faire des recherches rapides dans un tableau trié– transformer un tableau en liste

29

Les collections Les collections Exemple de listeExemple de liste

public class Main { public static void main(String[] args) { List <String> l = new ArrayList <String>();

l.add("Pierre Jacques");l.add("Pierre Paul");l.add("Jacques Pierre");l.add("Paul Jacques");

Collections.sort(l);System.out.println(l);

}}

30

Les collections Les collections Exemple de MapExemple de Map

public class Main { public static void main(String[] args) {

Map <String, Integer> frequences = new HashMap <String, Integer> ();

for (String mot : args) {

Integer freq = frequences.get(mot);if (freq == null)

freq = 1;

elsefreq = freq + 1;

frequences.put(mot, freq); }System.out.println(frequences);

Collections et types Collections et types primitifsprimitifsLes collections de java.util ne peuventcontenir de valeurs des types primitifs

Avant le JDK 5, il fallait donc utiliser explicitement les classes enveloppantes des types primitifs, Integer par exemple

A partir du JDK 5, les conversions entre les types primitifs et les classes enveloppantes peuvent être implicite avec le « boxing » /« unboxing »

31

Exemple de Map sans Exemple de Map sans (un)boxing(un)boxing

32

Map <String, Integer> frequences = new HashMap <String, Integer> ();String [] args = { ….} for (String mot : args) {

Integer freq = frequences.get(mot);if (freq == null)

freq = 1;

elsefreq = freq + 1;

frequences.put(mot, new Integer (freq));

les collections ne peuventcontenir des types primitifs

Exemple avec boxingExemple avec boxing

33

List<Integer> l =new ArrayList<Integer>();

l.add(10);l.add(-678);l.add(87);l.add(7);

Collections.sort(l);System.out.println(l);

INTERFACE INTERFACE COLLECTION<E>COLLECTION<E>

34

DéfinitionDéfinitionL’interface Collection<E> correspond à un

objet qui contient un groupe d’objets de type E

JDK ne fournit pas une implémentation directe de cette interface mais pour des interfaces plus spécifiques telles que Set et List

35

Méthodes communes héritées de Collection public interface Collection<E> extends Iterable<E> { // opérations de base int size(); boolean isEmpty(); boolean contains(Object element); boolean add(E element); //optional boolean remove(Object element); //optional Iterator<E> iterator(); // opérations sur d’autres collections boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); //optional boolean removeAll(Collection<?> c); //optional boolean retainAll(Collection<?> c); //optional void clear(); //optional // opérations sur les tableaux Object[] toArray(); <T> T[] toArray(T[] a); }

37

Collections : les Collections : les implémentationsimplémentations

Notion de méthode Notion de méthode optionnelleoptionnelleIl peut exister de nombreux cas

particuliers de collections ; par exemple,◦ collections composées d’objets non modifiables◦ collections de taille fixe,◦ collections dont on ne peut enlever des objets

Plutôt que de fournir une interface pour chaque cas particulier, l'API sur les collections comporte la notion de méthode optionnelle

38

Méthode optionnelleMéthode optionnelleMéthode qui peut renvoyer une

java.lang.UnsupportedOperationException

(sous-classe de RuntimeException) dans une classe

d'implantation qui ne la supporte pas

Les méthodes optionnelles renvoient cette exception dans les classes abstraites du paquetage

Exemple d’utilisation : si on veut écrire une classe pour des listes non modifiables, on ne redéfinit pas les méthodes set, add et remove de la classe abstraite AbstractList

39

ConstructeursConstructeursIl n’est pas possible de donner des

constructeurs dans une interface ; mais la convention donnée par les concepteurs des collections est que toute classe d’implantation des collections doit fournir au moins 2 constructeurs :◦ un constructeur sans paramètre◦ un constructeur qui prend une collection

d’éléments de type compatible en paramètre

40

Transformation en tableauTransformation en tableautoArray() renvoie une instance de

Object[] qui contient les éléments de la collection

Si on veut un tableau d'un autre type, il faututiliser la méthode paramétrée<T> T[] toArray(T[] tableau) à laquelle on

passe un tableau du type voulu◦ si le tableau est assez grand, les éléments de la

collection sont rangés dans le tableau◦ sinon, un nouveau tableau du même type est

créé pour recevoir les éléments de la collection

41

Transformation en tableau Transformation en tableau (2)(2)Forme simple : sans paramètre

◦ Object[] a = c.toArray();

Pour obtenir un tableau de type String[]:◦ String[] tableau =collection.toArray(new

String[0]);

Remarque : si la collection est vide, toArray renvoie un tableau de taille 0 (pas la valeur null)

42

INTERFACE SET & INTERFACE SET & implémentationsimplémentations

Les collections de type SET

43

Définition de l'interface Définition de l'interface Set<E>Set<E>Un ensemble (Set) est une collection

qui n'autorise pas l'insertion de

doublons.

Exemples :◦ Ensemble des matières d’un étudiant◦ Ensemble des processus s’exécutant sur

une machine

44

Méthodes de Méthodes de Set<E>Set<E>Mêmes méthodes que l’interface Collection

Mais les « contrats » des méthodes sont adaptés aux ensembles. Par exemple,◦ quand on supprime un objet, tout objet

égal (au sens du hashCode ) à l’objet passé en paramètre sera enlevé

◦ la méthode add n’ajoute pas un élément si un élément égal est déjà dans l’ensemble (la méthode renvoie alors false)

45

Interface SortedSetInterface SortedSetCette interface définit une collection de type

ensemble triée par un comparateur. Elle hérite de l'interface Set.

Définit les méthodes :◦ Comparator<? super E> comparator() : Renvoie le

comparateur utilisée pour définir l'ordre◦ E first(), last() : Renvoie le premier/dernier

élément

Très peu utiliser car SortedSet ne définie pas assez de méthodes et ne possédait qu'une implémentation TreeSet

46

Interface NavigableSet Interface NavigableSet <java 6><java 6>Set ordonné par un comparateur permettant de

naviguer entre les éléments (étend SortedSet)◦ E lower(e), floor(e), higher(e),

ceiling(e) : Respectivement renvoie l'élément <, <=, > et >= à E.

◦ E pollFirst(), pollLast() : Renvoie on supprimant le premier/dernier élément

Parcourir ou utiliser l'ensemble en ordre descendant◦ NavigableSet<E> descendingSet()◦ Iterator<E> descendingIterator()

47

ImplémentationsImplémentationsLe framework propose deux classes

qui implémentent l'interface Set : TreeSet et HashSet

Le choix entre ces deux objets est lié à la nécessité de trier les éléments :◦les éléments d'un objet HashSet ne sont

pas triés : l'insertion d'un nouvel élément est rapide

◦les éléments d'un objet TreeSet sont triés : l'insertion d'un nouvel élément est plus long

48

Classe HashSet<E>Classe HashSet<E>Cette classe est un ensemble sans

ordre de tri particulier.

Les éléments sont stockés dans une table de hashage : cette table possède une capacité.

Cette classe ne vérifie l’égalité que pour les objets qui ont le même hashCode

49

Exemple hashSetimport java.util.*;public class TestHashSet { public static void main(String args[]) { Set set = new HashSet(); set.add("CCCCC"); set.add("BBBBB"); set.add("DDDDD"); set.add("BBBBB"); set.add("AAAAA"); Iterator iterator = set.iterator(); while (iterator.hasNext())

{System.out.println(iterator.next());} }}

TreeSetTreeSetCette classe est un arbre qui représente un

ensemble trié d'éléments.

L'insertion d'un nouvel élément dans un objet de la classe TreeSet est donc plus lent mais le tri est directement effectué.

L'ordre utilisé est celui indiqué par les objets insérés si ils implémentent l'interface Comparable pour un ordre de tri naturel ou fournir un objet de type Comparator au constructeur de l'objet TreeSet pour définir l'ordre de tri.

51

Exemple TreeSetTreeSetpublic static void main(String[] args) { Set ts = new TreeSet(); ts.add("one"); ts.add("two"); ts.add("three"); ts.add("four"); ts.add("three"); System.out.println("Members from TreeSet

= " + ts); }

Resultat : Members from TreeSet = [four, one, three, two]

INTERFACE LIST<E> INTERFACE LIST<E> & implémentations& implémentations

Les collections de type LIST

53

Interface List <E>Interface List <E>Liste ordonnée (séquence commençant par

0)Peut contenir des éléments dupliquésAccès aux éléments par leur indice

Classes qui implémentent cette interface :◦ ArrayList<E>, tableau à taille variable◦ LinkedList<E>, liste chaînée

On utilise le plus souvent ArrayList, sauf si les insertions/suppressions au milieu de la liste sont fréquentes (LinkedList évite les décalages)

54

Nouvelles méthodes de Nouvelles méthodes de ListList public interface List<E> extends Collection<E> { // Positional access E get (int index); E set (int index, E element); //optional boolean add (E element); //optional void add (int index, E element); //optional E remove (int index); //optional boolean addAll (int index, Collection <? extends E> c); // Search int indexOf (Object o); int lastIndexOf (Object o); // Iteration ListIterator<E> listIterator(); ListIterator<E> listIterator(int index); // Range-view List<E> subList (int from, int to);

55

Classe Classe ArrayList<E>ArrayList<E>Une instance de la classe ArrayList<E> est une sorte de tableau qui peut contenir un nombre quelconque d’instances d’une classe E

Les emplacements sont repérés par des nombres entiers (à partir de 0)

56

ExemplesExemples

57

List<Employe> le =new ArrayList<Employe>();Employe e = new Employe("Dupond");le.add(e);. . . // Ajoute d’autres employésfor (int i = 0; i < le.size(); i++) {

System.out.println(le.get(i).getNom());}

Classe VectorClasse VectorAncienne version de ArrayList

(pre1.2), a été modifiée pour implémenter List

Synchronisé par défaut(4x plus lent que ArrayList)

A n'utiliser que par compatibilité avec des API’s existantes

58

Classe LinkedListClasse LinkedListListe toujours doublement

chaînéeMaintient une référence sur le

début et la fin de la liste

59

INTERFACESINTERFACESITERATOR<E> ET ITERATOR<E> ET boucle FORboucle FOR

Parcourir une Collection

60

Parcourir une CollectionL'interface Iterator

public interface Iterator {boolean hasNext(); //Permet de vérifier

s'il y a un élément qui suit

Object next(); //Permet de pointer l'élément suivant

void remove(); //Optional, Permet de retirer l'élément courant}

Parcourir une CollectionUn itérateur sert à parcourir les

éléments d'une collection.

Iterator it= c.iterator();while(it.hasNext()) {

Point p = it.next(); // Point p = (Point) it.next(); // ☺ ☺☺ ☺System.out.println(p.distance());if (p.distance <= 10) it.remove();}

Obtenir un itérateurObtenir un itérateurL’interface Collection<E> contient la

méthode Iterator<E> iterator() ◦ qui renvoie un itérateur pour parcourir les

éléments de la collection

L’interface List contient en plus la méthode ListIterator<E> listIterator()◦ qui renvoie un ListIterator (offre plus de

possibilités que Iterator pour parcourir une liste et la modifier)

63

ExempleExempleList<Employe> le = new ArrayList<Employe>();

Employe e = new Employe("Dupond");

le.add(e);

. . . // ajoute d’autres employés dans v

Iterator<Employe> it = le.iterator();

// le premier next() fournira le 1er élément

while (it.hasNext()) {

System.out.println(it.next().getNom());}

ListIterator it=le.listIterator(le.size());

for(;it.hasPrevious();)

System.out.println(it.previous());

64

Itérateur et modificationItérateur et modificationde la collection parcouruede la collection parcourue

Un appel d’une des méthodes d’un itérateur associé à une collection peut lancer ConcurrentModificationException si la collection a été modifiée directement depuis la création de l’itérateur (directement = sans passer par l’itérateur)

65

Itérateur de liste et ajoutItérateur de liste et ajoutdans la dans la liste parcourueliste parcourueSi l’on veut faire des ajouts dans une liste (pas

possible avec une collection qui n’implante pas l’interface List) pendant qu’elle est parcourue par un itérateur, il faut utiliser la sous-interface ListIterator de Iterator

Cette interface permet de :◦ parcourir la liste sous-jacente dans les 2 sens◦ de modifier cette liste (méthodes optionnelles add et set)

ListIterator it=list.listIterator();for(;it.hasNext()) {

if (o1.equals(it.next()))it.set(o2);

}66

TRI ET RECHERCHETRI ET RECHERCHEDANS UNE COLLECTIONDANS UNE COLLECTION

Les algorithmes usuelle

67

Classe Classe CollectionsCollectionsCette classe ne contient que des

méthodes static, utilitaires pour travailler avec des collections :

◦ trie (sur listes)◦ recherches (sur listes)◦ copies◦ minimum et maximum◦ ...

68

Trier une listeTrier une listeSi l est une liste, on peut trier l par :Collections.sort(l);Cette méthode ne renvoie rien ; elle trie

lPour que cela fonctionne, il faut que les

éléments de la liste soient comparablesPlus exactement, la méthode sort() ne

fonctionnera que si tous les éléments de la liste sont d’une classe qui implante l’interface

java.lang.Comparable<? super E>69

Interface Interface Comparable<T>Comparable<T>Cette interface correspond à l’implantation

d’un ordre naturel dans les instances d’une classe

Redéfinir la méthode public int compareTo (Object o) avec

◦ a.compareTo (b) == 0 si a.equals To(b)◦ a.compareTo (b) < 0 si a plus « petit »que

b◦ a.compareTo (b) > 0 si a plus « grand »

que b70

Interface Interface Comparable Comparable Toutes les classes du JDK qui enveloppent

les types primitifs (Integer par exemple) implantent l’interface Comparable

Il en est de même pour les classes du JDK◦ String, Date, Calendar, BigInteger,BigDecimal,

File, Enum et quelques autres

Par exemple, String implémente Comparable<String>

71

ExemplePublic class Personne implements Comparable {

String nom;int age;Personne (String nom, int age) {

this.nom=nom;this.age=age;

}Public String toString() {

return nom+"("+age+")";}public int compareTo (Objecto) {

if(o instanceof Personne) {return this.age - ((Personne)o).age;

}return Integer.MAX_VALUE;

}

Interface Interface Comparator<T>Comparator<T>Mais que faire si les éléments de la collection

n’implantent pas l’interface Comparable, ou si on ne veut pas les trier suivant l’ordre donné par Comparable ?

Réponse :1. on construit une classe qui implante

l’interface java.util.Comparator, qui permettra de comparer deux éléments de la collection

2. on passe en paramètre une instance de cette classe à la méthode sort()

73

Interface Interface Comparator<T>Comparator<T>Elle comporte une seule méthode :int compare(T o1, T o2)

qui doit renvoyer◦ un entier positif si o1 est « plus grand »

que o2◦ 0 si o1 a la même valeur (au sens de

equals) que o2◦ un entier négatif si o1 est « plus petit »

que o2

74

ExempleExemplepublic class CompareSalaireimplements Comparator<Employe> {public int compare(Employe e1, Employe e2) {

double s1 = ((Employe) e1).getSalaire();double s2 = ((Employe) e2).getSalaire();if (s1 > s2)

return 1;else if (s1 < s2)

return –1;else

return 0;} }

75

Utilisation d’un Utilisation d’un comparateurcomparateurList<Employe> employes = new

ArrayList<Employe>();// On ajoute les employés. . .Collections.sort(employes,new

CompareSalaire());System.out.println(employes);

76

INTERFACE MAPINTERFACE MAPLes collections de type MAP

77

DéfinitionDéfinitionL’interface Map<K,V> correspond à un groupe de couples clés-valeurs

La clé est unique, contrairement à la valeur qui peut être associée à plusieurs clés.

Dans la map il ne peut exister 2 clés égales au sens de equals()

78

ImplémentationImplémentationHashMap<K,V>, table de hachage ;

garantit un accès en temps constant

TreeMap<K,V>, arbre ordonné suivant les valeurs des clés avec accès en log(n) ;

La comparaison utilise l’ordre naturel (interface Comparable<K>) ou une instance de Comparator<? super K>

79

FonctionnalitésFonctionnalitésajouter et enlever des couples clé

– valeurrécupérer une référence à un des

éléments donnant sa clésavoir si une table contient une

valeur savoir si une table contient une

clé

80

Méthodes de Méthodes de MapMap void clear() boolean containsKey(Object clé) boolean containsValue(Object valeur)Set<Map.Entry<K,V>> entrySet() V get(Object clé) boolean isEmpty() Set<K> keySet() Object put(K clé, V valeur) void putAll(Map<? extends K, ? extends V>map) void remove(Object key) int size() Collection<V> values()

81

Itérer sur les Map// sur les clésfor (Iterator i = m.keySet().iterator(); i.hasNext(); )

System.out.println(i.next());

//sur les valeursfor (Iterator i = m.values().iterator(); i.hasNext(); )System.out.println(i.next());

//sur la paire clé/valeurfor (Iterator i = m.keySet().iterator(); i.hasNext(); )

{Map.Entry e = (Map.Entry) i.next();System.out.println (e.getKey() + " ; " + e.getValue());

}

Map: abstraction de structure de données avec adressage dispersé (hashcoding)

Peut être vu comme une table de couples clé/valeur

Map map = new HashMap();

Ajouter une entrée à la MapString s1 = new String("Sommet A");Point pt1 = new Point(15,11);Map.put (s1, pt1);

Créer un objet Map.Entry référençant s1 et pt1 Ranger cette Map.Entry dans la table à une

position qui dépend de la clé (s1). Cette position est calculée en envoyant le message hashCode() à l'objet clé (s1).

Exemple : Equals & hashcodeMap map= newHashMap();Personne p1 = new Personne

("DURAND","Sophie","Mlle");NumTel num= newNumTel ("1234547",'F');map.put (p1,num);NumTel num1 =map.get(p1);System.out.println(num1); // ☺ ☺☺ ☺ 1234547 (F);map.put (new Personne ("DUPONT","Jean","Mr"), new

NumTel("4234548",'D'));String nom =LectureClavier.lireChaine("Nom : "); //

DUPONTStringprenom=LectureClavier.lireChaine("Prénom : "); //

JeanStringcivilite=LectureClavier.lireChaine("Civilité : "); // MrPersonne p2 = new Personne (nom,prenom,civilite);NumTelnum2 =map.get(p2);System.out.println(num2); // null !!!!;

Exemple: equals & hashcodepublic class Personne { ...

Public boolean equals(Objecto) {if (! (o instanceof Personne) )

return false;Personne p = (Personne) o;return civilite_.equals(p.civilite_) && nom_.equals(p.nom_) &&prenom_.equals(p.prenom_);

}

Public int hashCode() {String nomPlusPrenomPlusCivilite = nom_ +prenom_ + civilite_;return nomPlusPrenomPlusCivilite.hashCode();

}}

hashCode() doit TOUJOURS être redéfinie en cohérence avec equals().

Personne p2 = new Personne("DUPONT","Jean","Mr");NumTelnum2 =map.get(p2);System.out.println(num2); // ☺ ☺☺ ☺ 4234548(D);

Interface Interface interne interne Entry<K,V> de MapEntry<K,V> de MapL’interface Map contient l’interface

interne public Map.Entry<K,V> qui correspond à un couple clé-valeur

Cette interface contient 3 méthodes◦ K getKey()◦ V getValue()◦ V setValue(V valeur)

La méthode entrySet() de Map renvoie un objet de type « ensemble (Set) de Entry »

86

Modification des clésModification des clésLa bonne utilisation d’une map n’est

pas garantie si on modifie les valeurs des clés avec des valeurs qui ne sont pas égales (au sens de equals) aux anciennes valeurs

Si on veut changer une clé, on enlève d’abord l’ancienne entrée (avec l’ancienne clé) et on ajoute ensuite la nouvelle entrée avec la nouvelle clé et l’ancienne valeur

87

Récupérer les valeurs d’une Récupérer les valeurs d’une MapMapOn récupère les valeurs sous

forme de Collection<V> avec la méthode values() ◦La collection obtenue reflétera les

modifications futures de la mapOn utilise la méthode iterator() de l’interface Collection<V> pour récupérer un à un les éléments

88

Récupérer les clés d’une Récupérer les clés d’une MapMapOn récupère les clés sous forme

de Set<K> avec la méthode keySet()

On utilise alors la méthode iterator() de l’interface Set<K> pour récupérer une à une les clés

89

Récupérer les entrées d’une Récupérer les entrées d’une MapMapOn récupère les entrées (paires clé-

valeur) sous forme de Set<Entry<K,V>> avec la méthode entrySet()

On utilise alors la méthode iterator() de l’interface Set<Entry<K,V>> pour récupérer une à une les entrées

90

Itérateur et suppression dans Itérateur et suppression dans la la map parcouruemap parcouruePendant qu’une map est

parcourue par un des itérateurs associés à la map◦On peut supprimer des éléments

avec la méthode remove() de Iterator (si elle est implémentée)

◦On ne peut ajouter des éléments dans la map

91

Interfaces et classes Interfaces et classes d’implémentationd’implémentation

92

<<interface>>

Map<K, V>

<<interface>>SortedMap <K,

V>

<<abstrract>>AbstractMap<K,

V>

HashMap<K, V>TreeMap<K, V>

Classe Classe HashMap HashMap ImplémentationImplémentationLa classe HashMap<K,V> utilise la

structure informatique nommée « table de hachage » pour ranger les clés

La méthode hashCode() (héritée de Object ou redéfinie) est utilisée pour répartir les clés dans la table de hachage

93

Exemple d’utilisation de Exemple d’utilisation de HashMapHashMapMap<String,Employe> hm =new

HashMap<String,Employe> ();

Employe e = new Employe("Dupond");

e.setMatricule("E125");

hm.put(e.getMatricule(), e);

//ajoute les autres employés dans la table de hachage

Employe e2 = hm.get("E369");

Collection<Employe> elements = hm.values();

Iterator<Employe> it = elements.iterator();

while (it.hasNext()) {

System.out.println(it.next().getNom());}

94

Classe Classe TreeMap TreeMap ImplémentationImplémentationLe conteneur TreeMap permet de

stocker des couples (clé, valeur), dans une structure d’arbre binaire équilibré

Cette classe garantit que la collection Map sera triée selon un ordre croissant, conformément à l'ordre naturel des clés ou à l'aide d'un comparateur fourni au moment de la création de l'objet TreeMap.

firstKey()lastKey()

95

Exemple d’utilisation de Exemple d’utilisation de TreeMapTreeMap

TreeMap <Integer, String>tMap = new TreeMap<Integer, String>(); tMap.put(1, "Dimanche"); tMap.put(2, "Lundi");//Ajouter des entrés

//Extraire tous les clés System.out.println(" Les clés du tree map: " + tMap.keySet());

//Extraire tous les valeurs

System.out.println(" Les valeurs du tree map: : " + tMap.values());

//Extraire la valeurs à partie de la clé numéro 5System.out.println(" Clé: 5 valeur: " + tMap.get(5)+ "\n");

//Extraire la première clé et sa valeur

System.out.println("1ere clé: " + tMap.firstKey() + " Valeur: " + tMap.get(tMap.firstKey()) + "\n");

96

Exemple d’utilisation de Exemple d’utilisation de TreeMapTreeMap//Extraire la dernière clé et sa valeur

System.out.println("dernière clé " +

tMap.lastKey() +" Valeur: "+tMap.get(tMap.lastKey())+"\n")

//Supprimer la première clé et sa valeur System.out.println("Supprimer la première

entré " + tMap.remove(tMap.firstKey()));//Supprimer la dernière clé et sa valeur System.out.println("Supprimer la dernière

entré " +tMap.remove(tMap.lastKey())); }}

97

HashCode ()Deux objets identiques ont le

même hashCode.Deux objets ayant le même

hashCode ne sont pas forcément identiques.

Utilisé pour retrouver des clés ou valeurs dans les collections.

Technology

Interface collectionsinter