Programmeringuppgift 3

Expressen eller Aftonbladet?

Den abstrakta datastrukturen queue-of-persons är en mängd element som avbildar en kiosk-kö. Nytillkommande kunder ställer sig sist i kiosk-kön och gamla expideras från början av kiosk-kön. Varje element är en person med ett namn, ett ärende och en tid som anger hur lång tid ärendet tar.

Bild 1. Kiosk-kö.

Skriv en funktion round-robin[queue;time;close-time] som tar tre argument:

queue som är en kö av personer, queue-person.

time som står för hur många sekunder varje kund betjänas innan de får ställa sig i sist i kön igen.

close-time som står för de antal sekunder som är kvar innan kiosken stänger.

round-robin ska returnera den kö som existerar när kiosken stängt. Varje person i kön betjänas i time sekunder (oavsett om den behöver det eller inte). Om personen är färdig inom den givna tiden så tas den helt bort ur kön. Annars ställer sig personen i kön igen efter att ha minskat sitt behov av tid med time. Samtidigt närmar man sig stångningsdags. Om det t.ex. bara är 3 sekunder kvar till stängningsdags och varje kund ska få 5 sekunder, så betjänas (av ren artighet) den kund som står främst i kön, men sedan stängs luckan obönhörligen.

Exempel (personerna i kön håller i en lapp där det står hur många sekunder de behöver för sitt årende):

Bild 2. Illustration av round-robin utan att avslöja någon lämplig datarepresentation.

Redovisning
Uppgiften får lösas individuellt eller i grupper om två. Uppgiften ska redovisas skriftligt med

noggrann specifikation av den eller de valda ADTerna
kortfattad beskrivning av implementeringen av valda ADTer
fallanalys för de väsentligaste funktionerna
programlista och körningsexempel

Ingen felhantering behövs.

Dina lösningar ska spegla god programmeringssed för funktionella språk. Således kan fungerande program, som ej är en bild av ett funktionellt synsätt och väl illustrerar en teknik med dataabstraktion, komma att underkännas. Du bör speciellt undvika tekniker med "räknare" eller "ackumulerande parametrar", om dessa ej är nödvändiga för uppgiftslösningen.

Handledning ges av Kjell Post, på anslagna tider. Uppgiften lämnas till Kjell Post.

Anders Berglund                        Office: Room 1254
Department of Computer Systems         E-mail: Anders.Berglund@docs.uu.se
Box 325                                Phone (work): +46 18 471 31 67
S-751 05 Uppsala                       Mobile phone: +46 425 02 11
Sweden                                 Fax (work):   +46 18 55 02 25

queue	som är en kö av personer, queue-person.
time	som står för hur många sekunder varje kund betjänas innan de får ställa sig i sist i kön igen.
close-time	som står för de antal sekunder som är kvar innan kiosken stänger.