| Parte
I |
HOW TO |
|
| Comprendere gli Avvisi del
compilatore |
Il compilatore talvolta produce
dei messaggi detti warnings
(avvisi). Si scarichino, ad esempio, la classe RawComparableContainer.java e l'interfaccia Container.java. Si compili la classe: $javac RawComparableContainer.java Note: RawComparableContainer.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. Non sono errori di compilazione! Sono solo segnalazioni (avvisi). Infatti il compilatore ha prodotto il bytecode RawComparableContainer.class. Approfondiamo le cause di questo comportamento. Il compilatore segnala di ricompilare con l'opzione -Xlint, facciamolo: $javac RawComparableContainer.java -Xlint RawComparableContainer.java:132: warning: [unchecked] unchecked call to compareTo(T) as a member of the raw type java.lang.Comparable if (b[ib].compareTo(c[ic]) < 0) ^ 1 warning Il compilatore ci avvisa che le variabili riferimento b[ib] e c[ic] potrebbero non appartenere alla stessa classe. Il compilatore sa, infatti, che entrambi sono di tipo Comparable, ma non sa se appartengono alla medesima classe. Ad esempio, entrambe le classi java.lang.String e java.lang.Integer realizzano l'interfaccia java.lang.Comparable. Se, per errore del programmatore, il metodo compareTo() viene invocato con due parametri (implicito e esplicito) di classi diverse, generera' l'eccezione java.lang.ClassCastException. |
|
| Correggere gli errori logici |
Il compilatore segnala gli
errori sintattici e un piccolo insieme di errori semantici (ovvero
logici). Per trovare gli errori semantici non segnalati dal compilatore i programmatori si avvalgono di programmi appositi, detti "debugger", che permettono di: - ispezionare il valore delle variabili; - eseguire il codice passo dopo passo, ovvero eseguire un enunciato e poi interrompere l'esecuzione; - marcare uno o piu' enunciati con punti di arresto (breakpoints); il programma si arresta prima dell'esecuzione dell'enunciato marcato con punto di arresto in modo che il programmatore possa verificare il valore delle variabili. Il comando jdb avvia il debugger del Sun jdk. In Bluj, nel menu' tools il comando Set/Clear Breakpoint serve per introdurre/cancellare un punto di arresto. Se siete curiosi provate. In questo corso non approfondiremo l'uso di debugger. Per correggere gli errori logici abbiamo, allora, a disposizione un solo modo: far stampare al codice dei messaggi a standard output in sezioni critiche del codice, per verificare il valore delle variabili. Impariamo a inserire nei metodi critici delle stampe per documentare l'evoluzione del programma. Ad esempio nel metodo add() di un contenitore, dopo aver aggiunto un oggetto obj inseriamo gli enunciati: // Stampe di debugging System.out.println("add(): inserito l'oggetto " + obj); System.out.println("Oggetti contenuti: ") for (int i = 0; i < size; i++) System.out.println(i + " " + a[i]); // dove a e' l'array contenente gli oggetti Il primo enunciato documenta l'inserimento appena effettuato, il secondo documenta lo stato dell'array a dopo l'ultimo inserimento. Le stampe vanno commentate nella versione finale del software: /* // Stampe di debugging System.out.println("add(): inserito l'oggetto" + obj); System.out.println("Oggetti contenuti: ") for (int i = 0; i < size; i++) System.out.println(i + " " + a[i]); // dove a e' l'array contenente gli oggetti */ Questo ci aiuta a identificare il comportamento dei metodi. |
| Parte
II |
Linguaggio
Java: classi,
ordinamento, ricerca di oggetti specifici |
La
mia soluzione |
| Ordinare Stringhe |
L'interfaccia Container.java definisce in astratto un
contenitore. Codificare la classe TextContainer, che realizza l'interfaccia Container, la cui interfaccia pubblica è documentata in TextContainer.html. La classe, che e' in grado di memorizzare le parole di un testo (contenitore di testo), realizzi il metodo void sort() per ordinare le parole in senso lessicografico crescente. Il metodo sia ottimizzato per l'ordinamento di un numero elevato di parole. Si scriva poi la classe TextContainerTester che: - definisce un esemplare della classe TextContainer e lo inizializzi con parole acquisite da standard input. Una parola sia una stringa delimitata dai caratteri delimitatori whitespaces e/o dai seguenti caratteri d'interpunzione: .,;:-!?(); - ordina gli elementi del contenitore in senso lessicografico; - elimina le parole eventualmente ripetute. Si noti che nel contenitore ordinato le parole ripetute sono vicine. Per eliminare le ripetizioni, si crei un nuovo contenitore dove inserire solo le parole senza ripetizione (prima di inserire verificare che la parola non sia uguale all'ultima inserita). - stampa a standard output le parole del testo nell'ordine in cui compaiono nel testo originale, precedute da una stampa del numero di parole. Esempio: *** STAMPA DELLE PAROLE IN ORDINE DI ACQUISIZIONE *** Numero delle parole nel testo originale: 3 >>> rosso >>> verde >>> rosso - stampa a standard output le parole del testo ordinate in senso lessicografico crescente, precedute da una stampa del numero di parole. Esempio: *** STAMPA DELLE PAROLE IN ORDINE LESSICOGRAFICO *** Numero delle parole nel testo ordinato: 3 >>> rosso >>> rosso >>> verde - stampa a standard output le parole del testo ordinate in senso lessicografico crescente, senza ripetizioni, precedute da una stampa del numero di parole. Esempio: *** STAMPA DELLE SINGOLE OCCORRENZE IN ORDINE LESSICOGRAFICO *** Numero delle parole non ripetute: 2 >>> rosso >>> verde Provare la classe acquisendo i dati dal file alberi.txt, mediante redirezione dello standard input. Esempio di uso: $java TextTester < nomeInputFile NOTA: per estrarre elementi dal contenitore e' disponibile solo il metodo removeLast() che ha due particolarita': - rimuove l'ultimo elemento del contenitore - estrae l'elemento dal contenitore Per estrarre gli elementi da un contenitore text senza perdere l'informazione contenuta bisogna programmare come segue: ... TextContainer inverseText = new TextContainer(); while (!text.isEmpty()) { String word = text.removeLast(); inverseText.add(word); // ... elaborazione di word } ... Il contenitore inverseText contiene ora tutte le parole contenute precedentemente nel contenitore text, ma nell'ordine inverso. l L'invocazione inverseText.removeLast() restituisce l'ultima parola del contenitore inverseText, che e' anche la prima parola precedentemente contenuta nel contenitore text. |
TextContainer.java TextContainerTester.java |
| Ordinare studenti |
Si consideri la
classe Studente.java fornita dal docente. Si scriva la classe StudentSortedContainer, che realizza l'interfaccia Container, per memorizzare oggetti di classe Studente. L'interfaccia pubblica della classe è specificata in StudentSortedContainer.html. I metodi add() devono inserire gli elementi nel contenitore ordinatamente secondo l'ordine naturale inverso della classe Studente (in ordine decrescente di matricola). Attenzione che il metodo add(String studenteString) genera l'eccezione java.util.NoSuchElementException se il parametro esplicito non e' nel formato corretto (nomexmatricola, dove x e' un carattere delimitatore). Si renda eseguibile la classe, programmando il metodo main() in modo che legga da standard input i dati di un insieme di studenti, uno per riga (formato "nome:matricola") e inserisca gli studenti in un contenitore di classe SortedStudentContainer. Le righe che iniziano con il carattere '*' sono da considerarsi righe di commento. Se una riga non ha il formato corretto, si eviti di inserire lo studente nel contenitore e si mandi un messaggio a standard output del tipo: Errore alla riga n. 9 >>> "testo della riga col formato errato" Per realizzare tale funzionalita', catturare l'eccezione java.util.NoSuchElementException lanciata dal metodo add(String studenteString) in caso di formato non corretto della stringa studenteString. Si invii, successivamente, gli elementi del contenitore in ordine crescente a standard output. Si provi la classe usando il file studenti.txt mediante redirezione dello standard input. Esempio di uso: $java StudentSortedContainer < studenti.txt Nota: se compilate la soluzione del docente, noterete che il compilatore non genera avvisi del tipo Note: ComparableContainer.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. Il motivo della mancanza degli avvisi e' che la classe Studente.java usa l'interfaccia parametrica java.lang.Comparable<Studente> e non l'interfaccia semplice java.lang.Comparable. |
StudentSortedContainer.java |
| Parte
III |
Linguaggio
Java: ordinamento di oggetti generici comparabili |
La mia soluzione |
| Ordinare generici
oggetti
comparabili |
Si scriva la classe SortedContainer che
realizza l'interfaccia Container. La classe e' un contenitore generico in cui possono essere inseriti oggetti comparabili qualsiasi (la cui classe realizza l'interfaccia Comparable): ad esempio, esemplari di classe java.lang.String, java.lang.Integer o di classe Studente. L'interfaccia pubblica della classe e' riportata in SortedContainer.html. Si scriva una classe di prova SortedContainerTester1.java che - legge da standard input i dati di un insieme di studenti (uno per riga nel formato "nome:matricola"). Se la riga inizia con il carattere '*' considerarla come una riga di commento - costruisce degli oggetti di classe Studente e li inserisce in un contenitore di classe SortedContainer - invia successivamente a standard output gli elementi contenuti nell'archivio in ordine decrescente. Per eseguire la funzione richiesta, si usi il metodo togliMax() che estrae dal contenitore l'elemento massimo (nel senso dell'ordinamento naturale della classe Studente). Attenzione: il metodo togliMax ritorna un generico oggetto di classe Object! Nota Bene: Per memorizzare il riferimento restituito dal metodo removeMax() si puo' usare un riferimento di classe Studente con un forzamento esplicito: Studente s = (Studente)archivio.removeMax(); Senza il forzamento esplicito, si deve usare un riferimento di classe Object: Object obj = archivio.removeMax(); Sul riferimento di classe s possiamo successivamente invocare i metodi della classe Studente, ad esempio: int matr = s.matricola(); mentre il compilatore segnala errore se lo facciamo sul riferimento di classe Object perche' nella classe Object non e' definito il metodo matricola(): int matr = obj.matricola(); // ERRORE Per la semantica del polimorfismo, funzionano correttamente invece i seguenti due enunciati: System.out.println(s); System.out.println(obj); Uso: $java SortedContainer < inputFile Come file di input si usi il file studenti.txt, mediante redirezione dello standard input. Si codifichi, successivamente, la classe SortedContainerTester2.java che - legge da standard input le parole di un testo da standard input e le inserisce in un contenitore di classe SortedContainer. - invia successivamente a standard output gli elementi contenuti nell'archivio in ordine decrescente. Si provi con il file animali.txt. |
SortedContainer.java SortedContainerTester1.java SortedContainerTester2.java |
| Ordinare generici oggetti comparabili | Si scriva la classe SortableContainer che
realizza l'interfaccia Container. Come la precedente, la classe e' un contenitore generico in cui possono essere inseriti oggetti che realizano l'interfaccia Comparable. L'interfaccia pubblica della classe e' riportata in SortableContainer.html. La differenza rispetto al contenitore precedente e' che ora gli elementi non sono mantenuti ordinati nel contenitore, ma possono essere ordinati. La classe realizza il metodo pubblico sort() per ordinare gli elementi comparabili contenuti nel contenitore. Per ordinare si usi l'algoritmo per fusione, programmandolo nella classe ArrayAlgorithms. Si scriva la classe di prova SortableContainerTester.java che - legge da standard input i dati di un insieme di studenti (uno per riga nel formato "nome:matricola") - costruisce degli oggetti di classe Studente e li inserisce in un contenitire di classe SortableContainer - invia successivamente a standard output l'elenco degli elementi contenuti nell'archivio due volte, la prima volta senza ordinamento, la seconda volta dopo aver ordinato l'archivio. Esempio usando i dati contenuti nel file studenti.txt: *** ELENCO NON ORDINATO DI STUDENTI *** 56971:Giovanni Sette 56816:Franca Sei 56985:Dario Quattro 56993:Carlo Tre 56789:Bice Due 56799:Antonio Uno *** ELENCO ORDINATO DI STUDENTI *** 56993:Carlo Tre 56985:Dario Quattro 56971:Giovanni Sette 56816:Franca Sei 56799:Antonio Uno 56789:Bice Due Uso: $ java SortableContainerTester < inputFile Come file di input si usi il file studenti.txt, mediante reindirezione dello standard input. |
SortableContainer.java SortableContainerTester.java |
| Ordinare oggetti confrontabili |
Ecco un'altra versione delle
classi dell'esercizio precedente: ContenitoreOrdinato.java
e ContenitoreOrdinabile.java. Le classi, fornite dal docente, si differenziano da quelle dell'esercizio precedente perche' sono definite per memorizzare generici oggetti di classe java.lang.Object. Naturalmente, per poter essere ordinati, gli oggetti inseriti nel contenitore devono essere di una classe che realizza l'interfaccia java.lang.Comparable. 1. Provare a compilare ed eseguire le seguenti classi di prova, fornite dal docente, che memorizzano oggetti di classe MyComplex (che non realizza l'interfaccia java.lang.Comparable): - ProvaContenitoreOrdinato1.java: usa la classe SortedContainer per memorizzare numeri complessi - ProvaContenitoreOrdinato2.java: usa la classe ContenitoreOrdinato per memorizzare numeri complessi - ProvaContenitoreOrdinabile1.java: usa la classe SortedContainer per memorizzare numeri complessi - ProvaContenitoreOrdinabile2.java: usa la classe ContenitoreOrdinabile per memorizzare numeri complessi - ProvaContenitoreOrdinabile3.java: usa la classe ContenitoreOrdinabile per memorizzare e ordinare numeri complessi Uso: $ java ProvaContenitoreOrdinato1 < complex.txt 2. Rispondere alle seguenti domande: 2.1/ Perche' il compilatore segnala errore nelle classi ProvaContenitoreOrdinato1 e ProvaContenitoreOrdinabile1 e non nelle altre classi? 2.2/ Perche' in esecuzione ProvaContenitoreOrdinato2 e ProvaContenitoreOrdinabile3 provocano l'eccezione java.lang.ClassCastException? 2.3/ Perche' la classe ProvaContenitoreOrdinabile2 viene eseguita senza lanciare l'eccezione java.lang.ClassCastException? |
| Parte IV |
Linguaggio
Java: ordinamento di oggetti generici comparabili |
La mia soluzione |
| Ordinare oggetti
comparabili. Criteri di ordinamento multipli. Definire Eccezioni. |
Realizzare la classe
Item.java
che rappresenta un prodotto commerciale secondo l'interfaccia pubblica Item.html. I campi che denotano un prodotto commerciale siano: - nome - codice - prezzo - data di scadenza. La classe realizza l'interfaccia parametrica java.lang.Comparable<Item> e permette di ordinare gli oggetti della classe alternativamente, per nome, codice, prezzo o data di scadenza. Si definisca, inoltre, l'eccezione IllegalSortCriterionException.java, che viene lanciata dal metodo sortBy() della classe Item quando viene selezionato un criterio di ordinamento non valido. Scrivere successivamente una classe di prova ItemTester.java che: - legge da standard input i dati di un insieme di prodotti. A ciascun prodotto sia riservata nel file una riga con il seguente formato: nome codice prezzo data_scadenza. Le righe che iniziano col carattere '*' siano considerate come righe di commento. - inserisce i prodotti in oggetti di classe SortableContainer.java (definita in un esercizio precedente) - ordina contenitori, per nome, codice, prezzo e data di sacdenza. - stampa a standard output la sequenza originale dei prodotti, i prodotti ordinati per nome, per codice, per prezzo e per data di scadenza. Provare con il file di input prodotti.txt, mediante reindirezione dello standard input. $java ItemTester < prodotti.txt Esempio di risultato: *** LISTA ORIGINALE DEI PRODOTTI *** latte : AB12 : 1.3 EURO scadenza 20061125 uova : CD11 : 0.9 EURO scadenza 20061129 arance : DA23 : 2.3 EURO scadenza 20061201 tonno : GE14 : 3.45 EURO scadenza 20061225 maionese : GH87 : 2.5 EURO scadenza 20070112 *** LISTA DEI PRODOTTI IN ORDINE DI NOME *** arance : DA23 : 2.3 EURO scadenza 20061201 latte : AB12 : 1.3 EURO scadenza 20061125 maionese : GH87 : 2.5 EURO scadenza 20070112 tonno : GE14 : 3.45 EURO scadenza 20061225 uova : CD11 : 0.9 EURO scadenza 20061129 *** LISTA DEI PRODOTTI IN ORDINE DI CODICE *** AB12 : latte : 1.3 EURO scadenza 20061125 CD11 : uova : 0.9 EURO scadenza 20061129 DA23 : arance : 2.3 EURO scadenza 20061201 GE14 : tonno : 3.45 EURO scadenza 20061225 GH87 : maionese : 2.5 EURO scadenza 20070112 *** LISTA DEI PRODOTTI IN ORDINE DI PREZZO *** 0.9 EURO : uova : CD11 scadenza 20061129 1.3 EURO : latte : AB12 scadenza 20061125 2.3 EURO : arance : DA23 scadenza 20061201 2.5 EURO : maionese : GH87 scadenza 20070112 3.45 EURO : tonno : GE14 scadenza 20061225 *** LISTA DEI PRODOTTI IN ORDINE DI DATA DI SCADENZA *** scadenza 20061125 : latte : AB12 : 1.3 EURO scadenza 20061129 : uova : CD11 : 0.9 EURO scadenza 20061201 : arance : DA23 : 2.3 EURO scadenza 20061225 : tonno : GE14 : 3.45 EURO scadenza 20070112 : maionese : GH87 : 2.5 EURO |
Item.java ItemTester.java IllegalSortCriterionException.java |
| Creare classi che realizzano l'interfaccia
Comparable. Usare l'ereditarieta'. |
I
poligoni convessi del piano sono caratterizzati dall'avere una misura
del
perimetro e dell'area. Questa proprieta' astratta e' descritta dalla
seguente
interfaccia Polygon.java. Nota: un'interfaccia puo' estendere un'altra interfaccia, come nel caso di Polygon che estende java.lang.Comparable. Le classi che realizzano l'interfaccia Polygon devono realizzare i metodi definiti in entrambe le interfacce, quindi area(), perimetro() e compareTo(). Gli oggetti di interfaccia poligono sono comparabili fra loro. Il criterio di comparazione sia la misura dell'area. Usando la seguente classe immutabile MyPoint2D.java, fornita dal docente, che rappresenta un punto nel piano, realizzare le seguenti classi: - MyPolygon che realizza l'interfaccia Polygon. La classe e' astratta perche' definisce ma non codificare il metodo area(). - MyTriangle che estende MyPolygon (rappresenta un triangolo) - MyTetragon che estende MyPolygon (rappresenta un quadrilatero) - MyRectangle che estende MyTetragon (rappresenta un rettangolo) - MySquare che estende MyRectangle (rappresenta un quadrato). Le interfacce pubbliche delle classi sono: MyPolygon.html, MyTriangle.html, MyTetragon.html, MyRectangle.html e MySquare.html. Si scriva poi una classe PolygonTester.java che: - legga dal file poligoni.txt, mediante redirezione dello standard input, un insieme di poligoni, uno per riga; a ciascun poligono sia riservata una riga nel file. Nella riga siano riportati i vertici del poligono nel formato (x y). - memorizzi i poligoni in un contenitre di classeSortedContainer del tipo realizzato nel primo esercizio - stampi alla fine a standard output l'elenco ordinato dei poligoni. Uso: $ java PolygonTester < inputfile |
MyPolygon.java MyTriangle.java MyTetragon.java MyRectangle.java MySquare.java PolygonTester.java |
| Parte V | Linguaggio
java e algoritmi di ordinamento |
Una soluzione possibile |
| Ordinamento |
Si scriva un programma che - legga da standard input una sequenza (di dimensione non predeterminata) di numeri interi, un numero per riga, senza alcun requisito di ordinamento (cioè, in generale, in ordine casuale); - visualizza i numeri sullo standard output dopo aver eliminato eventuali valori duplicati (o, in generale, replicati più volte), lasciando quindi un solo esemplare di ciascun numero presente nella sequenza originale; al termine, i numeri potranno trovarsi in un ordine diverso da quello iniziale (non è richiesto che siano ordinati). Risolvere il problema in due modi 1. effettuando prima un ordinamento dell'insieme dei dati con l'algoritmo mergesort (avente efficienza O(n lg n)), mettendo poi a punto e realizzando un algoritmo per l'eliminazione degli elementi replicati in un array ordinato con prestazioni asintotiche medie e di caso peggiore di tipo O(n)2. senza effettuare alcun ordinamento dell'insieme dei dati, mettendo a punto e realizzando un algoritmo con prestazioni asintotiche medie e di caso peggiore di tipo O(n2). Per la soluzione del problema dell'eliminazione dei duplicati, NON utilizzare array aggiuntivi oltre a quello in cui sono memorizzati i dati stessi (si possono usare altri array per la sola fase di ordinamento del punto 1. |
provate da soli |