Avvertenze     Le soluzioni devono essere scritte in modo chiaro e ordinato. Il codice deve essere indentato per facilitarne la lettura. Si possono consultare libri e appunti ma non è permesso usare computer. Ogni esercizio o parte di esercizio ha un punteggio massimo. Il voto (in trentesimi) sarà determinato dalla somma dei punteggi ottenuti nei vari esercizi.

[Seq]   Consideriamo sequenze di valori rappresentate dalla seguente interfaccia generica:

public interface Seq<V> {
         //Ritorna l'i-esimo valore della sequenza,
    V get(int i);    //la numerazione inizia da 0
    int length();    //Ritorna la lunghezza della sequenza
}

Ad esempio, una classe che rappresenta sequenze di interi potrebbe chiamarsi IntSeq e implementare Seq<Integer>. Vogliamo definire una classe che gestisce un insieme di sequenze ordinato lessicograficamente. In questo ordinamento, (v₀,...,v_n) < (u₀,...,u_m) se o n < m e v₀ = u₀,...,v_n = u_n o esiste i ≤ n, m tale che v₀ = u₀,...,v_{i − 1} = u_{i − 1} e v_i < u_i. Due sequenze sono uguali se hanno la stessa lunghezza e in ogni posizione hanno valori uguali (secondo il metodo equals del tipo V). Si tenga presente che il metodo equals di un oggetto di tipo Seq<V> non implementa questa relazione di uguaglianza.

1. (max 16 punti)  Definire una classe SeqSet con parametro di tipo V per gestire un insieme di sequenze (di tipo Seq<V>) ordinato lessicograficamente. Per determinare l'ordinamento la definizione deve richiedere che il tipo V implementi l'interfaccia Comparable relativamente al tipo V o a un suo supertipo. La classe deve realizzare le seguenti funzionalità.
   • Due costruttori, uno senza argomenti che costruisce l'insieme vuoto e uno che prende una Collection, con parametro di tipo il più generale possibile, e costruisce l'insieme con gli elementi (distinti) della collezione.
   • Metodi add, contains e remove che ritornano un booleano, prendono in input una sequenza e si comportano come gli omonimi metodi di Set.
   • Un metodo ceiling che prende in input una sequenza s e ritorna la sequenza nell'insieme che nell'ordinamento lessicografico è la minima tra quelle maggiori od uguali a s. Se una tale sequenza non c'è, ritorna null.
   • Implementa l'interfaccia Iterable per iterare sulle sequenze dell'insieme in ordine lessicografico ascendente.
   Tutti i metodi e costruttori lanciano NullPointerException se il parametro di input è null.


2. (max 16 punti)  Definire una sottoclasse SubSeqSet di SeqSet che gestisce insiemi di sequenze che sono sottosequenze di una sequenza base, fornita al momento della costruzione. Si ricorda che s₁ è una sottosequenza di s₂ se s₁ si può ottenere eliminando da s₂ zero o più elementi. Ad es. (2,2,1) e (1,3,4,2) sono sottosequenze di (1,2,3,4,3,2,1), ma (2,2,3) non lo è. La classe SubSeqSet deve realizzare le seguenti funzionalità.
   • Due costruttori, uno prende in input solo la sequenza di base e costruisce l'insieme vuoto, l'altro oltre alla sequenza di base prende una Collection (come il costruttore di SeqSet) e costruisce l'insieme con le sequenze (distinte) della collezione che sono sottosequenze della sequenza di base.
   • Ridefinisce il metodo add per impedire che si possano aggiungere sequenze che non siano sottosequenze della sequenza di base.
   • Un metodo count che ritorna una mappa (di tipo Map), con chiavi di tipo V, che ad ogni valore presente nella sequenza di base associa il numero di sequenze dell'insieme che contengono tale valore.

[Errori] (max 8 punti)   Il seguente codice Java contiene uno o più errori. Trovare gli errori, spiegarli e dire per ognuno se si verifica in compilazione o in esecuzione.

 1 import java.util.*;
 2 
 3 public class Test {
 4     public static <E> E[] copyifnull(List<? extends E> list, E[] a) {
 5         int i = 0;
 6         for (E x : list)
 7             if (a[i] == null)
 8                 a[i++] = x;
 9         return a;
10     }
11     public static void main(String[] args) {
12         List<Integer> iL = new ArrayList<Integer>();
13         iL.add(5);
14         List<? extends Integer> eL = iL;
15         Object[] objA = new Object[10];
16         copyifnull(eL, objA);
17         int val = eL.get(0);
18         objA = new String[50];
19         copyifnull(eL, objA);
20         eL.add(new Integer(7));
21         List<?> list = iL;          
22         Object o = list.get(0);
23         val = (int)o;
24         val = list.get(0);
25         objA = copyifnull(list, new Object[10]);   
26     }
27 }