Introducción a la Programación · 2014-01-09 · 4 Introducción a la Programación Como vemos en...

Introducción a la Programación

Tema 6. Iterables: Implementación, Composición y Uso

1. Introducción .......................................................................................................................... 1

2. Iterables e Iteradores ........................................................................................................... 2

3. Ejemplos de Iterables ........................................................................................................... 4

4. Operaciones sobre iterables: los tipos Function y Predicate ............................................ 11

5. Clausuras ............................................................................................................................. 13

6. Composición de Iterables, Predicados , Expresiones y Órdenes....................................... 14

7. Otros iterables: listas virtuales .......................................................................................... 20

8. Implementación de iterables, órdenes, expresiones y predicados compuestos ............. 22

9. El tipo Query ....................................................................................................................... 27

10. Problemas propuestos .................................................................................................... 33

1. Introducción

En el tema anterior vimos que es muy importante la reutilización para conseguir un software

de calidad. Esta reutilización es, también, muy importante en el diseño de las soluciones a los

problemas. Existen muchos problemas cuya solución sigue un mismo patrón.

Los patrones de software son soluciones probadas para determinados tipos de problemas que

se presentan a menudo en distintos contextos pero con características similares. Estos

patrones de software tienen muchas ventajas:

Probados, porque han sido usados en múltiples problemas anteriormente.

Reutilizables, porque los problemas que resuelven aparecen repetidos múltiples veces en

las aplicaciones.

Expresivos, porque establecen unos conceptos y en muchos casos una notación que

permite plantear la solución a un problema concreto como un caso particular de una

solución general.

La factoría de un tipo, ya vista en temas anteriores, es uno de los patrones de diseño. El

segundo patrón cuyo uso está muy extendido es el patrón Iterator. Aquí estudiaremos los tipos

Iterator e Iterable. El segundo es una factoría de objetos del primer tipo.

2 Introducción a la Programación

2. Iterables e Iteradores

Normalmente hay que hacer mucho código consistente en recorrer todos los elementos de un

agregado de objetos y hacer diversos tratamientos con ellos. Por ejemplo los vistos en el tema

cuatro. Para poder reutilizar el código de los diversos tratamientos es necesario que todos los

agregados de datos sean vistos desde el exterior como similares. Es decir que todos los

agregados de datos ofrezcan el mismo contrato a sus posibles clientes. La solución a este

problema es que cada agregado de datos implemente el contrato Iterable. Ahora veremos los

detalles de este contrato pero antes veamos las ventajas que ofrece.

En primer lugar si un agregado de datos ag implementa el contrato Iterable<T> entonces el

agregado puede ser recorrido mediante un for extendido de Java.

…

for( T e : ag){

Test.mostrar(e);

}

…

El código anterior es el mismo para cualquier agregado A que implemente Iterable<T>. Como

hemos visto en temas anteriores la sentencia for anterior recorre cada elemento del agregado

y termina cuando los haya recorrido todos.

Antes de pasar a la implementación veamos los tipos Iterable<T> e Iterator<T>. Para que un

agregado de datos pueda recorrerse mediante un for extendido debe ofrecer la interfaz

Iterable.

Cada agregado de datos puede tener diversas formas de recorrer los objetos que lo

componen. Un objeto que implementa el tipo Iterator<T> tiene como responsabilidad

gestionar un recorrido concreto de un agregado. Es decir ir proporcionando de forma

consecutiva cada uno de los elementos del recorrido en el orden especificado por el mismo.

Por cada recorrido de interés el agregado debe implementar un iterador (un objeto que

implementa de tipo Iterator<T>). El tipo Iterator<T> viene definido en el interface:

public interface Iterator<T>{

boolean hasNext();

T next();

void remove();

}

Como hemos indicado los objetos que implementan este tipo (iteradores) tienen como

responsabilidad proporcionar un primer elemento del recorrido que tienen asociado y

posteriormente los siguientes elementos del mismo. Además en cada momento indicarnos si

quedan más objetos por recorrer o no. El significado de los métodos es:

boolean hasNext(): Devuelve true si aún quedan elementos por recorrer y false en caso

contrario.

3 6. Iterables: Implementación, Composición y Uso

T next(): La primera vez que se le llama devuelve el primer elemento. En cada llamada

posterior devuelve el siguiente elemento del recorrido. Este método tiene como

precondición que hasNext() devuelva true. Si no se cumple la precondición entonces

disparará la excepción NoSuchElementException.

void remove(): Elimina del agregado el último elemento devuelto por el método next.

Junto al tipo anterior usaremos iteradores no modificables. Estos serán objetos del tipo

UnmodifiableIterator<T>. Los objetos de este tipo son objetos del tipo Iterator<T> que no

tienen disponible la operación remove. Es decir que si se invoca esta operación se dispararía la

excepción UnsupportedOperationException.

El tipo Iterable<T> es una factoría de objetos de tipo Iterator<T>. El tipo Iterable<T> viene

definido por el interface:

public interface Iterable<T>{

Iterator<T> iterator();

}

El método iterator() devuelve un iterador. Para comprender el funcionamiento del tipo

Iterable<T> veamos la forma de traducir una sentencia con un for extendido otra con un for

clásico o un while. Supongamos que el objeto ag implementa Iterable<T>. Entonces los tres

segmentos de código siguientes (con for extendido, for clásico y while) con equivalentes. Como

podemos ver la sentencia de control for extendido obtiene, en primer lugar, un iterador del

agregado que al implementar Iterable<T> es una factoría de los mismos. Usando el iterador el

bucle for entra en una secuencia de iteraciones mientras que el método hasNext devuelva

true. En cada iteración obtiene el elemento siguiente llamado al método next del iterador.

…

for(T e : ag){

mostrar(e);

}

…

…

for(Iterator<T> it = ag.iterator(); it.hasNext(); ){

T e = it.next();

mostrar(e);

}

…

…

Iterator<T> it = agregado.iterator();

while (it.hasNext()){

T e = it.next();

mostrar(e);

}

…

http://guava-libraries.googlecode.com/svn-history/r46/trunk/javadoc/com/google/common/collect/UnmodifiableIterator.html#UnmodifiableIterator()

Como vemos en la sentencia con el for extendido se usa internamente el iterador pero no se

muestra públicamente. Por lo tanto un agregado que quiera participar en un for extendido

debe implementar el tipo Iterable<T>. También debemos siempre se crea un iterador nuevo al

comenzar la sentencia for extendido.

Para implementar una clase que sea Iterable<T>, debemos seguir los pasos:

1. La clase implementará la interfaz Iterable<T>, siendo T el tipo de los elementos que se

van a recorrer.

2. Para cada tipo de recorrido que queramos permitir, implementaremos una clase

interna, la cual debe implementar Iterator<T>. Igual que dentro de una clase podemos

declarar un atributo o un método también podemos incluir otra clase u otro interface.

Estas clases incluidas dentro de otras se les llaman clases internas que pueden ser

declaradas públicas o privadas.

3. Cada posible iterador debe tener un estado para mantener la posición actual del

recorrido. Ese estado se concretará en atributos de la clase interna correspondiente. El

constructor de la misma debe inicializar el estado del iterador.

4. Los métodos hasNext() y next() de dicha clase interna deben implementarse de

acuerdo al tipo de recorrido que se esté llevando a cabo. El método hasNext(), como

hemos visto anteriormente, es un método observador que nos indica si hay o no más

elementos en el agregado. El método next() tiene como precondición que hasNext()

sea verdadero. La primera vez que lo llamamos devuelve el primer elemento del

recorrido. Cada vez que se llama devuelve un elemento del agregado y prepara el

estado del iterador para poder devolver el siguiente.

5. El método remove() contendrá el código adecuado para eliminar del agregado el

último elemento devuelto por el método next(). Si no queremos permitir el uso de este

método el cuerpo del mismo disparará la excepción UnsupportedOperationException.

6. El método iterator() devolverá un nuevo objeto de la clase interna oportuna. Si hay

varios recorridos posibles diseñaremos varias clases internas. El método iterator() se

diseñará como una factoría para devolver un objeto creado desde alguna de las clases

internas.

3. Ejemplos de Iterables

Veamos en primer lugar algunos iterables que nos permiten recorrer agregados virtuales. Es

decir agregados que sin estar en la memoria del ordenador pueden ser definidos

implícitamente. Los llamaremos iterables virtuales.

SecuenciaAritmetica

Será una clase iterable que permita recorrer los números de un intervalo con un incremento

determinado.

Constructor:

public SecuenciaAritmetica(Double vi, Double vf, Double inc)

El objetivo es poder operar del siguiente modo:

Iterable<Double> sec=new SecuenciaAritmetica(1.,30.,5.);

for(Double d : sec){

mostrar(d);

}

El resultado obtenido será

1.0

6.0

11.0

16.0

21.0

26.0

La implementación sigue una estructura que repetiremos en los siguientes iterables:

Definimos una variable privada en la clase interna. Esta variable mantiene el estado del

iterador. La variable guarda el siguiente valor a devolver por el método next o un valor que

está fuera del rango permitido. En algunos casos es necesario definir varias variables

privadas para mantener el estado el iterador.

El método hasNext simplemente comprueba si el valor de la variable está dentro del

rango.

El método next guarda el valor de la variable, calcula el siguiente actualizando la misma y

devuelve el valor antiguo.

public class SecuenciaAritmetica implements Iterable<Double> {

private Double primero,ultimo,incremento;

public SecuenciaAritmetica(Double a, Double b, Double c){

primero = a;

ultimo = b;

incremento= c;

if((ultimo-primero)*incremento < 0 ){

throw new IllegalArgumentException();

}

}

public SecuenciaAritmetica(Double a, Double b){

this(a,b,1.);

}

public Iterator<Double> iterator(){

return new IteradorSecuenciaAritmetica();

}

private class IteradorSecuenciaAritmetica

extends UnmodifiableIterator<Double>

implements Iterator<Double> {

private Double actual;

public IteradorSecuenciaAritmetica( ){

actual=primero;

}

public Double next() {

if(!hasNext()) throw

new NoSuchElementException();

Double r=actual;

actual = actual + incremento;

return r;

}

public boolean hasNext() {

return actual<ultimo;

}

}

}

Como el iterador que hemos diseñado es no modificable la clase interna que lo implementa

IteradorSecuenciaAritmetica hereda de UnmodifiableIterator<Double>. Esto hace que el

método remove ya esté disponible. Todos los iteradores no modificables disparan la excepción

correspondiente cuando se invoca al método remove.

Iterable de Pares

Es un iterable para generar pares de números enteros donde la primera componente del par

estará formada por los enteros desde ma1 (incluido) hasta ma2 (no incluido) y la segunda

componente formada por los enteros desde mb1 hasta mb2.

Constructor:

public IterableDePares(Integer ma1, Integer ma2, Integer mb1, Integer mb2)

Ejemplo de uso. La llamada:

Iterable<Tupla2<Integer,Integer>> it = new IterableDePares(1,3,2,5);

daría como resultado si se recorriera:

(1,2)

(1,3)

(1,4)

(2,2)

(2,3)

(2,4)

El tipo Tupla2 representa un par de elementos. Su diseño se deja como ejercicio.

prublic class IterableDePares implements Iterable<Tupla2<Integer, Integer>> {

private Integer a1;

private Integer a2;

private Integer b1;

private Integer b2;

public IterableDePares(Integer ma1, Integer ma2,

Integer mb1, Integer mb2) {

if(!((ma2>=ma1)|| (mb2>=mb1))) throw

new IllegalArgumentException();

a1 = ma1;

a2 = ma2;

b1 = mb1;

b2 = mb2;

}

public Iterator<Tupla2<Integer, Integer>> iterator() {

return new IteradorDePares();

}

private class IteradorDePares

extends UnmodifiableIterator<Tupla2<Integer,Integer>>

implements Iterator<Tupla2<Integer,Integer>>{

private Integer ia;

private Integer ib;

public IteradorDePares() {

ia = a1;

ib = b1;

}


return ia < a2;

}

public Tupla2<Integer,Integer> next() {



Integer oia = ia;

Integer oib = ib;

if(ib < b2-1) {

ib = ib +1;

} else {

ia = ia+1;

ib = b1;

}

return Tupla2.create(oia, oib);

}

}

}

Otros ejemplos de secuencias iterables que se dejan como ejercicio son:

Secuencia de Fibonacci

Secuencia Geométrica

Secuencia de Primos

Otros Iterables

Iterable de array

Se trata de hacer iterable un objeto que es un array que no es directamente iterable en Java.

Podemos permitir dos tipos de recorridos: hacia arriba y hacia abajo.

Constructor:

public ArrayIterable(T[] a) {…}

Ejemplo:

T[] a = {3,4,-7,23};

Iterable<Integer> v = new ArrayIterable(a);

Estos recorridos se pueden cambiar con el método setOpcion. Tal como vemos hay dos clases

internas y el método iterator se diseña como una factoría.

public class ArrayIterable<T> implements Iterable<T> {

public enum Recorrido {HACIA_ARRIBA,HACIA_ABAJO}

private T[] array;

private Recorrido opcion = Recorrido.HACIA_ARRIBA;

public ArrayIterable(T[] array) {

this.array = array;

}

@Override

public Iterator<T> iterator() {

Iterator<T> it = null;

switch(opcion){

case HACIA_ARRIBA: it = new IteratorArriba(); break;

case HACIA_ABAJO: it = new IteratorAbajo(); break;

}

return it;

}

public Recorrido getOpcion() {

return opcion;

}

public void setOpcion(Recorrido opcion) {

this.opcion = opcion;

}

private class IteratorArriba extends UnmodifiableIterator<T>

implements Iterator<T> {

private int actual;

public IteratorArriba( ){

actual=0;

}

@Override

public T next() {

if(!hasNext()) throw new NoSuchElementException();

int r = actual;

actual = actual + 1;

return array[r];

}

@Override


return actual < array.length;

}

}

private class IteratorAbajo extends UnmodifiableIterator<T>

implements Iterator<T> {

private int actual;

public IteratorAbajo( ){

actual = array.length;

}

@Override

public T next() {


int r =actual;

actual = actual - 1;

return array[r];

}

@Override


return actual >= 0;

}

}

}

Iterable Flujo Entrada

Esta clase nos permitirá leer datos desde un fichero de texto o desde el teclado convirtiéndolo

en un Iterable<String>.

Constructor:

public FlujoEntrada(String f)

Ejemplo de uso:

Iterable<String> it = new FlujoEntrada(“Puntos.text”);

Suponiendo que el fichero de nombre Puntos.txt es de la forma:

(2.0,3.1)

(2.2,3.1)

(3.2,3.0)

(4.1,3.2)

(2.0,3.2)

(2.1,3.2)

entonces cada uno de los objetos en it son las líneas de ese fichero. Si mostráramos el

contenido de it obtendríamos esos objetos de tipo String uno detrás de otro.

La implementación usa clase del paquete java.io de las cuales no daremos muchos detalles.

Estas clases son File, BufferedReader y FileReader cuyos detalles pueden consultarse en la

página correspondiente del API de Java. Sólo indicar que son clases adecuadas para leer datos

de un fichero. Si queremos destacar que el fin de fichero se detecta cuando se lee una cadena

null y este detalle es tenido en cuenta al implementar el correspondiente método hasNext. Por

otra parte los métodos que interaccionan con ficheros dispara algunas excepciones que

debemos gestionar. Aquí hemos decidido convertir esas excepciones en

IllegalArgumenException para no introducir nuevos tipos de excepciones.

private static class FlujoEntrada implements Iterable<String>{

private String nf;

public FlujoEntrada(String f) {

nf = f;

}

public Iterator<String> iterator(){

return new IteradorFlujoEntrada();

}

private class IteradorFlujoEntrada

extends UnmodifiableIterator<String>

implements Iterator<String>{

private File f;

private BufferedReader bf;

private String linea;

public IteradorFlujoEntrada(){

try{

f = new File(nf);

bf = new BufferedReader(new FileReader(f));

linea = bf.readLine();

} catch (IOException e) {throw


}

}


return linea!=null;

}

public String next() {



String pal = linea;

try{

linea=bf.readLine();

}catch(IOException e){throw


}

return pal;

}

}

}

El general cualquier agregado puede ofrecer el tipo Iterable. La implementación puede seguir

las pautas anteriores

4. Operaciones sobre iterables: los tipos Function y Predicate

En el capítulo de los tratamientos secuenciales vimos un conjunto esquemas para llevar a cabo

operaciones de cálculo de valores agregados sobre agregados o transformación de los mismos.

Veamos ahora forma de convertir aquellos esquemas en métodos genéricos que tomen un

objeto iterable como parámetro y otra información necesaria en el esquema.

Tal como vimos en los esquemas secuenciales aparece un iterable y otros elementos que, de

forma manual, sustituimos por código en cada caso concreto. Estos elementos eran los Filtros

y las Expresiones. Los primeros eran expresiones de tipo lógico sobre un objeto de tipo T en

general y los segundos eran expresiones calculadas sobre objetos de tipo F para dar un valor

de tipo T en general. Estas expresiones pueden ser modeladas como objetos. Los tipos

correspondientes los denominaremos Predicate<T> y Function<S,T>. Seguimos la

nomenclatura y conceptos proporcionados por el API Guava de Google.

Los tipos se representan por los interfaces:

interface Predicate<T> {

boolean apply(T input);

boolean equals(Object p);

}

interface Function<F,T> {

T apply(F input);

boolean equals(Object p);

}

Los requisitos de ambos tipos son:

Predicate

apply: el método no produce efectos laterales sobre el parámetro de entrada. Cuando se

aplica a dos objetos iguales (según equals) debe devolver el mismo valor lógico. Es decir

para cualquier predicado y par de objetos se debe cumplir: Objects.equals(o1,o2) =>

predicate.apply(o1) == predicate.apply(o2).

equals: Determina si o no el predicado p es iguala a this.

Function:

apply: el método no produce efectos laterales sobre el parámetro de entrada. Cuando se

aplica a dos objetos iguales (según equals) debe devolver el mismo valor. Es decir para

cualquier predicado y par de objetos se debe cumplir: Objects.equals(o1,o2) =>

Objects.equals(function.apply(o1), function.apply(o2)).

equals: Determina si o no el predicado p es iguala a this.

Hemos usado el método equals de la clase Objects que devuelve true si ambos objetos son

null, si ambos son distintos de null y al invocar equals sobre uno de ellos tomando el otro como

parámetro resulta true y false en el resto de los casos.

Podemos declarar variables de estos tipos, inicializarlas, usarlas y pasarlas como parámetros.

Para construir objetos de estos tipos, como en el caso del tipo Comparator<T>, tenemos que

diseñar clases que implementen estos tipos. Veamos algunos ejemplos.

Como primer ejemplo veamos una función que transforma unan cadena de caracteres con el

formato adecuado a un Racional.

class StringToRacional implements Function<String,Racional>{

public StringToRacional() {}

public Racional apply(String s) {

return Racionales.create(s);

}

}

Ideas parecidas se pueden usar para implementar funciones que conviertan una cadena de

caracteres, con el formato adecuado, a un objeto de un tipo dado. Ejemplos pueden ser:

StringToInteger, StringToDouble, StringToPunto, …

Como hemos dicho anteriormente el tipo Function<F,T> no permite representar un expresión

que toma un operando de tipo F y devuelve un resultado de tipo T. A la variable que hace el

papel de operando la llamamos variable ligada en la expresión. Pero una expresión puede

tener otras variables que denominaremos variables libres. Las expresiones con variables libres

se implementan mediante una clase que toma en su constructor como parámetros los valores

de las variables libres. Como ejemplo veamos al forma de implementar una expresión que

calcula la distancia de un objeto de tipo Punto (variable ligada) al centro de un Circulo dado

(variable libre).

public class DistanciaACentroDeCirculo implements Function<Punto, Double> {

private Circulo circulo;

public DistanciaACentroDeCirculo(Circulo circulo) {

this.circulo = circulo;

}

public Double apply(Punto a) {

return a.getDistancia(getCirculo().getCentro());

}

public Circulo getCirculo() {

return circulo;

}

}

Hemos supuesto que el tipo Punto ofrece el método getDistancia. La clase ofrece también un

método para consultar el valor de la variable libre. Vemos, por lo tanto, que el valor de la

variable (o variables libres) se guarda en un atributo y se inicializan en el constructor. El valor

de la variable ligada se proporciona como parámetro en el método apply.

Los predicados se implementan igual. Como ejemplo veamos un predicado sobre objetos de

tipo Punto (variable ligada) que decida si el objeto está en el primer cuadrante.

public class EnPrimerCuadrante implements Predicate<Punto> {

public EnPrimerCuadrante() {}

public boolean apply(Punto a) {

return a.getX() > 0. && a.getY() > 0.;

}

}

Los predicados pueden tener, también, variables libres y se implementan de la misma forma.

5. Clausuras

Junto a la forma anterior de inicializar predicados y expresiones en la versión 8 de Java se

proponen nuevas ideas para este objetivo. Son las denominadas clausuras o expresiones

lambda que ya están disponibles en otros lenguajes actuales como C#. Esencialmente una

expresión lambda es una expresión Java (o una secuencia de sentencias), con sus argumentos,

incluida dentro de los delimitadores (argumentos) -> expresión . Algunos ejemplos son:

(int x) -> x + 1: Una expresión que toma un entero y devuelve el siguiente.

(Person x, Person y) ->

x.getLastName().compareTo(y.getLastName()): Un expresión que toma dos personas y devuelve un entero. Es decir en este caso un orden sobre las personas.

(Person p) -> p.getName(): Un expresión que toma una persona y devuelve un cadena con su nombre.

(Integer e) -> e%2==0: Expresión lambda que toma un entero y devuelve un boolean.

(Circulo c) -> c.setRadio(c.getRadio()*1.2): Acción que aumenta el radio de un círculo en un 20%.

(Punto p) -> p.getX() > 0. && p.gteY() > 0.: Predicado que decide si un punto está en el primer cuadrante.

(String s) -> Racionales.create(s): Expresión que convierte una cadena en un racional.

(Punto p) -> p.getDistancia(circulo.getCentro(): Expresión que calcula la distancia de un punto al centro de un círculo dado. La variable circulo, de tipo Circulo, tiene que ser visible en el ámbito donde definimos esta expresión lambda. Es una variable libre de la misma.

En algunos es posible suprimir el tipo de la variable ligada si el compilador es capaz de deducirlo.

6. Composición de Iterables, Predicados , Expresiones y Órdenes.

A partir de iterables, criterios, expresiones y órdenes se pueden componen nuevos objetos de

estos tipos. Estos mecanismos de composición nos permitirán disponer de algunos iterables

complejos formados a partir de unos iterables básicos (los anteriores) y unos mecanismos de

composición (los que vamos a ver ahora). Igualmente ocurre con los predicados, las

expresiones y los órdenes.

Veamos, en primer lugar, algunos métodos estáticos para componer predicados agrupados en

la clase Predicates.

static <E> Predicate<E> and(Predicate<? super T>... components): Construye un nuevo

predicado que devuelve true si todos los predicados que se pasan como parámetros

devuelven true.

static <E> Predicate<E> or(Predicate<? super T>... components): Construye un nuevo

predicado que devuelve true si alguno de los predicados que se pasan como

parámetros devuelven true y en otro caso false.

static <A,B> Predicate<E> compose(Predicate predicate, Function<A,? extends

B> function): Se construye un predicado que funciona sobre la variable ligada x de la

forma predicate(function(x)).

static <T> Predicate<T> alwaysTrue(): Devuelve un predicado que siempre evalúa a

verdadero.

static <T> Predicate<T> alwaysFalse(): Devuelve un predicado que siempre evalúa a

falso.

En segundo lugar veamos algunos métodos estáticos para componer expresiones agrupados

en la clase Functions.

static <E> Function<E,E> identity(): Devuelve la función identidad. Es decir la expresión

devuelve como resultado el valor del operando.

static <A,B,C> Function<A,C> compose(Function<B,C> g, Function<A,? extends B> f):

Construye una expresión componiendo las dos expresiones que se dan como

parámetros. Es decir g(f(x)).

static <T> Function<T,Boolean> forPredicate(Predicate<T> predicate): Transforma un

objeto de tipo Predicate en otro de tipo Function.

static <E> Function<Object,E> constant(E value): Devuelve la función constante. Es

decir la expresión devuelve como resultado un valor constante.

Más adelante veremos algunos métodos de construir expresiones a partir de otros tipos de

datos.

En tercer lugar recordaremos métodos para componer órdenes (unos static y otros no)

agrupados en la clase Ordering.

http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/com/google/common/base/Predicates.html#and(com.google.common.base.Predicate...)

http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/com/google/common/base/Predicate.html


http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/com/google/common/base/Predicates.html#compose(com.google.common.base.Predicate, com.google.common.base.Function)


http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/com/google/common/base/Function.html


http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/src-html/com/google/common/base/Predicates.html#line.53




http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/src-html/com/google/common/base/Functions.html#line.70






http://download.oracle.com/javase/6/docs/api/java/lang/Boolean.html?is-external=true




http://download.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true

Ordering compound(Comparator<? super U> secondary): Construye

un orden compuesto que aplica primero el orden proporcionado como parámetro y

luego el this.

<S extends T> Ordering<S> reverse(): Construye un orden opuesto al que está en this.

static <C extends Comparable> Ordering<C> natural(): Construye un orden con el

orden natural del tipo.

static <T> Ordering<T> from(Comparator<T> comparator): Construye un objeto de tipo

Ordering a partir de un Comparator.

<F> Ordering<F> onResultOf(Function<F,? extends T> function): Construye un orden

sobre objetos de tipo F de la misma forma que los resultados de aplicar la función que

se proporciona como parámetro ordenados con el orden que estuviera en this.

<S extends T> Ordering<S> nullsFirst(): Construye un orden a partir del que estuviera

en this de tal forma que los valores null se colocan anteriores a cualquier valor.

<S extends T> Ordering<S> nullsLast(): Construye un orden a partir del que estuviera

en this de tal forma que los valores null se colocan posteriores a cualquier valor.

<E extends T> List<E> leastOf(Iterable<E> iterable, int k): Construye una lista con los k

valores más pequeños del iterable según el orden en this.

<E extends T> List<E> greatestOf(Iterable<E> iterable, int k) : Construye una lista con

los k valores más grandes del iterable según el orden en this.

<E extends T> E max(Iterable<E> iterable): Devuelve el máximo del iterable según el

orden en this o una excepción si el iterable está vacío.

<E extends T> E max(E a, E b, E c, E... rest): Devuelve el máximo de los valores de los

parámetros según el orden en this.

<E extends T> E min(Iterable<E> iterable): Devuelve el mínimo del iterable según el

orden en this o una excepción si el iterable está vacío.

<E extends T> E min(E a, E b, E c, E... rest): Devuelve el mínimo de los valores de los

parámetros según el orden en this.

boolean isOrdered(Iterable<? extends T> iterable): Verdadero si es iterable está

ordenado según el orden en this.

boolean isStriclyOrdered(Iterable<? extends T> iterable): Verdadero si es iterable está

estrictamente ordenado según el orden en this.

<E extends T> List<E> sortedCopy(Iterable<E> iterable): Proporciona una copia

ordenada del iterable por el orden en this. No descarta elementos que devuelvan cero

al ser comparados por el método compare del orden.

En cuarto lugar veamos algunos métodos estáticos para componer iterables agrupados en la

clase Iterables.

static <T> Iterable<T> concat(Iterable<? extends T>... inputs): Construye un iterable

concatenando los que recibe como parámetros.

static <T> Iterable<T> concat(Iterable<? extends Iterable<? extends T>> inputs): A

partir de un iterable cuyos elementos son iterables de objetos de tipo T construye un

iterable de objetos de tipo T.

http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/com/google/common/collect/Ordering.html


http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/src-html/com/google/common/collect/Ordering.html#line.306

http://download.oracle.com/javase/6/docs/api/java/util/Comparator.html?is-external=true




http://download.oracle.com/javase/6/docs/api/java/lang/Comparable.html?is-external=true

















http://download.oracle.com/javase/6/docs/api/java/util/List.html?is-external=true


http://download.oracle.com/javase/6/docs/api/java/lang/Iterable.html?is-external=true

























http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/src-html/com/google/common/collect/Iterables.html#line.409

static <T> Iterable<T> filter(Iterable<T> unfiltered, Predicate<? super T> predicate):

Construye un iterable a partir de los elementos de otro que cumplen un predicado.

static <F,T> Iterable<T> transform(Iterable<F> fromIterable, Function<? super F,?

extends: T> function): Construye un iterable aplicando una expresión a los elementos

de otro.

static boolean removeAll(Iterable<?> removeFrom, Collection<?> elementsToRemove):

Actualiza el iterable eliminado de él todos los que también están en la colección.

static boolean retainAll(Iterable<?> removeFrom, Collection<?> elementsToRetain):

Actualiza el iterable dejando en él los que también están en la colección.

static <T> boolean removeIf(Iterable<T> removeFrom, Predicate<? super T> predicate):

Actualiza el iterable eliminado de él los que cumplen el predicado.

static <T> boolean addAll(Collection<T> addTo, Iterable<? extends T> elementsToAdd):

Actualiza la colección añadiendo los que están en el iterable.

Y el la clase Iterables2.

static Iterable<String> fromFile(String nombreFichero): Crea un iterable de cadenas de

caracteres a partir de un fichero de texto.

static Iterable<String> fromString(String cadena, String delim): Crea un iterable de

cadenas de caracteres a partir de una cadena y unos delimitadores proporcionados en

una segunda cadena.

static Iterable<Double> from(Double a, Double b, Double c): Crea un iterable que

contiene progresión aritmética de números reales.

static Iterable<Integer> from(Integer a, Integer b, Integer c): Crea un iterable que

contiene progresión aritmética de números reales.

static Iterable<Tupla2<Integer,Integer>> fromPairs(Integer a, Integer b, Integer c,

Integer d): Crea un iterable que contiene pares de número enteros. La primera

componente del par va desde a hasta b (sin incluir) y de uno en uno y la segunda

componente de c hasta d (sin incluir) también de uno en uno.

static <T> Iterable<T> fromArray(T[] a): Crea un iterable a partir de un array.

Aunque veremos con más detalle estos aspectos los tipos Set<T> y List<T> son subtipos de

Collection<T> que a su vez lo es de Iterable<T>.

También podemos utilizar algunos métodos estáticos, agrupados en la clase Iterables que

calculan valores agregados sobre un iterable.

static int size(Iterable<?> iterable): Devuelve el número de objetos del iterable.

static boolean contains(Iterable<?> iterable, Object element): Verdadero si el iterable

contiene el elemento.

static int frequency(Iterable<?> iterable, Object element): Número de veces que

aparece el elemento en el iterable.

static <T> boolean any(Iterable<T> iterable, Predicate<? super T> predicate):

Verdadero si alguno de los elementos del iterable cumple el predicado.











http://download.oracle.com/javase/6/docs/api/java/util/Collection.html?is-external=true

static <T> boolean all(Iterable<T> iterable, Predicate<? super T> predicate): Verdadero

si todos los elementos del iterable cumplen el predicado.

static <T> T find(Iterable<T> iterable, Predicate<? super T> predicate): Devuelve el

primer elemento que cumple el predicado o una excepción si no encuentra ninguno.

static <T> int indexOf(Iterable<T> iterable, Predicate<? super T> predicate): Devuelve la

posición del primer element que cumple el predicado o -1 si no encuentra ninguno.

static <T> T getFirst(Iterable<T> iterable, T defaultValue): Devuelve el primer elemento

del iterable o un valor por defecto si el iterable está vacío.

static <T> T getLast(Iterable<T> iterable): Devuelve el ultimo elemento del iterable.

static <T> boolean isEmpty(Iterable<T> iterable): Verdadero si el iterable está vacío.

Veamos ahora ejemplos de uso de los métodos y funciones anteriores.

Como primer ejemplo veamos la forma de construir un iterable que contenga pares de

números enteros que cumplan alguna propiedad.

Iterable<Tupla2<Integer,Integer>> it = Iterables2.fromPairs(20,25,10,12);

Iterable<Tupla2<Integer,Integer>> it2 = Iterables.filter(it,

(Tupla2<Integer,Integer> p) -> p.getP1()%2==0 && !(p.getP2()%2==0));

Si mostramos el resultado de it obtendremos:

(20,10)

(20,11)

(21,10)

(21,11)

(22,10)

(22,11)

(23,10)

(23,11)

(24,10)

(24,11)

Y el contenido de it2 será

(20,11)

(22,11)

(24,11)

Como segundo ejemplo veamos la forma de construir un iterable que contenga los números

primos en un determinado rango.

Iterable<Integer> it = Iterables2.from(1,b,2);

Iterable<Integer> it2= Iterables.filter(it,(Integer e)->Enteros.esPrimo(e)));

Como tercer ejemplo se trata de construir un iterable de números reales en otro formado por

enteros obtenidos de redondear los anteriores.

Iterable<Double> it = Iterables.from(2.6,30.,3.5);

Iterable<Integer> it2 = Iterables.transform(it, (Double d) -> (int)(d+0.5));

En este caso it contiene los objetos de tipo Double siguientes:

2.6

6.1

9.6

13.1

16.6

20.1

23.6

27.1

Y it2 contiene, tal como se muestra abajo, los objetos de tipo Integer obtenidos redondeando

los anteriores.

3

6

10

13

17

20

24

27

Otro ejemplo de uso frecuente Un caso concreto es la obtención de un Iterable del tipo T a

partir de un fichero y una expresión que convierte de String a T. Veamos el siguiente ejemplo

que combina los diferentes iterables vistos.

Supongamos que el fichero Puntos.txt contiene las líneas de texto siguientes.

(2.0,-3.1)

(5.2,3.1)

(3.2,-3.0)

(4.1,3.2)

(-2.0,3.2)

(-2.1,-3.2)

Veamos la líneas de código siguientes:

Iterable<String> it1 = Iterables2.fromFile("Puntos.txt");

Iterable<Punto> it2= Iterables.transform(it1,(String s) -> Puntos.create(s));

Iterable<Punto> it3 = Iterables.filter(it2, (Punto p) -> p.getY() > 0.);

Iterable<Double> it4 = Iterables.transform(it3, (Punto p) -> p.getX());

En el código construimos un iterable de cadenas de caracteres a partir de un fichero, lo

transformamos en un iterable de puntos, lo filtramos y lo transformamos en un iterable de

números reales. El contenido del iterable it4 es:

5.2

4.1

-2.0

Como siguiente ejemplo veamos la forma de construir, a partir de un fichero de texto, un

iterable de cadenas de caracteres que contenga los fragmentos de cada una de las líneas del

fichero delimitados por unos caracteres delimitadores proporcionados.

Iterable<String> it1 = Iterables2.from("Puntos.txt");

Iterable<Iterable<String>> it2 =

Iterables.transform(it1, (String s) -> Iterables2.from(s,"(,)") ); Iterable<String> it3 = Iterables.concat(it1);

Si el fichero Puntos.txt tiene el contenido:

(2.0,-3.1)

(5.2,3.1)

El iterable it3 muestra el siguiente resultado:

2.0

-3.1

5.2

3.1

En el ejemplo anterior hemos usado una expresión que convierte un String en un iterable de

String. Esta expresión viene proporcionada en la clase Iterables2.

En el ejemplo anterior hemos para transformado un Iterable<String> (formado por las líneas

de un fichero de texto) en otro Iterable<String> formado por los trozos de la cada una de las

líneas definidos por unos delimitadores. En general esta idea es adecuada siempre que

tengamos un Iterable<T> y el tipo T tiene un método que devuelve Iterable<R> y queremos

obtener un Iterable<R>.

Suponiendo que tenemos un tipo Aeropuerto (cada aeropuerto tiene una propiedad Vuelos de

tipo List<Vuelo> y cada vuelo las propiedades NumeroDePasajeros, Precio y Destino) entonces

el siguiente código calcula la recaudación de los vuelos que tienen destino París del conjunto

de aeropuertos dados en una lista.

List<Aeropuerto> la = ...;

Iterable<Iterable<Vuelo>> it1 =

Iterables.transform(la, (Aeropuerto a) -> a.getVuelos());

Iterable<Vuelo> it2 = Iterables.concat(it1);

Iterable<Vuelo> it3 =

Iterables.filter(it2, (Vuelo v) -> v.getDestino().equals(“Paris”));

Iterable<Double> it4 =

Iterables.transform(it3,

(Vuelo v) -> v.getPrecio()*v.getNumeroDePasajeros());

Double recaudacion = Iterables2.suma(it4);

En el ejemplo siguiente trata de construir a partir de elementos del mismo tipo contenidos en

dos fuentes de datos.

Punto p1 = Puntos.create(7.0,9.7);

Punto p2 = Puntos.create(-25.,9.);

Punto[] ap = {p1,p2};

Iterable<Punto> ip = Iterables2.from(ap);

Iterable<String> it1 = Iterables2.from("Puntos.txt");

Iterable<Punto> it2= Iterables.transform(it1,(String s) -> Puntos.create(s));

Iterable<Punto> it3 = Iterables.concat(it2,ip);

Si el fichero Puntos.txt contiene

(2.0,-3.1)

(5.2,3.1)

Entonces el it3 contiene:

(2.0,-3.1)

(5.2,3.1)

(7.0,9.7)

(-25.0,9.0)

Esta clase nos permite fundir en un único iterable objetos procedentes de dos fuentes de datos

distintas, en este caso un fichero y un array, para hacer un posterior tratamiento conjunto de

los mismos. El tipo T[] no es directamente iterable en Java. Por eso es necesario una

transformación del tipo T[] a algún tipo iterable. Una posibilidad es proporcionada en la clase

Iterables2 donde se trata a los arrays como una fuente de datos junto con los ficheros y otras.

7. Otros iterables: listas virtuales

Los iterables y sus correspondientes iteradores asociados nos proporcionan mecanismos para

manipular listas descritas de forma implícita. Hasta ahora hemos visto el tipo List<E>. Los

valores de este tipo son listas de elementos de tipo E. Son listas que se construyen en memoria

de forma explícita. Junto a ellas vamos a considerar listas implícitas. Estas últimas no son

valores del tipo List<E>. Son simplemente secuencias de elementos cuyas propiedades se

describen de forma abstracta.

Desde un punto de vista abstracto vamos a llamar lista a secuencias de elementos que

representaremos por [ ]. Las variables serán listas, las

funciones y las predicados. Representaremos las listas de

varias maneras. La primera, que llamaremos lista explícita, son objetos de tipo List<E>. En

estas listas, y de ahí su nombre, los datos son explícitos y están disponibles para cada índice de

la lista en al memoria. También tendremos varias formas de listas implícitas. Una primera

forma de estas listas la representaremos en la forma [ ] Dónde es el número de

elementos y ( una función que cada [ ] nos devolverá el valor de la

correspondiente casilla. Un segundo tipo listas implícitas las modelaremos como [ ].

Donde es una función que a partir del valor de una casilla calcula el valor ( de la

casilla siguiente, el valor de la casilla inicial (la de índice ) y ( un predicado que

especifica un dominio dentro del cual deben estar los valores de la lista. El último elemento

será aquel cuyo siguiente elemento esté fuera del dominio. Alternativamente podemos

describir la lista dando una propiedad que tiene el último elemento y solamente él. Lo

haremos en la forma [ ].

Las listas implícitas las implementamos como objetos de tipo Iterable<E> siguiendo las ideas

vistas anteriormente. En la clase Iterables2 se ofrecen métodos estáticos para construir listas

virtuales. Son los métodos:

Iterable<T> fromDomain(Function<T,T> fl, T v0, Predicate<T> domain){...}: Construye una lista virtual con un primer elemento v0 y dónde para cada elemento el siguiente se calcula con la función fl. La lista continúa mientras se cumpla el predicado domain.

Iterable<T> fromToLast(Function<T,T> fl, T v0, Predicate<T> esElUltimo){...}: Construye una lista virtual con un primer elemento v0 y dónde para cada elemento el siguiente se calcula con la función fl. La lista continúa hasta que el predicado esElUltimo se haga verdadero.

Iterable<T> fromIndex(Function<Integer,T> fl, Integer n){...}: Construye una lista virtual cuyos elementos son los valores obtenidos por la función fl al aplicarla a los enteros [0,n-1].

Como ejemplo se muestra la implementación de la primera de las listas virtuales. Dejamos las

otras dos como ejercicio.

class IterableListaVirtualDomain<T> implements Iterable<T> {

private Function<T,T> f;

private T v0;

private Predicate<T> domain;

public IterableListaVirtualDomain(Function<T, T> fl,

T v0, Predicate<T> domain) {

super();

this.f = fl;

this.v0 = v0;

this.domain = domain;

}

@Override

public Iterator<T> iterator() {

return new IteratorListaVirtualDomain();

}

private class IteratorListaVirtualDomain extends

UnmodifiableIterator<T> implements Iterator<T>{

private T a;

public IteratorListaVirtualDomain() {

super();

a = v0;

}

@Override


return domain.apply(a);

}

@Override

public T next() {

Preconditions.checkState(hasNext());

T oldA = a;

a = f.apply(a);

return oldA;

}

}

}

Como ejemplo de uso veamos una lista virtual que contenga los elementos de una secuencia

geométrica:

public class TestIterables {

public static void main(String[] args) {

Iterable<Integer> is = Iterables2.fromDomain((e)->e*5,50,(e)->e<10000);

for(Integer e: is){

System.out.println(e);

}

}

}

El resultado es:

50

250

1250

6250

8. Implementación de iterables, órdenes, expresiones y predicados compuestos

Veamos en primer lugar la implementación de órdenes, expresiones y predicados compuestos.

Sólo veremos algunos ejemplos dejando el resto de los métodos como ejercicio.

La implementación de expresiones, predicados u órdenes compuestos sigue siempre un mismo

patrón. Se trata de implementar una clase interna que tome en el constructor los parámetros a

componer. El método diseñado, que suele ser static, construye y devuelve un objeto de la

clase interna anterior. Como ejemplo presentamos la composición de dos expresiones.

static <A,B,C> Function<A,C>compose(Function<B,C> g,Function<A,?extends B> f){

return new ComposeFunctions<A,B,C>(g,f);

}

private static class ComposeFunctions<A,B,C> implements Function<A,C> {

private Function<B,C> g;

private Function<A,? extends B> f;

public ComposeFunctions(Function<B, C> g, Function<A, ? extends B> f) {

super();

this.g = g;

this.f = f;

}

@Override

public C apply(A a) {

return g.apply(f.apply(a));

}

}

La composición de órdenes para construir objetos de tipo Ordering tiene algunas

peculiaridades. Muchos métodos no son static puesto que construyen un nuevo Ordering a

partir de un parámetro y la información en el this. Vemos el ejemplo de composición de una

expresión con un orden implementado en un objeto de tipo Ordering. Es el método onResultOf

de la clase Ordering.. Una posible implementación es la que se propone.

public <F> Ordering<F> onResultOf(Function<F,? extends T> f) {

return new FunctionToOrder<F,T>(f,this);

}

private class FunctionToOrder<F,S> extends Ordering<F> {

private Function<F,? extends S> f;

private Comparator<S> cmp;

public FunctionToOrder(Function<F, ? extends S> f, Comparator<S> cmp) {

super();

this.f = f;

this.cmp = cmp;

}

@Override

public int compare(F a1, F a2) {

return cmp.compare(f.apply(a1),f.apply(a2));

}

}

La implementación de iterables simples y compuestos tiene dos aproximaciones: una más

intuitiva pero menos eficiente (que llamaremos implementación naif) y otra menos intuitiva

pero más eficiente (que denominaremos, por la razones que veremos, implementación lazy o

perezosa). Veamos la diferencia entre las dos aproximaciones en el ejemplo de la secuencia

aritmética que hemos visto al principio del capítulo. La implementación que vimos era de tipo

lazy. Veamos una implementación naif para el mismo iterable.

public class SecuenciaAritmeticaNaif implements Iterable<Double> {

private Double primero,ultimo,incremento;

public SecuenciaAritmetica(Double a, Double b, Double c){

primero = a;

ultimo = b;

incremento= c;

if((ultimo-primero)*incremento < 0 ){

throw new IllegalArgumentException();

}

}

public SecuenciaAritmetica(Double a, Double b){

this(a,b,1.);

}

public Iterator<Double> iterator(){

List<Double> lis = Lists.newArrayList();

for(Double e = a; e < b; e= e+c){

lis.add(e);

}

return lis;

}

}

Si comparamos esta implementación (naif) con la que vimos al principio del capítulo (lazy)

podemos observar que esta implementación obliga a construir en memoria una lista con todos

los elementos de la secuencia mientras que la otra implementación va calculando el siguiente

elemento de la secuencia a medida que se necesario. Es decir cuando se llama al método next

del correspondiente iterador. Las dificultades de la implementación naif se agravan cuando

componemos varios iterables.

Otros lenguajes, aunque no Java, disponen de una sentencia que permite implementar

iterables con una aproximación similar a la que hemos llamado naif pero con la eficiencia de la

que hemos llamado lazy.

De los iterables compuestos solo presentaremos las ideas para implementar los métodos filter

y transform de la clase Iterables. Veremos en primer lugar la implementación naif. En esta

forma de implementación se trata de construir a partir de un iterable un agregado con las

técnicas vistas en el capítulo de esquemas secuenciales. El agregado puede ser una lista. La

implementaciones de estos dos métodos serían:

public static <F> Iterable<F> filter(Iterable<F> fromIterable,

Predicate<? super F> p){

List<F> lista = Lists.newArrayList();

for(F e : fromIterable){

if(p.apply(e)){

lista.add(e);

}

}

return lista;

}

public static <F,S> Iterable<S> transform(Iterable<F> fromIterable,

Function<? super F, ? extends S> f){

List<S> lista = Lists.newArrayList();

for(F e : fromIterable){

lista.add(f.apply(e));

}

return lista;

}

De la misma forma se podrían obtener implementaciones naif del resto de los métodos

disponibles para implementar iterables. Pero esta implementación obliga a recorrer el iterable

completo, ubicar todos los objetos en memoria en un agregado de tipo lista y posteriormente

devolver este agregado. La dificultad de esta implementación es cuando usamos varios

métodos de la clase Iterables de forma secuencial. En definitiva construimos, como hemos

visto en ejemplos anteriores, un iterable a partir de pasos elementales de filtrado,

transformación, etc. En cada paso elemental hay que recorrer en iterable entero, construir

unan nueva lista y devolverla. Por lo tanto si el número de pasos elementales (filtros,

transformaciones, concatenaciones, etc.) es muy grande el número de recorridos del iterable

original puede ser muy elevado (además del uso de memoria). Por ello abordamos otra

implementación donde cada iterable se construye a partir del anterior de tal forma que cada

uno de ellos avance sólo cuando sea necesario. Por eso esta técnica de implementación la

denominamos lazy o perezosa. Esencialmente consiste en construir una clase interna que

implemente iterable y que tome en su constructor otro iterable y según los casos una

expresión, un predicado u otros tipos de objetos.

Veamos este tipo de implementación para los dos métodos anteriores.

public static <F> Iterable<F> filter(Iterable<F> fromIterable,

Predicate<? super F> predicate){

return new IterableFilter(fromIterable,predicate);

}

private class IterableFilter<T> implements Iterable<T> {

private Iterable <T> fromIterable;

private Predicate<T> predicate;

public IterableFilter(Iterable<T> fromIterable, Predicate<T> p){

this.fromIterable = fromIterable;

this.predicate = p;

}

public Iterator<T> iterator(){

return new IteratorFilter();

}

private class IteratorFilter extends UnmodifiableIterator<T>

implements Iterator<T>{

private Iterator<T> iterator;

private T element = null;

public IteratorFilter() {

iterator = fromIterable.iterator();

nextElement();

}

public boolean hasNext(){ return element != null; }

public T next(){


T a = element;

siguiente();

return a;

}

private void nextElement(){

element = null;

T a2;

while(iterator.hasNext()){

a2 = iterator.next();

if (predicate.apply(a2)){

element = a2;

break;

}

}

}

}

}

Como podemos comprobar mantenemos en el atributo element el siguiente elemento a

devolver. Si element es null es que no quedan más elementos. El método privado nextElement

busca el siguiente elemento que cumple el predicado y actualiza el atributo element.

La implementación lazy del método transform sigue ideas parecidas.

public static <F,S> Iterable<S> transform(Iterable<F> fromIterable,

Function<? super F, ? extends S> function){

return new IterableFunction(fromIterable,function);

}

private class IterableFunction<F,S> implements Iterable<S> {

private Iterable<F> fromIterable;

private Function<F,S> function;

public IterableFunction(Iterable<F> it, Function<F,S> f) {

this.fromIterable = it;

this.function = f;

}

public Iterator<S> iterator(){

return new IteradorFunction();

}

private class IteratorFunction extends UnmodifiableIterator<S>

implements Iterator<S> {

private Iterator<F> iterator;

public IteradorExpresion(){

iterator = fromIterable.iterator();

}

public boolean hasNext(){ return (iterator.hasNext()); }

public S next() {


S a= iterator.next();

return function.apply(a);

}

}

}

9. El tipo Query

Una vez vistos los iterables básicos presentados arriba y la forma de componerlos es

conveniente construir un tipo que permita trabajar de una forma sistemática con

combinaciones de iterables, expresiones, criterios, órdenes, etc. Para ello diseñamos los tipos

Query0, Query1, Query2 que ofrecen la funcionalidad adecuada para construir consultas

complejas sobre una o varias fuentes de datos. Los objetos de este tipo los llamaremos

consultas. El primer requisito es que las consultas (objetos de tipo Query) sean objetos

iterables. Por lo tanto agregados de objetos que pueden ser recorridos mediante un for

extendido.

El tipo Query0<T> es una consulta simple. Implementa Iterable<T> y es, por lo tanto, una

secuencia de elementos de tipo T. El tipo Query1<K,T> es una consulta agrupada. Implementa

Iterable<Tupla2<K, Query0<T>>> y es, por lo tanto, una secuencia de pares cuya primera

componente es de tipo K y la segunda de tipo Query0<T>. El tipo Query2<K1,K2,T> es una

consulta agrupada de nivel 2. Implementa Iterable<Tupla2<K1, Query1<K2,T>>> y es una

secuencia de pares cuya primera componente es de tipo K1 y la segunda de tipo Query1<K2,T>

El tipo Query0<T> se ha diseñado con un conjunto de métodos que aplicados sucesivamente

definen una consulta. Ofrece en primer lugar un conjunto de métodos para inicializar la

consulta a partir de una fuente de datos. Consideramos diferentes fuentes de datos: un fichero

de texto, un array, una secuencia aritmética de enteros o de números reales y en general

cualquier objeto de tipo Iterable<T> puede ser una fuente de datos.

Como veremos abajo cada método de este nuevo tipo puede implementarse usando los

métodos vistos arriba para componer iterables, expresiones y órdenes vistos anteriormente.

Algunos métodos (groupBy, join) necesitan tipos de datos que veremos en capítulos

posteriores.

Los métodos que el tipo ofrece para ello son:

class Query0<T> implements Serializable, Iterable<T>{

static <T> Query0<T> create(Iterable<T> it);

static Query0<T> fromIterable(Iterable<T> it) {…}

static Query0<T> fromArray(T[] it) {…}

static Query0<String> fromFile(String f) {…}

static Query0<String> fromFile(String f, String delim) {…}

static <N extends Number> Query0<N>

fromArithmeticSequence(N a, N b, N c) {…}

Iterator<T> iterator(){...}

Boolean all(Predicate<T> c) {…}

Boolean any(Predicate<T> c) {…}

Boolean contains(T o) {…}

Integer count() {…}

<N extends Number> N sum() {…}

<N extends Number> N multiply() {…}

<N extends Number> Double average() {…}

<F extends FieldElement<F>> N sum(Field<F> f) {…}

<F extends FieldElement<F>> N multiply(Field<F> f) {…}

<S extends Comparable<? super T>> max() {…}

T max(Comparator<T> c) {…}

<S extends <Comparable<? super S>> max(Function<T,S> f) {…}

<S extends Comparable<? super T>> min() {…}

T min(Comparator<T> c) {…}

<S extends <Comparable<? super S>> min(Function<T,S> f) {…}

T[] toArray() {…}

List<T> toList() {…}

Set<T> toSet() {…}

SortedSet<T> toSortedSet() {…}

SortedSet<T> toSortedSet(Comparator<? Super T> c) {…}

Query0<T> concat(Query0<T>… q) {…}

<S> Query0<S> concat() {…}

Query0<T> union(Query0<T> e) {…}

Query0<T> except(Query0<T> e) {…}

Query0<T> intersect(Query0<T> e) {…}

<S> Query0<S> selectMany(Function<T, Iterable<S>> e) {}

<S> Query0<S> select(Function<T, S> e) {…}

<K,R> Query1<K,T> groupBy(Function<T, K> e1 f) {…}

<K, S extends Comparable<? super S>> Query1<K,T> groupBy(

Function<T, K> f, Function<T,S> fo){...}

<K, S extends Comparable<? super S>> Query1<K,T> groupBy(

Function<T, K> f, Function<T,S> fo, Query0.TipoDeOrden t)

<U, K, R> Query0<R> join(Query0 q, Function<T, K> f1,

Function<U, K> f2, Function2<T,U,R> e3) {…}

Query0<T> distinct() {…}

Query0<T> distinct(Function<T,K> f) {…}

Query0<T> where(Predicate<T> ct) {…}

Query0<T> orderBy() {…}

Query0<T> orderBy(Comparator<T> ct) {…}

<S extends Comparable<? super S>> Query0<T> orderBy(Function<T> f) {…}

<S extends Comparable<? super S>> Query0<T> orderBy(

Function<T,S> f, Query0.TipoDeOrden t)

String toString() {…}

boolean equals(Object o) {…}

int hashCode() {…}

}

Los detalles de los tipos Query1 y Query2 se dejan como ejercicio.

Veamos los métodos por bloques y su semántica con algunos ejemplos. La implementación se

propone como ejercicio.

Métodos from:

Query0<String> fromFile(String f);

Query0<T> fromFile(String f, String delim);

Query0<T> fromIterable(Iterable<T> it);

Query0<T> fromArray(T[] it);

<N extends Number> Query0<N> fromArithmeticSequence(N a, N b, N c) {…}

Son encargados de inicializar una consulta a partir de una fuente de datos. El primero toma

como fuente de datos un fichero de texto. El segundo el nombre de un fichero y unos

delimitadores. Este construye una consulta con las palabras del fichero delimitadas por los

delimitadores. El tercero convierte un Iterable<T> en una consulta. Esto permite que cualquier

agregado iterable (como el tipo List<T>) pueda convertirse en una consulta. El cuarto convierte

el tipo T[] en una consulta. Los últimos métodos construyen secuencias aritméticas de

números. La secuencia es de a hasta b (sin incluir) con incremento c.

Todos ellos pueden ser implementados con los iterables explicados al principio del capítulo.

Método where:

Query0<T> where(Predicate<T> ct);

Es un método encargado de realizar un filtro. Es decir forma una consulta con los objetos de

otra que cumplen un criterio que se da como parámetro.

Este método se puede implementar usando el método filter de la clase Iterables.

Métodos select

<S> Query0<S> select(Function<T, S> e);

<S> Query0<S> selectMany(Function<T, Iterable<S>> e);

El método select tiene como objetivo transformar un Query0<T> en otra consulta formada por

objetos de tipo S. Cada objeto de tipo S se calcula a partir de otro de tipo T mediante la

expresión e.

Para implementar este método podemos usar el método transform de la clase Iterables.

El método selectMany es una variante del select. Tiene el mismo objetivo a partir de una

consulta formada por objetos de tipo T y una expresión e de tipo Function<T,Iterable<S>>

construye una consulta de objetos de tipo S.

Para implementar este método podemos usar los método transform y concat de la clase

Iterables.

Métodos que operan con conjuntos

Query0<T> union(Query0<T> e);

Query0<T> intersect(Query0<T> e);

Query0<T> except(Query0<T> e);

Query0<T> distinct();

<K> Query0<T> distinct(Function<T,K> e);

Query0<T> concat(Query0<T>… q);

Boolean contains(T o);

El método distinct produce una nueva consulta donde se han eliminado los elementos

repetidos. Los tres primeros (unión, intersect, except) hacen operaciones con conjuntos.

Convierten la consulta actual (denominada usualmente this en terminología Java) y la que se

recibe como parámetro en conjuntos y posteriormente hacen la unión, intersección o

diferencia de conjuntos. El conjunto resultante es un iterable que se ofrece como resultado del

método.

El método distinct ofrece otra posible cabecera: tomando una expresión como parámetro. En

este caso produce una nueva consulta donde sólo se ha conservado un objeto de cada grupo

que tiene el mismo valor cuando se aplica la expresión e.

La implementación de estos métodos usan funciones ya estudiadas sobre conjuntos y se dejan

como ejercicios.

El método contains decide si la consulta contiene un objeto particular. Su implementación

puede hacerse directamente usando el método contains de la clase Iterables.

Por último el método concat combina secuencialmente varias consultas tras la que está en

this. Se puede implementar usando el método concat de la clase Iterables.

Métodos que calculan valores agregados

Integer count();

<N extends Number> N sum();

<N extends Number> N multiply();

<N extends Number> Double average();

<F extends FieldElement<F>> N sum(Field<F> f) {…}

<F extends FieldElement<F>> N multiply(Field<F> f) {…}

T min();

T min(Comparator<T> c);

<S extends Comparable<? super S>>T min(Function<T,S> e);

T max();

T max(Comparator<T> c);

<S extends Comparable<? super S>>T max(Function<T,S> e);

Boolean any(Predicate<T> c);

Boolean all(Predicate<T> c);

T[] toArray();

List<T> toList();

Set<T> toSet();

SortedSet<T> toSortedSet(Comparator<T> c);

SortedSet<T> toSortedSet();

Cada método calcula un valor agregado y algunos son similares a métodos vistos de las clases

Iterables y Ordering. Veamos la correspondencia y el significado en la tabla siguiente.

Método Significado Equivalente Clase

count Cuenta el número de objetos size Iterables

min Mínimo con respecto a un orden min Ordering

max Máximo con respecto a un orden max Ordering

any Cumple alguno el criterio? any Iterables

all Cumplen todos el criterio? all Iterables

Además se ofrecen otros métodos como sum, multiply o average que calcula la suma, el

producto o el promedio de los valores de la consulta. El método sum asume que el tipo T es un

subtipo de Number. Si no es así dispara una excepción.

Los métodos min y max sin parámetros asumen que T tiene orden natural. Si no tiene disparan

una excepción. Se ofrecen, además estos métodos tomando una expresión como parámetro.

En este caso se calcula el máximo o mínimo con el orden sobre el tipo dado por lo valores

calculados por e.

Los métodos toArray, toList, toSet, toSortedSet convierten la consulta al tipo correspondiente.

El tipo SortedSet lo veremos en el capítulo siguiente. El método toSortedSet sin parámetros

asume que T tiene orden natural.

Métodos de ordenación

Query<T> orderBy() {…}

Query<T> orderBy(Comparator<T> ct) {…}

<S extends Comparable<? super >> Query<T> orderBy(Function<T> f) {…}

<S extends Comparable<? super S>> Query0<T> orderBy(Function<T,S> f,

Query0.TipoDeOrden t)

Los métodos anteriores construyen una consulta ordenada a partir de otra. En el primer caso

se asume que T tiene orden natural. En el segundo se proporciona el orden. En los últimos se

ordena por el orden de los valores calculados por una expresión y este orden puede ser

ascendente o descendente.

El método groupBy

<K> Query1<K, T> groupBy(Function<T, K> e);

<K, S extends Comparable<? super S>> Query1<K,T> groupBy(Function<T, K> f,

Function<T,S> fo){…}

<K, S extends Comparable<? super S>> Query1<K,T> groupBy(Function<T, K> f,

Function<T,S> fo, Query0.TipoDeOrden t)

Este método sirve para producir consultas agregadas por una clave dada. La clave se calcula

por la expresión e. El resultado es una consulta agrupada. Una consulta agrupada es un objeto

de tipo Query1<K, T>. Este es un tipo de consulta cuyos elementos son pares formados por una

clave de tipo K y una consulta de objeto de tipo T. Los dos últimos métodos producen

consultas agrupadas con las subconsultas ordenadas según los valores devueltos por la función

f0 en orden ascendente o descendente.

El método join

<U, K, R> Query0<R> join(Query0 q, Function<T, K> e1, Function<U, K> e2,

BinaryFunction<T,U,R> e3);

El método join enlaza dos iterables, this y q, a través de claves comunes. La clave sobre los

objetos de this se calcula por la expresión e1 y sobre los de q por e2. Por cada par de objetos

o1, o2 (uno de cada iterable) con la misma clave se calcula un valor mediante la expresión e3.

El iterable de salida, de tipo R, está formado por todos los valores que calcula e3 sobre todos

los pares posibles o1, o2 con la misma clave.

El tipo BinaryFunction<T,S,R> representa una expresión con dos variables (de tipos T y S) y un

resultado de tipo R. El tipo tiene un solo método cuya cabecera es R apply(T e1, S e2).

Para la implementación de este método necesitamos tipos que veremos en capítulos

próximos.

Ejemplo de uso

En los ejemplos siguientes vamos a suponer que están disponibles las lambda expresiones en

Java. Actualmente eso no es posible aunque se anuncia para la versión 8. Los detalles

sintácticos pueden variar pero entendemos que son más claros los ejemplos. En la versión 6 de

Java cada criterio, expresión u orden hay que implementarlo con una clase tal como se ha

explicado arriba. Asumimos también que el tipo de la variable ligada en la lambda expresión

puede ser deducido por el compilador.

En el primer ejemplo se leen líneas de un fichero, se convierten a enteros y se filtran los que

son positivos.

Query0<Integer> qi = Query0.fromFile("enteros.txt")

.select((s) -> new Integer(s))

.where((e) -> e > 0});

En el ejemplo siguiente se leen las líneas de un fichero, se convierten a racionales, se escoge

uno por cada grupo que tenga el mismo numerador.

Query0<Racional> qr2 = Query0.fromFile("racional1.txt")

.select((s) -> Racionales.create(s))

.distinct((r) -> r.getNumerador());

En el ejemplo siguiente se leen líneas de un fichero, se transforman a racionales y

posteriormente se agrupan según su numerador. La consulta resultante puede ser recorrida

mediante un for extendido.

Query1<Integer,Racional> qr = Query0.fromFile("racional1.txt")

.select((s) -> Racionales.create(s))

.groupBy((r) -> r.getNumerador());

Las consultas agrupadas pueden ser recorridas por for extendidos anidados. En este recorrido

se puede acceder a información sobre las consultas de cada uno de los grupos. Por ejemplo:

Mostrar (”Número de grupos = “ + qr.count());

for(Group<Integer, Racional> g : qr){

mostrar(“Numerador = ” + g.getKey()

+ ”Numero de racionales =” + g.getElements().count());

for(Racional r: g.getElements(){

mostrar(r.toString());

}

}

Por último mostramos un ejemplo de join. En el ejemplo se leen dos ficheros que contienen

líneas que representan números racionales y se transforman en consultas de racionales. Se

hace un join de una sobre otra sobre el numerador y se construyen pares de números enteros.

La consulta final está constituida por los pares (distintos) formados por el denominador de un

racional de la consulta q1 y otro de la consulta q2 que tienen el mismo numerador. La consulta

está ordenada según la primera componente del par.

Query0<Racional> q1 = Query0.fromFile("racional1.txt")

.select((s) -> Racionales.create(s));

Query0<Racional> q2 = Query0.fromFile("racional2.txt")

.select((s) -> Racionales.create(s));

Query<Tupla2<Integer,Integer>> qr = q1.join(q2,

(r) -> r.getNumerador()},

(r) -> r.getNumerador()},

(r1,r2)->

Tupla2.create(r1.getDenominador(),

r2.getDenominador())

.distinct()

.orderBy((p -> p.getP1()});

10. Problemas propuestos

1. Implementar los siguientes métodos de la clase Predicates que se han explicado

anteriormente:

static <E> Predicate<E> and(Predicate<? super T>... components)

http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/com/google/common/base/Predicates.html#and(com.google.common.base.Predicate...)

static <E> Predicate<E> or(Predicate<? super T>... components

static <A,B> Predicate<E> compose(Predicate predicate, Function<A,? extends

B> function)

static <T> Predicate<T> alwaysTrue()

static <T> Predicate<T> alwaysFalse()

2. Implementar los siguientes métodos de la clase Functions que se han explicado

anteriormente:

a. static <E> Function<E,E> identity()

b. static <A,B,C> Function<A,C> compose(Function<B,C> g, Function<A,? extends B> f)

c. static <T> Function<T,Boolean> forPredicate(Predicate<T> predicate)

d. static <E> Function<Object,E> constant(E value)

3. Implementar los siguientes métodos de la clase Ordering que se han explicado

anteriormente:

a. Ordering compound(Comparator<? super U> secondary)

b. <S extends T> Ordering<S> reverse()

c. static <C extends Comparable> Ordering<C> natural()

d. static <T> Ordering<T> from(Comparator<T> comparator)

e. <F> Ordering<F> onResultOf(Function<F,? extends T> function)

f. <S extends T> Ordering<S> nullsFirst()

g. <S extends T> Ordering<S> nullsLast()

h. <E extends T> List<E> leastOf(Iterable<E> iterable, int k)

i. <E extends T> List<E> greatestOf(Iterable<E> iterable, int k)

j. <E extends T> E max(Iterable<E> iterable)

k. <E extends T> E max(E a, E b, E c, E... rest)

l. <E extends T> E min(Iterable<E> iterable)

m. <E extends T> E min(E a, E b, E c, E... rest)

n. boolean isOrdered(Iterable<? extends T> iterable)

o. boolean isStriclyOrdered(Iterable<? extends T> iterable)

p. <E extends T> List<E> sortedCopy(Iterable<E> iterable)

4. Implementar los siguientes métodos de la clase Ordering2 que se han explicado

anteriormente:

a. <E extends T> boolean isEQ(E a, E b)

b. <E extends T> boolean isLT(E a, E b)

c. <E extends T> boolean isLE(E a, E b)

d. <E extends T> boolean isGT(E a, E b)

e. <E extends T> boolean isGE(E a, E b)


http://guava-libraries.googlecode.com/svn/tags/release08/javadoc/com/google/common/base/Predicates.html#compose(com.google.common.base.Predicate, com.google.common.base.Function)














http://download.oracle.com/javase/6/docs/api/java/lang/Boolean.html?is-external=true













http://download.oracle.com/javase/6/docs/api/java/lang/Comparable.html?is-external=true

5. Implementar los siguientes métodos de la clase Iterables que se han explicado

anteriormente:

a. static <T> Iterable<T> concat(Iterable<? extends T>... inputs)

b. static <T> Iterable<T> concat(Iterable<? extends Iterable<? extends T>> inputs)

c. static <T> Iterable<T> filter(Iterable<T> unfiltered, Predicate<? super T> predicate)

d. static <F,T> Iterable<T> transform(Iterable<F> fromIterable, Function<? super F,?

extends: T> function)

e. static boolean removeAll(Iterable<?> removeFrom,

Collection<?> elementsToRemove)

f. static boolean retainAll(Iterable<?> removeFrom, Collection<?> elementsToRetain)

g. static <T> boolean removeIf(Iterable<T> removeFrom,

Predicate<? super T> predicate)

h. static <T> boolean addAll(Collection<T> addTo,

Iterable<? extends T> elementsToAdd)

i. static int size(Iterable<?> iterable)

j. static boolean contains(Iterable<?> iterable, Object element)

k. static int frequency(Iterable<?> iterable, Object element)

l. static <T> boolean any(Iterable<T> iterable, Predicate<? super T> predicate):

m. static <T> boolean all(Iterable<T> iterable, Predicate<? super T> predicate):

n. static <T> T find(Iterable<T> iterable, Predicate<? super T> predicate)

o. static <T> int indexOf(Iterable<T> iterable, Predicate<? super T> predicate)

p. static <T> T getFirst(Iterable<T> iterable, T defaultValue)

q. static <T> T getLast(Iterable<T> iterable)

r. static <T> boolean isEmpty(Iterable<T> iterable)

6. Implementar los siguientes métodos de la clase Iterables2 que se han explicado

anteriormente:

a. static Iterable<String> from(String nombreFichero)

b. static Iterable<String> from(String cadena, String delim)

c. static Iterable<Double> from(Double a, Double b, Double c)

d. static Iterable<Integer> from(Integer a, Integer b, Integer c)

e. static Iterable<Integer> from(Integer a, Integer b, Integer c, Integer d)

f. static <T> Iterable<T> from(T[] a)

g. static <F> void modify(Iterable<F> fromIterable, Function<? super F,Void> function)

h. static <F> void saveToFile(String file, Iterable<F> fromIterable)

7. Implementar el tipo Query basándose en los métodos anteriores. Para implementar los

métodos groupBy y join es necesario conocer algunos tipos que veremos en el capítulo

siguiente.

8. En una clase de utilidad EjerciciosIterables escriba los siguientes métodos usando las clases

Iterables, Iterables2 o Query junto con Ordering, Ordering2, Functions y Predicates.

a) Un método que guarde en un fichero de texto los números primos hasta un número n dado. Su signatura será la siguiente:

public static void crearFicheroNumerosPrimos(String nomFich, Long n)

b) Un método que guarde en un fichero de texto el cuadrado de los números primos hasta un número n dado. Su signatura será la siguiente:

public static void crearFicheroCuadradosNumerosPrimos(String nomFich, Long num)

c) Un método que devuelva un Iterable<Integer> a partir de un fichero de texto que contiene en cada línea un número entero. La signatura del método será:

public static Iterable<Integer> obtenerIterableEnteros(String nomFich)

d) Un método devuelva un Iterable<Long> que vaya recorriendo los números primos menores

que un número n y que terminen en un dígito dado. La signatura del método será:

public static Iterable<Long> iterablePrimoTerminadoEn (Integer digito, Long num)

e) Un método que devuelva un Iterable<Punto> con los puntos del plano cuya coordenada sea (X,X), siendo X un número primo menor que un número dado. La signatura del método será:

public static Iterable<Punto> iterablePuntoPrimo(Long num)

f) Un método que dado un fichero de texto con una fecha escrita en cada línea, genere otro fichero con las fechas ordenadas y que estén entre dos fechas dadas. La signatura del método será:

public static void crearFicheroFechasEntreOrd(String nomFich,Fecha fIni, Fecha

fFin)

Suponga definido un método que dado el nombre del fichero original, devuelve el nombre de

un fichero de salida, que será exactamente igual que el original, pero con el prefijo “Ord_”.

Así, por ejemplo, el fichero de salida para un fichero llamado “Fechas.txt” será

“Ord_Fechas.txt”, mientras que si el fichero de entrada es “./res/Fechas.txt”, el de

salida será “./res/Ord_Fechas.txt”. La signatura de este método es:

public static String getNombreFicheroOrdenado (String nomFich)

g) Un método que dado un fichero de texto con una fecha escrita en cada línea, devuelva un Iterable<Integer> que permita iterar sobre los años de las fechas incluidas en el fichero. La signatura del método será:

public static Iterable<Integer> iterableDiasFecha(String nomFich)

h) Un método que a partir de dos cadenas de texto, devuelva un Iterable<String> que permita recorrer las palabras de las dos cadenas ordenadas. La signatura del método será:

public static Iterable<String> iterablePalabrasOrdenadas(String c1, String c2)

9. Sean los tipos Cancion y Album especificados mediante las interfaces siguientes:

public interface Cancion extends

Comparable<Cancion>, Copiable<Cancion> {

String getNombre();

String getInterprete();

Hora getDuracion();

public interface Album {

String getNombre();

Integer getAño();

Integer getNumeroDeCanciones();

Boolean getEsRecopilacion();

Integer getAño();

String getGenero();

Integer getNumeroDeReproducciones();

void setNumeroDeReproducciones (Integer n);

Integer getCalificacion();

void setCalificacion (Integer c);

Boolean getReproducir();

void setReproducir (Boolean r);

}

List<Cancion> getCanciones();

void setCanciones(List<Cancion> v);

Hora duracionAlbum();

Double calificacionAlbum();

}

El criterio de ordenación natural de Cancion es por nombre de canción y a igualdad de nombre de

canción, por intérprete. En una clase de utilidad Canciones, escriba los siguientes métodos:

a) Un método getGenero que dado un Iterable<Cancion> y un género musical, obtenga otro Iterable<Cancion> compuesto solamente por las canciones de ese género. La signatura del método será:

public static Iterable<Cancion> getGeneros (

Iterable<Cancion> itCancion, String genero)

b) Un método getGenerosOrdenadosCalificacion que a partir de un Iterable<Cancion>

obtenga un Iterable con todas las canciones de la biblioteca de dos géneros determinados, ordenados por su calificación. La signatura del método será:

public static Iterable<Cancion> getGenerosCalificacion(

Iterable<Cancion> itCancion, String genero1, String genero2)

c) Un método getCancionesRecopilatorios que a partir de un Iterable<Album> obtenga un Iterable con todas las canciones de todos los álbumes que sean recopilatorios. La signatura del método será:

public static Iterable<Cancion> getCancionesRecopilatorios(

Iterable<Album> itAlbum)

Introducción a la Programación · 2014-01-09 · 4 Introducción a la Programación Como vemos en...

Documents

Transcript of Introducción a la Programación · 2014-01-09 · 4 Introducción a la Programación Como vemos en...