Les Collections

Les collections

Page 1

Les collections Java

n

Une collection (parfois appelée conteneur) est un objet qui regroupe de multiples éléments.

n

Un framework de collections est une architecture unifiée de représentation et de manipulation de collections.

n

Le framework de collections java consiste en : u

Des interfaces

u

Des collections concrètes (Structures de données réutilisables).

u

Des algorithmes (Fonctionnalités réutilisables)

copyright ©Thierry Douchet Janvier 2006

2

Présentation du framework

«interface» Iterator

«interface» ListIterator

«interface» Collection

utilise

utilise

«interface» Map

utilise

«interface» List

«interface» Set

«interface» SortedMap

HashMap

LinkedList

Vector

ArrayList

«interface» SortedSet

TreeMap

HashSet

Stack TreeSet

copyright ©Thierry Douchet Janvier 2006

3

L’interface Collection

n

Une collection est utilisée pour manipuler n’importe quelle collection réelle à partir d’une interface de services générale : public interface Collection { boolean add(Object o); boolean addAll(Collection c); void clear(); boolean contains(Object o); boolean containsAll(Collection c); boolean equals(Object o); int hashCode(); boolean isEmpty(); Iterator iterator(); boolean remove(Object o); boolean removeAll(Collection c); boolean retainAll(Collection c); int size(); Object[ ] toArray(); Object[ ] toArray(Object a[ ]); copyright ©Thierry Douchet } Janvier 2006

4

L’interface List

n

C’est une collection ordonnée (parfois appelée Séquence) qui peut contenir des éléments dupliqués (redondance).

n

Elle vient compléter l’interface collection en ajoutant des méthodes spécifiques pour les listes. public interface List extends Collection { boolean add ( int index , Object o ) ; Object remove ( int index ) ; Object get ( int index ) ; Object set ( int index , Object o ) ; public int indexOf ( Object o ) public int lastIndexOf ( Object o ) ListIterator listIterator() ; List SubList ( int fromIndex , int toIndex ) ; }

copyright ©Thierry Douchet Janvier 2006

5

Implémentation de List

n

Java ne propose pas d’implémentation directe des interfaces. implémentations se situent dans une hiérarchie de classes abstraites. «interface» Iterator

«interface» ListIterator

utilise

utilise

«interface» Collection

«interface» List

Ces

AbstractCollection

AbstractList

ArrayList

copyright ©Thierry Douchet Janvier 2006

6

La classe AbstractCollection

public abstract class AbstractCollection implements Collection { protected AbstractCollection() { } public abstract int size(); public abstract Iterator iterator(); public boolean isEmpty() { return size() == 0; } public boolean contains(Object o) { Iterator e = iterator(); if (o==null) { while (e.hasNext()) if (e.next()==null) } else { while (e.hasNext()) if (o.equals(e.next())) } return false; } }

return true;

return true;

copyright ©Thierry Douchet Janvier 2006

7

La classe AbstractList

n

La classe AbstractList redéfinit les méthodes de la classe List ou requalifie d’abstract celles qu’elle n’est pas capable de définir. public abstract class AbstractList extends AbstractCollection implements List { abstract public Object get(int index); public int indexOf ( Object o ) { ListIterator e = listIterator(); if (o==null) { while (e.hasNext()) if (e.next()==null) return e.previousIndex(); } else { while (e.hasNext()) if (o.equals(e.next())) return e.previousIndex(); } return -1; } } copyright ©Thierry Douchet Janvier 2006

8

La classe ArrayList

n

La classe ArrayList vient compléter la hiérarchie en donnant un sens à l’ensemble des méthodes restantes : public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { private transient Object elementData[] ; private int size ; public ArrayList ( int initialCapacity ) { super(); if (initialCapacity < 0) throw new IllegalArgumentException ( "Illegal Capacity: "+ initialCapacity ); this.elementData = new Object[initialCapacity]; } public ArrayList() { this ( 10 ) ; } public boolean add(Object o) { ensureCapacity(size + 1); // Increments modCount!! elementData[size++] = o; return true; } } copyright ©Thierry Douchet Janvier 2006

9

Exemple

import java.util.* ; class Demo { public static void main (String args [ ]) { ArrayList list ; list = new ArrayList () ; list.add ( new Point ( 10 , 20 ) ) ; list.add ( new Point ( 20 , 40 ) ) ; list.add ( new Point ( 30 , 50 ) ) ; for ( int i = 0 ; i < list.size () ; i++ ) ( ( Point ) list.get ( i ) ).print () ; } }

copyright ©Thierry Douchet Janvier 2006

10

Recherche d’un élément

n

La méthode contains () permet de rechercher si un élément est présent dans le tableau : import java.util.* ; class Demo { public static void main (String args [ ]) { ArrayList list = new ArrayList () ; ; Point p1 = new Point ( 10 , 20 ) ; list.add ( p1 ) ; list.add ( new Point ( 20 , 40 ) ) ; list.add ( new Point ( 30 , 50 ) ) ; if ( list.contains ( p1 ) ) System.out.println ( "ok" ) ; else System.out.println ( "non ok " ) ; if ( list.contains ( new Point ( 20 , 40 ) ) ) System.out.println ( "ok" ) ; else System.out.println ( "non ok " ) ; } } copyright ©Thierry Douchet Janvier 2006

11

Redéfinition de la méthode equals

n

La classe Point doit redéfinir la méthode equals :

class Point { ….. public boolean equals ( Object obj ) { if ( ! ( obj instanceof Point ) ) return false ; return ( ( x == ( ( Point ) obj ).x ) && ( y == ( ( Point ) obj ).y ) ) ; } }

copyright ©Thierry Douchet Janvier 2006

12

Les itérateurs

n

Un itérateur permet de parcourir une collection sans se soucier de la nature des objets.

n

Le parcours d’une collection s’effectue de la manière suivante :

n

u

appel de la méthode iterator() sur le conteneur pour renvoyer un iterator.

u

récupérer l'objet suivant dans la séquence grâce à sa méthode next().

u

vérifier s'il reste encore d'autres objets dans la séquence via la méthode hasNext().

On a également la possibilité d’enlever le dernier élément renvoyé par l'itérateur avec la méthode remove().

copyright ©Thierry Douchet Janvier 2006

13

Exemple

import java.util.* ; class Demo { public static void main ( String args [ ] ) { ArrayList list ; list = new ArrayList () ; list.add ( "chaine1" ) ; list.add ( "chaine2" ) ; list.add ( "chaine3" ) ; for ( Iterator i = list.iterator () ; i.hasNext ( ) ; ) System.out.println ( i.next() ) ; } }

copyright ©Thierry Douchet Janvier 2006

14

L’interface Set

n

Elle correspond à un groupe d’objets qui n’accepte pas 2 objets égaux au sens de equals (comme les ensembles des mathématiques).

n

L’interface Set n’ajoute aucune méthode à l’interface Collection. Elle ne spécifie que les restrictions attendues sur les méthodes de base (unicité des objets).

n

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) import java.util.* ; public class Demo { public static void main ( String args[] ) { Set s = new HashSet ( ); String tab[] = { "a" , "b" , "c" , "b" } ; for ( int i = 0 ; i < tab.length ; i++ ) if ( ! s.add ( tab[i] ) ) System.out.println ("duplication detectee : " + tab[i] ); System.out.println ( s.size() + " mots dans le set " + s ); } } copyright ©Thierry Douchet Janvier 2006

15

La classe TreeSet

n

C’est un ensemble trié. Il garantit que les éléments sont rangés dans leur ordre naturel.

n

Pour effectuer le tri, le TreeSet a besoin d’utiliser une méthode de comparaison.

n

Une relation d’ordre sur des objets peut être définie en implémentant l’interface Comparable

n

L’interface Comparable consiste en une seule opération : public interface Comparable { public int compareTo ( Object o ) ; }

n

Les classes implémentant cette interface peuvent être triées automatiquement.

copyright ©Thierry Douchet Janvier 2006

16

L’interface Comparable

n

n

Une relation d’ordre naturelle n’est pas toujours suffisante : u

Ordonner des objets à travers une autre relation d’ordre

u

Ordonner des objets qui n’implémentent pas l’interface Comparable

Un comparateur (interface Comparator) peut être utilisé dans le cas où la relation d’ordre naturelle ne suffit pas : public interface Comparator { public int compare ( Object o1 , Object o 2 ) ; }

copyright ©Thierry Douchet Janvier 2006

17

Exemple

class Revue implements Comparable { private String titre ; private int numero ; public Revue ( int _numero , String _titre ) { titre = _titre ; numero = _numero ; public int getNumero () {return numero ; } public String getTitre () {return titre ; }

}

public String toString () { return titre + " " + numero ; } public int compareTo ( Object obj ) { return titre.compareTo ( ((Revue ) obj ).titre) ; } }

copyright ©Thierry Douchet Janvier 2006

18

Exemple

import java.util.* ; public class Demo { public static void main ( String args[] ) { TreeSet listeRevues = new TreeSet () ; listeRevues.add ( new Revue ( 1 , "Geo") ) ; listeRevues.add( new Revue ( 2 , "Paris Match" ) ) ; listeRevues.add( new Revue ( 3 ,"France Football") ) ; listeRevues.add( new Revue ( 4 , "Paris Match" ) ); for ( Iterator i = listeRevues.iterator () ; i.hasNext () ; ) System.out.println ( i.next () ) ; } }

copyright ©Thierry Douchet Janvier 2006

19

L’interface Map

n

L’interface Map correspond à un groupe de couples objets-clés. public interface Map { void clear() boolean containsKey(Object clé) boolean containsValue(Object valeur) Set entrySet()

retourne null si la clé n’existe pas

Object get(Object clé) boolean isEmpty() Set keySet()

Object put(Object clé, Object valeur) void putAll(Map map) void remove(Object key) int size() Collection values() }; n

Une clé repère un et un seul objet.

n

Deux clés ne peuvent être égales au sens de equals. copyright ©Thierry Douchet Janvier 2006

20

Les HashMap

n

n

Les Classes qui implémentent l’interface Map sont : u

HashMap, table de hachage ; garantit un accès en temps constant

u

TreeMap, arbre ordonné suivant les valeurs des clés

Exemple import java.util.* ; public class Demo { public static void main ( String args[] ) { HashMap listePersonne = new HashMap () ; listePersonne.put( "Bond" , new Personne ( "Bond" , "James" , 45) ) ; listePersonne.put( "Jones" , new Personne ( "Jones" , "Indiana" , 40 )) ; (( Personne )listePersonne.get ( "Bond" )).afficher() ; } } copyright ©Thierry Douchet Janvier 2006

21

Les utilitaires

n

La classe Collections fournit un ensemble d’algorithme pour travailler sur les collections (tri, recherche, copie…) : public class Demo { public static void main ( String args[] ) { String tabChaine [] = { "chaine3" , "chaine1" , "chaine2" } ; List listeChaine ; listeChaine = Arrays.asList ( tabChaine ) ; Collections.sort ( listeChaine ) ; for ( Iterator i = listeChaine.iterator () ; i.hasNext () ; ) System.out.println (i.next()); } }

copyright ©Thierry Douchet Janvier 2006

22