PDF de programación - Algoritmos y Estructuras de Datos

Algoritmos y Estructuras de Datos

Iteradores

Guillermo Román Díez

groman@fi.upm.es

Universidad Politécnica de Madrid

Curso 2015-2016

Guillermo Román, UPM

AED: Introducción

1/26

Iteradores

Es muy común tener que iterar linealmente sobre todos los
elementos de un TAD

Recordamos el código del método show

public static <E > void show ( PositionList <E > list ) {

if ( list == null ) return ;
Position <E > cursor = list . first () ;
while ( cursor != null ) {

System . out . println ( cursor . element () ) ;
cursor = list . next ( cursor ) ;

}

}

Poblemas de este código

Es específico para la lista de posiciones
El programador “cliente” es el responsable de iterar
adecuadamente

Guillermo Román, UPM

AED: Introducción

2/26

Iteradores

Se puede abstraer el cursor para tener código reutilizable para
otros TAD convirtiendo el cursor en un TAD llamado Iterador
Un objeto Iterador permite iterar linealmente sobre los
elementos de otro TAD

La iteración se realiza utilizando métodos del Iterador
No se usan métodos del TAD
Se puede reutilizar código para iterar otros TADs

public static <E > void show ( PositionList <E > list ) {

Iterator <E > it = list . i t e r a t o r () ;

while ( it . hasNext () ) {

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

}

}

// Nos da un i t e r a d o r
// ya i n i c i a l i z a d o
// B u c l e m i e n t r a s
// hay mas e l e m e n t o s
// C o g e m o s el e l e m e n t o
// y q u e d a el c u r s o r
// a v a n z a d o

Guillermo Román, UPM

AED: Introducción

3/26

Iterador

El método iterator devuelve un iterador inicializado en el
primer elemento de la estructura de datos
hasNext devuelve true mientras haya algún elemento
pendiente
next devuelve el elemento accesible desde el cursor

Deja el cursor avanzado (post-incremento)
Esto se conoce como un “efecto secundario” o “side effect”

Es análogo al recorrido de un array con post-incremento

int i = 0;
while ( i < arr . length ) {

System . out . println ( arr [ i ++]) ;

}

Guillermo Román, UPM

AED: Introducción

4/26

Ejemplo con otra estructura

Pregunta

¿cuáles serían los cambios sobre el método show para recorrer una
estructura de datos de tipo FIFO o LIFO?

public static <E > void show (PositionList <E > list ) {

Iterator <E > it = list . i ter ato r () ;
while ( it . hasNext () ) {

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

}

}

Guillermo Román, UPM

AED: Introducción

5/26

Ejemplo con otra estructura

Pregunta

¿cuáles serían los cambios sobre el método show para recorrer una
estructura de datos de tipo FIFO o LIFO?

public static <E > void show (FIFO <E > list ) {

Iterator <E > it = list . i ter ato r () ;
while ( it . hasNext () ) {

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

}

}

Guillermo Román, UPM

AED: Introducción

5/26

Ejemplo con otra estructura

Pregunta

¿cuáles serían los cambios sobre el método show para recorrer una
estructura de datos de tipo FIFO o LIFO?

public static <E > void show (FIFO <E > list ) {

Iterator <E > it = list . i ter ato r () ;
while ( it . hasNext () ) {

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

}

}

Ahora con un bucle for

for ( Iterator <E > it = list . i ter ato r () ; it . hasNext () ; ) {

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

}

Guillermo Román, UPM

AED: Introducción

5/26

Interfaces Iterator<T> e Iterable<T>

java.util.Iterator<E> declara todos los métodos que debe
implementar un objeto iterador

public i n t e r f a c e Iterator <E > {

public E next () ;
/* o b l i g a t o r i o */
public boolean hasNext () ; /* o b l i g a t o r i o */
public void remove () ;

/* p r o b l e m a t i c o */

}

java.util.Iterable<E> es la pieza que nos permitirá asociar
iteradores a un TAD

public i n t e r f a c e Iterable <E > {

public Iterator <E > i ter ato r () ;

}

Guillermo Román, UPM

AED: Introducción

6/26

Métodos Iterator

hasNext indica si el cursor referencia a un elemento (es
distinto de null)

NO debe entenderse como ¿hay siguiente cursor?

next guarda el elemento al que apunta el cursor, avanza el
cursor y devuelve el elemento guardado

NO debe interpretarse como dame el siguiente elemento
Puede dejar el cursor a null después de avanzar (si es el
último)

remove borra el elemento que devolvió next en su última
ejecución

Es necesario que previamente se haya ejecutado next
No es obligatorio implementarlo en la asignatura

Guillermo Román, UPM

AED: Introducción

7/26

Ejemplo Iterador

Iterator <E > = tad . i ter ato r () ;

{A , B }
↑

cursor

hasNext () dev uel ve true
next () avanza el cursor a B y d evu elv e A

Guillermo Román, UPM

AED: Introducción

8/26

Ejemplo Iterador

Iterator <E > = tad . i ter ato r () ;

{A , B }
↑

cursor

{A , B }
↑

cursor

hasNext () dev uel ve true
next () avanza el cursor a B y d evu elv e A

hasNext () dev uel ve true
next () avanza el cursor a null y d evu elv e B

Guillermo Román, UPM

AED: Introducción

8/26

Ejemplo Iterador

Iterator <E > = tad . i ter ato r () ;

hasNext () dev uel ve true
next () avanza el cursor a B y d evu elv e A

hasNext () dev uel ve true
next () avanza el cursor a null y d evu elv e B

hasNext () dev uel ve false
next ()

lanza N o S u c h E l e m e n t E x c e p t i o n

{A , B }
↑

cursor

{A , B }
↑

cursor

{A , B }

cursor

↓
null

Guillermo Román, UPM

AED: Introducción

8/26

Objeto Iterador

Si al crearse el iterador el TAD está vacío

hasNext devuelve false
next lanza NoSuchElementException

Si el TAD no está vacío

hasNext devuelve true
next avanza el cursor devolviendo el elemento actual

Si el cursor apunta a null

hasNext devuelve false
next lanza NoSuchElementException

Pregunta

¿es posible usar a la vez dos iteradores sobre el mismo TAD?

Guillermo Román, UPM

AED: Introducción

9/26

Método remove

Debe borrar del TAD el elemento devuelto por el último next
Si no ha habido next → IllegalStateException

while ( it . hasNext () ) {

it . next () ;
it . remove () ;

}

// c o r r e c t o

if (! it . hasNext () )

it . remove () ;

// Incorrecto , no hay e l e m e n t o s

if ( it . hasNext () )

it . remove () ;

// Incorrecto , no hay next previo

it . next () ;
it . remove () ;

// c o r r e c t o
// c o r r e c t o

Guillermo Román, UPM

AED: Introducción

10/26

Ejemplo: Décimo

Ejercicio

Método que devuelve el décimo elemento de una lista

Guillermo Román, UPM

AED: Introducción

11/26

Ejemplo: Décimo

Ejercicio

Método que devuelve el décimo elemento de una lista

public static <E > E tenth ( PositionList <E > list )

throws N o S u c h E l e m e n t E x c e p t i o n {

if ( list . size () < 10) {

throw new N o S u c h E l e m e n t E x c e p t i o n () ;

}
Iterator <E > it = list . i ter ato r () ;
for ( int i = 1; i < 10; i ++) {

it . next () ;

}
return it . next () ;

}

Guillermo Román, UPM

AED: Introducción

11/26

Ejemplo: Borra todos

Ejercicio

Método que borra todos los elementos de una lista

Guillermo Román, UPM

AED: Introducción

12/26

Ejemplo: Borra todos

Ejercicio

Método que borra todos los elementos de una lista

public <E > void d e l e t e A l l ( PositionList <E > list ) {

Iterator <E > it = list . i ter ato r () ;
while ( it . hasNext () ) {

it . next () ;
it . remove () ;

}

}

NOTA!!
Recordad que remove debe invocarse siempre después de next

Guillermo Román, UPM

AED: Introducción

12/26

Ejemplo: Suma

Ejercicio

Método que devuelve la suma de los elementos de una lista de enteros

Guillermo Román, UPM

AED: Introducción

13/26

Ejemplo: Suma

Ejercicio

Método que devuelve la suma de los elementos de una lista de enteros

public int s u m a E l e m s ( PositionList < Integer > list ) {

Iterator <E > it = list . i ter ato r () ;
int suma = 0;
while ( it . hasNext () )

suma += it . next () ; // A s u m i m o s != null

return suma ;

}

Guillermo Román, UPM

AED: Introducción

13/26

Ejemplo: Sublista

Ejercicio

Método que indica si una lista es sublista de otra

Guillermo Román, UPM

AED: Introducción

14/26

Ejemplo: Sublista

Ejercicio

Método que indica si una lista es sublista de otra

public static <E > boolean sublist ( PositionList <E > l1 ,

PositionList <E > l2 ) {

if ( l1 == null || l2 == null ) return false ;
if ( l1 == l2 ) return true ;
Iterator <E > it1 = l1 . i ter ato r () ;
boolean res = false ;
while ( it1 . hasNext () &&

( res = this . member ( it1 . next () , l2 ) ) )

;

return res ;

}

Guillermo Román, UPM

AED: Introducción

14/26

Ejemplo: Sublista

Ejercicio

Método que indica si dos listas son iguales

Guillermo Román, UPM

AED: Introducción

15/26

Ejemplo: Sublista

Ejercicio

Método que indica si dos listas son iguales

<E > boolean iguales ( PositionList <E > list1 ,

PositionList <E > list2 ) {

...
Iterator <E > it1 = list1 . i ter ato r () ;
Iterator <E > it2 = list2 . i ter ato r () ;
E e1 , e2 ;
boolean iguales = true ;
while ( it1 . hasNext () && iguales ) {

e1
e2
iguales = i g u a l e s E l e m ( e1 , e2 ) ;

= it1 . next () ;
= it2 . next () ;

}
return iguales ;

}

Guillermo Román, UPM

AED: Introducción

15/26

¿cómo y cuándo usar iteradores?

Los iteradores se usan para iterar sobre TADs que son
colecciones de elementos

No todos los TADs serán colecciones de elementos
Hay TADs que son colecciones de elementos pero dada su
naturaleza no son iterables

El problema debe requerir únicamente el acceso a elementos
(next)

No permite el acceso al nodo (sólo al elemento)

Sólo se puede borrar el último elemento devuelto por el
iterador (remove)

Guillermo Román, UPM

AED: Introducción

16/26

Implementación de Iteradores: Alternativas

El objeto iterador itera usando los métodos del interfaz del
TAD

El iterador puede usarse para iterar sobre objetos de cualquier
clase que implemente el interfaz
El iterador puede iterar sobre cualquier clase que implemente
’I’ si usa únicamente métodos de ’I’ para ”mover” el cursor.

El objeto mueve el cursor accedi