Liste Ordinate 3 Maggio 2005. Ultima Lezione Abbiamo visto i tipi di dato astratti IntList e...
-
Upload
giuseppe-gasparini -
Category
Documents
-
view
216 -
download
2
Transcript of Liste Ordinate 3 Maggio 2005. Ultima Lezione Abbiamo visto i tipi di dato astratti IntList e...
Liste Ordinate
3 Maggio 2005
Ultima Lezione
• Abbiamo visto i tipi di dato astratti IntList e StringList
• Realizzano liste di interi e di stringhe• Realizzati mediante Liste Concatenate• Non sarebbe meglio avere un tipo di datoOList piu’ generale che possa essere
istanziato per un dato tipo?
OList
• Vorremmo potere definire liste di tipo generico parametriche rispetto al tipo degli elementi
• Che possano essere istanziate con vari tipi
• Si chiama polimorfismo (astrarre dal tipo)
Esempio
• Un tipo di dato primitivo polimorfo: l’array
int[] a=new int[10]• Al momento della creazione scegliamo il tipo
degli elementi• Possiamo creare arrays per ogni tipo
Da non confondere con Vector
• Vector memorizza generici sottotipi di Object
• Ma non e’ polimorfo• Quando lo creiamo non istanziamo il tipo
Vector a=new Vector()• Non vi e’ alcuna garanzia che a sia
omogeneo
Tornando alle Liste
• Per realizzare una lista generica potrei dire che ha elementi Object
• E’ facile modificare la specifica e l’implementazione che abbiamo visto
• Non sarebbe garantita l’omogeneita’, ovvero non sarebbe possibile istanziare la lista con un dato tipo
• Sarebbe tipo Vector
In Java
• Non esistono meccanismi diretti per fare il polimorfismo
• Si puo’ ottenere usando varie tecniche• Oggi ne vedremo una che e’ basata sull’idea di
usare l’ereditarieta’ ovvero i sottotipi per realizzare una lista polimorfa
• In particolare vedremo come le interfacce possano essere usate per realizzare una forma di polimorfismo
Per cominciare a capire
• Supponiamo di volere realizzare una lista polimorfa
• In cui gli elementi sono ordinati in ordine crescente
• Deve essere parametrica sia nel tipo degli elementi che nel relativo ordinamento
• Per esempio: se istanziata con stringhe l’ordinamento sara’ quello lessicografico etc..
Interfaccia Comparable (è definito in java.util)
–Ha un solo metodo compareTo che serve per realizzare confronti
–Tutti i sottotipi implementano il metodo compareTo
–Fornisce un supertipo i cui sottotipi hanno tutti un metodo per
il confronto (relazione di ordinamento totale)
L’interfaccia Comparable
public interface Comparable {
// OVERVIEW: i sottotipi di Comparable forniscono un metodo
// per determinare la relazione di ordinamento fra i loro
// oggetti; l’ordinamento deve essere totale e, ovviamente,
// transitivo e simmetrico; infine
// x. compareTo (y) == 0 implica x. equals (y)
public int compareTo (Object x) throws ClassCastException, NullPointerException;
// EFFECTS: se x è null, lancia NullPointerException;
// se this e x non sono confrontabili, solleva ClassCastException;
// altrimenti, se this è minore di x ritorna -1;
// se this = x ritorna 0; se this è maggiore di x, ritorna 1
}
Nota
• Il metodo compareTo realizza l’ordinamento
• Se chiamato su oggetti che non sono omogenei (tipo String ed Integer) allora solleva ClassCastException
Uso di Comparable
• Facciamo una lista ordinata generica ed omogenea usando Comparable
• Gli elementi della lista sono di tipo Comparable (invece che Integer o String etc…)
• Il confronto e’ fatto in modo generico usando compareTo
• Questo permette di usare la lista per memorizzare
qualsiasi sottotipo di Comparable
Cosa cambia nella Specifica?
• Bisogna indicare che gli elementi sono Comparable
– argomenti e risultati sono Comparable invece che int
– bisogna indicare che gli elementi sono ordinati rispetto a compareTo
• OrderedList assicura che gli elementi della lista siano omogenei – Si sfutta il fatto che compareTo solleva un’eccezione se gli oggetti
non sono confrontabili
• il tipo degli elementi nella lista è determinato dall’inserimento del primo elemento – se la lista diventa vuota il tipo può cambiare con l’aggiunta di un
nuovo elemento
Specifica di OrderedList
public class OrderedList {
// OVERVIEW: `e una lista modificabile ordinata di oggetti omogenei di tipo Comparable
// Oggetto tipico [x1, . . . , xn] con xi < xj se i < j
// Il confronto fra gli elementi è effettuato con il loro metodo compareTo
• Nota: xi < xj significa rispetto a compareTo
Costruttori e Metodi
public OrderedList ( ) {
// EFFECTS: inizializza this alla lista ordinata vuota}
public void addEl (Comparable el) throws NullPointerException,
DuplicateException, ClassCastException {// MODIFIES: this
// EFFECTS: se el è in this, solleva DuplicateException; se el è null solleva NuIlPointerException; se el non è confrontabile con gli altri elementi in this solleva ClassCastException; altrimenti, aggiunge el a this}
Nota: in questo caso aggiunge vuol dire che lo aggiunge in base all’ordinamento
Specifica di IntList
public Comparable first () throws EmptyException{
// EFFECTS: se this è vuoto solleva EmptyException, altrimenti
// ritorna il primo elemento di this}
public OrderedList rest () throws EmptyException{
// EFFECTS: se this è vuoto solleva EmptyException, altrimenti
// ritorna la lista ottenuta da this togliendo il primo elemento}
Altri Metodi
public int size () { // EFFECTS: ritorna il numero di elementi di this
}
public String toString (){\\EFFECTS: standard}
}
Testing
• Il tipo di dato e’ fatto per memorizzare valori di tipi diversi sottotipi di Comparable
• String, Integer sottotipi di Comparable
• Fare Testing (scegliendo p.e. Integer)
• Attenzione ai metodi che restituiscono Comparable (bisogna fare cast())
Cosa bisogna testare
• Tutti i metodi soprattutto addEl (per verificare che faccia l’ordinamento giusto)
• Provare mettendo dei valori a caso
• Provare mettendo due volte lo stesso valore (deve sollevare DuplicateException)
• Provare mettendo valori di tipo diverso (deve sollevare ClassCastException)
Esempiopublic static void main(String[] args) {
OrderedList l=new OrderedList();System.out.println(l.toString()); //test lista vuotal.addEl("b");l.addEl("a");l.addEl("ac");System.out.println(l.toString()); //test lista ordinatatry{l.addEl("a"); }catch (DuplicateException e) {System.out.println("hai inserito un duplicato");} //test duplicato
try{l.addEl(new Integer (1)); }catch (ClassCastException e){ System.out.println("non omogeneo");} //test del cast
OrderedList p=new OrderedList(); p.addEl(new Integer (1));System.out.println(p.toString()); //test lista Integerp.addEl(new Integer (6));p.addEl(new Integer (3));System.out.println(p.toString()); //test lista Integer
}}
OrderedList
public class OrderedList{
private boolean vuota;private Comparable val;private OrderedList next;
public OrderedList(){vuota=true;}
public void addEl (Comparable el) throwsNullPointerException, NullPointerException,ClassCastException {if (el==null) throw newNullPointerException("OrderedList.addEl");if (vuota) {vuota=false; val=el;next=new OrderedList();}else{ int comp=el.compareTo(val); if (comp==0) throw newNullPointerException("OrderedList.addEl"); if (comp > 0) next.addEl(el); else {OrderedList n=new OrderedList(); n.val=this.val; n.vuota=false;n.next=this.next; this.val=el; this.next=n;}}}
public Comparable first () throws NullPointerException{if (vuota) throw newNullPointerException("OrderedList.addEl");return val;
}
public OrderedList rest () throws NullPointerException{if (vuota) throw newNullPointerException("OrderedList.addEl");return next;
}
public int size () { if (vuota) {return 0;} return 1+ next.size();}
public String toString() { if (vuota) {return "VUOTA";} return this.val+ next.toString();}
Procedura Stand-Alonepublic class Proc { public static void removeall(OrderedList l,Comparable c) {\\REQUIRES: l e c non sono null
\\MODIFIES: l\\EFFECTS: rimuove da l tutti i valori maggiori di c}