PDF de programación - Clase 7: Abstracción de iteración e iteradores

Clase 7: Abstracción de iteración e iteradores

7.1 Introducción

En este tema, describiremos la abstracción de iteración y los iteradores. Los iteradores son una
generalización del mecanismo de iteración disponible en la mayoría de los lenguajes de programación.
Éstos permiten a los usuarios iterar sobre los tipos de datos arbitrarios de un modo práctico y eficaz.

Por ejemplo, un claro uso de un conjunto de elementos consiste en llevar a cabo alguna operación para
cada uno de sus elementos:

Para todos elementos del conjunto

hacer acción

En este tema, discutiremos cómo se puede especificar e implementar la abstracción de iteración. También
describiremos la exposición de representación relacionada con el uso de los iteradores.

7.2 Lecturas

Lea el capítulo 6 de Liskov y Guttag antes de continuar. La primera mitad de los apuntes de este tema
está basada en el capítulo 6 de este libro, por lo que no se volverá a repetir aquí.

7.3 Exposición de representación en iteradores

Considere la implementación de un iterador para una clase denominada IntSet. La estructura general
de la clase IntSet sería de la siguiente forma:

public class IntSet {

private Vector els; // representación
private int size; // representación

// constructores, etc., van aquí, vea pág. 88 de Liskov

…

public Iterator elems() {

return new IntGen(this); }

// clase interna estática (static inner class )
private static class IntGen implements Iterator {

public boolean hasNext() { … }
public Object next() throws NoSuchElementException { … }
public void remove(Object o) { … }

} // fin de IntGen

}

70

Observe el método adicional remove() en la clase IntGen. No es necesario que se implemente, es
opcional. El método permite que se extraiga un elemento de IntSet mientras se itera sobre los elementos
del conjunto. ¡Debe implementarse muy cuidadosamente!

Observe que en Liskov no se permiten modificaciones en el objeto sobre el que se da la iteración (es
decir, en nuestro ejemplo, IntSet). Sin embargo, la interfaz Iterator de Java, incluye el método opcional
remove().

Ahora queremos implementar la clase IntGen. Nos damos cuenta de que la clase IntSet está representada
por el objeto de tipo Vector els, y que la clase Vector posee un método que devuelve un iterador, así que
podríamos, perfectamente, implementar nuestro método elems() de la siguiente forma:

public class IntSet {

…

public Iterator elems() {
return els.iterator(); }

}

El generador devuelto, els.iterator(), provee a los métodos next(), hasNext() y remove(). Esto nos ahorra
mucho trabajo, pero desafortunadamente, provoca una sutil forma de exposición de representación.

Hemos tratado ya una forma simple de exposición de representación relacionada con los métodos
remove() en IntSet y Vector. IntSet implementa un método remove() que puede afectar al método size().
El método remove() de la clase Vector no conoce el tamaño (size) de IntSet. Por tanto, si un cliente invoca
al método remove() de Vector directamente, algunas cosas pueden fallar, p. ej. size se calculará
incorrectamente.

Del mismo modo, en la clase Iterator, si el cliente utiliza directamente g.remove(), donde g = els.iterator(),
dado que hay un estado compartido entre els.iterator() y el campo els de Vector, varios errores pueden
tener lugar.

Resumiremos el problema mediante el dibujo que se muestra a continuación:

71

Class

IntSet
size()
remove()
elems()

els

Vector
remove()

BAD

dependence

Client

elems()


els.iterator()
remove()
next()
hasNext()

shared
state

¿Qué deberíamos hacer? Podríamos, obviamente, retirar el método remove() de la clase IntGen o incluso
no llamarlo más, pero esto sería igual que abandonar el problema. Necesitamos que la implementación del
método remove() de la clase IntGen sea similar a la implementación del método remove() de la clase
IntSet, es decir, manteniendo del mismo modo la integridad del objeto IntSet. Éste sería pues, el único
método accesible para el cliente. El método remove() de IntGen puede llamar a g.remove(), dondeg =
els.iterator(), el cual manipula la representación subyacente mientras el iterador se está utilizando. Esto
queda resumido en el dibujo siguiente:

xxxxxxxx
Class

IntSet
size()
remove()
…

els

Vector
remove()

Iterator Inner Class

IntGen
remove()

els

els.iterator()
remove()
next()
hasNext()

shared
state

72

Observe que implementar el método remove() de la clase IntGen, invocando al método remove() del
objeto de tipo Vector, es decir, els.remove(), no es tampoco una buena idea. Esto podría arruinar al
iterador con respecto a los métodos next() o hasNext( ).



73