Overview

Many languages include “enhanced” array classes that include features of both arrays and linked-lists. The Java ArrayList class and the Vector class from the C++ standard template library are examples. For this project, you will constructe a Sequence class that supports random access like an array, but also allows dynamic insertion and removal of new elements.

The Sequence Class

Your Sequence Class should be implemented as a doubly-linked list. Here are a few example of how your Sequence class will be used:

Sequence mySequence(5); // create a Sequence of length 5 (indexes 0 through 4)

mySequence[0] = 1;

mySequence[1] = 2;

mySequence[4] = 3;

After executing this code block, your sequence would appear as follows:

Note: Sequence locations with a content of ? can contain any value.

The push_back() member function grows the Sequence by adding values to the end. The call mySequence.push_back(20) produces:

We can also grow the Sequence using the insert() member function. The first argument to insert is the index (position) at which to insert the new data. The second argument is the data to insert. The data is inserted at the designated position, and the remaining items in the sequence are shifted to the right. Starting with the previous Sequence, mySequence.insert(1, 30) would produce:

We can reduce the size of the Sequence using pop_back(), which removes the last element of the Sequence, or erase(). The call mySequence.erase(3,2) removes 2 items starting at position 3, producing:

Required Member Functions

You will be provided a starting template for your sequence, implemented in the files Sequence.h and Sequence.cpp. You must implement each of the functions defined in these files. A full description of each function is given in the header file (Sequence.h).

Error Handling

Your solution should throw an exception if a user attempts to access an item outside of the bounds of the sequence in any member function. For example, each of the following calls after the Sequence of length three is created should throw an exception:

Sequence mySequence(3);                  // mySequence has elements 0 through 2

mySequence[3] = 100;                         // Error: There is no element 3

cout << mySequence[-1] << endl;      // Another error

mySequence.erase(2,5);                     // Error: Tries to erase non-existent elements

You can throw a C++ exception using the following syntax:

#include <exception>

Sequence::value_type& Sequence::operator[]( index_type position )

{

 if ( index position is invalid ) {

 throw exception();

 }

 ...

}

The Test Harness

For this project (only), you will be provided with the entire test harness that I will use to test your code.

safari-2

safari-4

sequence-2