In this lab you will implement a templated C++ linked list and then use that linked list to simulate the behavior of shoppers in a grocery store, comparing the behavior of two scenarios described below. To get started, run update35 from a computer science lab computer. The program update35 will create a cs35/labs/04 directory in your CS home directory, and the program handin35 will subsequently submit files from that directory.

This lab will require much more time than the earlier labs in the course. Because you will use many pointers in this lab, you will probably have more trouble debugging your program than in labs 01 or 02.

You will earn reasonable partial credit for this lab if you complete and test your linked list implementation. For full credit you also must complete at least one of the simulated shopping scenarios; to do that, you should expect to have already completed and tested your linked list before the end of the Monday night ninja session.

In a normal store there are two possible strategies for queuing shoppers to check out their purchases:

1. Have a distinct line for each checkout register. To check out through a given register, a customer must wait in that register's checkout line.
2. Have one checkout line for the entire store, regardless of the number of checkout registers. When a customer reaches the front of the line, they may proceed to the first available checkout register.

It is not immediately clear which strategy is superior. In fact, the true answer is complex and depends on various reasonable assumptions about the queues and shopper behavior. Your goal in this lab is to determine which strategy is better given a set of assumptions described below.

We will only consider stores with two checkout registers. For both strategy scenarios, we will assume that all shoppers enter the store simultaneously, but each shopper finishes shopping at some time specified by the user input (that shopper's timeDoneShopping). For each shopper, the user also specifies how much time that shopper spends at the checkout register after they reach the register (the timeSpentAtRegister). A checkout line can be arbitrarily long, but only one shopper is at each register at a time.

In the one-line scenario, each shopper's behavior is naturally defined: each shopper shops until her specified timeDoneShopping. She then gets in the only checkout line. When she reaches the front of the line she waits until there is an available register, then proceeds to that register. She then waits at that register for her timeSpentAtRegister, at which point she can exit the store.

The two-line scenario is similar, except that each shopper must choose one of the two lines when she is done shopping. At timeDoneShopping, she gets in the checkout line that currently contains the fewest shoppers, without any information about how long those shoppers will spend at the register. After all, this can be hard to predict. ("Pardon me, sonny, I think I have a coupon here, somewhere...") If both checkout lines are empty and one of the registers is available, the shopper can go straight to the available register. If both lines otherwise contain the same number of shoppers, the shopper always gets in the line for register 1.

At the conclusion of the simulation, your program should specify the total time spent in line for all shoppers. This total time should not include the time each shopper spent shopping or the time each shopper spent at the checkout register itself.

We have provided a templated List interface, matching the one given in lecture. You must define and implement a LinkedList class that implement the List interface, without altering the List interface. We've also provided a Shopper class which provides an interface for setting and accessing basic information about each shopper.

After you have completed and tested your LinkedList you should write two separate programs, one-line and two-lines for the one-line and two-line shopping simulations, respectively. Both of those programs should accept the same input format, which consists of:

• A single line specifying the number of total shoppers in the store.
• For each shopper, a single line with two numbers, separated by a space. The first number should be that shopper's timeDoneShopping and the second number is that shopper's timeSpentAtRegister.

You may assume that at least two shoppers enter the store, that the user enters shoppers in increasing order by their timeDoneShopping and that all times are positive integers. You do not need to sort or otherwise validate user input.

Here is an example execution of the two shopping simulations:

  $ ./one-line
  How many shoppers will enter the store?  4

  Please enter the time done shopping and time spent at register
  for the 4 shoppers: 
  5 8
  12 12
  22 10
  23 19

  Total time spent waiting:  1

  $ ./two-lines
  How many shoppers will enter the store?  4

  Please enter the time done shopping and time spent at register
  for the 4 shoppers: 
  5 8
  12 12
  22 10
  23 19

  Total time spent waiting:  9

You should always program incrementally such that you can test your work as you go. Here is one suggested strategy:

1. Start by implementing the LinkedListNode class -- which consists of a constructor, destructor and simple access and update functions -- then test your implementation using a test program or gdb.
2. Implement the LinkedList constructor, then either implement a print() method or use gdb to verify that your list is correctly constructed.
3. Implement one of insertAtHead or insertAtTail. Then implement getSize, isEmpty, peekHead and peekTail. Use print or gdb to verify correctness.
4. Implement getItem and verify.
5. Implement removeHead or removeTail and verify. Then implement the other function and verify.
6. Implement the destructor. Carefully consider every possible way that your class might allocate memory on the heap, and be sure that there is a corresponding call to delete for each call to new.

At this point you should have a complete working LinkedList class whose behavior matches the ArrayList from lecture (except that the example ArrayList has a capacity of just 10 items, whereas your LinkedList should have no artificial capacity limits). Write a small test program to verify that your LinkedList matches the ArrayList's behavior.

You should not under any circumstances begin the shopping simulation until you have thoroughly verified the correctness of your LinkedList class. Any bugs in your LinkedList class will hinder progress on the shopping simulation.

Work on just one shopping simulation at a time. Do not consider starting the second shopping simulation until your first simulation is complete. I have no recommendation about which scenario -- one line or two -- is easier. After you have completed and tested one scenario, the second scenario is much easier to complete as it should use the same input format and similar representations for the shoppers, lines, and register data.

• Do not modify the List interface.
• Linked lists are a classic computer science topic. As you work on this lab, you should actively avoid reading code or pseudocode for linked lists from the web or other sources.
• Although your LinkedList must be an independent List implementation using linked nodes, you can use the ArrayList to test the behavior of your LinkedList class. For a given set of List operations, the external behavior (as seen through the List interface) of your LinkedList should be identical to the ArrayList.
• Each checkout line can easily be represented using a List: to add a shopper to the end of the line, use that line's insertAtTail() function. To move a shopper from the front of the line to a checkout register, remove the shopper from the list using the removeHead() function.
• We also recommend using a List to represent all shoppers currently still shopping. At the beginning of the program read all shopper's input, immediately construct each shopper, and place every shopper into a single List using insertAtTail(). Because you may assume that the shoppers are in order of their timeDoneShopping, you can check when the next shopper is done shopping using the list's peekHead() method.
• Represent time as an int starting at 0. At each time, perform all operations that should occur at that time. (Check the queue of shoppers to see if any new shoppers are done shopping. Check each register to see if its current shopper is done at the register. For each available register, check the appropriate queue to see if any shoppers are waiting in line for that register.) After you've simulated all events for the current time, increment the time and continue the simulation until all shoppers have exited the registers. This is a discrete event simulator, not a real-time simulator. You should not attempt to simulate real time or use any real time functions in your simulation.
• When a shopper enters a checkout register, call the Shopper's setTimeEnteredRegister() function with the current time. You can then use the getTimeSpentInLine() and getTimeDoneAtRegister() accessors on that shopper to simplify your implementation.
• Your implementation might be simpler if you design and implement a CheckoutRegister class that manages the work for a single checkout register.

Once you are satisfied with your program, hand it in by typing handin35 at the unix prompt.

You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them.