Course Home | Course Policies | Homework | Lab Open Hours | Programming | Labs | Schedule & Lecture Notes

Programming Assignment 2
Web History

Due: Saturday, October 2, 11:59pm

Please see the programming webpage for details about the programming environment for this course, guidelines for programming style, and details on electronic submission of assignments.

The files you may need for this assignment can be downloaded here.

Collaboration Policy

For this assignment, you will work individually and submit your own work.

Please make sure you adhere to the policies on academic integrity in this regard.


Contents:


Overview

Web browsers commonly allow you to navigate through a "history" of web pages that have previously been visited. The mechanism is somewhat like a stack, in that the most recently visited pages are at the top of the history and revisited when the "back" button is pressed.

However, the history does not necessarily have unbounded capacity. In reality, there may exist a fixed limit on the size of the history. The issue arises as to what should happen when the capacity is exhausted and a new item is pushed onto the stack. One possibility is to throw an exception. But this is not how a Web browser behaves. If it only has room to save 50 pages in its history and yet you visit more pages, it will make room in the history for a new page by throwing away the page that is on the very bottom of the history (i.e., the least recently visited page). The formal Stack interface does not help, as it gives us no way to directly access or remove the object on the bottom of the stack.

In this assignment, we define a new ADT that we call a LeakyStack. The interface for a LeakyStack is very similar to the interface given for a Stack. However in the case when the capacity is exhausted, a call to push will result in the placement of the new page at the expense of the loss of the least recently accessed page. We formalize this interface as an abstract class definition, provided online in file LeakyStack.h.

/**
 * Interface for a leaky stack: A collection of objects that are inserted
 * and removed according to the last-in first-out principle, but with
 * overflow handled by the removal of the least-recently accessed item.
 */
class LeakyStack {
 public:
  /** Returns the number of objects in the stack.
   *  @return number of elements
   */
  int size() const;

  /** Determines if the stack is currently empty.
   *  @return true if empty, false otherwise.
   */
  bool empty() const;

  /** Returns a const reference to the top object in the stack.
   *  Throws a runtime_error if the stack is empty.
   * @return reference to top element
   */
  const string& top() const;

  /** Inserts an object at the top of the stack. If the stack
   *  is already at capacity, the oldest element will be lost.
   *  @param the new element
   */
  void push(const string& elem); 

  /** Removes the top object from the stack.
   *  Throws a runtime_error if the stack is empty.
   */
  void pop();
};

Your Task

For this assignment, you will be required to give two different implementations for the LeakyStack interface, as described below. We will provide you with sample initial files for these classes.

Simplifications

To make things a bit easier for this assignment,


Files We Are Providing

All such files can be downloaded here.


Use of the Driver

WebHistoryDriver is a text-based, menu-driven program for testing your LeakyStack implementations. The menu allows you to call any combination of LeakyStack methods. You may even call the constructors for either of the two implementations anytime you want to restart with a different capacity.

By default, the program takes input from the keyboard. However the driver has an optional feature which allows it to read input from a file rather than from a keyboard. The file should have the identical characters which you would use if you were typing them yourself on the keyboard. This feature simply allows you to test and retest your program on a particular input without having to retype the input each time you want to run the program. It is also convenient at times when running with a debugger to have the input read from a file rather than from the keyboard. If the program reaches the end of the file without exiting, then it will revert back to reading input from the keyboard for the remainder of the program.

To use this feature, you must specify the exact filename (including any suffix), as a single argument at runtime, using a syntax such as

./WebHistoryDriver inputfile

Black-Box, Unit Testing

Part of developing good software is also knowing how to perform meaningful testing of your software. Our hypothetical motivation for this data structure was that it might be used in the larger context of a web browser. One approach to testing would be to wait until the entire project were completed and then to test the final result. Of course, if the browser history were not operating properly at that point, we would have to wonder whether the problem was due to an errant implementation of the data structure, to an errant use of a well-written data structure, or some other problem. Rather than relying on a test of the entire end product, a useful approach is to make sure that each individual piece works in isolation. This is called unit testing. So for this assignment, you will develop a test plan for evaluating the correctness of the LeakyStack implementations without actually considering the larger application (in fact, we will not actually be writing any such hypothetical web browser). To perform unit testing of this data structure, you will use the provided driver which allows you to individually call any of the public methods supported by the data structure.

There is another issue we wish for you to consider when developing test plans. Often, testing is performed in close coordination with an examination of source code. For example, we may write some code or view some code, and then try to test that particular chunk of code. There is an inherent danger in relying only on such tests. In particular, if the tests are based on the same flow of thoughts as (errant) code, we are more likely to forget to test for a particular combination of events that were not considered by the code. The practice of "black box" testing is to design a set of tests based purely on the formal specifications for a data structure, but without actually seeing the source code.

On this assignment, we will have you develop a black-box unit test plan for LeakyStack implementations. Specifically, you must submit a plain text file named "inputfile" which will be used to test other students' implementations. The goal is to create test input which causes as many as possible of the other students' programs to fail in some way. Because our execution of student tests will be automated, you must make sure that your "inputfile" strictly adheres to the file format which is expected by the text-based driver, WebHistoryDriver, described earlier. Your file may use at most 100 commands. If your input file contains more than the prescribed number of commands, we will simply truncate the end of the file. In order to make sure that your inputfile follows the proper format, we strongly recommend that you run your program on your inputfile to make sure it is accepted by the driver.

Here is a sample input file, appropriately formatted.


Files to Submit


Grading Standards

The assignment is worth 10 points. Eight points will be awarded based on our own evaluation of your assignment and the readme file. One point will be based on how well your test input checks both your and the other students' implementations.

The final point will be added based on an early check-in with the professor; you will be expected to show at least 25 lines of (new) code in by Tuesday, Sept. 25. This may be done via email, after class, in normal office hours, or at a different time by appointment, but it must be done by the end of the day on Tuesday.


Hints Regarding Modular Arithmetic

When dealing with an array in a circular fashion, there are many possible ways for adjusting indicies as they "wrap around" the ends of the array. The text chooses to use modular arithmetic (the "%" operator in C++). Please note that its precedence is equivalent to multiplication and division, and therefore the expression a+b%c+d is evaluated as a+(b%c)+d by default. Also, the results of a%b is system dependent if one of the operands is negative.