2A – Informatique S4
JAV_COLL / H. Nguyen-Phu
Cr.: 22/08/2002
Dernière
MAJ: 2011.04.02 08:11
C1.1: LES CLASSES ET INTERFACES DE COLLECTIONS DE L’API
Plan:
----
Hiérarchie des classes
Les objets de type 'ArrayList'
et 'Vector' (T.G.V. à capacité finie)
Les objets de type ' Stack ' ( pile
)
Les objets de type ' LinkedList
' (LCAB ou Liste
Chaînée Auto-référencée et Bilatère)
Les interfaces ' Iterator
' ('Enumeration') et 'ListIterator'
Les objets de type ' Properties
' (dictionnaire à clés uniques)
Les objets de type ' HashMap/TreeMap ' (table à clés uniques / triées)
Les objets de type ‘ArrayDeque<E>’ et l’interface ‘Deque<E>’
------------------------------------------------------------------------------
1. HIERARCHIE DES CLASSES
*************************
Une collection est, par définition, un objet capable de contenir d'autres objets. Les principales collections développées sont:
- un 'ArrayList' ou collection dynamique de taille variable,
- un 'Vector' ou tableau dynamique de taille variable,
- une pile implémentée par tableaux ('Stack') qui est une sous-classe de 'Vector',
- une LCAB ou liste doublement chaînée par référence ('LinkedList' ici) qui est une sous-classe de 'AbstractSequentialList',
- un objet 'Properties' ou collection dynamique à indexation par chaîne,
- la table de hachage ('HashTable') ou collection dynamique à indexation par objet quelconque [version JDK 1.1],
- la table associative par hachage ('HashMap'), une sous-classe de 'AbstractMap' selon le diagramme des hiérarchies ci-après [à partir de JDK 1.2]. Il est donc recommandé de l'employer à la place de 'Hashtable'.
Il en est de même pour 'Iterator' à la place de 'Enumeration', et pour 'ArrayList' à la place de 'Vector'. Toutes ces classes et interfaces font partie du paquet « java.util ».
Classes:
Interfaces:
========
===========
[AbstractCollection] ...........................Collection
--------------------
----------
|_ [AbstractList].......................... |__ List
| |_ [AbstractSequentialList] ........... |__ Set
| | |__
LinkedList : ......... |__ SortedSet
| |_
ArrayList
: :
| |_
Vector
: :
| |__
Stack
: :
|_ [AbstractSet]..................: :
|_
HashSet
:
|_ TreeSet ....................:
[Dictionary]
-----------
|_ Hashtable ...............................Map
[AbstractMap]
................................: ----
-------------
.....|__ SortedMap
|_
HashMap
:
|_ TreeMap ..............................:
Arrays
Map.Entry
Collections
Iterator
--------
BitSet
|_ ListIterator
Comparator
StringTokenizer ................................ Enumeration
La classe abstraite 'AbstractCollection' est la seule classe qui implémente l'interface 'Collection' offrant ainsi l'accès aux principales méthodes:
add(Object) Ajout d'un objet à la collection référencée par 'this'
addAll(Collection) Ajout des objets d'une collection passée en argument
remove(Object) Supprime un objet de la collection référencée par 'this'
removeAll(Collection) Enlève tous les objets d'une collection donnée en entrée
contains(Object) Teste si 'Object' appartient à la collection courante
containsAll(Collection) Idem. mais pour tous les objets d'une collection donnée
size() retourne le nombre d'objets (taille) de la collection
iterator() retourne un itérateur (cf. 'java.util.Iterator')
toArray() convertit la collection courante en tableau
L'interface 'java.util.List' qui dérive de l'interface 'Collection' autorise deux objets (ou plus) identiques au sein d'une même collection. Elle est implémentée par les classes 'ArrayList' et 'Vector'.
L'interface 'java.util.Set' qui dérive aussi de l'interface 'Collection' n'autorise pas d'objets identiques au sein d'une même collection. Elle est implémentée par les classes 'HashSet' (ensemble d'objets non ordonnés) et 'TreeSet' (ensemble d'objets ordonnés).
2.- Les objets de type 'ArrayList' et 'Vector'
**********************************************
Ces classes ont pratiquement les mêmes fonctionnalités. L'une des principales différences réside dans le fait qu'aucune des méthodes de la classe 'ArrayList' n'est synchronisée. Les constructeurs et les principales méthodes sont:
Classe 'ArrayList' Classe 'Vector' Remarques
----------------- -------------- ---------
ArrayList() Vector() Constructeur sans arguments
Vector(int capacity) Constructeur avec capacité déf.
Vector(int capa, int dCap) Constructeur avec capacité init.
'capa' puis par incrément dCap
add(Object) addElement(Object) Ajout en queue d'un objet
add(int, Object) insertElementAt(Object,int) Ajout mais à l'indice 'int'
capacity() renvoie la capacité
clear() efface tous les éléments
clone() renvoie un clone du 'Vector'
contains(Object) contains(Object) Test d'appartenance
get(int pos) elementAt(int pos) renvoie l'objet à l'indice 'pos'
elements() renvoie la liste des élements
indexOf(Object) renvoie l'indice de 'Object'
isEmpty() teste si l'objet 'Vector' est vide
iterator() renvoie un itérateur
lastElement() renvoie le dernier élément
removeElement(Object) retire l'élément 'Object'
remove(int i) removeElementAt(int i) retire l'élément à l'indice 'i'
en décalant en amont les éléments
qui suivent
removeAllElements() retire tous les éléments de 'Vector'
set(int i, Object) setElementAt(Object, int i) modifie l'élément en position 'i'
setSize(int) modifie la taille d'un 'Vector'
size() size() retourne la taille courante
toString() renvoie une chaîne contenant la
liste des éléments d'un 'Vector'
trimToSize() pour forcer: capacité == taille
Voici un exemple typique d'emploi des objets correspondants:
import
static java.lang.System.*; // cf. Java 5
import java.util.*;
import java.io.*;
public
class vecarray {
ArrayList<String> shape = new
ArrayList<String>(); // cf. Java 5
Vector<String> color = new
Vector<String>(10,5);
public static void main(String [] arg) {
vecarray O = new vecarray(); // O : un objet courant
out.println("\nVECARRAY : Un exemple d'emploi de 'ArrayList', 'Vector',");
out.println("\t'Iterator'
et 'Enumeration' (c)~/2a env. MAJ:
2006.08.23 19h00\n");
O.shape.add( (new String(
"rectangle") ) );
O.shape.add("triangle");
O.shape.add("cercle");
for (int i=0; i< O.shape.size();
++i)
out.println(O.shape.get(i));
/* // Que se passe-t-il si on dé-commente ce bloc ?
Iterator it = O.shape.iterator();
while(it.hasNext()) {
String str = (String) it.next();
out.println(str);
}
*/
out.printf("\n"); // cf. Java 5
O.color.add("bleu "); O.color.add("blanc ");
O.color.addElement("rouge
");
for (int i=0; i < O.color.size();
++i)
out.println(O.color.get(i));
/* // Que se passe-t-il si on dé-commente ce bloc ?
Enumeration listColor =
O.color.elements();
while(listColor.hasMoreElements()) {
String str = (String) listColor.nextElement();
out.println(str);
}
*/
if ( O.color.elementAt(O.color.size()-1).equals(
O.color.lastElement()))
out.println("\nDernier élément = "+ O.color.lastElement());
out.println("Capacité= "+O.color.capacity()+" Taille= "+O.color.size());
O.color.trimToSize();
out.println("Nouvelle capacité = "+O.color.capacity() );
es.attente();
}
}
Question: Qu'affiche le programme Java ci-dessus (cf. vecarray.java)?
--------
3.- Les objets de type 'Stack'
******************************
La structure de données "pile" qui est une liste linéaire de type 'LIFO' ('Last In First Out') est implantée en Java via la classe 'java.util.Stack'. Comme elle hérite de la super classe 'java.util.Vector', elle reprend toutes ses méthodes mais l'enrichit de cinq fonctionnalités à savoir:
- push() pour empiler un élément en sommet de la pile courante,
- pop() pour dépiler un élément du sommet de la pile,
- peek() pour consulter l'élément situé au sommet SANS dépilement,
- empty() pour savoir si la pile courante est vide,
- search() recherche un élément au sein de la pile en indiquant sa position.
Exercice 1: Ecrire un programme Java pour vérifier si une expression arithmétique est bien parenthésée i.e. le nombre de parenthèses ouvrantes est égal à celui des parenthèses fermantes et dans le bon sens.
Solution 1: (cf. parenthe.java)
import static java.lang.System.*; // cf. Java 5
import java.util.*;
import java.io.*;
public class parenthe {
private String expr;
private Stack<Character>
pileParentheses;
private parenthe(String uneExpression) {
expr = uneExpression;
pileParentheses = new Stack<Character>(); // cf. Java 5
}
private boolean valide() {
try
{
for(int i = 0; i<expr.length();
i++)
switch(expr.charAt(i)) {
case '(':
pileParentheses.push(new
Character('(')); break;
case ')':
pileParentheses.pop(); break;
}
} catch (EmptyStackException ese) {
return false; }
return
pileParentheses.empty();
}
public static void main(String [] arg) {
out.println("\nparenthe : Un exemple d'emploi de 'Stack' en Java 5");
out.println("\t(c) ~/2a env. 2006.08.23 19h35 \n");
out.println("Tapez votre expression \u00e0 valider en parenth\u00e9sage");
out.println("Exemple: (x+y) ou ((1-3)/2)) ou 1+3)*4( etc ... \n");
parenthe O = new parenthe(es.LireCh()); // O : une instance courante
out.println("\nVotre parenth\u00e9sage est "+(O.valide()?"bon!":"incorrect!"));
es.attente();
}
}
4.- Les objets de type 'LinkedList'
***********************************
La classe 'java.util.LinkedList' définit aussi un type abstrait de données (TAD) nommé LCAB « Liste Chaînée par Auto-référence et Bilatère" (ou encore liste doublement chaînée via les deux pointeurs ‘suivant’ et ‘prédécesseur’). Ainsi on peut parcourir en allant du premier au dernier élément et aussi dans le sens inverse.
Chaque objet référencé est du type générique 'E' (à compter de JDK 1.5): on peut donc y insérer des objets de type quelconque. On retrouve des méthodes analogues à celles de 'Vector' mais aussi des méthodes telles que:
addFirst()
getFirst() removeFirst() peek()
listIterator()
addLast()
getLast() removeLast() poll()
offer()
Méthodes “communes”’ des classes:
Classe 'LinkedList' Classe 'Vector' Remarques
------------------ -------------- ---------
LinkedList() Vector() Constructeur sans arguments
... ... Autres constructeurs ...
boolean add(E o) Ajout en queue d'un élément E
void add(int i, E o) Ajout mais à l'indice 'i'
boolean addAll(coll) Ajout d'une collection 'coll'
void addFirst(E o) void add(0, E o) Adjonction en tête ("Adjt")
void addLast(E o) void addElement(E o)
Adjonction en queue ("Adjq")
void clear() RAZ de l’instance courante
Object clone() renvoie un clone de ‘this’
boolean contains(Object e) Test d'appartenance de ‘e’
E get(int i) E elementAt(int i) renvoie l'objet à l'indice 'i'
E getFirst() E firstElement() renvoie l'élément de tête
E getLast() E lastElement() renvoie le dernier élément
int hashCode() renvoie le code de hachage
int indexOf(Object e) renvoie l'indice de 'e'
int lastIndexOf(Object e) renvoie le dernier indice de 'e'
boolean isEmpty() boolean isEmpty() teste si l'objet courant est vide
ListIterator<E> listIterator(int i) - NEANT - renvoie une liste d’itérateurs ...
boolean offer(E o) ajout en queue de ‘o’
E peek()
- NEANT - renvoie l'élément de tête
uniquement
E poll()
- NEANT - renvoie et supprime la tête de
liste
E
remove(int i) supprime et renvoie l'élément en ‘i’
boolean
remove(Object o) supprime l'objet 'o' de
« this »
E remove()
-
NEANT -
supprime et renvoie l'élément de tête
E
removeFirst() <=> remove(0);
supprime et renvoie la tête de liste
E
removeLast() <=> remove(size()-1); supprime et renvoie le dernier élément
boolean removeAll(Collection<?> c)
supprime ‘c’ du vecteur courant
void removeAllElements() RAZ le vecteur courant
boolean removeElement(Object o) supprime
‘o’ du vecteur courant
void removeElementAt(int i)
supprime l'élément en ‘i’ du vecteur courant
E set(int i, E elt) remplace l’élément en ‘i’ par ‘elt’ et retourne l’ancien
int size() retourne la taille courante de « this »
5.- Les interfaces 'Iterator' ('Enumeration') et 'ListIterator'
***************************************************************
Java propose d'employer à partir de sa version JDK 1.2 l'interface 'Iterator' pour rechercher un élément au sein d'un objet de la famille des collections. Une interface est une classe "implémentable" par d'autres classes via le
mot-clé 'implements'. Le code de chaque méthode est fourni pour un emploi spécifique et associé à une implémentaion particulière. On distingue:
- hasNext() qui renvoie Vrai si l'itérateur courant indique qu'il y a encore au moins un élément de la collection ('Vector', 'LinkedList'...) à étudier;
- next() qui permet à l'itérateur de référencer (pointer sur) l'élément suivant;
- remove() supprime de la collection l'élément qui vient d'être référencé.
Bien que le code soit spécifique à chacune des collections, leur emploi reste le même, ceci quelque soit le type de collections.
L'interface 'java.util.Enumeration' possède des propriétés similaires à l'interface 'java.util.Iterator'. Depuis la version 1.2, seule la classe StringTokenizer implémente encore cette interface. Une comparaison succinte entre les deux interfaces est donnée par:
Interface 'Iterator'
Interface 'Enumeration'
-------------------
-----------------------
hasNext()
hasMoreElements()
next() nextElement()
Question 2: Utiliser 'Iterator' pour remplacer, dans 'vecarray.java', les lignes:
----------
for (i=0; i< O.shape.size(); ++i) // Rappel:
out.println(O.shape.get(i)); // 'shape' est une instance de 'ArrayList'
Réponse
2:
---------
Iterator it = O.shape.iterator();
while(it.hasNext()) {
String str = (String) it.next();
out.println(str); }
Question 3: Utiliser 'Enumeration' pour remplacer les deux lignes:
----------
for (i=0; i < O.color.size(); ++i) // Rappel:
out.println(O.color.get(i)); // 'color' est une instance de 'Vector'
Réponse
3:
---------
Enumeration listColor = O.color.elements();
while(listColor.hasMoreElements()) {
String str = (String) listColor.nextElement();
out.println(str); }
Par ailleurs, l'interface 'java.util.ListIterator' qui dérive de l'interface 'Iterator' permet de parcourir la collection dans les deux sens et aussi de modifier ou d'ajouter un élément de la collection:
Interface 'ListIterator'
------------------------
hasPrevious() teste s'il existe un élément précédent dans la collection
set(Object o) modifie l'élément courant par le nouvel objet 'o'
add(Object o) ajoute l'objet 'o' dans la collection ...
nextIndex() renvoie l'indice de l'élément suivant indiqué par l'itérateur
previousIndex() renvoie l'indice de l'élément précédent indiqué par l'itérateur
Exercice 2: Ecrire un programme Java pour implémenter le type abstrait de donnée "FADE" ou file à double entrée (file avec deux entrées mais une seule sortie) en employant la classe 'LinkedList' et l'interface 'ListIterator'. Simuler une file d'attente de personnes valides qui laissent, par courtoisie, la priorité aux personnes à mobilité réduite bien que ces personnes arrivent après [A terminer en TPP ...].
6.- Les objets de type 'Properties'
***********************************
La classe 'java.util.Properties' permet d'étudier des collections d'objets sous forme "clef - valeur" où la clef et la valeur sont des chaînes 'String'. C'est déjà une structure de données de type "dictionnaire" où la clé, appelée aussi l'index, offre un moyen plus efficace que les indices dans les tableaux dynamiques 'Vector' pour retrouver la valeur associée.
En général, on importe cette classe pour gérer les variables d'environnement système. Dans l'exemple ci-dessous, la méthode 'getProperties()' de la classe 'java.lang.System' permet de récupérer ces variables et la méthode 'list(System.out)' de la classe 'java.util.Properties' affiche la liste sur la sortie standard.
import static java.lang.System.*; // cf. Java 5
import java.util.Properties; // cf. list_sys.java
public class list_sys {
public static void main(String [] arg) {
out.println("list_sys: Affichage des variables d'env. de Java - 2005.10.01");
getProperties().list(out);
es.attente();
}
}
Les principales méthodes de la classe 'java.util.Properties' sont:
- load(f_name) pour charger de la table des propriétés depuis un fic. 'f_name',
- store(f_name) pour enregistrer la table associative dans un fic. 'f_name',
- setProperty(clef,valeur) pour enrichir la table par une nouvelle propriété.
Exercice 3: Ecrire un programme pour gérer une table associative des romans avec chargement à partir d'un fichier disque, puis enrichissement par de nouveaux enregistrements en cours d'exécution et enfin, avec sauvegarde sur disque sous le même nom.
Solution partielle: (cf. l_roman.java)
------------------
import static java.lang.System.*; // cf. Java 5
import java.util.*;
import java.io.*;
class l_roman
{
Properties
lesRomans;
l_roman()
{ lesRomans = new
Properties(); }
void chargerRomans(String f_n) { //
f_n: file name
try
{
BufferedInputStream jin= new BufferedInputStream(new
FileInputStream(f_n));
lesRomans.load(jin);
jin.close();
} catch(IOException ioe) { err.println("Pas de chargement (fic. nouveau) ..."); }
}
void ajout_Romans() {
String auteur, oeuvre;
boolean conti = true;
do {
try {
auteur = es.LireCh("Tapez le nom de l'auteur (ou retour chariot pour quitter): ");
oeuvre = es.LireCh("Tapez le titre de l'oeuvre (ou retour chariot pour quitter): ");
if (!
auteur.equalsIgnoreCase("") && ! oeuvre.equalsIgnoreCase("") )
lesRomans.setProperty(auteur, oeuvre);
else conti = false;
} catch(Exception e) { err.println("Pb. de saisie des données !"); }
} while(conti);
}
void afficherRomans() {
out.println("Contenu de la table 'Auteur=Oeuvre' :");
lesRomans.list(out);
}
void sauvegarderRomans(String f_n) { // f_n: file name
try
{
BufferedOutputStream jout= new BufferedOutputStream(new
FileOutputStream(f_n));
lesRomans.store(jout,"Liste des romans MAJ le ...");
jout.close();
out.println("Sauvegarde de la liste des romans terminée !");
}
catch(IOException er) { err.println("Pb. de sauvegarde (fic. protégé !) ..."); }
}
public static void main(String [] arg) {
String nom_fic;
l_roman table = new l_roman();
out.println("l_roman : Emploi de 'java.util.Properties' (c)~/2A env. 2002.08.29 22H21");
if (arg.length == 0) nom_fic = "l_roman.txt";
else nom_fic = arg[0];
table.chargerRomans(nom_fic);
table.ajout_Romans();
table.afficherRomans();
table.sauvegarderRomans(nom_fic);
es.attente();
}
}
// Question: Que se passe-t-il si on souhaite enregistrer:
Hugo : Les Misérables
Steinbeck : Les Raisins de la colère
Duras : Un barrage contre le Pacifique
Duras : L'Amant
Zola : Germinal
Réponse: On ne peut enregistrer ici qu'un seul ouvrage de M. Duras car deux clés ne peuvent être égales. On peut résoudre ce problème par l'emploi des tables associatives généralisées de couples <Object, Object>.
7.- Les objets de type 'HashMap' [ou 'Hashtable']
********************************
Pour cela, on va construire une table de hachage, objet de la classe 'java.util.HashMap' nommé "hash" et formé de couples <auteur, valeur>. Ici, chaque clé 'auteur' correspond à un nom d'auteur et chaque 'valeur' est au fait un tableau vectoriel 'Vector' contenant éventuellement plusieurs titres du même auteur. Ainsi, la contrainte "deux clés ne peuvent être égales" est respectée comme le montre l'exemple ci-dessous (cf. tab_hach.java) :
import
static java.lang.System.*; // cf. Java 5
import java.io.*;
import java.util.*;
/**
* Classe 'tab_hachage' : Test de qq. méthodes du conteneur 'HashMap'
* @author (c) ~/2A env.
* @version 1.1 2006.08.23
* @since
1.0 2005.10.01
*/
class
tab_hachage {
private
HashMap<String, Vector<String>> hash;
// cf. Java 5
public tab_hachage() { hash= new
HashMap<String, Vector<String>>(); }
public void insere(String author, String
novel) {
Vector<String> livres =
hash.get(author);
if (livres == null) {
// l'auteur 'author' est nouveau ici <==> il n'est pas enregistré encore !
Vector<String> v = new
Vector<String>();
hash.put(author, v);
v.add(novel);
} else {
// le nom de l'auteur est déjà enregistré dans la table !
Vector<String> titres = livres;
if ( !titres.contains(novel) ) titres.add(novel);
// on ajoute le nouveau roman 'novel' parmi les titres anciens
}
}
public void affich() {
Iterator it = hash.keySet().iterator();
while(it.hasNext()) {
String str = (String) it.next();
out.println(str+" ==>
");
Vector<String> titres =
(Vector<String>) hash.get(str);
for (int i=0; i<titres.size();
++i) {
String s = (String) titres.elementAt(i);
out.println(" "+s);
}
}
}
}
/**
* Classe 'tab_hach' : pour tester la classe 'tab_hachage'
* @author (c) ~/2A env.
* @version 1.1 2006.08.23
* @since
1.0 2005.10.01
* @see
tab_hachage
*/
public
class tab_hach {
public static void main (String [] arg) {
out.println("\ntab_hach : Un exemple d'emploi de HashMap en Java 5");
out.println("\t(c)~/2a env. 2006.08.23 21h11 \n");
tab_hachage th = new tab_hachage();
th.insere("Steinbeck","Les Raisins de la col\u00e8re");
th.insere("Hugo","Les Mis\u00e9rables");
th.insere("Duras","Un barrage contre le Pacifique");
th.insere("Duras","L'Amant");
th.insere("Zola","Germinal");
th.insere("Zola","La B\u00eate humaine");
th.affich();
es.attente();
}
}
Exercice 4 [A FAIRE] :
1- Une exécution de ce programme donne le résultat typique suivant [A compléter...]
2- Remplacer le conteneur ‘Vector’ par ‘ArrayList’ désormais et montrer qu’on aboutit aux mêmes résultats.
Question: Comment obtenir une table triée selon l'ordre lexicographique des clés ?
Réponse: Il suffit de remplacer 'HashMap' par 'TreeMap' (cf. tab_hatr.java')
import
static java.lang.System.*; // cf. Java 5
import java.io.*;
import java.util.*;
/**
* Classe 'tab_hachage_triee' : Test de qq. méthodes du conteneur 'TreeMap'
* @author (c) ~/2A env.
* @version 1.15 2006.08.24
* @since
1.0 2005.10.01
*/
class
tab_hachage_triee {
private
TreeMap<String, ArrayList<String>> hash;
// Java 5
public tab_hachage_triee() {
hash= new TreeMap<String, ArrayList<String>>();
}
public void insere(String author, String
novel) {
ArrayList<String> ouvrages =
hash.get(author);
if (ouvrages == null) {
// l'auteur 'author' est nouveau ici <==> il n'est pas enregistré encore !
ArrayList<String> v = new
ArrayList<String>();
hash.put(author, v);
v.add(novel);
}
else { // le nom de l'auteur est déjà enregistré dans la table !
ArrayList<String> titres = ouvrages;
if ( !titres.contains(novel)) titres.add(novel);
// on ajoute le nouveau roman 'novel' parmi les titres anciens
}
}
public void affich() {
Iterator it = hash.keySet().iterator();
while(it.hasNext()) {
String str = (String) it.next();
out.println(str+" : ");
ArrayList<String> titres
= (ArrayList<String>) hash.get(str);
for (int i=0; i<titres.size();
++i) {
String s = (String) titres.get(i);
out.println(" "+s);
}
}
}
}
/**
* Classe 'tab_hatr' : pour tester la classe 'tab_hachage_triee'
* @author (c) ~/2A env.
* @version 1.15 2006.08.24
* @since 1.0 2005.10.01
* @see tab_hachage_triee
*/
public
class tab_hatr {
public static void main (String []
arg) {
out.println("\ntab_hatr: Un exemple d'emploi de TreeMap (Java 5) pour trier la");
out.println("table via un ABO des clés (c)~/2a env. 2006.08.24 09h53\n");
tab_hachage_triee th = new
tab_hachage_triee();
th.insere("Zola","La B\u00eate humaine");
th.insere("Zola","Germinal"); // insertions
th.insere("Hugo","Les Mis\u00e9rables"); // dans le désordre ...
th.insere("Duras","L'Amant");
th.insere("Steinbeck","Les Raisins de la col\u00e8re");
th.insere("Duras","Un barrage contre le Pacifique");
th.affich();
// On doit obtenir la liste par ordre alphabétique des auteurs
// mais les titres des ouvrages restent non triés
es.attente();
}
}
En effet, l'interface 'java.util.Map' est implémentée par les sous-classes 'HashMap' et 'TreeMap' (table dont les clés sont représentées par un arbre binaire ordonné ou ABO – cf. chap. suivant). Elle spécifie une collection de couples <Clé, Valeur> permettant de localiser une et une seule clé, ceci à partir de JDK 1.2.
Le tableau récapitulatif ci-dessous compare les principales méthodes des TAD 'tables associatives' en fonction des différentes versions de Java:
HashMap/TreeMap (JDK 1.2) | Hashtable (JDK 1.1) | Fonctionnalités
--------------------------|---------------------|---------------------------
HashMap() / TreeMap() | Hashtable() | Constructeurs sans arguments
containsKey(Object clef) | containsKey(Object) | Test d'existence d'une clé
containsValue(Object val) | contains(Object) | Test d'existence d'une valeur
boolean isEmpty() | boolean isEmpty() | teste si l'objet Map est vide
keySet() renvoie un objet 'Set' de clés
values() renvoie un objet collection de valeurs
| keys() renvoie un objet 'Enumeration' de clés
| elements() renvoie un objet 'Enumeration' de valeurs
| rehash() réorganise les clés pour optimiser l'accès...
get(Object clef) | get(Object clef) | renvoie un objet Map s'il existe (ou null sinon)
put(Object k, Object v) | put(Object, Object) | modifie l'objet ayant la clé 'k' par la valeur 'v'
remove(Object k) | remove(Object k) | supprime l'objet ayant la clé 'k'
clear() | clear() | supprime tous les couples <clé, valeur>
size() | size() | renvoie la taille de l'objet 'Map'
Object getKey() retourne une clé via l'interface 'Map.entry'
Object getValue() retourne une valeur via l'interface 'Map.entry'
Object.setValue(Object) modifie une valeur via l'interface 'Map.entry'...
entrySet() renvoie un objet 'Set' d'objets 'Entry'
(couple <clé, objet>)
Un exemple d'application de la classe 'TreeMap' est le comptage d'occurrences de mots d'un fichier texte donné.
Exercice 5: Analyser le fichier tab_occu.java ci-après :
import
static java.lang.System.*; // cf. Java 5
import java.io.*;
import java.util.*;
/**
* Classe 'tab_occu' : pour tester la classe 'StreamTokenizer' de l'API
* @author (c) ~/2A env.
* @version 1.1 2006.08.23
* @since
1.0 2005.10.01
*/
public
class tab_occu {
TreeMap<String,
Integer> tableMots;
StreamTokenizer inFlux;
tab_occu(String nomFic) throws java.io.FileNotFoundException {
tableMots= new TreeMap<String,
Integer> ();
inFlux = new StreamTokenizer(new
BufferedReader(new FileReader(nomFic)));
//
inFlux.ordinaryChar('.');
}
public void comptageMots() throws
java.io.IOException {
Integer tmp, un = new Integer(1);
while (inFlux.nextToken() !=
StreamTokenizer.TT_EOF) {
if ( inFlux.ttype ==
StreamTokenizer.TT_WORD) {
Object dejaVu = tableMots.get(inFlux.sval);
if( dejaVu == null) tmp = un;
else
tmp = new Integer(Integer.parseInt(dejaVu.toString())+1);
tableMots.put(inFlux.sval, tmp);
}
}
}
public void affich() {
Iterator it =
tableMots.keySet().iterator();
while(it.hasNext()) {
String str = (String) it.next();
out.println(str+" : "+
tableMots.get(str) + " occurence(s)" );
}
}
public static void main (String [] arg)
throws java.io.IOException {
out.println("tab_occu: Table d'occurences de mots via 'StreamTokenizer' en Java 5");
out.println("\td'après: Leduc & Leduc pp.129-130 (c)~/2a env. 2006.08.23 21h22\n");
String fName;
if (arg.length == 0 ) fName =
"tab_occu.java";
else fName = arg[0];
tab_occu toc = new tab_occu(fName);
toc.comptageMots();
toc.affich();
es.attente();
}
}
Remarque : Si le fichier d’entrée est tab_occu.in , on obtient
les résultats dans tab_occu.txt .
Exercice
6: Etendre la
classe 'es'
en écrivant une méthode de lecture récursive croisée de valeurs
entières signées occupant un octet (cf. type ‘byte’ en Java) via le clavier en
gérant l'exception d'E/S.
Exercice 7:
Etendre la classe 'es' en écrivant une méthode de lecture récursive de
valeurs booléennes par le clavier en gérant l'exception d'E/S. On acceptera
indifféremment des majuscules / minuscules:
{true, false, Vrai, Faux, VRAI, FAUX, V, F, etc... } [A TERMINER en
TPP].
8. Les objets de type ‘ArrayDeque<E>’ et l’interface
‘Deque<E>’
La classe 'java.util.ArrayDeque<E>' définit une file d’attente avec deux extrêmités nommée Dèque (i.e. Deque ou « double ended queue » en anglais) implémentée par un tableau de taille variable à partir de la version JDK 1.6. On peut insérer et supprimer aux deux bouts de la structure de donnée. On retrouve ainsi les caractéristiques à la fois d’une file d’attente émulée par ‘java.util.LinkedList’ et d’une pile implantée par ‘java.util.Stack’. Les principales méthodes de cette classe sont à comparer donc avec celles des classes 'LinkedList<E>' et 'Stack<E>'.
La classe 'ArrayDeque<E>' implémente l’interface ‘Deque<E>’ qui fournit le profil des méthodes permettant d’adjoindre, d’enlever et de consulter un élément dans la dèque courante. Chacune de ces méthodes existe en deux versions: la première génère une erreur d’exécution appelée exception si l’opération échoue alors que la seconde retourne une valeur spéciale (soit ‘null’ soit ‘false’).
Les douze méthodes décrites précédemment sont résumées ci-après:
|
|
Premier Element (‘Head’) |
Dernier Element (‘Tail’) |
||
|
|
‘Throws’ exception |
Valeur spéciale |
‘Throws’ exception |
Valeur spéciale |
|
Adjonction |
addFirst(e) |
offerFirst(e) |
addLast(e) |
offerLast(e) |
|
Suppression |
removeFirst() |
pollFirst() |
removeLast() |
pollLast() |
|
Consultation |
getFirst() |
peekFirst() |
getLast() |
peekLast() |
L’interface
‘Deque<E>’ spécialise l’interface ‘Queue<E>’. Lorqu’une dèque est
employée comme une file, il en résulte un comportement FIFO
(« First-In-First-Out »). Des éléments sont insérés à la fin mais
enlevés au début de la dèque. Les méthodes héritées de l’interface
‘Queue<E>’ sont équivalentes aux propres méthodes de ‘Deque<E>’
selon la table comparative ci-dessous:
|
Méthodes de Queue<E> |
Méthodes équivalentes de Deque<E> |
|
add(e) |
addLast(e) |
|
offer(e) |
offerLast(e) |
|
remove() |
removeFirst() |
|
poll() |
pollFirst() |
|
element() |
getFirst() |
|
peek() |
peekFirst() |
Des
dèques peuvent être utilisées comme des piles LIFO («Last-In-First-Out»).
Lorsqu’une dèque se comporte comme une pile, des éléments sont insérés et
enlevés toujours d’une même extrêmité (soit au
début soit à la fin). Les méthodes de la classe ‘Stack<E>’ sont donc
équivalentes à celles de ‘Deque<E>’ de deux versions :
|
Méthodes ‘Stack’ |
Méthodes équivalentes (I) |
Méthodes équivalentes (II) |
|
push(e) |
addFirst(e) |
addLast(e) |
|
pop() |
removeFirst() |
removeLast() |
|
peek() |
peekFirst() |
peekLast() |
Comme les objets ‘ArrayDeque’ sont des dèques implantées via des tableaux munis de deux index entiers pointant sur la tête (‘head’) et aussi sur le dernier élément (‘tail’), l’emploi des méthodes (I) est conseillé pour émuler une pile générique (cf. PileG21.java – Emploi conseillé). On n’est pas obligé de privilégier la version des méthodes équivalentes (II) afin d’éviter des décalages inutiles comme pour le cas des objets de ‘ArrayList’ (cf. PileG22.java – A éviter !) ou de ‘Vector’ (cf. PileG26.java – A éviter !). Pour les instances de type ‘LinkedList<E>’ qui implémente aussi l’interface ‘Deque<E>’ à partir de JDK 1.6, les deux versions précédentes présentent la même complexité temporelle en O(1) (cf. Chap. « Complexité des algorithmes ») mais, dans tous les cas, la durée d’exécution via ‘ArrayDeque’ reste la plus courte (cf. fichiers PileGjTest, FileGjTest et PileGj & FileGj.java avec j = {1,…, 6} ).
A consulter : Gestion des exceptions
en Java.