In deze oefening simuleren we de parkeerplaats aan een winkel. Op gegeven tijdstippen komen klanten toe. Is er een parkeerplaats beschikbaar, dan zal een klant zich daar parkeren en zijn boodschappen doen. Als zijn boodschappen gedaan zijn, vertrekt hij gewoon weer. Klanten die toekomen wanneer alle plaatsjes bezet zijn, besluiten om (tevergeefs) een blokje rond te rijden op zoek naar andere parkeerplaats. Na gegeven tijd komen ze terug aan bij de parking, waar ze opnieuw proberen te parkeren. We willen achterhalen wanneer de laatste klant vertrekt en de parking bijgevolg terug leeg is. Merk op dat bij race-condities (twee of meer klanten komen tegelijk toe) de klanten die minder lang willen winkelen voorrang krijgen.

Op onderstaande figuur zie je een voorbeeld met drie parkeerplaatsen en negen klanten. Initieel zijn alle plaatsen vrij.

De eerste twee klanten die aankomen, kunnen ongestoord parkeren en hun boodschappen doen.

Ook de derde klant kan zich meteen parkeren, ofwel op parkeerplaats 1 (want de eerste klant is al weg), ofwel op parkeerplaats 3. We kiezen steeds de eerste vrije parkeerplaats. Ook wanneer de vierde en vijfde klant arriveren, is er al terug een plekje vrij. De zesde en de zevende klant komen op hetzelfde moment toe, maar de zevende klant krijgt voorrang omdat die een korter winkelbezoek zal doen.

Hierdoor kan de zesde klant niet langer parkeren, en besluit om een blokje rond te rijden.

Enige tijd later komt de zesde klant terug. Aangezien op dat moment de derde parkeerplaats terug vrij is, kan deze klant nu zijn boodschappen doen. Niet veel later komt de achtste klant toe, die opnieuw merkt dat de parking vol staat. De achtste klant rijdt een blokje rond.

Ondertussen komt echter de negende klant reeds aan en gaat met de eerste parkeerplaats lopen.

Nu komt de achtste klant voor de derde maal een plekje zoeken en gelukkig is er ondertussen een parkeerplaats vrij. Nadat deze klant zijn boodschappen gedaan heeft, is de parking terug leeg.

Gegeven de interface ParkingSimulator¹, implementeer methode public int simulate(int capacity, int returnTime, Collection<Event> arrivalEvents) in een klasse genaamd QueueParkingSimulator. In deze methode simuleer je bovenstaande situatie met behulp van een prioriteitswachtlijn. Het aantal parkeerplaatsen wordt gegeven door capacity, returnTime geeft aan na welke periode een klant terug opduikt als hij geen parkeerplaats vond en arrivalEvents bevat de collectie van alle toekomende klanten. De gevraagde returnwaarde is het tijdstip waarop de laatste auto de parking verlaat.

De gebeurtenissen (van gegeven klasse Event²) kunnen een aankomst en een vertrek voorstellen. Indien isArrival waar is, betreft deze gebeurtenis een aankomst. In dat geval geeft timestamp aan wanneer de klant aankomt en geeft duration aan hoeveel tijd deze klant nodig heeft om te winkelen. Anders, als isArrival false teruggeeft, gaat het over een vertrek. Hier geeft timestamp aan wanneer dit vertrek plaatsvindt en speelt de waarde van duration geen rol.

Je kan jouw implementatie lokaal testen met SimpleTest³.

We raden sterk aan de PriorityQueue⁴ datastructuur hiervoor te gebruiken. Deze heeft volgende interessante methoden:

• Een constructor⁵ waaraan je een Comparator mee kan geven, die de prioriteitsordening bepaald.
• Een add-methode⁶ om elementen op hun plaats in de wachtlijn te zetten.
• Een poll-methode⁷ om het element met de hoogste prioriteit uit de wachtlijn te halen.