In the class, we discussed an implementation FixedQueue of the Queue trait using a circular buffer and a fixed-length array. Your task is to write an implementation GrowQueue in a file growqueue.scala that will grow the array when the circular buffer is full and another element is enqueued. This is very similar to what we did in GrowStack, but you have to be more careful with copying the elements, because they may not be in a contiguous interval of the array.
Start by compiling the three sources (queue.scala, growqueue.scala, checksuite.scala), and run the test suite:
$ fsc queue.scala $ fsc growqueue.scala $ fsc checksuite.scala $ scala org.scalatest.run QueueCheckSuite Run starting. Expected test count is: 3 QueueCheckSuite: - basic queue test - many items *** FAILED *** - interleaved enqueuing and dequeuing *** FAILED *** Run completed in 348 milliseconds. Total number of tests run: 3 Suites: completed 1, aborted 0 Tests: succeeded 1, failed 2, canceled 0, ignored 0, pending 0 *** 2 TESTS FAILED ***
As usual, when you are done with your implementation, all tests should pass.
Unix systems have a utility called tail that prints out the last \(k\) lines of a text file. This works well and uses little memory even for very large files, because it uses a queue.
The algorithm works as follows: Create an empty queue Queue[String]. Read each line from the file, and enqueue it. If the size of the queue is now larger than \(k\), then dequeue one line. Finally, print all the lines in the queue.
Note that our Queue trait doesn't have a length method, so we can't ask the queue for its current size—we have to maintain such a count ourselves.
Write a compiled scala application tail.scala that compiles to an object Tail. The application takes two command line parameters: the name of a text file, and the number \(k\).
For example:
> fsc tail.scala > scala Tail planets.txt 4 Jupiter Saturn Uranus Neptune
You can start with the template tail.scala.
Your program should use the GrowQueue from the previous task. If you failed to implement that task perfectly, then use the Scala queue scala.collection.mutable.Queue. You can create it like this:
val q: Queue[String] = new scala.collection.mutable.Queue[String] with Queue[String]
In this task, we will work on a simulation of a waiting process. Examples are the cars waiting to pay at a highway tollgate, or the customers queuing inside a bank or post office. Simulating such a system can help us understand the process, and how it might be made more efficient. For instance, the simulation might suggest that we should open an additional counter in the post office during certain hours of the day.
Simulation is also an area where object-oriented programming really helps. This is because in a simulation, we typically have several "things" (objects) that interact with each other. We can model each "thing" by a class. The interactions of the "things" with each other are called events, and are modeled by the simulation.
We will keep our simulation rather simple. The objects we need are clients (customers in the post office) and servers (employees of the post office). Clients come into the post office at random time intervals (determined by the average time between clients). If a server is free, the client is directly served by this server. Otherwise the client enters at the rear of a single queue, the waiting line. Whenever a server finishes serving a client, the next client from the front of the queue comes to this server.
You can download the code as simulation.zip. Compile all the files, then run the simulation, for instance as
scala Simulation 3 100 12 4This will simulate for 100 ticks (a tick is the basic time interval of the simulation), with three servers. The average serving time per client is 12 ticks, and clients come in on average every 4 ticks.
We model each server and each client by a Scala object. Since there could be different servers and different clients with differing behavior, we first create a Client trait and a Server trait, with all the methods needed to program our simulation.
The simulation itself is controlled by a Simulation object. We implement a discrete time-step simulation, where the entire process is simulated in discrete time units (called ticks). Events, such as a client coming in or leaving, can only occur in these discrete time steps. The method Simulation.simulate is called once for each tick, and controls the entire simulation:
for (t <- 0 until timeSteps)
sim.simulate(t)
The implementation of the method Simulation.simulate(t: Int) is
as follows:
def simulate(t: Int) {
println("Time " + t + ": ")
checkClientArrival(t)
for (j <- 0 until servers.length) {
val s = servers(j)
if (s.client != null && t == s.client.stopTime)
s.stopServing(t)
if (s.isIdle(t) && !queue.isEmpty) {
val client = queue.dequeue()
s.startServing(client, t)
}
}
}
The method checkClientArrival uses a random number to determine the arrival time of the next client. (The arrival of clients is usually modeled as a Poisson process—you will run into this if you learn more about probability and statistics). For simplicity, we do not consider the case where more than one client comes in at the same tick. The method simply adds the new client to the rear of the waiting queue.
We then check all the servers: if its client is done, the client leaves. If the server is now idle, it starts serving the first client from the queue.
Note that all the client and server methods called by the simulation are methods of the Client and Server trait. This will allow you to add different kinds of clients and servers in this task.
In the original code, there is only one kind of client (SimClient), and only one kind of server (SimServer), which perform only basic functions and output.
Your task is to implement the new server class CoffeeDrinkingServer (in the file coffeeserver.scala) and the new client class DemandingClient (in the file demandingclient.scala).
A CoffeeDrinkingServer needs a five-tick coffee break after each client. That means, the method isIdle will return false for four ticks even after the last client has left.
A DemandingClient simply needs much more time: His service time is always the meanServiceTime of the simulation plus 10 ticks (so there is no randomness at all).
The toString methods of the two new classes indicate the different server/client type by puttin a star after the client number/server letter.
The CoffeeDrinkingServer should print a message while it is drinking coffee (you can do this in the isIdle method), like this:
Time 62:
Time 63:
Client 18 arrived
Server B* stopped serving Client 15
Time 64:
Server B* is drinking coffee.
Time 65:
Client 19 arrived
Server B* is drinking coffee.
Time 66:
Server B* is drinking coffee.
Time 67:
Client 20* arrived
Server B* is drinking coffee.
Time 68:
Server B* finished drinking coffee.
Client 17 waited 9 ticks.
Server B* started serving Client 17 and will finish at time 95
You must not modify any of the existing classes. Only work on CoffeeDrinkingServer in the file coffeeserver.scala, and on DemandingClient in the file demandingclient.scala. Do not change any other file! (In any case, you will only submit the two files coffeeserver.scala and demandingclient.scala.)
You can test your new servers and clients with the two extra arguments to the Simulation object. For instance, if you run the simulation as
scala Simulation 3 100 12 4 2 0then every second server is a coffee-drinking server (that is, servers B, D, F, etc.). If you run it as
scala Simulation 3 100 12 4 0 5then every fifth client (that is, clients 0, 5, 10, 15, etc.) is a demanding client. And of course you can combine these to have both coffee-drinking servers and demanding clients:
scala Simulation 3 100 12 4 2 5Experiment with different numbers of coffee-drinking servers and demanding clients.