11. vaje: DINAMIČNA TABELA (18. 05. - 25. 05.)

Dinamična tabela

Za hranjenje seznamov objektov bomo napisali nov razred DinamicnaTabela, ki bo omogočal delo s seznamom poljubnih objektov (ti objekti so lahko tudi podvojeni, ne morejo pa biti null). Za ta razred bomo napisali tudi iterator, ki bo omogočal sprehod preko vseh elementov seznama v takem vrstnem redu, kot smo jih vstavljali v seznam. Nekatere operacije nad seznamom ne bodo podprte, zato naj se v takem primeru sproži nepreverljiva izjema. Za preverjanje delovanja seznama bomo napisali tudi razred Vaje11 z metodo main, v kateri zgradimo seznam naključnih števil in nad njim izvedemo različne operacije (preverjanje velikosti seznama, preverjanje praznega seznama, dodajanje elementov, brisanje elementov in druge, tudi nepodprte operacije).

a) Napišite razred DinamicnaTabela, ki implementira vmesnik Collection. Razred hrani poljubne objekte v tabeli, katera ima privzeto začetno velikost 10. Začetno velikost tabele lahko nastavimo poljubno, če velikost podamo kot parameter konstruktorju. Na začetku je tabela vedno prazna. (Pozor: za hranjenje objektov uporabite tabelo, ne javanske zbirke!)

b) V razredu definirajte tudi naslednje metode: size(), isEmpty(), contains(), add(), addAll(), remove() in removeAll(), ki naj delujejo v skladu z opisom vmesnika. Pri dodajanju elementa v seznam ko je tabela že zapolnjena, se naj poveča velikost tabele za ena, da seznam lahko sprejme še novi element. Ostalih metod (npr. metod clear(), toArray() in retainAll()) ne bomo implementirali, zato naj te metode sprožijo nepreverljivo izjemo IzjemaNepodprteOperacije (slednja naj razširja razred RuntimeException).

c) V razredu definirajte tudi metodo iterator(), ki vrne iterator po našem seznamu objektov. V ta namen napišite tudi razred DinamicniIterator, ki implementira vmesnik Iterator in predstavlja iterator po našem seznamu objektov. V razredu morate seveda implementirati tudi metodi hasNext() in next().

d) Metoda add() razreda DinamicnaTabela doda nov element v seznam. Če v tabeli, ki hrani elemente seznama, ni dovolj prostora za nov element, je tabelo potrebno povečati. Povečanje tabele je lahko poljubno. Uporabimo dve strategiji, ki ju bomo tudi primerjali po učinkovitosti: 1) tabelo vedno povečamo za 1, saj potrebujemo prostor za en nov element (to smo uporabili v točki b); 2) ob vsakem povečanju tabele njeno velikost podvojimo. Napišite dve različici metode za povečevanje tabele elementov in primerjajte čas ustvarjanja tabele za prvo in za drugo različico. Za merjenje časa ustvarjanja seznama lahko uporabite naslednjo metodo main, v kateri zgradimo seznam 100.000 naključnih števil in hkrati tudi merimo čas za izgradnjo tega seznama. Kaj ugotovite? Katera strategija povečevanja tabele je bolj učinkovita? Zakaj?