Esercitazione
Object, Vettori, Liste
Ereditarieta’
• Abbiamo visto come tramite l’ereditarieta’
e’ possibile estendere classi esistenti
-arricchendo lo stato degli oggetti
-aggiungendo nuove operazioni
•Se c1 estende c2, c1 e’ un sottotipo di c2
Ricordiamo che
• Se una classe c1 estende la classe c2
-c1 eredita tutte le variabili ed i metodi d’istanza di
c2 (a meno di overriding)
-puo’ accedere a tutte le variabili e ai metodi
statici di c2
Classe Object
• La classe Object è la superclasse, diretta o indiretta, di
ciascuna classe in Java
• Object è supertipo di qualsiasi oggetto
Attenzione
• I tipi primitivi int, boolean, double non sono
sottotipi di Object, non sono oggetti (vedi la differenza
nella semantica)
• String e’ un tipo primitivo sottotipo di Object
• BankAccount, Persona sono esempi di tipi non
primitivi sottotipi di Object
A cosa serve?
Grazie al meccanismo dell'ereditarietà
 i suoi metodi sono ereditati da tutti i sottotipi
ad una variabile di tipo Object possiamo assegnare oggetti di
qualsiasi tipo (principio di sostituzione)
•Un oggetto del supertipo puo’ essere usato ovunque sia richiesto un valore
del supertipo
Esempio
Object obj;
String s=“io”;
Obj=s;
\\ e’ corretto un sottotipo e’ assegnato ad un supertipo
BankAccount b=new BankAccount();
Obj=b;
\\ e’ corretto un sottotipo e’ assegnato ad un supertipo
Obj=4;
\\ e’ un errore non e’ sottotipo
•Analogamente un metodo che ha un parametro formale Object potrebbe essere chiamato
con un parametro attuale del sottotipo
•Meccanismo essenziale per utilizzare lo stesso codice per i vari sottotipi
Metodi Eredidati da Object
•Sono metodi ereditati da tutti i sottotipi (devono tipicamente essere
sovrascritti)
•I metodi più utili sono:
{
\\EFFECTS: restituisce una rappresentazione
dell'oggetto this in forma di stringa. }
public String toString()
public boolean equals(Object obj)
\\EFFECTS :verifica se l'oggetto this è uguale a obj.
Commenti a toString()
•La definizione del metodo nella classe Object restituisce una stringa che contiene
il nome della classe dell'oggetto ed una rappresentazione esadecimale del codice hash
dell'oggetto (indirizzo in memoria dell'oggetto).
•Questo accade perché la classe Object non può conoscere la struttura dell'oggetto.
Il metodo ereditato e’ poco utile.
•Il metodo deve quindi essere sovrascritto in ogni classe che lo usa per ottenere
un risultato significativo. Tipicamente, di un oggetto si vogliono mostrare
(nella stringa restituita) i valori delle variabili d'istanza o comunque una
informazione significativa che descriva
lo stato interno
Commenti ad
equals
•Concettualmente, l'invocazione
<obj1>.equals(<obj2>)
del metodo equals dovrebbe restituire true quando il contenuto
dei due oggetti è uguale (non il riferimento, come per l'operatore ==).
•L'esempio tipico è il confronto tra stringhe.
•D’altra parte il metodo equals della classe Object, e’ implementato
non potendo fare alcuna assunzione sulla struttura interna degli
oggetti su cui viene invocato (utilizza semplicemente l'operatore == per confrontarli.)
•Deve quindi essere sovrascritto in modo opportuno nel sottotipo (overriding)
a seconda delle caretteristiche degli oggetti
•Per il tipo String il metodo e’ gia’ ridefinito in modo primitivo
Object come supertipo
• Utilizzando Object e’ possibile definire collezioni di dati generiche
•Non hanno un tipo fissato, ma sono
in grado di memorizzare elementi di ogni sottotipo di Object
•Vediamone un esempio tramite un tipo di dato primitivo, vettori
•Analizzeremo la classe Vector
•Simile all’array, i vettori permettono di memorizzare sequenze di
valori di dimensione variabile
•Esistono anche altri tipi di dato primitivo, simili. Consideriamo un
caso come esempio
Un tipo di dato primitivo
•La classe java.util.Vector permette di definire degli oggetti
chiamati vettori (Vector)
-memorizzano sequenze di oggetti di lunghezza variabile
-possono memorizzare oggetti di tipo diverso, purche’ sottotipi
di Object, (es. String, etc.)
Tipo
Vector
Simili agli array a parte il fatto che
•
la dimensione di un vettore può variare durante
l'esecuzione di un programma
• non vanno creati per un tipo prefissato, le posizioni del Vector hanno
un tipo generico Object
• quindi possono contenere oggetti di ogni tipo anche tra loro
disomogenei (tipo String o Integer) grazie al principio di
sostituzione
Tipo
Vector
• Vediamo la specifica
• Principali costruttori e metodi
• Non daremo una trattazione completa
Costruttore
public Vector (){
\\EFFECTS: crea un vettore vuoto}
• Notate che a differenza che per gli arrays non e’ necessario fissare al momento
della creazione la dimensione
Metodi simili a quelli dell’array
public int size (){
\\EFFECTS: restituisce il numero di elementi presenti nel
vettore}
public Object elementAt (int index){
\\EFFECTS: restituisce l'elemento di indice index }
public void setElementAt (Object obj, int index){
\\MODIFIES: this
\\EFFECTS:
sostituisce obj all'oggetto della posizione index}
•
Se l’index non e’ presente nel vettore viene sollevata una eccezione
come per gli arrays
Metodi per aggiungere
public void insertElementAt (Object obj, int index){
\\MODIFIES:this
\\EFFECTS: inserisce obj nella posizione index e sposta tutti gli
elementi, da index in poi, di una posizione}
public void addElement (Object obj){
\\MODIFIES:this
\\EFFECTS: aggiunge una posizione alla fine che contiene obj }
• La dimensione del Vector cambia, viene aggiunta una posizione
alla fine o in un dato punto
Metodi per rimuovere
public void removeElementAt (int index){
\\MODIFIES:this
\\EFFECTS: rimuove l'oggetto presente nella posizione index e sposta
all'indietro di una posizione tutti gli elementi successivi
a quello rimosso}
public boolean removeElement (Object obj){
\\MODIFIES:this
\\EFFECTS: rimuove la prima occorrenza
dell'oggetto obj se presente restituendo true,oppure
restituisce false}
•
La dimensione del Vector cambia, viene ricompattato (non rimane una
posizione vuota)
Vector per memorizzare stringhe
Vector v=new Vector();
\\ [] inizialmente vuoto
v.addElement(“a”); \\ [a]
v.addElement(“b”); \\ [a,b]
v.addElement(“c”); \\ [a,b,c]
v.removeElementAt(1); \\ [a,c]
Come leggere gli elementi?
public Object elementAt (int index){
\\EFFECTS: restituisce l'elemento di indice index }
Vector v=new Vector();
\\ []
v.addElement(“a”); \\ [a]
v.addElement(“b”); \\ [a,b]
v.addElement(“c”); \\ [a,b,c]
String s= v.elementAt(0);
•
\\ e’ corretto?
Sembrerebbe, dovrebbe restituire una stringa, ma……..
Problema:errore di compilazione
•
Stiamo usando un tipo Vector per memorizzare stringhe, ma il Vector e’ dichiarato
generico
Vector v=new Vector();
\\ non si fissa il tipo degli elementi
String[] v=new String[5]; \\ differenza con l’array
• il compilatore non puo’ sapere quale tipo di valori sono correntemente
memorizzati nella prima posizione del Vector (il suo tipo effettivo)
•
il compilatore conosce solo il tipo restituito dal metodo (il suo tipo apparente)
Necessario: Cast
Vector v=new Vector();
\\ []
v.addElement(“a”); \\ [a]
v.addElement(“b”); \\ [a,b]
v.addElement(“c”); \\ [a,b,c]
String s= ((String) v.elementAt(0));
\\ compila
•Il compilatore non riporta errori in quanto String e’ sottotipo del tipo
apparente Object
•Il Cast potrebbe provocare un errore a run-time qualora il valore
restituito dal metodo non fosse sottotipo di String
Tipi Primitivi?
Vector elements=new Vector();
elements.addElement(3);
errore di tipo!
non e’ sottotipo di Object (il metodo addElement ha
parametro Object)
• int
• Analoghi problemi per gli altri tipi boolean,
double…
La soluzione
• Ogni tipo primitivo ha un corrispondente sottotipo
di Object, sono oggetti che memorizzano i valori
corrispondenti
• Per esempio, Integer e’ la classe involucro di int
• Ogni Integer e’ un oggetto che memorizza un
valore int
•
Integer e’ sottotipo di Object
• Classi analoghe per tutti gli altri tipi primitivi
•Integer ha (oltre ai soliti metodi toString e equals):
•un costruttore con parametro di tipo primitivo
public Integer(int value){
\\EFFECTS: crea un Integer che contiene il valore value}
•un metodo che produce il valore di tipo primitivo corrispondente
public int intValue(){
\\EFFECTS: restituisce il numero intero
contenuto in this}
Esempio
•Vogliamo memorizzare il valore 3 in un Vector
Integer e= new Integer(3); //creiamo l’Integer
elements.addElement(e); //lo inseriamo
•Vogliamo leggere un valore da un Vector di Integer e
trasformarlo in int
Integer i= (Integer) elements.elementAt(3); //Cast
int x= i.intValue();//conversione
•E’ una delle strutture dati fondamentali in tutti i
linguaggi di programmazione di alto livello
•Una Lista Concatenata serve per rappresentare
sequenze di elementi (di dimensione variabile)
[ 19
[]
57
3
35 11
91
5 ]
•Le operazioni permettono di aggiungere elementi
all’inizio o alle fine, e di scorrere la lista
•Facciamo vedere una realizzazione ricorsiva in Java
Tipo di dato ricorsivo
• Definizione ricorsiva: una lista concatenata e’
• vuota
• o e’ un nodo che contiene un valore e un
riferimento al resto della lista
Esempio
val next
Lista non vuota:
Primo elemento
11
64
Lista vuota
IntList
• Vediamo per esempio una possibile specifica nel
caso di elementi di tipo Integer
• Definiamo un tipo di dato astratto modificabile
• Si puo’ ovviamente anche definire non
modificabile
Specifica di IntList
public class IntList {
// OVERVIEW: un IntList è una lista modificabile
// di Integer.
// Elemento tipico [x1,...,xn]
public IntList () {
// EFFECTS: inizializza this alla lista vuota }
public IntList (Integer x){
//REQUIRES: x e’ diverso da null
// EFFECTS: se x e’ null solleva
//NullPointerException, inizializza this alla
//lista che contiene esattamente x }
Specifica di IntList
public void addEl (Integer x)
{//MODIFIES:this
//REQUIRES: x e’ diverso da null
// EFFECTS: se x e’ null solleva
//NullPointerException, altrimenti
//all’inizio di this }
aggiunge x
public Integer first (){
//REQUIRES: this non e’ vuota
// EFFECTS:ritorna il primo elemento di this}
public IntList rest (){
//REQUIRES: this non e’ vuota
// ritorna la lista ottenuta da this togliendo
//il primo elemento}
Specifica di IntList
public int size () {
// EFFECTS: ritorna il numero di elementi di
//this}
public String toString (){
//EFFECTS: restituisce una stringa che descrive
//la sequenza di elementi di this }
}
}
Come si implementa?
•Si puo’ implementare in tanti modi diversi (scegliendo opportune
variabili d’istanza)
•Notiamo in ogni caso che il tipo di dato si puo’ usare utilizzando
solo la specifica
•La specifica contiene tutte le informazioni che servono per usare il tipo
di dato
•Programmando tramite la specifica astraiamo dalla particolare
implementazione
Esempio: astrazione tramite
specifica
•Il metodo rest restituisce il resto della lista (la lista meno
il primo elemento)
•Usando first e rest si puo’ scorrere una lista (indipendentemente da
come e’ implementata)
•Esempio: metodo di ricerca statico realizzato in un modulo (classe)
separata
public static boolean cerca (Intlist l,Integer x)
throws NullPointerException{
//REQUIRES: l ed x diversi da null
// EFFECTS: restituisce true se x occorre nella
//lista l, false se non occorre}
Utilizzando solo la specifica
public static boolean cerca
(Intlist l,Integer x){
//caso base
if (l.size()==0) {return false;}
//caso ricorsivo
{Integer el=l.first();
if (el.equals(x)) {return true;}
return cerca(l.rest(),x);}
}
Come si implementa?
• Dobbiamo scegliere delle variabili d’istanza che
permettano di rappresentare sia la lista vuota che
quella non vuota
• Deve essere possibile distinguere i due casi in
modo chiaro
private boolean vuota;
private Integer val;
private IntList next;
//indica se e’ vuota
//contiene il valore
//puntatore al resto
Rappresentazione Lista
val
next
vuota
Lista vuota:
Lista non vuota:
any
any
154
24
any
any
true
false
false
true
Nota
• Il flag vuota serve per indicare la lista vuota
• Nell’implementazione che facciamo quando
vuota e’ falso garantiamo che il puntatore al
resto della lista sia inizializzato (diverso da
null)
• Semplifica l’implementazione dei metodi
ricorsivi (non sono necessari test per vedere
che il puntatore sia definito)
Costruttori
public IntList () {
// EFFECTS: inizializza this alla lista vuota
vuota=true;}
public IntList (Integer x) {
// EFFECTS: inizializza this alla lista che
contiene esattamente x
vuota=false; val=x; next=new IntList();}
Notate che nel secondo costruttore next viene inizializzato alla lista
vuota (sta sempre alla fine, definizione ricorsiva) !
Costruttori
val
next
vuota
Lista vuota:
Lista con un elemento:
any
any
24
any
any
true
false
true
Inserimento
public void addEl (Integer x) {
//MODIFIES:this
// EFFECTS: aggiunge x all’inizio di this
{if (vuota) {val=x;next=new IntList();vuota=false;}
else
{IntList n = new IntList(val);
n.next = this.next; //copia di this
this.val =x;
this.vuota=false;
this.next=n;}
}}
Mettiamo l’elemento in testa,
creando un nuovo nodo che contiene x ed ha come resto
della lista this
First e rest
public Integer first () {
//REQUIRES: this non e’ vuota
// EFFECTS: ritorna il primo elemento di this
return val;}
public IntList rest (){
//REQUIRES: this non e’ vuota
// EFFECTS: ritorna la lista ottenuta da this
//togliendo il primo elemento
return next;}
Size e toString()
public int size () {
// EFFECTS: ritorna il numero di elementi di this
if (vuota) return 0;
return 1 + next.size();
}
public String toString (){
// EFFECTS: ritorna una stringa che
//descrive gli elementi di this
String s=“”;
if (vuota) {return s;}
return val.intValue() + next.toString();
}
Esercizio I
• Definire una variante StringList
• Contiene Stringhe
• Ha un metodo d’istanza per aggiungere all’inizio
ed alla fine, e per rimuovere una stringa data
• Ha un metodo d’istanza per cercare un elemento,
ovvero una stringa data
• La rappresentazione deve essere realizzata da
variabili private
Testing
• Il tipo di dato deve essere testato per verificare il
funzionamento di costruttori e metodi
• Il testing va ovviamente implementato in un
opportuno metodo main
• E’ conveniente dichiarare il metodo main in una
classe separata (in modo da usare la classe che
definisce le liste da un altro modulo)
• Nota: il metodo toString() utile per il testing
• Servirebbero comandi di input-output da tastiera
e/o file
Esercizio 2
• Implementare la seguente classe
• Classe che definisce alcune procedure
statiche per manipolare liste di stringhe
• E’ una classe separata (non si vedono le
variabili d’istanza della classe StringList)
public class IntListProc {
// OVERVIEW: fornisce metodi statici per manipolare
//liste di stringhe
public static String min(StringList l)
{// REQUIRES: l non e’ null e non e’ vuota
//EFFECTS: restituisce il minimo elemento di l}
public
static StringList
append (StringList l1, StringList l2)
{// REQUIRES: l1 ed l2 non null
//EFFECTS: restituisce una lista che e’ la
//concatenazione di l1 ed l2. Ex: l1=[8,0], l2=[9]
===> [8,0,9]}
public
static void
reverse(StringList l1)
{// REQUIRES: l1 non null
//MODIFIES:l1
//EFFECTS:modifica l1 invertendo l’ordine degli elementi}
}
Esercizio II
• Vogliamo una variante di StringList
• Contiene Stringhe, ma ordinate in ordine crescente
• E’ possibile mantenere il tipo di dato ordinato?
• Basta modificare i costruttori ed i metodi
d’istanza?