Fondamenti di Informatica 1 - gr. 89
                    Prova di Programmazione del 1.09.2008
                              a.a. 2007 - 2008


Dizionario
==========
L'interfaccia Map definisce un dizionario, ovvero un contenitore di coppie
chiave/attributo, dove la chiave e' univoca (non possono essere presenti nel
contenitore due coppie con la medesima chiave).

public interface Map  // --Dizionario
{
  boolean isEmpty();
  int size();
  void insert(Comparable key, Object x);
  Object find(Comparable key);
  void remove(Comparable key);
}

dove:
- boolean isEmpty() restituisce true se il contenitore e' vuoto, false
  altrimenti;
- int size() restituisce il numero di coppie presenti nel contenitore;
- void insert(Comparable key, Object x) se la chiave key non e' presente nel
  contenitore  vi inserisce la coppia key/x, altrimenti sovrascrive la coppia
  di chiave key;
- Object find(Comparable key): se la chiave key e' presente nel contenitore
  restituisce l'attributo associato, altrimenti lancia l'eccezione
  java.util.NoSuchElementException;
- void remove(Comparable key): se la chiave key e' presente nel contenitore
  rimuove la coppia key/x, altrimenti lancia l'eccezione
  java.util.NoSuchElementException;

La seguente classe MyMap realizza l'interfaccia Map:

public class MyMap implements Map // --Dizionario
{ 
  // parte privata
  ...
  // parte pubblica
  public MyMap() {...}
  public String[] toStringArray() {...}
}

dove:
- il costruttore inizializza un dizionario vuoto;
- String[] toStringArray() restituisce in un array le coppie del dizionario
  come stringhe, una per elemento dell'array, nel formato
  chiave + " " + attributo

La classe eseguibile MyMapTester, di prova della classe MyMap, definisce il
solo metodo main che esegue un ciclo per leggere da file un insieme di parole
(sequenze di caratteri separate da spazi o fine riga) terminando quando sono
state acquisite tutte le parole. Il nome del file e' passato come argomento
nella riga di comando.
A ogni iterazione del ciclo:
- si acquisisce una parola, la parola Pn (n = 0, 1, ...);
- se la parola Pn e' composta di soli caratteri numerici ed esiste una prossima
  parola Pn+1, allora si acquisisce la parola Pn+1 e si inserisce nel dizionario
  la coppia Pn+1/Pn, dove Pn+1 e' la chiave e Pn l'attributo (nell'iterazione
  successiva si acquisira' la parola Pn+2, se presente); se la parola acquisita
  Pn non e' composta di soli caratteri numerici, si passa alla prossima
  iterazione (dove si acquisira' la parola Pn+1, se presente);
  Esempio: la stringa "1234" e' composta di soli caratteri numerici, mentre la
  stringa "1A234" non lo e' (contiene il carattere 'A' che non e' numerico)
All fine del ciclo il metodo main  stampa il contenuto del dizionario usando
il metodo toStringArray().

Il candidato scriva la parte privata e completi la parte pubblica delle classi
MyMap e MyMapTester. Saranno considerate ottime quelle soluzioni della classe
MyMap in cui il metodo find ha andamento asintotico della complessita'
temporale migliore di O(n).

Suggerimento: nella classe MyMapTester, per riconoscere se una stringa e'
formata da soli caratteri numerici, si consideri l'uso del metodo statico
isDigit(Char c) della classe java.lang.Character.

In sede di correzione il codice sara' provato con i comandi:

   $rm *.class
   $javac MyMapTester.java
   $java MyMapTester list.txt

dove list.txt e' il file allegato.

Nella realizzazione delle classi MyMap e MyMapTester non e' lecito:
- aggiungere elementi, se non privati;
- usare classi della libreria standard, ad eccezione di quelle dei package
  java.lang e java.io e delle classi java.util.Scanner e
  java.util.NoSuchElementException.

Alla fine della prova il candidato lascera' nella directory di lavoro i file
eventualmente prodotti: MyMap.java, MyMapTester.java
e i file allegati dal docente: Map.java, list.txt.
I file prodotti dal candidato dovranno contenere come prima riga un commento
con nome e cognome, matricola, data, numero della postazione.


-------------------------------------------------------------------------------
Cognome   ______________________________ Nome _________________________________


Matricola _______________ Corso di Laurea _______________ Postazione __________
-------------------------------------------------------------------------------
Consegno l'elaborato che consiste dei seguenti file (contrassegnare con X):


[] MyMap.java        [] MyMapTester.java      Firma ___________________________
-------------------------------------------------------------------------------
Non consegno l'elaborato e mi ritiro
dall'esame.                              Firma ________________________________
-------------------------------------------------------------------------------