PROGRAMMAZIONE 2 14. Collezioni in Java: il Java Collec...

1PR22017-2018

PROGRAMMAZIONE214.CollezioniinJava:ilJavaCollec@onsFramework(JCF)

Perchélecollezioni

•  Spessoinunprogrammadobbiamorappresentareemanipolaregruppidivalorioppureogge:diunostesso;po–  insiemedistuden;diunaclasse–  listadegliul;miSMSarriva;sulcellulare–  l’insiemedeirisulta;diunaqueryaldatabase–  lacodadeipazien;inaAesadiun’operazione–  …

•  Chiamiamocollezioneungruppodiogge:omogenei(cioèdellostesso;po)

2PR22017-2018

Arraycomecollezioni

•  Java(comealtrilinguaggi)forniscegliarraycome;podida;primi;vo“parametrico”perrappresentarecollezionidiogge:

•  Array:collezionemodificabile,lineare,didimensionenonmodificabile

•  Masonou;lianchealtri;pidicollezioni–  modificabili/nonmodificabili–  conripe;zioni/senzaripe;zioni(comegliinsiemi)–  struAuralineare/adalbero–  elemen;ordina;/nonordina;

3PR22017-2018

Ilnostrointeresse

•  Nonèsolouninteressepra;co(èu;lesaperecosafornisceJava)…

•  maancheunesempiosignifica;vodell’applicazionedeiprincipididataabstrac/oncheabbiamovisto

•  Unpo’dicontestoo  JCF(JavaCollec;onsFramework)o  C++StandardTemplateLibrary(STL)o  Smalltalkcollec;ons

4PR22017-2018

Manonbastavano…

•  Vector=collezionedielemen;omogeneimodificabileeestendibile?

•  Inprincipiosi…maèmoltomeglioavereunavarietàampiadistruAureda;concontrollista;ciperverificarelacorreAezzadelleoperazioni

5PR22017-2018

JavaCollec;onsFramework(JCF)

•  JCFdefinisceunagerarchiadiinterfacceeclassicherealizzanounariccavarietàdicollezioni

•  SfruAaimeccanismidiastrazione–  perspecifica(vediades.ladocumentazionedelleinterfacce)–  perparametrizzazione(usodi;pigenerici)

perrealizzarelevarie;pologiediastrazioneviste–  astrazioneprocedurale(definizionedinuoveoperazioni)–  astrazionedaida;(definizionedinuovi;pi–ADT)–  iterazioneastraKa<=lovedremoindeKaglio–  gerarchiedi;po(conimplementseextends)

•  Con;eneancherealizzazionidialgoritmiefficien;diu;litàgenerale(ades.ricercaeordinamento)

6PR22017-2018

JCF in sintesi

•  Una architettura per rappresentare e manipolare collezioni.

–  Gerarchia di ADT –  Implementazioni –  Algoritmi polimorfi

•  Vantaggi –  Uso di strutture standard con algoiritmi testati –  Efficienza implementazioni –  Interoperabilità –  Riuso del software

PR22017-2018 7

L’interfaccia Collection<E>

•  Definisceoperazionibasichesucollezioni,senzaassunzionisustruAura/modificabilità/duplica;…

•  Modifiersopzionali:add(E e), remove(Object o), addAll(Collection<? extends E>), clear( )

•  …perdefinireunaclassedicollezioninonmodificabili public boolean add(E e) { throw new UnsupportedOperationException( ); }

•  Observers:contains(o), equals(o), isEmpty( ), size( ), toArray()

•  Accessoaglielemen;coniterator( ) (vedidopo)8PR22017-2018

JCF:altreinterfacceimportan;

•  Set<E>:collezionesenzaduplica;.StessimetodidiCollection<E>, malaspecificacambia,ades.–  add(E el) res;tuisce false se el ègiàpresente

•  List<E>:sequenzalinearedielemen;.Aggiungemetodiperoperareinunaspecificaposizione,ades.–  add(int index, E el), int indexOf(el), remove(index),

get(index), set(index, el)

•  Queue<E>:supportapoli;caFIFO–  Deque<E>:“doubleendedqueue”,“deck”.Fornisceoperazioniper

l’accessoaidueestremi•  Map<K,T>: definisceun’associazionechiavi(K) – valori (T).Realizzata

daclassicheimplementanovari;piditabellehash(ades.HashMap)

9PR22017-2018

JCF:partedellagerarchia

10

Ne parliamo dopo è

JCF:alcuneclassiconcrete

•  ArrayList<E>, Vector<E>:implementazionediList<E> basatasuarray.Sos;tuiscel’arraydisupportoconunopiùgrandequandoèpieno

•  LinkedList<E>:implementazionediList<E>basatosudoubly-linkedlist.UsaunrecordtypeNode<E>–  Node<E> prev, E item, Node<E> next

•  TreeSet<E>:implementaSet<E>conordinecrescentedeglielemen;(definitodacompareTo<E>)

•  HashSet<E>,LinkedHashSet<E>:implementanoSet<E>usandotabellehash

11PR22017-2018

Proprietàdiclassiconcrete

12PR22017-2018

JCF:classidiu;litàgenerale

•  [email protected]:forniscemetodista;cipermanipolazionediarray,ades.–  ricercabinariaeordinamento:binarySearchesort–  operazionibasiche:copyOf,equals,toString–  conversioneinlista[inversoditoArray( )]:

static <T> List<T> asList(T[ ] a)–  NB:perfarcopiediarray,usareSystem.arraycopy(…)

•  [email protected]@ons:forniscemetodista;ciperoperaresucollezioni,compresoricerca,ordinamento,massimo,wrapperpersincronizzazioneeperimmutabilità,ecc.

13PR22017-2018

Iterazionesucollezioni:mo;vi

•  Tipicheoperazionisudiunacollezionerichiedonodiesaminaretu6glielemen/,unoallavolta.

•  Esempi:stampa,somma,ricercadiunelemento,minimo…•  Perunarrayounalistasipuòusareunfor

for (int i = 0; i < arr.length; i++) System.out.println(arr[i]);

for (int i = 0; i < list.size( ); i++) System.out.println(list.get(i));

•  Infa:,perarrayeveAorisappiamo–  ladimensione:quan;elemen;contengono(lengthosize())–  comeaccedereinmododireAoaognielementoconunindice

14PR22017-2018

Gliiteratori...

•  Uniteratoreèun’astrazionechepermeAediestrarre“unoallavolta”glielemen;diunacollezione,senzaespornelarappresentazione

•  Generalizzalascansionelinearediunarray/listaacollezionigeneriche

•  Sonoogge:diclassicheimplementanol’interfaccia

public interface Iterator<E> { boolean hasNext( ); E next( ); void remove( );}

15PR22017-2018

...eillorouso

•  Tipicousodiuniteratore(iterazioneastra;a)// creo un iteratore sulla collezione Iterator<Integer> it = myIntCollection.iterator( );while (it.hasNext( )) { // finché ci sono elementi

int x = it.next( ); // prendo il prossimo ... // uso x

}

16PR22017-2018

SpecificadeimetodidiIterator

public interface Iterator<E> {

boolean hasNext( );

/*returns:trueiftheitera;onhasmoreelements.(Inotherwords,returns

trueifnextwouldreturnanelementratherthanthrowinganexcep;on.)*/

E next( );

/*returns:thenextelementintheitera;on.

throws:NoSuchElementExcep;on-itera;onhasnomoreelements.*/ void remove( ); /*Removesfromtheunderlyingcollec;onthelastelementreturnedbytheiterator(op;onalopera;on).

Thismethodcanbecalledonlyoncepercalltonext.Thebehaviorofaniteratorisunspecifiediftheunderlyingcollec;onis

modifiedwhiletheitera;onisinprogressinanywayotherthanbycallingthismethod.*/

} 17PR22017-2018

Interpretazionegrafica-1

•  Creiamounacollezioneeinseriamodeglielemen;(nonfacciamoassunzionisuordineeripe;zionideisuoielemen;)Collection<Item> coll = new ...; coll.add(...); ...

18PR22017-2018


•  CreiamouniteratoresullacollezionecollIterator<Item> it = coll.iterator( );

•  Lorappresen;amocomeun“saccheAo”conuna“finestra”o  lafinestracon;enel’ul;moelementovisitatoo  IlsaccheAoquelligiàvisita;

19PR22017-2018


•  Invocoit.next():res;tuisce,peresempio,l’elementoC•  Graficamente,lafinestrasispostasuC

20PR22017-2018


•  Invoconuovamenteit.next():orares;tuiscel’elementoA•  Graficamente,lafinestrasispostasuA,mentrel'elementoC

vienemessonelsaccheAopernonesserepiùconsiderato

21PR22017-2018


•  it.next()res;tuisceB•  it.hasNext()res;tuiscetrueperchéc’èalmenounelemento

“fuoridalsaccheAo”

22PR22017-2018


•  it.remove()cancelladallacollezionel’elementonellafinestra,cioèB(l’ul;movisitato)

•  Uninvocazionediit.remove()quandolafinestraèvuotalanciaunaIllegalStateExcep@on

23PR22017-2018


•  it.next()res;tuisceD

24PR22017-2018


•  it.next()res;tuisceA•  Orait.hasNext()res;tuiscefalseperchénoncisonoaltri

elemen;davisitare•  Seeseguoancorait.next()vienelanciatauna

NoSuchElementExcep@on

25PR22017-2018

Riassumendo:usodiiteratore

•  Consuccessivechiamatedinext()sivisitanotu:glielemen;dellacollezioneesaAamenteunavolta

•  next()lanciaunaNoSuchElementExcep@onesaAamentequandohasNext()res;tuiscefalse

•  L’ordinenelqualevengonores;tui;glielemen;dipendedall’implementazionedell’iteratore–  unacollezionepuòaverepiùiteratori,cheusanoordinidiversi–  perlecollezionilineari(comeList)l’iteratoredefaultrispeAal’ordine

•  Sipossonoa:varepiùiteratorisimultaneamentesuunacollezione•  Seinvocolaremove()senzaaverchiamatoprimanext()silancia

unaIllegalStateExcep@on()•  Selacollezionevienemodificatadurantel’iterazionedisolitoviene

invocataunaConcurrentModifica@onExcep@on26

Iterazione,astrendodallacollezione

•  Javaforniscemeccanismiperrealizzare,tramitegliiteratori,algoritmiapplicabiliaqualunque;podicollezione

•  CreazionediiteratoredefaultsucollezioneconilmetodoIterator<E>iterator()o  definitonell’interfacciaIterable<E>cheèestesadaCollec@on<E>

•  Esempio:stampadeglielemen;diunaquasiasicollezione

public static <E> void print(Collection<E> coll) { Iterator<E> it = coll.iterator();

while (it.hasNext( )) // finché ci sono elementiSystem.out.println(it.next( ));

}

27PR22017-2018

Ilcomandofor-each(enhancedfor)

•  DaJava5.0:consentel’iterazionesutu:glielemen;diunarrayodiunacollezione(odiunoggeAocheimplementaIterable<E>)

Iterable<E> coll = ...; for (E elem : coll) System.out.println(elem); // equivalente a Iterable<E> coll = ...; Iterator<E> it = coll.iterator( ); while (it.hasNext( )) System.out.println(it.next( ));

E[ ] arr = ...; for (E elem : arr) System.out.println(elem); // equivalente a E[ ] arr = ...;

for (int i = 0; i < arr.size( ); i++) System.out.println(arr[i]);

28PR22017-2018

Modificheconcorren;

•  ContraAoconiteratore:lacollezionepuòesseremodificatasoloaAraversol’iteratore(conremove)

•  Selacollezionevienemodificatadurantel’iterazione,disolitovienelanciataunaConcurrentModifica@onExcep@on

•  Esempio List<Integer> lst = new Vector<Integer>( ); lst.add(1); // collezione con un solo elemento Iterator<Integer> it = lst.iterator( ); System.out.println(it.next( )); // stampa 1 lst.add(4); // modifica esterna all’iteratore!!! it.next( ); // lancia ConcurrentModificationException

29PR22017-2018

Iteratorieordinesuperiore

•  L’usodegliiteratoripermeAedisepararelagenerazionedeglielemen;diunacollezione(ades.intestazionedifor-each)dalleoperazionichesifannosudiessi(corpodifor-each)

•  Questosirealizzafacilmenteconnormaleastrazioneproceduraleinlinguaggi(funzionali)neiqualileproceduresono“ciAadinidiprimaclasse”,cioèvaloricometu:glialtri–  possonoesserepassatecomeparametriadaltreprocedure–  ilgeneratoreèunaprocedurachehacomeparametrolaprocedura

checodifical’azionedaeseguiresuglielemen;dellacollezione–  ilgeneratore(parametrico)èunaoperazionedel;poastraAo

•  esempio:mapdiOcaml

30PR22017-2018

Specificadiiteratori

•  Abbiamovistocomesiusauniteratoreassociatoaunacollezione

•  Vediamocomesispecificanoecomesiimplementano•  ConsideriamolaclasseIntSetdellibrodiLiskov,ma

aggiornandolarispeAoaJava5.0•  Vediamoanchecomesidefinisceuniteratore“standalone”,

chegeneraelemen;senzaessereassociatoaunacollezione•  Useremogeneratoreperiteratorenonassociatoauna

collezione•  L’implementazionefaràusodiclassiinterne

31PR22017-2018

SpecificadiiteratoreperIntSet

public class IntSet implements Iterable<Integer> {// come prima piu’ public Iterator<Integer> iterator( ); // REQUIRES: this non deve essere modificato // finche’ il generatore e’ in uso // EFFECTS: ritorna un iteratore che produrra’ tutti // gli elementi di this (come Integers) ciascuno una // sola volta, in ordine arbitrario}

•  LaclausolaREQUIRESimponecondizionisulcodicecheu;lizzailgeneratore–  ;picadegliiteratorisu;pidida;modificabili

•  DatochelaclasseimplementaIterable<E>sipuòusarefor-each

32PR22017-2018

Specificadigeneratorestandalone

public class Primes implements Iterator<Integer> { public Iterator<Integer> iterator( ) // EFFECTS: ritorna un generatore che produrra’ tutti // i numeri primi (come Integers), ciascuno una // sola volta, in ordine crescente

}

•  Un;podidatopuòavereanchepiùiteratori,quellores;tuitodalmetodoiterator()èil“default”

•  Inquestocasoillimitealnumerodiiterazionideveessereimpostodall’esternoo ilgeneratorepuòprodurreinfini;elemen;

33PR22017-2018

Usodiiteratori:stampaprimi

public class Primes implements Iterator<Integer> { public Iterator<Integer> iterator( ); // EFFECTS: ritorna un iteratore che produrrà tutti i numeri // primi (come Integers) ciascuno una sola volta, in ordine //crescente

}public static void printPrimes (int m) { // MODIFIES: System.out // EFFECTS: stampa tutti i numeri primi minori o uguali a m // su System.out for (Integer p : new Primes( )){

if (p > m) return; // forza la terminazione System.out.println("The next prime is: " + p);

}}

34PR22017-2018

Usodiiteratori:massimo

•  Essendoogge:,gliiteratoripossonoesserepassa;comeargomentoametodicheastraggonodadovevengonogliargomen;suiqualilavorano–  maxfunzionaperqualunqueiteratorediinteri

public static int max (Iterator<Integer> g) throws EmptyException, NullPointerException {

// EFFECTS: se g e’ null solleva NullPointerException; se g e’ // vuoto solleva EmptyException, altrimenti visita tutti gli

// elementi di g e restituisce il massimo intero in g try { int m = g.next( ); while (g.hasNext( )) { int x = g.next( ); if (m < x) m = x; } return m; } catch (NoSuchElementException e){ throw new EmptyException("max"); } }

35PR22017-2018

Implementazionedegliiteratori

•  Gliiteratori/generatorisonoogge:chehannocome;pounsoAo-;podiIteratoro  istanzediunaclasseγche“implementa”l’interfacciaIterator

•  Unmetodoα(standaloneoassociatoaun;poastraAo)ritornal’iteratoreistanzadiγ.Tipicamenteαèiterator()o  γdeveesserecontenutanellostessomodulochecon;eneα

ü dall’esternodelmodulosidevepotervederesoloilmetodoα (conlasuaspecifica)

ü nonlaclasseγchedefiniscel’iteratore•  Laclasseγdeveavereunavisibilitàlimitataalpackageche

con;eneαo  oppurepuòesserecontenutanellaclassechecon;eneα

ü comeclasseinternaprivata•  Dall’esternogliiteratorisonovis;comeogge:di;poIterator:ilsoAo-;poγnonèvisibile

36PR22017-2018

Classiinterne/annidate

•  Unaclasseγdichiaratacomemembroall’internodiunaclasseα puòessereo  sta;c(diproprietàdellaclasseα)o  diistanza(diproprietàdegliogge:istanzediα)

•  Seγèsta;c,comesemprenonpuòaccederedireAamenteallevariabilidiistanzaeaimetodidiistanzadiαo  leclassichedefinisconoigeneratorisonodefinitequasisemprecomeclassiinterne,sta;cheodiistanza

37PR22017-2018

Classiinterne:seman;ca

•  Lapresenzadiclassiinternerichiedelapresenzadiunambientediclassi–  all’internodelledescrizionidiclassi–  all’internodegliogge:(perclassiinternenonsta;c)–  vannomodificatediconseguenzaanchetuAeleregolecheaccedonoinomi

38 PR22017-2018

Implementazioneiteratori:Primes

public class Primes implements Iterable<Integer> { public Iterator<Integer> iterator( ) { return new PrimeGen( ); } // EFFECTS: ritorna un generatore che produrra’ tutti i numeri primi // (come Integers) ciascuno una sola volta, in ordine crescente private static class PrimeGen implements Iterator<Integer> {

// class interna statica private List<Integer> ps; // primi gia’ dati private int p; // prossimo candidato alla generazione PrimeGen( ) { p = 2; ps = new ArrayList<Integer>( ); } // costruttore public boolean hasNext( ) { return true; } public Integer next( ) { if (p == 2) { p = 3; ps.add(2); return new Integer(2); } for (int n = p; true; n = n + 2)

for (int i = 0; i < ps.size( ); i++) { int e1 = ps.get(i); if (n%e1 == 0) break; // non e’ primo if (e1*e1 > n) { ps.add(n); p = n + 2; return n; } } }

public void remove( ) { throw new UnsupportedOperationException( ); } } } 39

Classiinterneeiteratori

•  Leclassiicuiogge:sonoiteratoridefinisconocomunquedei;piastra:–  soAo-;pidiIterator

•  Inquantotalidevonoesseredota;di–  unainvariantedirappresentazione–  unafunzionediastrazione

•  dobbiamosaperecosasonoglista;astra:•  pertu:gliiteratori,lostatoastraAoè

–  lasequenzadielemen;chedevonoancoraesseregenera;•  laFAmappalarappresentazionesutalesequenza

40PR22017-2018

Generatoredinumeriprimi:FA

public class Primes implements Iterable<Integer> { public Iterator<Integer> iterator( ) { return new PrimeGen( ); } private static class PrimeGen implements Iterator<Integer> { // class interna statica private List<Integer> ps; // primi già dati

private int p; // prossimo candidato alla generazione

// la funzione di astrazione // α(c) = [ p1, p2, ... ] tale che // ogni pi e’ un Integer, e’ primo ed e’ < c.p, // tutti i numeri primi < c.p occorrono nella // sequenza, e // pi > pj per tutti gli i > j > 1

41PR22017-2018

Generatoredinumeriprimi:IR

public class Primes implements Iterable<Integer> { public Iterator<Integer> iterator( ) { return new PrimeGen( ); } private static class PrimeGen implements Iterator<Integer> { // class interna statica private List<Integer> ps; // primi già dati

private int p; // prossimo candidato alla generazione

// l’invariante di rappresentazione // I(c) = c.ps != null, // tutti gli elementi di c.ps sono primi, // sono ordinati in modo crescente e // contengono tutti i primi < c.p e >= 2

42PR22017-2018

Conclusionisugliiteratori

•  Inmol;;pididatoastra:(collezioni)gliiteratorisonouncomponenteessenziale–  supportanol’astrazioneviaspecifica–  portanoaprogrammiefficien;intempoespazio–  sonofacilidausare–  nondistruggonolacollezione–  cenepossonoesserepiùd’uno

•  Seil;podida;astraAoèmodificabilecidovrebbesempreessereilvincolosullanonmodificabilitàdellacollezionedurantel’usodell’iteratore–  altrimen;èmoltodifficilespecificarneilcomportamentoprevisto–  inalcunicasipuòessereu;lecombinaregenerazioniemodifiche

43PR22017-2018

Generareemodificare

•  ProgrammacheeseguetaskinaAesasuunacodaditask

Iterator<Task> g = q.allTasks( ); while (g.hasNext( )) { Task t = g.next( ); // esecuzione di t // se t genera un nuovo task nt, viene messo // in coda facendo q.enq(nt) }

•  Casicomequestosonomoltorari•  L’interfacciaListIterator<E>definisceiteratoripiùricchi,

perchéassumonodilavoraresuunacollezionedoublylinked–  permeAonodispostarsiinavan;eindietro(next()eprevious())–  permeAonodimodificarelalistaconadd(Ee)eset(Ee)oltrearemove()

44PR22017-2018

Sullamodificabilità

•  Duelivelli:modificadicollezioneemodificadiogge:•  LecollezionidelJCFsonomodificabili•  Sipossonotrasformareinnonmodificabiliconilmetodo public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c)

•  Ancheselacollezionenonèmodificabile,seil;pobasedellacollezioneèmodificabile,sipuòmodificarel’oggeAores;tuitodall’iteratore.QuestononmodificalastruAuradellacollezione,mailsuocontenuto

•  Infa:gliiteratoridelJCFres;tuisconoglielemen;dellacollezione,nonunacopia

45PR22017-2018

Esempio:iteratoreperarray

•  Gliarraypossonoesserevisita;conilfor-each,manonhannouniteratoredefault

•  SirealizzilaclasseArrayIteratorcherappresentauniteratoreassociatoaunveAorediinteri:inpar;colare–  laclasseArrayIteratorimplemental’interfacciaIterator<Integer>–  ilcostruAoredellaclassehacomeunicoparametrol’arraychecon;enegli

elemen;suiqualiiterare–  implementatu:imetodidiIterator<Integer>einpar;colarepublicboolean

hasNext()epublicIntegernext()•  Suggerimento:permanteneretracciadell’aAualeelementodell’iteratore

siu;lizziuncampointerocherappresental’indicedelveAore•  Sidiscutaun’eventualerealizzazionedellaremove()•  Sirendagenericalaclasse,inmododarealizzareuniteratoresuun

genericoarraydi;pobaseT

46PR22017-2018

Esempio:iteratoreinversoperVector

•  L’iteratorestandarddellaclasseVector<T>scandisceglielemen;dallaposizione0finoallaposizionesize()–1

•  SiscrivalaclasseRevVector<T>cheestendeVector<T>eridefinisceilsolometodoiterator(),res;tuendounoggeAodellaclasseRevVectIterator<T>

•  SidefiniscalaclasseRevVectIterator<T>cheimplementaIterator<T>erealizzauniteratorechescandisceglielemen;diunveAoreinordineinversoaquellostandard.Sidiscutanopiùopzioni:(1)classetop-level,classeinterna(2)sta;ca/(3)nonsta;ca,inpar;colarerispeAoallavisibilitàeaiparametridapassarealcostruAore

•  SiscrivalaclassePrintCollec@onchecon;eneilmetodosta;copublicsta@c<T>printCollec@on(Collec@on<T>coll)

•  chestampatu:glielemen;dellacollezionecollusandouniteratore–  sicostruiscanelmainunoggeAodiVectoreunodiRevVector,riempiendolicon

glistessielemen;,esiinvochiprintCollec@onsuentrambi,perverificarel’ordinenelqualevengonostampa;glielemen;

47PR22017-2018

PROGRAMMAZIONE 2 14. Collezioni in Java: il Java Collec...

Documents

Transcript of PROGRAMMAZIONE 2 14. Collezioni in Java: il Java Collec...