Lab 3

In the previous lab, customers were processed one at a time. As an example, for the following input with three customers and two servers (both with service time of 1.0),

$ cat 1.in 2 3 1 0.5 2 0.6 3 0.7

the output produced is as follows.

customer 1 arrives customer 1 served by server 1 customer 2 arrives customer 2 served by server 2 customer 3 arrives customer 3 leaves

In this lab, we would like to include the time of occurrence for the output of each event, as well as include another event to indicate when a service completes.

0.5 customer 1 arrives 0.5 customer 1 serve by server 1 0.6 customer 2 arrives 0.6 customer 2 serve by server 2 0.7 customer 3 arrives 0.7 customer 3 leaves 1.5 customer 1 done 1.6 customer 2 done

Notice that we no longer can process a customer from start to finish, before proceeding on to the next customer.

An event occurs at a particular time, and each event alters the state of the system and may generate more events. We call this a discrete event simulator as states remain unchanged between two successive events, which allows the simulation to jump from the time of one event to another in discrete time, rather than continous time. You will also be making use of an event priority queue to manage the sequence of events for processing.

Level 1 (to be completed during the lab)

We start by creating the different events for the simulation. As a customer arrives, there are one of two possible event transitions based on the availability of the server.

ARRIVE → SERVE: a new customer arrives, then served immediately; or
ARRIVE → LEAVE: a new customer arrives, then leaves immediately.

Here is an example of customer 1 arriving at time 1.0.

jshell> Customer customer1 = new Customer(1, 1.0) customer1 ⇒ customer 1

Customer arrivals are represented with an ArriveEvent as shown below.

jshell> ArriveEvent arriveEvent = new ArriveEvent(customer1, 1.0) arriveEvent ⇒ 1.0 customer 1 arrives

Since an event has a time of occurrence, the time of the arrival event is the same as the customer’s arrival time. Clearly, an arrival event is also an event.

jshell> arriveEvent instanceof Event $.. ⇒ true

From an arrival event, one can generate a serve event (ServeEvent) if a server is available to serve the customer. Let us create an available server 2 with a service time of 2.0.

jshell> Server server1 = new Server(1, 2.0) // new server is available to serve server1 ⇒ server 1

jshell> ServeEvent serveEvent = new ServeEvent(new ArriveEvent(customer1, 1.0), server1) serveEvent ⇒ 1.0 customer 1 serve by server 1

An arrival event may also result in a leave event (LeaveEvent) if no servers are available to serve the customer.

jshell> LeaveEvent leaveEvent = new LeaveEvent(new ArriveEvent(customer1, 1.0)) leaveEvent ⇒ 1.0 customer 1 leaves

You will notice that both ServeEvent and LeaveEvent will always have the same event time as its associated ArriveEvent since the transition happens immediately.

We now include another event transition:

SERVE → DONE: a server is done serving a customer.

When a customer arrives and a server is available, the SERVE event follows right after ARRIVE, while the DONE event occurs sometime in future.

ARRIVE → SERVE → after some time… → DONE

As an example, customer 1 arriving at 1.0 gets served by an available server 2 with a service time of 2.0. This will result in the service completing at 3.0 with a done event (DoneEvent).

jshell> DoneEvent doneEvent = new DoneEvent( …> new ServeEvent( …> new ArriveEvent(customer1, 1.0), …> new Server(2, 2.0)), …> 3.0) doneEvent ⇒ 3.0 customer 1 done

Hint: the time returned from customer’s serveTill method can be passed to completionTime. Doing this avoids having to retrieve the server’s service time and/or the customer’s arrival time.

The following sample run demonstrates polymorphism where InfList’s map operation goes through all stream elements one by one, with event (of type Event) taking the form of either ArriveEvent, ServeEvent, LeaveEvent or DoneEvent so as to invoke the respective toString methods.

jshell> InfList.of(arriveEvent, serveEvent, leaveEvent, doneEvent). // InfList …> map(event → event.toString() + “\n”). // InfList …> reduce((x, y) → x + y). // Maybe …> ifPresent(x → System.out.println(x)) 1.0 customer 1 arrives 1.0 customer 1 serve by server 1 1.0 customer 1 leaves 3.0 customer 1 done

Now processing events in the desired sequence requires the use of an event priority queue where events need to be compared against one another so as to return (or poll) events out of the queue based on some priority. As such, we need to first define a natural ordering of events.

As an example, Strings can be compared based on the natural order by implementing the Comparable interface and defining the compareTo method. Refer to the Java API to learn more about the Comparable interface and how the compareTo method should be defined.

jshell> “one”.compareTo(“two”) $.. ⇒ -5

Events are ordered by earliest occurrence of the event, and in the case of ties, by order in which the customer arrives. You may assume that no two customers arrive at the same time.

jshell> new ArriveEvent(new Customer(1, 1.0), 1.0). …> compareTo(new ArriveEvent(new Customer(2, 2.0), 2.0)) < 0 $.. ⇒ true

jshell> new ArriveEvent(new Customer(1, 3.0), 3.0). …> compareTo(new LeaveEvent( …> new ArriveEvent(new Customer(2, 2.0), 2.0))) > 0 $.. ⇒ true

jshell> new ServeEvent(new ArriveEvent(new Customer(2, 2.0), 2.0), …> new Server(2, 2.0)). …> compareTo(new ArriveEvent(new Customer(3, 3.0), 3.0)) < 0 $.. ⇒ true

jshell> new ArriveEvent(new Customer(4, 4.0), 4.0). …> compareTo(new DoneEvent( …> new ServeEvent( …> new ArriveEvent(new Customer(2, 2.0), 2.0), …> new Server(2, 2.0)), …> 4.0)) > 0 $.. ⇒ true

Level 2

We are now ready to process our events using a priority queue. While Java provides the PriorityQueue class which is a mutable collection (like ArrayList), we have provided our own PQ class that is immutable, as well as the accompanying Maybe and Pair classes.

The programs PQ.java, Pair.java, Maybe.java and InfList.java are given. Just like Maybe.java and InfList.java, PQ.java also includes javadoc comments. To automatically generate HTML documentation from the comments, issue the command:

$ja v a d oc - dd oc PQ . ja v a Y o u ma y t h e nna v i g a t e t h ro ug h t h e d oc u m e n t a t i o n f ro m a ll c l a sses - in d e x . h t m l f o u n d in t h e d oc d i rec t ory . T h e f o ll o w in g s h o w s h o w an e m pt y PQ o f s t r in g sc anb eco n s t r u c t e d . j s h e ll > PQ < St r in g > pq = n e wPQ < St r in g > () pq ==> [] W ec ana dd e l e m e n t s t o t h e p r i or i t y q u e u e v ia t h e a dd m e t h o d . j s h e ll > pq . a dd (" o n e ") $ .. ⇒ [one]

jshell> pq // note that pq is immutable
pq ⇒ []

jshell> pq = pq.add(“one”).add(“two”).add(“three”)
pq ⇒ [one, two, three]

Values can be returned from PQ via the poll method. Each call to poll gives a pair of values comprising the element polled from the PQ wrapped in an Maybe, and the remaining PQ.

jshell> pq.poll()
$.. ==> P ai r [t = M a y b e [o n e], u = [t h ree, tw o]] j s h e ll > pq . p o ll () . u () . p o ll () $ .. ⇒ Pair[t=Maybe[three], u=[two]]

jshell> pq.poll().u().poll().u().poll()
$.. ==> P ai r [t = M a y b e [tw o], u = []] j s h e ll > pq . p o ll () . u () . p o ll () . u () . p o ll () . u () $ .. ⇒ []

jshell> pq.poll().u().poll().u().poll().u().poll()
$.. ⇒ Pair[t=Maybe.empty, u=[]]

You may notice that the output of elements in a priority queue is not necessarily in order. What matters most is the values returned from the poll method.


The programs PQ.java, Pair.java, Maybe.java and InfList.java are given. Just like Maybe.java and InfList.java, PQ.java also includes javadoc comments. To automatically generate HTML documentation from the comments, issue the command: $ja v a d oc - dd oc PQ . ja v a < b r >< b r > Y o u ma y t h e nna v i g a t e t h ro ug h t h e d oc u m e n t a t i o n f ro m a ll c l a sses - in d e x . h t m l f o u n d in t h e d oc d i rec t ory . < b r >< b r > T h e f o ll o w in g s h o w s h o w an e m pt y PQ o f s t r in g sc anb eco n s t r u c t e d . < b r >< b r > j s h e ll > PQ < St r in g > pq = n e wPQ < St r in g > () < b r > pq ==> [] < b r >< b r > W ec ana dd e l e m e n t s t o t h e p r i or i t y q u e u e v ia t h e a dd m e t h o d . < b r >< b r > j s h e ll > pq . a dd (" o n e ") < b r >$ .. ⇒ [one] jshell> pq // note that pq is immutable pq ⇒ [] jshell> pq = pq.add(“one”).add(“two”).add(“three”) pq ⇒ [one, two, three] Values can be returned from PQ via the poll method. Each call to poll gives a pair of values comprising the element polled from the PQ wrapped in an Maybe, and the remaining PQ. jshell> pq.poll() $.. ==> P ai r [t = M a y b e [o n e], u = [t h ree, tw o]] < b r >< b r > j s h e ll > pq . p o ll () . u () . p o ll () < b r >$ .. ⇒ Pair[t=Maybe[three], u=[two]] jshell> pq.poll().u().poll().u().poll() $.. ==> P ai r [t = M a y b e [tw o], u = []] < b r >< b r > j s h e ll > pq . p o ll () . u () . p o ll () . u () . p o ll () . u () < b r >$ .. ⇒ [] jshell> pq.poll().u().poll().u().poll().u().poll() $.. ⇒ Pair[t=Maybe.empty, u=[]] You may notice that the output of elements in a priority queue is not necessarily in order. What matters most is the values returned from the poll method.

In our simulation, we first create arrival events for all customer arrivals and add them into a priority queue. Having included all arrival events in the priority queue, we can begin processing the queue:

poll an event from the queue
if necessary, generate the next event using the current state of the servers in the shop and add into the queue

Repeat the above until the queue is empty. Remember to update the server along the way. Here is an example of how we can iterate through the priority queue.

jshell> PQ eventPQ = new PQ(). …> add(new ArriveEvent(new Customer(1, 0.5), 0.5)). …> add(new ArriveEvent(new Customer(2, 0.6), 0.6)). …> add(new ArriveEvent(new Customer(3, 0.7), 0.7)) eventPQ ⇒ [0.5 customer 1 arrives, 0.6 customer 2 arrives, 0.7 customer 3 arrives]

jshell> InfList.iterate(eventPQ, pq → pq.poll().u()). …> takeWhile(pq → !pq.isEmpty()). // InfList<PQ> …> map(pq → pq.poll().t()). // InfList<Maybe> …> forEach(t → t.ifPresent(x → System.out.println(x))) 0.5 customer 1 arrives 0.6 customer 2 arrives 0.7 customer 3 arrives

From the arrival event, we need to determine the next event, which could either be a serve event or a leave event based on the status of the servers in the shop. Moreover from a serve event, we need to generate the done event, as well as update the appropriate server in the shop. As such, for each type of event you will need to define a next method that takes in a Shop and return the next event and an updated shop as a pair.

For the design aspect of this lab, you are free to declare the return type of the next method in a way that you deem appropriate. The test cases in this level serves to demonstrate the functionality of the next method and will not be evaluated in your final submission.

One might start by considering the next method to return Pair<Event,Shop>, e.g.

jshell> Event e1 = new ArriveEvent(new Customer(1, 1.0), 1.0) e1 ⇒ 1.0 customer 1 arrives

jshell> Pair<Event,Shop> pair = e1.next(new Shop(1, 2.0)) pair ⇒ Pair[t=1.0 customer 1 serve by server 1, u=Shop:<server 1>]

jshell> pair.t().next(pair.u()) $.. ⇒ Pair[t=3.0 customer 1 done, u=Shop:<server 1>]

You also need to be mindful that for LeaveEvent and DoneEvent, what event (if any) will be returned upon calling the next method. In this case, a return type of Pair<Maybe,Shop> may be more appropriate.

jshell> Event e1 = new ArriveEvent(new Customer(1, 1.0), 1.0) e1 ⇒ 1.0 customer 1 arrives

jshell> Pair<Maybe,Shop> pair = e1.next(new Shop(1, 2.0)) pair ⇒ Pair[t=Maybe[1.0 customer 1 serve by server 1], u=Shop:<server 1>]

jshell> pair.t().map(event → event.next(pair.u())) $.. ⇒ Maybe[Pair[t=Maybe[3.0 customer 1 done], u=Shop:<server 1>]]

With the next method of the individual events defined, you will soon realize that you have cases of cyclic dependencies. For example, ServeEvent takes in an ArriveEvent in its constructor, and ArriveEvent generates a ServeEvent in the former’s next method. To circumvent this, let ServeEvent take in an Event instead. Indeed, there could be other events that can be passed to the constructor of ServeEvent. Do the same for the other event cyclic dependencies that you identify.

Level 3

In the previous lab, you have seen how the State can be used to set up a specific configuration of the simulation, so that the next method can be used to test the rest of the simulation for correctness. To do the same for this lab, you will need to include the PQ and set up the events correctly. You may ignore extra blank lines in the output as these will be trimmed off before testing.

jshell> PQ pq = new PQ().add(new ArriveEvent(new Customer(1, 1.0), 1.0)). …> add(new ArriveEvent(new Customer(2, 2.0), 2.0)) pq ⇒ [1.0 customer 1 arrives, 2.0 customer 2 arrives]

jshell> new State(pq, new Shop(2, 1.0)).next() $.. ⇒ 1.0 customer 1 arrives

jshell> new State(pq, new Shop(2, 1.0)).next().next() $.. ⇒ 1.0 customer 1 arrives 1.0 customer 1 serve by server 1

jshell> new State(pq, new Shop(2, 1.0)).next().next().next() $.. ⇒ 1.0 customer 1 arrives 1.0 customer 1 serve by server 1 2.0 customer 1 done

jshell> InfList.iterate(new State(pq, new Shop(2, 1.0)), state → state.next()). …> takeWhile(state → !state.isEmpty()). …> map(state → state.toString()). …> reduce((x,y) → y). …> ifPresent(x → System.out.println(x)) $.. ⇒

1.0 customer 1 arrives 1.0 customer 1 serve by server 1 2.0 customer 1 done 2.0 customer 2 arrives 2.0 customer 2 serve by server 1 3.0 customer 2 done

Level 4

You are given the following Main class.

import java.util.List; import java.util.Scanner;

static final double SERVICE_TIME = 1.0;

void main() { Scanner sc = new Scanner(System.in); int numOfServers = sc.nextInt(); int numOfCustomers = sc.nextInt();

sc.nextLine(); // removes trailing newline
InfList<Pair<Integer,Double>> arrivals = InfList.iterate(1, x -> x + 1)
    .limit(numOfCustomers)
    .map(x -> new Pair<>(sc.nextInt(), sc.nextDouble()));

new Simulator(numOfServers, numOfCustomers, arrivals, SERVICE_TIME)
    .run().ifPresent(x -> System.out.println(x));

}

Write the Simulator class so as to carry out the simulation. Sample runs of the program is given below. You may ignore extra blank lines in the output as these will be trimmed off before testing.

$ javac —release 21 —enable-preview Main.java Note: Main.java uses preview features of Java SE 21. Note: Recompile with -Xlint:preview for details.

$ cat 1.in 3 3 1 0.5 2 0.6 3 0.7

$ cat 1.in | java —enable-preview Main

0.5 customer 1 arrives 0.5 customer 1 serve by server 1 0.6 customer 2 arrives 0.6 customer 2 serve by server 2 0.7 customer 3 arrives 0.7 customer 3 serve by server 3 1.5 customer 1 done 1.6 customer 2 done 1.7 customer 3 done

$ cat 2.in 2 3 1 0.5 2 0.6 3 0.7

$ cat 2.in | java —enable-preview Main

0.5 customer 1 arrives 0.5 customer 1 serve by server 1 0.6 customer 2 arrives 0.6 customer 2 serve by server 2 0.7 customer 3 arrives 0.7 customer 3 leaves 1.5 customer 1 done 1.6 customer 2 done

$ cat 3.in 2 3 1 0.5 2 0.6 3 1.5

$ cat 3.in | java —enable-preview Main

0.5 customer 1 arrives 0.5 customer 1 serve by server 1 0.6 customer 2 arrives 0.6 customer 2 serve by server 2 1.5 customer 1 done 1.5 customer 3 arrives 1.5 customer 3 serve by server 1 1.6 customer 2 done 2.5 customer 3 done

Explorer

Lab 3

Level 1 (to be completed during the lab)

Level 2

Level 3

Level 4