LSD
Mercoledi'8 maggio 2002

ESERCIZI SU INSIEMI

Si scriva la classe SetTheory che contiene i seguenti metodi:
- public static Set union (Set s1, Set s2) che restituisce l'unione degli insiemi passati per argomento.
- public static Set intersection (Set s1, Set s2) che restituisce l'intersezione degli insiemi passati per argomento.
- public static Set difference (Set s1, Set s2) che restituisce la differenza degli insiemi passati per argomento, cioe' gli elementi di s1 che non sono elementi di s2 .
Scrivere inoltre un semplice programma di verifica per testare i metodi.

Si scriva la classe NextElement contentente il metodo statico next:

import lab2.*;

public class NextElement {
    public static Integer next ( int n, Set s ) {
     // da completare
   }
}

Si assume che tutti gli elementi nell'insieme s siano di tipo Integer: se ciò non è vero, il metodo deve lanciare un'eccezione ClassCastException. Il metodo next restituisce l'oggetto in s il cui valore è il più piccolo tra quelli strettamente maggiori di n, e null se questo non esiste (cioè se tutti gli elementi di s hanno valore minore o uguale a n).
Per testare la classe NextElement, si compili ed esegua la classe TestNextElement. L'output deve essere il seguente:

Provo il metodo NextElement.next(int,Set)...
Next di 5 in { -5 0 1 2 6 7 9 10 11 45}: 6
Insieme dopo next:{ -5 0 1 2 6 7 9 10 11 45}
Next di 15 in { 6 9 11 -5}: null
Insieme dopo next: { 6 9 11 -5}
Next di 48 nell'insieme vuoto : null
invoco next({ 3 56 89 bingo!},2)
Ok: multipli ha lanciato l'eccezione java.lang.ClassCastException

Sia data la seguente interfaccia che estende Set:

import lab2.*;
interface RetSet extends Set{
    /* restituisce un oggetto dell'insieme su cui
     * viene invocato che sia uguale (nel senso di
     * "equals") all'oggetto passato per argomento.
     * Restituisce null se non esiste un tale oggetto.
     */
    Object retrieve (Object o);
}

Si scriva una classe HashRetSet, che eredita da HashSet ed implementa questa interfaccia. Si compili la classe; per testarla si passi al prossimo esercizio.

Si vuole realizzare una rudimentale rubrica telefonica, in cui ad ogni nome è associato al massimo un numero. Si scriva per prima cosa una classe chiamata Entry, avente
- due variabili d'istanza private, nome e numTel di tipo String;
- un costruttore Entry(String name, String tel);
- un costruttore Entry(String name);
- un metodo String getTel() che restituisce il valore di numTel;
- un metodo String getNome() che restituisce il valore di nome;
- un metodo public boolean equals(Object obj) tale che entry.equals(obj) vale true solo se obj è un'istanza della classe Entry e i valori della variabile d'istanza nome di obj ed entry sono equals.
- un metodo public int hashCode() che sovrascrive il corrispondente metodo della classe Object in accordo al nuovo metodo equals.
Si scriva quindi la classe principale Rubrica contenente solo il metodo main. Questo metodo dichiara una variabile rubrica di tipo RetSet (si veda l'esercizio precedente) e le assegna un'istanza della classe HashRetSet. Quindi chiede all'utente un certo numero di nomi e corrispondenti numeri di telefono, crea le corrispondenti istanze di Entry e le inserisce nella rubrica. Infine chiede all'utente alcuni nomi da cercare, e ne stampa il numero di telefono se esiste, o un messaggio opportuno altrimenti.

Altri Esercizi su Liste e Insiemi

[AbsSet] Si scriva la classe AbsSet contentente il metodo statico abs:

import lab2.*;

public class AbsSet {
    public static int abs ( Set s ) {
     // da completare
   }
}

Si assume che tutti gli elementi dell'insieme s siano di tipo Integer: se ciò non è vero, il metodo deve lanciare un'eccezione IllegalArgumentException. Il metodo abs deve modificare l'insieme passato come parametro attuale, sostituendo ogni oggetto con valore negativo con un Integer avente il corrispondente valore assoluto. Il metodo restituisce la somma degli elementi dell'insieme s PRIMA della modifica.
Per testare la classe AbsSet, si compili ed esegua la classe TestAbsSet. L'output deve essere ESATTAMENTE il seguente:

Provo il metodo AbsSet.abs(Set)...
Somma di { -45 -10 -5 -1 0 2 6 7 9 11}: -26
Insieme dopo abs:{ 0 1 2 5 6 7 9 10 11 45}
Somma di { 5 6 9 11}: 31
Insieme dopo abs: { 5 6 9 11}
Insieme vuoto. Somma: 0
Invoco abs({ 3 56 89 bingo!})
Ok: togliMultipli ha lanciato una IllegalArgumentException

[SortedUnion] Si scriva la classe SortedUnion, contenente il metodo statico merge:

import lab2.*;

public class SortedUnion {
    public static List merge ( Queue q, Stack s) {
     // da completare
   }
}

Si assuma che la coda q e la pila s contengano solo istanze di Integer (quindi che implementano l'interfaccia Comparable). Il metodo merge, senza modificare né la coda q né la pila s passate per argomento, deve restituire una lista che contiene tutti gli oggetti che compaiono in q o in s, senza ripetizioni ed in ordine crescente. Il metodo deve lanciare una IllegalArgumentException se uno dei due parametri è null.
Suggerimento: per ottenere in modo automatico l'ordinamento degli oggetti, si utilizzi una istanza di TreeSetcome contenitore ausiliario.

Per testare il metodo, si esegua la classe TestSortedUnion.class. e si corregga il programma finché l'output non sia esattamente il seguente:

Provo il metodo ' SortedUnion.merge(Queue,Stack)'...
OK: il metodo mi sembra corretto.

[Implementazione di Set con Array]
Si scriva la classe ArraySet che implementa l'interfaccia Set usando un array in modo naif (senza l'uso di una funzione hash). Ad ogni istante, un segmento iniziale dell'array (determinato dal valore di una variabile d'istanza) è occupato, o con elementi dell'insieme o con elementi marcati per cancellazione.
Il metodo add scandisce la parte occupata dell'array per vedere se l'elemento è già presente, ed in caso contrario lo inserisce nella prima posizione libera dell'array. remove non cancella effettivamente l'elemento dall'insieme, ma lo marca come cancellato. Gli elementi marcati vengono effettivamente eliminati (e l'array ricompattato) quando si esegue una add ma l'array è pieno.
Se si invoca una add quando l'array è pieno e non ci sono elementi marcati per cancellazione, allora si raddoppia la dimensione dell'array (come in ArrayStack.java).
L'iteratore scandisce gli elementi dell'insieme nell'ordine in cui compaiono nell'array.

Il numero ed il tipo di variabili d'istanza della classe ArraySet sono a discrezione dello studente. L'unico vincolo è che la classe realizzi tutti i metodi dell'interfaccia Set secondo le indicazioni date.

[NextElement] Si scriva la classe NextElement contentente il metodo statico next:

import lab2.*;

public class NextElement {
    public static Integer next ( int n, Set s ) {
     // da completare
   }
}

Si assume che tutti gli elementi nell'insieme s siano di tipo Integer: se ciò non è vero, il metodo deve lanciare un'eccezione ClassCastException. Il metodo next restituisce l'oggetto in s il cui valore è il piu' piccolo tra quelli strettamente maggiori di n, e nullse questo non esiste (cioè se tutti gli elementi di s hanno valore minore o uguale a n).
Per testare la classe NextElement, si compili ed esegua la classe TestNextElement. L'output deve essere il seguente: