www.infkoffler.com - Site de cours d'informatique

Accueil

Java Standard Edition

Java EE 5

Visual Basic .Net 2005

Cours Javascript - DOM - DHTML

Nouveautés sur le site

Contacts

Accueil > Java Standard Edition > Les collections(3): AbstractCollection(java.util)

____________________________________________________________________________________________________

Connexion

Les collections(3): AbstractCollection(java.util)

Sommaire :

I) Généralités
II) Les méthodes abstraites
III) Les méthodes implémentées

I) Généralités

En résumé, on retient que AbstractCollection est une implémentation minimale pour l'interface Collection. Ainsi, il ne reste plus qu'à hériter de cette classe, et d'implémenter les deux méthodes iterator et size, pour les collections non modifiables. Et il faut, de plus, redéfinir la méthode add pour les collections modifiables. Le développeur peut, de plus, redéfinir les méthodes qu'il peut implémenter de manière plus efficace.

II) Les méthodes abstraites

Les deux méthodes abstraites sont:
Ce sont les primitives de base indispensables pour l'implémentation des autres méthodes de AbstractCollection. Tout se base sur ces deux méthodes. En effet, AbstractCollection ne possède pas l'implémentation de la structure de données interne qui contient les données de la collection. Par conséquent, elle a besoin qu'on lui fournisse la méthode size. De plus, avec un itérateur( qu'elle obtient par l'appel de la méthode iterator() ), elle peut parcourir la collection, sans avoir besoin de la structure de données interne de la collection. Il n'est pas possible pour elle d'implémenter iterator(), car elle ne peut pas savoir comment parcourir la collection, ne disposant pas de la structure interne contenant les données de la collection.

Regardons la méthode add:
On remarque que add ne fait, par défaut, que déclencher une UnsupportedOperationException.
Le développeur devra redéfinir cette méthode, s'il souhaite supporter cette opération.
En effet, il n'est pas possible d'implémenter pour le moment cette méthode, car on n'est pas sûr que la collection soit modifiable!

III) Les méthodes implémentées

Nous allons voir les méthodes caractéristiques.
Regardons l'implémentation de la méthode contains. Elle travaille à partir d'un itérateur, qu'elle obtient en appelant simplement sa méthode iterator().

Elle se sert des méthodes hasNext et next de l'itérator. Elle ne fait que parcourir ainsi toute la collection, jusqu'à trouver un élément égal à l'objet recherché.

/**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over the collection looking for the
     * specified element.  If it finds the element, it removes the element
     * from the collection using the iterator's remove method.
     *
     * <p>Note that this implementation throws an
     * <tt>UnsupportedOperationException</tt> if the iterator returned by this
     * collection's iterator method does not implement the <tt>remove</tt>
     * method and this collection contains the specified object.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     */
    public boolean remove(Object o) {
	Iterator<E> e = iterator();
	if (o==null) {
	    while (e.hasNext()) {
		if (e.next()==null) {
		    e.remove();
		    return true;
		}
	    }
	} else {
	    while (e.hasNext()) {
		if (o.equals(e.next())) {
		    e.remove();
		    return true;
		}
	    }
	}
	return false;
    }

La méthode remove utilise doublement l'itérateur. D'abord pour retrouver l'objet, en parcourant la collection avec l'itérateur. Puis en appelant la méthode remove() de l'itérateur. On remarque que si la méthode remove de l'itérateur n'est pas supportée, alors elle déclenchera une UnsupportedOperationException(java.lang), qui se propagera au remove de AbstractCollection, quand celui-ci essayera d'appeler le remove de l'itérateur. Cette exception sera, de nouveau, propagée par remove de AbstractCollection.
Elle se sert de la méthode size()

/**
     * {@inheritDoc}
     *
     * <p>This implementation returns an array containing all the elements
     * returned by this collection's iterator, in the same order, stored in
     * consecutive elements of the array, starting with index {@code 0}.
     * The length of the returned array is equal to the number of elements
     * returned by the iterator, even if the size of this collection changes
     * during iteration, as might happen if the collection permits
     * concurrent modification during iteration.  The {@code size} method is
     * called only as an optimization hint; the correct result is returned
     * even if the iterator returns a different number of elements.
     *
     * <p>This method is equivalent to:
     *
     *  <pre> {@code
     * List<E> list = new ArrayList<E>(size());
     * for (E e : this)
     *     list.add(e);
     * return list.toArray();
     * }</pre>
     */
    public Object[] toArray() {
        // Estimate size of array; be prepared to see more or fewer elements
	Object[] r = new Object[size()];
        Iterator<E> it = iterator();
	for (int i = 0; i < r.length; i++) {
	    if (! it.hasNext())	// fewer elements than expected
		return Arrays.copyOf(r, i);
	    r[i] = it.next();
	}
	return it.hasNext() ? finishToArray(r, it) : r;
    }

La méthode toArray gère les modifications concurrentes. C'est-à-dire qu'au fûr et à mesure que la collection est recopiée dans le tableau, la collection peut avoir diminué ou agrandi de taille, par rapport à sa taille initiale.
On s'aperçoit qu'un tableau d'Object r, de la taille de la collection, est alloué au départ. Puis une boucle est faite, qui va remplir chaque index du tableau, en utilisant un itérateur pour parcourir la collection. Dans le cas où l'itérateur arrive à la fin de la collection de manière imprévue( c'est-à-dire que la collection a été dimininuée en même temps qu'on travaillait), on a fini notre travail. Donc on retourne une copie de r, avec les i éléments( une copie pour avoir un tableau à la bonne taille).
Dans le cas où la boucle ne s'est pas terminée prématurément, on vérifie que l'itérateur est bien terminé. Si ce n'est pas le cas, c'est que la collection a été agrandie de manière concurrente.
On se sert alors de la méthode privée finishToArray, qui va finir de recopier les valeurs manquantes.
Enfin, si le tableau n'a pas été agrandi, c'est que tout s'est passé sans modification concurrente, on retourne alors r.

REINDEMPTEE
/**
     * Reallocates the array being used within toArray when the iterator
     * returned more elements than expected, and finishes filling it from
     * the iterator.
     *
     * @param r the array, replete with previously stored elements
     * @param it the in-progress iterator over this collection
     * @return array containing the elements in the given array, plus any
     *         further elements returned by the iterator, trimmed to size
     */
    private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
	int i = r.length;
        while (it.hasNext()) {
            int cap = r.length;
            if (i == cap) {
                int newCap = ((cap / 2) + 1) * 3;
                if (newCap <= cap) { // integer overflow
					if (cap == Integer.MAX_VALUE)
						throw new OutOfMemoryError
						("Required array size too large");
					newCap = Integer.MAX_VALUE;
				}
				r = Arrays.copyOf(r, newCap);
			}
			r[i++] = (T)it.next();
        }
        // trim if overallocated
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }

C'est la méthode privée utilisée, ci-dessus, par la méthode public Object[] toArray().
Elle intervient lorsque l'itérateur a retourné plus d'éléments que prévu.

On fait une boucle tant que l'itérateur a un hasNext(): en effet, ici on veut copier tous les éléments de la collection, et agrandir le tableau recepteur, si besoin est.
i est initialisé au début avec la taille de départ du tableau, puis i est incrémenté de 1 à chaque fois qu'on copie un élément dans le tableau. Donc i contient l'index du dernier élément utilisé dans le tableau, + 1.
A chaque fois que i atteint la taille du tableau, on doit réallouer un nouveau tableau, qui fait une fois et demie la taille de l'ancien. Si cette nouvelle taille n'est pas overflow, on alloue un nouveau tableau r, en prenant soin de recopier les valeurs du tableau précédent.
Si on est overflow, c'est à dire si la nouvelle capacité est < l'ancienne capacité, alors on donne comme nouvelle capacité integer.MAX_VALUE. Et si, la fois suivante, cap = integer.MAX_VALUE, c'est que le max_value n'était pas suffisant, donc on jette une OutOfMemoryError(java.lang).

A chaque tour du while, on inscrit l'élément dans le tableau, à la place i. Enfin, après la boucle while, il suffit de redimensionner le tableau si nécessaire, en réallouant un nouveau tableau, si i!=r.length( c'est-à-dire si le tableau r n'est pas complètement utilisé).

RETOUR HAUT