Realizzazione di Tipi Astratti di Dato in Java

Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Realizzazione di Tipi Astratti di Dato in Java
Laboratorio di Programmazione II
Corso di Laurea in Bioinformatica
Dipartimento di Informatica - Università di Verona
Realizzazione di Tipi Astratti di Dato
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Tipi Astratti di Dato
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Tipo Astratto di Dato
Permette di specicare dati in modo astratto
Astratto
Indipendentemente dal linguaggio (e.g., Java, C++, etc.)
Indipendentemente dalla modalità di realizzazione (e.g.
Lista, ListaLink, ListaArray)
Tipi Astratti di Dato
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Denizione
Oggetto matematico costituito da:
1
2
dominio del tipo (o dominio di interesse): insieme dei
valori validi per il tipo
funzioni: operazioni che possono essere eettutate sui
valori del tipo
Example (Il tipo Boolean)
1
2
Dominio di interesse: true, false
Funzioni: not, or, and, etc.
Esempio: Lista
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
TDA Lista
dominio del tipo: L Liste di elementi di un certo tipo T
Operazioni:
1
2
3
4
5
isEmpty(L): L ⇒ B vero se la lista L è vuota (B =
Boolean)
get(L,k): L × N ⇒ T oggetto (di tipo T ) in posizione k
nella lista L (N = interi positivi)
lenght(L): L ⇒ N il numero di oggetti contenuti in L
remove(L,k): L × N ⇒ T × L oggetto in posizione k nella
lista L, ed una Lista L0 risultante da L in cui l'oggetto in
posizione k viene rimosso.
insert(L,k,u): L × N × T ⇒ L Lista L0 risultante da L in
cui viene aggiunto l'oggetto u in posizione k .
Realizzare TDA in Java
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
TDA in Java
Elementi fondamentali della realizzazione di un TDA
Interfaccia che denisce le operazioni (e.g. Lista.java)
Scelta della rappresentazione (ListaArray.java,
ListaLink.java)
Schema Realizzativo
Schema Realizzativo
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Modalità principali
Modalità di realizzazione delle operazioni
Due schemi principali
1
2
side eect: i metodi della classe operano modiche su
oggetti di moduli cliente
funzionale: i metodi della classe calcolano valori senza
modicare gli oggetti della classe
Realizzazione con Side Eect
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Side Eect
Modica gli oggetti
Si discostano notevolmente dalla denizione matematice di
ADT (concetto di oggetto)
Ecienti: metodi agiscono direttamente sugli oggetti
Danno luogo ad oggetti mutabili
Example (Side Eect)
Lista a = new ListaLink();
Lista b = a;
a.insert(0, new Integer(1));
a.insert(2, new Integer(2));
System.out.println("Lista a = "+a);
System.out.println("Lista b = "+b);
Realizzazione funzionale
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Funzionale
Non modicano mai gli oggetti di invocazione ma
restituiscono un nuovo oggetto per ogni operazione di
modica
Insert per Lista funzionale
Lista insert(int k, Object o)...
Molto simili alla denizione matematica dell'ADT
Tipicamente meno ecienti, ma più sicuri
Danno luogo ad oggetti immutabili
Example (Oggetti immutabili)
String a = new String("ciao");
String b = a;
a.toUpperCase();
System.out.println("Stringa a = "+a);
System.out.println("Stringa b = "+b);
Uguaglianza per TDA
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Uguaglianza profonda
promemoria ==⇒ uguaglianza tra riferimenti (uguaglianza
superciale)
promemoria metodo equals(Object) della classe Object
puo' essere re-implementato da tutte le classi derivate
(overriding)
promemoria metodo equals di default controlla
l'uguaglianza superciale
uguaglianza profonda: uguaglianza basata sulle
informazioni contenute nell'oggetto
Per ADT è consigliabile re-implementare equals per
ottenere l'uguaglianza profonda (e.g., metodo equals() di
ListaArray.java)
Utilizzo Java API per implementare ADT
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Utilizzo API per ADT
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
API per ADT
ADT più importanti sono implementati nelle API di JAVA
Utilizzo librerie disponibili riduce notevolmente il tempo di
sviluppo (e soprattutto il debug)
ADT lineari: Lista
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
API per Lista
Interfaccia List
Molte realizzazioni, in particolare:
ArrayList: basata su array
LinkedList: basata su strutture collegate
Utilizzo delle API per ADT Lista
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Esempio: ArrayList
Creazione: List l = new ArrayList();
Utilizzo:
aggiunta oggetto: l.add(new Integer(3))
accesso oggetto: int pos= ...; l.get(pos)
scansione:
for (int i = 0; i < l.size(); i++) {
System.out.println(i+ " " + l.get(i));
}
Note su utilizzo API
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Note
ArrayList e LinkedList implementano l'interfaccia List
quindi
Utilizzare ArrayList o LinkedList per istanziare un oggetto
di tipo List è trasparente in fase di compilazione
Esempio: metodo ll() classe TestList.java
La particolare realizzazione impatta sull'ecienza del
codice: tempo esecuzione e memoria
ArrayList: ri-allocazione del vettore se necessario
LinkedList: accesso sequenziale
Liste e tipo degli elementi contenuti
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Liste e tipo degli elementi
ADT lista: sequenza di elementi di un solo tipo
In java posso inserire in una lista elementi di tipi diversi,
perchè tutto deriva da Object
Si discosta dal ADT e crea problemi a tempo di esecuzione
Example (Esempio di lista con elementi eterogenei)
List lista = new ArrayList();
lista.add(new Studente("001"));
lista.add(new Studente("002"));
lista.add(new Integer(3));
Forzare liste di elementi omogenei
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Il meccanismo della parametrizzazione del tipo
Generics o tipi parametrizzati
Dichiaro al momento della creazione quali elementi saranno
inseriti nella lista
List<tipoElemento> listaT = new
ArrayList<tipoElemento>()
Il compilatore controlla che il vincolo sul tipo degli elementi
sia rispettato
listaT.add(elementoTipoNonCorretto) errore a tempo di
compilazione
Esempio: TestGenerics.java
Leggere le API di java
Realizzazione
di Tipi
Astratti di
Dato in Java
Come leggere le API
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
informazioni principali per ciascuna classe:
Classi e/o interfacce che vengono estese e/o realizzate
dalla classe corrente
Classi e/o interfacce che implementano e/o estendono la
classe corrente
Eventuale parametrizzazione dei tipi
Package da includere (e.g. import java.util.*);
Esercizi
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Esercizi API
1 realizzare il metodo elimina doppi della classe UtilList.java
utilizzando ArrayList o LinkedList
2 realizzare il metodo sottoSequenza della classe UtilList.java
utilizzando LinkedList o ArrayList
3 realizzare il metodo stampa inversi della classe UtilList.java
utilizzando la classe Stack
Nota sull'interfaccia Comparable
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Utilizzo appropriato di Comparable<E>
1 l'interfaccia comparable utilizza un tipo parametrizzato
Comparable<E>
2 E e' il tipo degli elementi con cui la classe che implementa
l'interfaccia puo' essere comparata.
3 Permette di evitare il downcast nel compareTo() ed evita
warning in compilazione
4 Vedi UtilComparable.java e StudenteTypeSafe.java
Collezioni di Oggetti
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Collezioni di oggetti
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Collezioni
Lista è una particolare tipologia di collezione di oggetti
Ne esistono molte altre: Pila, Coda, Insieme etc.
Le tipologie di collezioni principali sono realizzate nelle
librerie Java di base
L'interfaccia Collection rappresenta i metodi di base per
una qualsiasi collezione
Collezioni in Java I
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Interfaccia Collection
Collezioni in Java II
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Interfaccia Collection: metodi
ADT Insieme
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Insieme
Dominio di interesse: è formato da insiemi di elementi di
un certo dominio E
Operazioni:
1
2
3
4
5
emptySet(), che restituisce il valore corrispondente
all'insieme vuoto.
isEmpty(i), che restituisce true se l'insieme i è l'insieme
vuoto, false altrimenti.
add(i,e), che restituisce l'insieme j ottenuto dall'insieme i
aggiungendo l'elemento e; se e appartiene già a i allora j
coincide con i.
remove(i,e), che restituisce l'insieme j ottenuto dall'insieme
i eliminando l'elemento e; se e non appartiene a i allora j
coincide con i.
contains(i,e), che restituisce true se l'elemento e
appartiene all'insieme i, false altrimenti.
ADT Insieme in Java
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Interfaccia Set
ADT Insieme in Java: caratteristiche
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Interfaccia Set caratteristiche
Tipo parametrizzato: E rappresenta il tipo degli elementi
dell'insieme
Mette a disposizione molti metodi oltre alle operazioni di
base (e.g. addAll(...), removeAll(...), retainAll(...))
Insieme di Interi: Set<Integer> insiemeInteri = ...
L'interfaccia Set viene realizzata da numerose classi
1
2
HashSet: operazioni di base in tempo costante (sotto
opportune ipotesi)
TreeSet: operazioni di base in tempo O(log n)
Un insieme non puo' avere occorrenze multiple di elementi,
questo viene garantito dai metodi che gestiscono l'insieme
(tutti i metodi add)
Utilizzo Set
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
HashSet
Dichiarazione
Set<Integer> s1 = new HashSet<Integer>();
Aggiunta elementi
s1.add(new Integer(1));
Aggiunta di una collezione di elementi
s1.addAll(collezione);
Set: Accesso agli elementi
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Iteratori
Non esiste il concetto di posizione di un elemento
non esiste il metodo s.get(i) dove i è la posizione
dell'elemento
Si utilizzano gli iteratori
Un iteratore è un riferimento ad un oggetto contenuto in
una collezione
Permettono di accedere in maniera sequenziale qualsiasi
collezione (pile,liste,code,insiemi, etc.)
Utilizzo iteratori
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Creare un iteratore
Data una collezione c
Collection<T> c = ...
iterator() metodo della collezione, restituisce un iteratore al
primo elemento della collezione
Iterator<T> it = c.iterator();
Utilizzo degli iteratori
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
iteratori
Dato un iteratore
Iterator<T> it = c.iterator();
metodo hasNext() restituisce true se la collezione su cui
l'iteratore agisce ha almeno un altro elemento
for(Iterator<T> it = c.iterator(); it.hasNext();)
metodo next() restituisce l'elemento a cui l'iteratore si
riferisce ed aggiorna l'iteratore al prossimo elemento della
collezione.
for(Iterator<T> it = c.iterator(); it.hasNext();)
T elemento = it.next()
esempio di scansione di tutti gli elementi di un insieme:
calcolaMedia(Set<Integer>) della classe TestSet.java
Esercizi
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Esercizi su Set
Implementare il metodo
migliorMedia(Set<Set<Integer>>)
della classe TestSet.java
Implementare il metodo
intersezione(Set<Integer>, Set<Integer>)
della classe TestSet.java
Sottoinsiemi di un insieme (insieme delle parti)
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Insieme delle parti (power set)
dato un insieme S il power set P(S ) è l'insieme di tutti i
sottoinsiemi di s
S = {1, 2}, P(S ) = {{}, {1}, {2}, {1, 2}}
concetto molto importante per algoritmi a forza bruta
Calcolo ricorsivo dell' insieme delle parti
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Insieme delle parti: calcolo ricorsivo
dato un insieme di elementi S ed un insieme (di insiemi) T
detta F(e , T ) = {X ∪ {e }|X ∈ T }
denizione ricorsiva:
P(S ) = {∅} se
S =∅
e primo elemento di S , T = S \ {e },
P(S ) = P(T ) ∪ F(e , P(T ))
Esercizi
Realizzazione
di Tipi
Astratti di
Dato in Java
Realizzazione
di Tipi
Astratti di
Dato
Utilizzo Java
API per implementare
ADT
Collezioni di
oggetti
Esercizi su Set
Implementare il metodo sottoinsiemi(Set<Integer>) della
classe TestSet.java