UL/FRI/VSP-RI/OAPS1/Seminarske/2006-01-14

Izvirnik seminarske naloge (pdf)

Napišite program v javi, ki realizira vrsto kot povezan linearni seznam objektov, pri čemer naj bo vrsta predstavljena kot generični razred. Pri tem izhajajte iz vmesnika Queue in razredov AbstractQueue in LinkedQueue, kjer slednjega ustrezno spremenite oziroma dopolnite. Upoštevajte, da imajo objekti v linearnem seznamu povezavo samo s svojim naslednikom (in ne s predhodnikom), generični razred pa omogoča shranjevanje le za objekte izbranega tipa.

Napišite tudi testni razred TestVrste, ki omogoča interaktiven prikaz uporabe vseh operacij vrste nad objekti tipa, ki ste ga uporabljali v prvih dveh seminarskih nalogah.

A) za 3 točke

Vrsta naj bo realizirana s (spremenjenim) razredom LinkedQueue, ki vsebuje (spremenjen) notranji razred Node.

Vsebovati mora tudi ustrezno realizacijo iteratorja ter štirih osnovnih operacij, ki smo jih spoznali na predavanjih:

• dodajanje na konec vrste (enqueue)
• izločanje prvega elementa iz vrste (dequeue)
• izpis prvega elementa vrste (getFront)
• izpis zadnega elementa vrste (getBack)

Poleg teh operacij realizirajte še nekaj drugih, ki omogočajo (enostavnejši) prikaz uporabe:

• tvorbo prazne vrste
• dodajanje tabele elementov na konec vrste
• praznjenje vrste
• primerjavo enakosti dveh vrst (za izbran atribut)
• izpis števila objektov vrste
• izpis vseh elementov vrste (z iteratorjem)
• izpis vseh elementov vrste (za izbran atribut)

Testni razred naj omogoča prikaz delovanja vseh metod na interaktiven način; torej tako, da zaporedoma vnašamo in izvajamo operacije v poljubnem zaporedju nad izbrano vrsto. V ta namen uporabite enak tip objektov kot v prejšnjih seminarskih nalogah (Delavec, Sportnik, Popotnik, Varcevalec in druge), kar pomeni, da bo treba tvoriti vrsto z objekti ustreznega tipa.

Za preverjanje enakosti vsebine dveh vrst potrebujemo vsaj dve vrsti, zato je primerno uporabiti enak pristop kot pri drugi seminarski nalogi - deklarirati tabelo nekaj vrst in nato pred vsako operacijo izbrati tisto, nad katero naj se operacija izvede.

B) za 4 točke

Realizacijo vrste iz naloge A dopolnite z razredom PriorityLinkedQueue, ki predstavlja prioritetno vrsto. Nad prioritetno vrsto izvajamo enake opreracije kot nad “navadno” vrsto s to razliko, da se pri izločanju (in posledično tudi izpisu prvega elementa) vedno izloči (izpiše) element z največjo prioriteto. To pomeni, da mora med elementi vrst obstajati urejenost, ki določa, kateri element je po prioriteti prvi.

V našem primeru naj bo prioriteta določena s pomočjo metode manjši in z upoštevanjem izbranega atributa (imena, priimka, ipd.) in smeri (naraščajoče/padajoče), ki ju tudi lahko sproti spreminjamo med izvajanjem.

Primer: pri izbiri atributa datumR in smeri naraščajoče je po prioriteti na prvem mestu najstarejša oseba.

Prioritetno vrsto realizirajte kot neurejeno zaporedje elementov, kjer metoda za izločanje, izpis prvega in zadnjega elementa s pregledom celotne vrste poišče ustrezen element za izločanje ali izpis. Ostalih metod v novem razredu ni potrebno redefinirati. Enako kot v prejšnjem primeru naj tudi tu testni razred poskrbi za interaktivno preverjanje (vnos potrebnih podatkov in izpis rezultatov) vseh metod.

C) za 5 točk

Nalogo B rešite na drugi način: razred PriorityLinkedQueue naj vrsto realizira kot urejeno zaporedje elementov, kjer je pri dodajanju (posameznega elementa ali tabele elementov) potrebno poskrbeti za ustrezno urejenost, medtem ko lahko ostale metode ostanejo nespremenjene. Poleg tega smiselno dopolnite (ali nadomestite) nabor metod iz naloge B z metodami, ki omogočajo simulacijo delovanja poljubnega večjega števila vrst (recimo v trgovskem centru). Za hranjenje vrst uporabite vektor, operacije pa naj omogočajo naslednje:

• odpiranje nove (prazne) vrste (z določanjem povprečnega časa obdelave enega elementa),
• zapiranje izbrane vrste,
• začasne zaustavitev izbrane vrste (za določen čas),
• aktiviranje izbrane začasno zaustavljene vrste,
• sprememba povprečnega časa obdelave enega elementa v določeni vrsti,
• preusmeritev določene vrste v izbrano drugo vrsto (recimo ob zapiranju ali začasni zaustavitvi),
• preureditev znotraj vseh vrst ob spremembi prioritete (spremembi atributa in/ali smeri),
• določitev optimalne vrste za nov element - optimalna vrsta je tista, kjer bo element najmanj čakal glede na prioriteto (svojo vrednost izbranega atributa v primerjavi z vrednostmi atributov ostalih elementov v vrsti), časa začasne zaustavitve vrste in povprečnega časa obdelave enega elementa,
• izpis elementov vrste, ki se jim splača zamenjati vrsto (brez spremembe vsebine vrst),
• preusmeritev dela izbrane vrste (od izbranega mesta do konca) na optimalen način v druge vrste,
• optimalna preureditev vsebine vseh vrst - lahko se uporabi po spremembi prioritete (spremembi atributa in/ali smeri), začasni zaustavitvi ali spremembi povprečnega časa obdelave elementa vrste,
• izpis statusa (števila elementov, časa zaustavljenosti in povprečnega časa obdelave elementa) vseh vrst ter
• izpis vseh elementov izbrane vrste, kjer je ob vsakem elementu izpisan tudi predviden čas čakanja.

Enako kot pri nalogi B tudi tu realizirajte testni razred za domeno, ki vam je pripadala glede na vpisno številko pri prvih dveh seminarskih nalogah.