Programming Assignment 1: Discrete Event Simulation

Due: 11:30 am, Friday, April 25

The purpose of this assignment is to continue your work with linked lists and learn a little bit about how discrete time simulations work. The scenario to be simulated is a set of users (1 through NumUsers) who send and receive email messages.

The Mail_Queue

Each user has a list called a Mail_Queue, but it is not a standard FIFO queue; it is a little unusual. Messages that come to a user will be tagged as NORMAL (priority=1), RUSH (priority=2), and TOP_PRIORITY (priority=3). NORMAL messages will be added to the end of the Mail_Queue. RUSH messages will be added from the front of the Mail_Queue, but after all other RUSH messages already on that Mail_Queue. Finally, TOP_PRIORITY messages are added to the very front of the Mail_Queue. As you can see, there are several different methods for entering a new message. Note that all of them can be done quite efficiently. There will also be a method needed for removing a message from a Mail_Queue and reading its contents. Users remove messages only from the very front of the Mail_Queue.

The Simulator

You are going to simulate the various users sending messages to one another, reading those messages, and printing them to show they were read. In order to do this, we need an event generator and an Event_Queue data structure. An event will have the following attributes:

event_id: an integer identifier for any event
event_type: a char S representing sending event or a char R representing receiving event
sender_id: the integer user_id of the sending user for sending events
receiver_id: the integer user_id of the receiving user for any event
time: the time (integer between 0 and infinity) at which the event is to occur for any event
priority: the integer priority of the message as described above for sending events
message: a sentence up to 80 chars , the text of the message for sending events

Note that sending events use all of the fields, but receiving events only need a few, because the action required of a receiver is just to read, print, and delete his/her first message. However all fields are available in all events.

There will be several different event files for testing your program. You should deal with different numbers of users and events. The format of a 5-event 2-user file is as follows:

event_id     event_type     time     receiver_id     sender_id     priority     message
1                     R              670          20
2                     S              652          10                 10             1         Assignments are so easy
3                     R              946          10
4                     S              362          10                 20             1         Midterm is coming soon
5                     S              561          20                 10             3         CSE373 is interesting

Download more event files: 10E-1U 20E-2U 100E-3U 200E-4U. Running EventGenerator.java, you can generate any event files by specifying the numbers of events and users. There is a Java program ReadEvents.java, and a C++ version ReadEvents.cpp, illustrating how to read each field in an event from an event file that is given as a command line argument, do some computation, and output formatted events to a file. If you are not familiar with I/O, please read the example carefully.

What You Do

You will design and implement the discrete event simulator. It will create the Event_Queue and populate it with the events that you read from the event file. Again, this is called a queue, but it is to be kept in ascending order of the times of the events. Thus an event at time 34 will come before an event at time 55, and so on. The events will not come to you in order; they are generated randomly. So you will have to enter them in the Event_Queue so that the queue is always maintained in order of time. If two events have the same timestamps, the one with smaller event_id should have a higher priority.

The job of the simulator is to remove events from the Event_Queue and simulate their executions. For a sending event, the simulator must invoke the proper methods to put a message on the Mail_Queue of the specified receiver in the right position. For a receiving event, the simulator must read and remove the first message from the queue of the receiver and print its time, receiver_id, sender_id, priority and text message to a result file mails.txt (one receiving event each line). If there are no message in its Mail_Queue, output "No recent messages" to mails.txt. After simulating an event, the simulator just goes right back to the Event_Queue to get another one. It stops when the Event_Queue becomes empty.

The only input to your program is an event file, specified by command line arguments. Do NOT prompt for any other user-input.
The only output from your program is mails.txt. Do NOT output anything else.

For example, given the 5-event 2-user file above, the output mails.txt should be like:

time receiver_id sender_id priority message

561 20 10 3 CSE373 is interesting

362 10 20 1 Midterm is coming soon

Grading

1. Compilable. Any program that cannot compile will receive a low grade.

2. Correctness, based on the output file mails.txt, which will be generated by running your program.

3. Clearness of code, good coding style, simpleness, etc.

4. Readme.txt, explaining how you implement the Mail_Queue, the Event_Queue, and the simulator. Also mention how you implement your insertion routines and in which files these insertions are. The insertions into the Mail_Queue should be done in O(1) time and you must do it the most efficient way possible. In your code, please label the insertions.

5. Testing: we run your program with command line arguments, using the above 4 files and 2 more files 20E-2U-2, 100E-3U-2.
The results are: 10E-1U-mails 20E-2U-mails 100E-3U-mails 200E-4U-mails 20E-2U-2-mails, 100E-3U-2_mails

What and how to turn in

All source files should be turned in online.

Java programmers: Make sure your program is compatible with Java2 SDK 1.4.x. Turn in only .java source files. You must include your main method in Simulator.java. Go to http://www.cs.washington.edu/education/courses/373/03sp/homework/prj1/turnin-java.html

C++ programmers: Your programs are strongly suggested to be compatible with MSVC 6.0. By default, your program will be compiled by MSVC 6.0 compiler at turn-in time. If your program only works on Linux/Unix, you must include detailed information in Readme.txt showing how to compile and run your program. Turn in only .cpp and .h files. You must include your main function in Simulator.cpp.
Go to http://www.cs.washington.edu/education/courses/373/03sp/homework/prj1/turnin-cpp.html