Diploma Universitario di Ingegneria Informatica
Esame di Fondamenti di Informatica II - secondo modulo
A.A. 2000/01 - Appello del 24 aprile 2001

Problema 1   Si consideri la seguente specifica del tipo astratto PlayList:

TipoAstratto PlayList

Sorte PL (sorta per il dominio di interesse)

Funzioni

• Crea : (URL) --> PL
  precondizioni e postcondizioni per crea(u) = p
  pre: nessuna
  post: p è una playlist avente url (uniform resource locator) u e nessun file MP3 associato

• URL : (PL) --> URL
  precondizione e postcondizioni per URL(p) = u
  pre: nessuna
  post: u è l'url della playlist p

• Inserisci : (PL, MP3) --> PL
  precondizioni e postcondizioni per Inserisci(p,m) = q
  pre: nessuna
  post: q è la playlist ottenuta da p aggiungendo il file MP3 m se non già presente, q=p altrimenti

• Elimina : (PL, MP3) --> PL
  precondizioni e postcondizioni per Elimina(p,m) = q
  pre: nessuna
  post: q è la playlist ottenuta da p eliminando il file MP3 m (se presente)

• Presente : (PL, MP3) --> Bool
  precondizioni e postcondizioni per Presente(p,m) = b
  pre: nessuna
  post: b=true se il file MP3 è presente in p; b=false altrimenti

Scrivere una classe C++ PlayList (file .h e file .cpp) che realizza il tipo astratto PlayList facendo uso di una tavola hash, definita in modo da eseguire tutte le operazione del tipo astratto in tempo costante (O(1)) nel caso atteso, avendo cura che il fattore di carico fc della tavola hash sia sempre compreso tra 0.25 e 0.75. Si consideri che per riferirsi al tipo astratto MP3 è necessario utilizzare la classe MP3 che si suppone già realizzata, della quale però non è nota la definizione. Inoltre si assuma che URL sia rappresentato da oggetti di una classe Stringa per la quale sono disponibili, assegnazione, construttore di copia ed uguaglianza.

Problema 2   Si modifichi la definizione del tipo astratto PlayList aggiungendo la funzione

• TuttiMP3 : (PL) --> Enumerazione(MP3)
  precondizioni e postcondizioni per TuttiMP3(p) = e
  pre: nessuna
  post: e è una enumerazione dei file MP3 presenti nella playlist p; l'ordine della enumerazione è qualsiasi

Aggiungere alla classe PlayList realizzata per il Problema 1 una funzione che realizzi TuttiMP3 in modo che venga eseguita in tempo costante (O(1)), definendo una opportuna classe Iteratore per realizzare il tipo astratto Enumerazione(MP3).