Astrazione sul controllo: gli iteratori Perché vogliamo iterarare “in modo astratto”



Scaricare 1.25 Mb.
23.05.2018
Dimensione del file1.25 Mb.


Astrazione sul controllo: gli iteratori


Perché vogliamo iterarare “in modo astratto”

  • problema: iterare su tipi di dato arbitrari

  • esempio: procedura stand-alone per calcolare la somma di tutti gli elementi di un IntSet

  • public static int setSum (IntSet s) throws NullPointerException

  • // EFFECTS: se s è null solleva

  • // NullPointerException altrimenti

  • // ritorna la somma degli elementi di s



Problema

  • Non vediamo la rappresentazione (p.e. quella realizzata dal vettore els)

  • Dobbiamo usare i metodi pubblici forniti dalla classe IntSet

  • Unico modo per accedere agli elementi: choose







Una soluzione

  • Prendiamo un elemento a caso con il metodo choose

  • Lo rimuoviamo

  • Ripetiamo fino a svuotare l’insieme

  • La procedura non deve modificare

  • l’insieme (non e’ riportato in MODIFIES)

  • Quindi ci vuole una struttura di supporto per memorizzare gli elementi



Soluzione insoddisfacente 1

  • public static int setSum (IntSet s) throws NullPointerException {

  • // EFFECTS: se s è null solleva

  • // NullPointerException altrimenti

  • // ritorna la somma degli elementi di s

  • int[ ] a = new int [s.size( )];

  • int sum = 0;

  • for (int i = 0; i < a.length; i++)

  • {a[i] = s.choose( );

  • sum = sum + a[i];

  • s.remove(a[i]); }

  • // risistema s

  • for (int i = 0; i < a.length; i++)

  • s.insert(a[i]);

  • return sum;}

  • ad ogni iterazione vengono chiamate due operazioni (choose e remove)

  • gli elementi rimossi li mettiamo in un array, poi li riinseriamo



Soluzione Sbagliata

  • Un modo di risolvere il problema (accedere alla rappresentazione)

  • Per esempio, in IntSet accedere agli elementi memorizzati nel vettore els (dichiarando il vettore pubblico)

  • Da evitare: rompe l’astrazione rendendo dipendenti gli altri moduli dall’implementazione



Soluzione insoddisfacente 2

  • Il tipo di dato astratto non e’ progettato bene (metodi pubblici forniti sono limitati….)

  • potremmo aggiungere setSum come metodo d’istanza della classe IntSet

    • in modo più efficiente
      • accedendo la rappresentazione
    • non è direttamente collegata al concetto di IntSet
    • quante altre operazioni simili dovremmo mettere in IntSet?
      • trovare il massimo elemento.....
  • Meglio sarebbe modifacre la specifica mettendo delle operazioni che siano un piu’ generali





Soluzione leggermente diversa

  • public int [ ] members ()

  • // EFFECTS: restituisce un array contenente gli

  • // elementi di this, ciascuno esattamente una volta,

  • // in un ordine arbitrario

  • public static int setSum (IntSet s) {

  • int[ ] a = s.members();

  • int sum = 0;

  • for (int i = 0; i < a.length; i++) sum = sum + a[i];

  • return sum;}

  • inefficiente

    • due strutture dati
    • non sempre vogliamo generare tutti gli elementi della collezione
      • massimo elemento


Di cosa abbiamo bisogno?

  • un meccanismo generale di iterazione, che permette di iterare sugli elementi di IntSet

    • facile da usare
    • efficiente
    • che preservi l’astrazione (ovvero che non riveli a chi lo usa il modo in cui l’insieme e’ implementato)


Vorremmo un generatore

  • un generatore g produce in modo incrementale (uno alla volta) tutti gli elementi i della collezione corrispondente all’oggetto

  • Utilizzando un generatore e’ possibile realizzare l’iterazione astratta: per ogni i prodotto da g esegui a su i

  • l’azione a da compiere sugli elementi è separata dalla generazione degli elementi stessi



Generatori in Java

  • i generatori sono oggetti di particolari classi (tipi)

  • Sono sottotipi di una Interfaccia Iterator

    • il tipo Iterator è definito dalla seguente interfaccia Java (java.util package)


Cos’e’ una Interfaccia

  • Una Interfaccia e’ un particolare tipo di classe

  • Contiene solo specifica e nessuna implementazione

  • La specifica non contiene costruttori e neanche metodi statici

  • Solo metodi d’istanza





Interfaccia Iterator (versione semplificata)

  • public interface Iterator {

  • public boolean hasNext ( );

  • // EFFECTS: restituisce true se ci sono altri

  • // elementi altrimenti false

  • public Object next throws NoSuchElementException;

  • // MODIFIES: this

  • // EFFECTS: se ci sono altri elementi da generare

  • //dà il successivo e modifica lo stato di this,

  • //altrimenti solleva NoSuchElementException (unchecked)

  • }



Versione semplificata

  • L’interfaccia che usiamo e’ semplificata a scopo didattico

  • Riferiamo alla documentazione di Java per un trattamento completo



Generatori



Cosa vedremo?

  • Come si usa un generatore per realizzare l’iterazione astratta su un tipo di dato (dal punto di vista degli altri moduli)

  • Come si implementa l’interfaccia Iterator per iterare su un certo tipo di dato astratto





Specifica di un iteratore per IntSet

  • public class IntSet {

  • // come prima più

  • public Iterator elements (){

  • // EFFECTS: ritorna un generatore che produrrà tutti

  • // gli elementi di this (come Integers) ciascuno una

  • // sola volta, in ordine arbitrario

  • // REQUIRES: this non deve essere modificato

  • // finché il generatore è in uso }

  • la clausola REQUIRES impone condizioni sul codice che utilizza il generatore

    • per questo è messa alla fine
    • tipica degli iteratori su tipi di dato modificabili




Specifica di un iteratore stand alone

  • public static Iterator allPrimes ()

  • // EFFECTS: ritorna un generatore che produrrà tutti

  • // i numeri primi (come Integers) ciascuno una

  • // sola volta, in ordine arbitrario

  • }

  • il limite al numero di iterazioni deve essere imposto dall’esterno

    • il generatore può produrre infiniti elementi








IntSet

  • public Iterator elements ()

  • // EFFECTS: ritorna un generatore che produrrà tutti

  • // gli elementi di this (come Integers) ciascuno una

  • // sola volta, in ordine arbitrario

  • // REQUIRES: this non deve essere modificato

  • // finché il generatore è in uso }

  • Lo possiamo usare per realizzare:

  • public static int setSum (IntSet s) throws NullPointerException

  • // EFFECTS: se s è null solleva

  • // NullPointerException altrimenti

  • // ritorna la somma degli elementi di s





Iteratori

  • Abbiamo visto la specifica e l’uso dei metodi che ritornano un generatore (sottotipo di Iterator)

  • Questi metodi li abbiamo chiamati iteratori

  • Come e dove si definiscono generatori?



Implementazione degli iteratori e dei generatori

  • i generatori sono oggetti che hanno come tipo un sottotipo di Iterator

    • istanze di una classe  che “implementa” l’interfaccia Iterator
  • un iteratore  è un metodo (stand alone o associato ad un tipo astratto) che ritorna il generatore istanza di 

  • Vogliamo che  acceda alla rappresentazione (deve iterare) senza renderla visibile



Esempio

  • Il generatore di IntSet deve produrre tutti gli elementi dell’insieme

  • Deve necessariamente poter accedere alla rappresentazione, ovvero al vettore els

  • Quindi non e’ possibile dichiarare la classe come

  • classe separata

  • La classe che definisce il generatore deve essere dichiarata all’interno di IntSet



Classi nidificate

  • una classe  dichiarata all’interno di una classe può essere

    • static (di proprietà della classe )
    • di istanza (di proprietà degli oggetti istanze di )
  • se  è static come sempre non può accedere direttamente le variabili di istanza ed i metodi di istanza di 

    • le classi che definiscono i generatori si possono quasi sempre definire come inner classes statiche
    • prendono gli oggetti come parametro


Classi interne

  • Non descrivere tutti i dettagli

  • Una classe interna statica e privata ha la semantica standard (come se fosse separata)

  • Solo che non e’ visibile da fuori e puo’ accedere alle variabili private della classe che la contiene













Implementazione degli iteratori 3

  • public class Num {

  • public static Iterator allPrimes (){return new PrimesGen();}

  • // EFFECTS: ritorna un generatore che produrrà tutti

  • // i numeri primi (come Integers) ciascuno una

  • // sola volta, in ordine arbitrario

  • private static class PrimeGen implements Iterator {

  • // inner class (classe annidata)

  • private Vector ps; // primi già dati

  • private int p; // prossimo candidato alla generazione

  • PrimesGen () {p = 2; ps = new Vector(); }

  • public boolean hasNext () {return true }

  • public Object next () {

  • if (p == 2) { p = 3; return new Integer(2);}

  • for (int n = p; true; n = n + 2)

  • for (int i = 0; i < ps.size(); i++){

  • int e1 = ((Integer) ps.get(i)).intValue();

  • if (n%e1 == 0) break; // non è primo

  • if (e1*e1 > n)

  • {ps.add(new Integer(n); p = n + 2;

  • return new Integer(n);}}} }}



Classi nidificate e generatori

  • le classi i cui oggetti sono generatori definiscono comunque dei tipi astratti

    • sottotipi di Iterator
  • in quanto tali devono essere dotati di

    • una funzione di astrazione
    • un invariante di rappresentazione


Funzione di astrazione per i generatori

  • dobbiamo sapere cosa sono gli stati astratti

  • per tutti i generatori, lo stato astratto è

    • la sequenza di elementi che devono ancora essere generati
    • la funzione di astrazione mappa la rappresentazione su tale sequenza


Funzione di Astrazione: IntSetGen



Invariante di rappresentazione

  • I(c) = c.s != null e

  • (0 <= c.next <= c.s.els.size())

  • Il next varia tra 0 e la lunghezza del vettore



Correttezza dell’iteratore







Correttezza del generatore

  • Valgono le invarianti di Intset e di IntSetGen

  • E’ facile convincersi che i metodi next e hasnext() soddisfano la specifica



Correttezza dell’iteratore

  • il generatore soddisfa anche la specifica (quella richiesta in elements)

  • // EFFECTS: ritorna un generatore che produrrà tutti

  • // gli elementi di this (come Integers) ciascuno una

  • // sola volta, in ordine arbitrario

  • Il generatore ritorna gli elementi del vettore che rappresenta l’insieme

  • E’ corretto perche’: (1) non ci sono occorrenze multiple nel vettore; (2)

  • gli elementi del vettore sono Integer

  • Queste proprieta’ sono garantite dall’invariante di IntSet



Conclusioni sugli iteratori

  • in molti tipi di dato astratti (collezioni) gli iteratori sono un componente essenziale

    • supportano l’astrazione via specifica
    • portano a programmi efficienti in tempo e spazio
    • sono facili da usare
    • non distruggono la collezione
    • ce ne possono essere più d’uno
  • se il tipo di dato astratto è modificabile ci dovrebbe sempre essere il vincolo sulla non modificabilità del dato durante l’uso dell’iteratore

    • altrimenti è molto difficile specificarne il comportamento previsto
    • in alcuni casi può essere utile combinare generazioni e modifiche




Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale