1- Introduction:

In this lab you will implement a singly-linked list version of the sequence (template) class.

2- Files: Create the .hpp le for a template class called sequence and associated unit tests (sequence tests.cpp).

3- Unit-tests Try to force yourself to work test rst through this class. That is, write a test, verify that it fails, make it pass. Dont write code in your sequence class until you have a test that needs it. Begin by writing a test that ensures that a sequence is empty when it is rst created. Next write a test that checks that adding an item increases the size of the sequence. Keep moving forward in small steps. See the sections below for lists of required methods and instance variables.

4- Instance variables: You will need the following instance variables (ValueType below is intended to be the template type parameter used when this class is dened):

node head head pointer for the linked list

std :: size _t used number of nodes in the linked list (faster than computing size from list)

5- Operations:

Implement the operations below. Use assert to check preconditions. Note: ValueType below is intended to be the template type parameter used when this class is dened. Also,each of these must be template methods with ValueType as the template parameter.

sequence() construct an empty sequence.

std :: size _t size() const return the number of items stored in the sequence

ValueType& at(std :: size _t i) (precondition: i < size()) return the item at position i in the sequence. Note that sequence indices start at zero (just like arrays).

ValueType&operator[](std:: size _t i) return the item at position i in the sequence (without bounds check). Note that sequence indices start at zero (just like arrays).

bool empty() const return true if this sequence is empty, false otherwise.

void add(const ValueType& value) add the specied value to the end of the sequence

void insert (std :: size _t index, const ValueType& value)

(precondition: index <= size()) insert the specied value at the specied index, shifting values to higher indexes if needed. If index == size this operation is the same as add.

void remove(std:: size _t index) (precondition: index < size()) remove the value at the specied index, shifting other values down as needed.

the big 5 implement the copy constructor, move constructor, copy assignment operator, move assignment operator, and destructor

sequence operator +(const sequence& s1, const sequence& s2)

free function (you may implement this as a member function if you prefer) return a new sequence that is the result of appending s2 on to the end of s1

void operator +=(const sequence& other) append other onto the end of this sequence

sequence::iterator begin() return a forward iterator positioned at the beginning of the sequence. Note: You will have to create the iterator class your self.

sequence::iterator end() return an iterator positioned one past the end of the sequence.

void erase(sequence::iterator it) remove the item referenced by the iterator. This method must not loop over the array so your iterator class may need to be modied to support an efcient erase method.