Problema 1 Si consideri la seguente specifica del tipo astratto DepositoOggetti:
precondizioni e postcondizioni per Crea() = d
pre: nessuna
post: d è un deposito con 0 oggetti;
precondizioni e postcondizioni per InserisciOggetto(d,o) = (e,t)
pre: o non è nel deposito d
post: e è il deposito ottenuto da d aggiungendo l'oggetto o; all'oggetto o viene associato il timestamp t;
precondizioni e postcondizioni per EliminaOggetto(d,t) = e
pre: l'oggetto al quale è associata il timestamp t è nel deposito d
post: e è il deposito ottenuto da d eliminando l'oggetto al quale è associata la targa t;
precondizioni e postcondizioni per EstInDeposito(d,t) = b
pre: nessuna
post: b=true se l'oggetto alla quale è associata il timestamp t è nel deposito, b=false altrimenti;
precondizioni e postcondizioni per DammiOggetto(d,t) = a
pre: l'oggetto al quale è associata il timestamp t è nel deposito d
post: a è l'oggetto al quale è associata il timestamp t;
precondizioni e postcondizioni per OggettoPiuVecchio(d) = t
pre: nessuna
post: t è il timestamp dell'oggetto che da più tempo sta nel deposito (se il deposito e vuoto viene restituito un timestamp speciale);
precondizioni e postcondizioni per OggettoSuccessivo(d,t) = r
pre: l'oggetto al quale è associata il timestamp t è nel deposito d
post: r è il timestamp dell'oggetto inserito subito dopo l'oggetto con timestamp t; se tale oggetto non esiste viene restituito t;
Domanda 1 Realizzare il tipo astratto DepositoOggetti mediante una classe C++ DepositoOggetti in modo da rendere le operazioni del tipo astratto il più efficienti possibile. Se si utilizzano strutture dati note (quali, Heap, AlberoRicerca, TavolaHash, ecc), riportare solo la definizione della classe corrispondente (file .h) e una breve descrizione di ciascuna delle operazioni. Per riferirsi al tipo astratto Oggetto è necessario utilizzare la classe già definita Oggetto, della quale non è nota la struttura. Infine si rappresenti il tipo astratto TimeStamp come un intero non negativo.
Domanda 2 Si discuta brevemente la complessità di ciascuna delle funzioni pubbliche della classe DepositoOggetti.