Bonus assignment: url stack

The bonus lab exercise is to be submitted electronically by 10 a.m. April 8th, and will not be explicitly covered in labs or lectures.

The submission mechanism is detailed below, and must be followed to obtain credit for the lab.

The exercise will be marked out of 10, and can be substituted for your lowest mark of the six regular lab assignments.

Absolutely no late submissions will be accepted for the bonus assignment. Make sure you submit before the deadline if you want credit for the assignment.


Exercise details:

We all use the back/forward buttons on browsers on a regular basis, this assignment implements a possible stack-based data structure for them.

The data structure is defined in the urlStack class, in the urlStack.h file shown below. Your task is to implement all the methods for the class, conforming to the definitions and comments in the .h file.

Note that the header file specifies the underlying implementation uses an array based, wrap-around approach (much like the circular buffers from labex3). You MUST follow that approach to receive credit for the assignment.

All of your code is to be in a single file, named urlStack.C, which includes and uses the urlStack.h file.

I will be using my own copy of urlStack.h for compiling and testing your code and using my own test program for the class, so make sure it conforms exactly to the specifications.

A test program is provided in file bonus.C if you want to try out your implementation. Compile using
g++ -Wall bonus.C urlStack.C -o bonus

#ifndef URLSTACK_H
#define URLSTACK_H

#include 
using std::string;

// class urlStack
// ==============
// class to store a stack of urls as strings,
// allowing the caller to 
//    push urls on top (e.g. when going to a new page),
//    pop top url off (e.g. for back button),
//    unpop a url (e.g. for a forward button,
//    peek deeper in the stack (e.g. for retrieving history),
//    clear the stack (e.g. to clear history),
//    and get the current size of the stack
//
// the class constant MaxURLs specifies maximum stack depth,
// if more urls are pushed onto the stack then old ones
//    fall off the bottom (i.e. a history limit)      
class urlStack {
   private:
      // the maximum number of urls that can be stored 
      //    (i.e. the size of the urls array)
      static const long MaxURLs = 5;

      // array holding the urls
      string *urls;

      // current number of urls stored in the array
      long currentSize;

      // array index of the top and bottom stack items,
      // implemented as a wrap-around array (i.e. both
      //    top and bottom can be incremented, wrapping
      //    around to position 0 if the hit MaxURLs)
      // both are -1 whenever the stack is empty
      long    top, bottom;

   public:

      // initialize an empty url stack:
      //    allocate the urls array to hold MaxURLs strings,
      //    initialize all the strings to "",
      // and initialize top, bottom, and currentSize 
      urlStack();

      // deallocate the urls array
      ~urlStack();

      // clear all the current stack contents, i.e.
      //    reset all the strings in the urls array to "",
      // and reset top, bottom, and currentSize
      //    to their starting values 
      void clear();

      // return currentSize
      long getSize();

      // if n is in the range 0..currentSize-1
      //    return the nth url from the top of the stack
      // i.e. peek(0) returns the top url,
      //    peek(currentSize-1) returns the bottom url
      // if n is out of range return ""
      string peek(long n);

      // if the stack is empty return "", otherwise
      //    pop the top url off the stack and return it
      string pop();

      // if the stack is full discard the bottom url to create space
      //    then push the new url on the top of the stack
      // otherwise simply push the new url on top
      void push(string u);

      // if the stack isn't full, and the url one spot "above"
      //    the current top of the stack isn't empty (""), 
      // then adjust currentSize and top to include that url
      //    as the new top, returning a copy of the url
      // otherwise leave the stack unchanged and return ""
      string unpop();
};

#endif


Submission mechanism

All the urlStack methods must be in file urlStack.C
(correct spelling and capitalization is essential for the submission to work correctly).

To submit the assignment, cd to the directory that contains your urlStack.C file and type the following command:

   /home/faculty/wesselsd/bin/submit  161  urlStack.C
Note that each submission overwrites any previous submission you have made.


Marking guidelines:

Marks will be based on:

Code standards:

The submission must follow the code standards for labex2,