112 p5

CSCI 112: Programming and Algorithms II
Spring 2006
Program 5: Kwik-E-Mart Simulation
Code due: 8am Monday April 10
Grading weight: 5 (this is one of the hardest programs, please start early)
Links: Makefile tests/p5

Overview:

Write a program to simulate the daily operations of a Kwik-E-Mart.

There are two types of customers, those that buy things (shoppers), and those that steal things and money (robbers).

Your program will (1) read in a list of customers (name, shopper/robber, arrival time, number of items to buy/steal), (2) run the simulation. Output will be generated while the simulation is running.

Customers will enter the store at a specified arrival time, spend time shopping for their items, get in line to pay/steal, spend some time paying or stealing money, and then leave the store. When a customer performs an action (arrive in store, get in checkout line, start paying/stealing, leave the store) your program will print a message documenting the customer's action and the current time.

Program Requirements:

Your program must take three command line arguments: number of checkers, name of input file, and name of output file. Your program must check that the number of checkers is 1 or greater, and that the input file and output files can be opened. If there is an error with a command line argument, write to standard error (cerr) the appropriate message from the following list and exit the program:

Error: invalid number of command line arguments.
Error: could not open input file <t01>.
Error: could not open output file <t01.out>.
Error: invalid number of checkers specified.

Time will be represented by a single integer starting at 1.

The input file will be arbitrarily ordered and will have the format:

Homer shopper 3 9
Bart shopper 5 23 
Lisa shopper 2 12
Maggie robber 27 1

Names will be a single string without any spaces.
Type of customer will always be either "shopper" or "robber."
Arrival time will be an integer greater than 0.
Number of items will be an integer greater than 0.

Output:

An output message must be printed every time a customer:

enters the store
finishes shopping
starts checkout
finishes checkout

Your output must be identical to the following. Even the order must be the same. This is the output for the sample input given above executed with 2 checkers. Note that robbers "stole" "from" and shoppers "paid" "to." Also notice that item is sometimes plural (items) and sometimes singular (item).

2: Lisa entered store
3: Homer entered store
5: Bart entered store
12: Homer done shopping
12: Homer started checkout with checker 0
14: Lisa done shopping
14: Lisa started checkout with checker 1
21: Homer paid $27 for 9 items to checker 0
26: Lisa paid $36 for 12 items to checker 1
27: Maggie entered store
28: Bart done shopping
28: Maggie done shopping
28: Bart started checkout with checker 0
28: Maggie started checkout with checker 1
29: Maggie stole $36 and 1 item from checker 1
51: Bart paid $69 for 23 items to checker 0

Use one queue for all the checkers. When taking a customer off of the checker queue, assign the customer to the empty checker with the lowest number.

All items in the Kwik-E-Mart cost $3. The checkers start out with no money in their registers. When a customer buys items from a checker, increment the checkers balance. When a checker is robbed, he gives all his money to the robber.

Customers must shop 1 time unit for each item they buy/steal. For example, if a customer arrives at time 10, and buys 15 items, the customer should not be allowed to start the check-out/steal process until time = 25 (10 + 15).

Customers must spend 1 time unit for each item they buying/stealing performing the check-out/steal process. For example, if a customer is removed from the checker queue and assigned a checker at time = 32 and he is buying/stealing 7 items, he won't be done until time = 39 (32 + 7).

If two (or more) customers arrive at the same time, put them in the arrival queue in the same order they appear in the input file. For example, if Homer arrives at time=10 and Lisa arrives at time=10, if Homer is before Lisa in the input file, Homer should be in front of Lisa in the arrival queue.

Required classes:

class Cust	Stores information about a customer
class Pqueue	Priority queue of Cust *, will use time as the priority

Hints:

There are many ways to implement this assignment. The following hints describe the most straightforward solution.

The file sim.cpp will contain the function main() and run_simulation().

Perform all the input in main(). Read the customers one at a time, create a Cust object for the new customer, and then insert the Cust onto a priority queue ordered by their arrival time (you could call this arrival_q).

Once all the customers have been read and inserted into the arrival queue, call run_simulation(). You will need to pass it the arrival queue, the number of checkers, and an ofstream (to be used for output).

Checkers can be implemented as a pointer to their current Cust. If they are not serving anyone, they can have the value NULL. An array of pointers to Cust can be used to represent all the checkers. A separate array of integers can be used to store the amount of money in a checker's register. Since you don't know how many checkers there are until run time, you cannot create these arrays until run time, and thus it is easier to make this array of checker a local variable:

void run_simulation(Pqueue &arrival_queue, int num_checkers, ostream &os)
{
    Cust *checkers[num_checkers];
    int register_totals[num_checkers];
    // now use loops to initialized all elements of both of these arrays to 0
    ...

}

The body of the simulation should proceed as follows. If you don't follow this order, your output will not be in the correct order:

for (clock = 1; true; clock++)
For all the customers currently being served by a checker that are done at time == clock

print the appropriate message (leaving store)

delete this customer

set the checker to 0 (indicates it has no customer)

For all customers waiting on the queue to enter the store (i.e. those on the arrival_queue) that have an arrival_time == clock

remove them from the arrival_queue

print the appropriate message (entering store)

calculate what time they will be done shopping (done_time = arrival_time + num_items)

place them on the shopping_queue using done_time as priority

If any customers on the shopping_queue are done shopping

remove them from the shopping_queue

print the appropriate message (done shopping)

place them on the checkout_queue (don't need a priority, use the same priority for all customers)

While there is an empty checker and there is a customer on the checker_queue

remove the customer from the checker_queue and assign it to the free checker (always pick the free checker w/the lowest index)

increment/decrement the checker's total cash

calculate the time the customer will be done checking-out/stealing (store this done time in the Cust class)

If there are no more customers waiting on the arrival_queue, the shopping_queue, or the checker_queue and if all the checkers are idle, the simulation is done.

General Requirements:

I will deduct 10 percent if your program does not compile using my Makefile on Jaguar. Thus you must make sure to use the filenames listed below (do not capitalize your filenames), and if you are working on windows, you should compile and test your program on Jaguar before turning it in.

We will grade your program using another program, so if your program does not work exactly as specified below you will lose points.

The first lines of all your files (.h and .cpp) must contain:

// last name, first name
// ecst_username@ecst.csuchico.edu
// 112 Program 5: Kwik-E-Mart Simulator

How to turn in code:

If you download my Makefile, and have your program on a Department machine, you can submit your program by typing:

$ make submit

Look carefully at the output to make sure all the following files were copied:

sim.cpp
pqueue.h
pqueue.cpp
cust.h
cust.cpp

You may submit as many times as you want before the deadline. Once the deadline passes, you will not be able to submit.

You can also just copy (using local cp or remote scp) or sftp the above files into the directory:

/user/projects/csci112/p5/USERNAME

where USERNAME is your ecst username.

See how to turn in assignments for detailed instructions on how to turn in the assignment.

Note: You will not be able to access this directory once the deadline has passed.

Late assignments:

If you do not finish by the deadline (see top for the deadline), you may turn your assignment in up to 24 hours late. You will lose 15% for turning your assignment in 1-24 hours late.

If you are working on the department machines and you have a copy of my makefile, you can submit your late files using

$ make submit_late

You can also copy your files into the following directory:

/user/projects/csci112/p5_late/USERNAME

Assignments will not be accepted if more than 24 hours late.