The purpose of this lab is to help reinforce linked list concepts in C++. Specifically, the lab to repeat the "sequence" lab except to use a linked list. Note that there is no upper bound on the size of the sequence. You need to use author's header file and test file. sequence3.h and sequence_exam3.cpp and the node1.h and node1.cpp files. You will be provided with a partially implemented sequence3.cpp. Your assignment includes:Implement attach and remove_current functions.

// FILE: node1.h

// PROVIDES: A class for a node in a linked list, and list manipulation

// functions, all within the namespace main_savitch_5

//

// TYPEDEF for the node class:

// Each node of the list contains a piece of data and a pointer to the

// next node. The type of the data is defined as node::value_type in a

// typedef statement. The value_type may be any

// of the built-in C++ classes (int, char, ...) or a class with a copy

// constructor, an assignment operator, and a test for equality (x == y).

//

// CONSTRUCTOR for the node class:

// node(

// const value_type& init_data = value_type(),

// node* init_link = NULL

// )

// Postcondition: The node contains the specified data and link.

// NOTE: The default value for the init_data is obtained from the default

// constructor of the value_type. In the ANSI/ISO standard, this notation

// is also allowed for the built-in types, providing a default value of

// zero. The init_link has a default value of NULL.

//

// NOTE:

// Some of the functions have a return value which is a pointer to a node.

// Each of these functions comes in two versions: a non-const version (where

// the return value is node*) and a const version (where the return value

// is const node*).

// EXAMPLES:

// const node *c;

// c->link( ) activates the const version of link

// list_search(c,... calls the const version of list_search

// node *p;

// p->link( ) activates the non-const version of link

// list_search(p,... calls the non-const version of list_search

//

// MEMBER FUNCTIONS for the node class:

// void set_data(const value_type& new_data)

// Postcondition: The node now contains the specified new data.

//

// void set_link(node* new_link)

// Postcondition: The node now contains the specified new link.

//

// value_type data( ) const

// Postcondition: The return value is the data from this node.

//

// const node* link( ) const <----- const version

// node* link( ) <----------------- non-const version

// See the note (above) about the const version and non-const versions:

// Postcondition: The return value is the link from this node.

//

// FUNCTIONS in the linked list toolkit:

// size_t list_length(const node* head_ptr)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: The value returned is the number of nodes in the linked

// list.

//

// void list_head_insert(node*& head_ptr, const node::value_type& entry)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: A new node containing the given entry has been added at

// the head of the linked list; head_ptr now points to the head of the new,

// longer linked list.

//

// void list_insert(node* previous_ptr, const node::value_type& entry)

// Precondition: previous_ptr points to a node in a linked list.

// Postcondition: A new node containing the given entry has been added

// after the node that previous_ptr points to.

//

// const node* list_search(const node* head_ptr, const node::value_type& target)

// node* list_search(node* head_ptr, const node::value_type& target)

// See the note (above) about the const version and non-const versions:

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: The pointer returned points to the first node containing

// the specified target in its data member. If there is no such node, the

// null pointer is returned.

//

// const node* list_locate(const node* head_ptr, size_t position)

// node* list_locate(node* head_ptr, size_t position)

// See the note (above) about the const version and non-const versions:

// Precondition: head_ptr is the head pointer of a linked list, and

// position > 0.

// Postcondition: The pointer returned points to the node at the specified

// position in the list. (The head node is position 1, the next node is

// position 2, and so on). If there is no such position, then the null

// pointer is returned.

//

// void list_head_remove(node*& head_ptr)

// Precondition: head_ptr is the head pointer of a linked list, with at

// least one node.

// Postcondition: The head node has been removed and returned to the heap;

// head_ptr is now the head pointer of the new, shorter linked list.

//

// void list_remove(node* previous_ptr)

// Precondition: previous_ptr points to a node in a linked list, and this

// is not the tail node of the list.

// Postcondition: The node after previous_ptr has been removed from the

// linked list.

//

// void list_clear(node*& head_ptr)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: All nodes of the list have been returned to the heap,

// and the head_ptr is now NULL.

//

// void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)

// Precondition: source_ptr is the head pointer of a linked list.

// Postcondition: head_ptr and tail_ptr are the head and tail pointers for

// a new list that contains the same items as the list pointed to by

// source_ptr. The original list is unaltered.

// void list_piece(

// const node* start_ptr, const node* end_ptr,

// node*& head_ptr, node*& tail_ptr

// )

// Precondition: start_ptr and end_ptr are pointers to nodes on the same

// linked list, with the start_ptr node at or before the end_ptr node

// Postcondition: head_ptr and tail_ptr are the head and tail pointers for a

// new list that contains the items from start_ptr up to but not including

// end_ptr. The end_ptr may also be NULL, in which case the new list

// contains elements from start_ptr to the end of the list.

//

// DYNAMIC MEMORY usage by the toolkit:

// If there is insufficient dynamic memory, then the following functions throw

// bad_alloc: the constructor, list_head_insert, list_insert, list_copy,

// list_piece.

#ifndef MAIN_SAVITCH_NODE1_H

#define MAIN_SAVITCH_NODE1_H

#include // Provides size_t and NULL

namespace main_savitch_5

{

class node

{

public:

// TYPEDEF

typedef double value_type;

// CONSTRUCTOR

node(

const value_type& init_data = value_type( ),

node* init_link = NULL

)

{ data_field = init_data; link_field = init_link; }

// Member functions to set the data and link fields:

void set_data(const value_type& new_data) { data_field = new_data; }

void set_link(node* new_link) { link_field = new_link; }

// Constant member function to retrieve the current data:

value_type data( ) const { return data_field; }

// Two slightly different member functions to retreive

// the current link:

const node* link( ) const { return link_field; }

node* link( ) { return link_field; }

private:

value_type data_field;

node* link_field;

};

// FUNCTIONS for the linked list toolkit

std::size_t list_length(const node* head_ptr);

void list_head_insert(node*& head_ptr, const node::value_type& entry);

void list_insert(node* previous_ptr, const node::value_type& entry);

node* list_search(node* head_ptr, const node::value_type& target);

const node* list_search

(const node* head_ptr, const node::value_type& target);

node* list_locate(node* head_ptr, std::size_t position);

const node* list_locate(const node* head_ptr, std::size_t position);

void list_head_remove(node*& head_ptr);

void list_remove(node* previous_ptr);

void list_clear(node*& head_ptr);

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);

}

#endif

_________________________________________________________________________

// FILE: node1.cxx

// IMPLEMENTS: The functions of the node class and the

// linked list toolkit (see node1.h for documentation).

// INVARIANT for the node class:

// The data of a node is stored in data_field, and the link in link_field.

#include "Node.h"

#include // Provides assert

#include // Provides NULL and size_t

using namespace std;

namespace main_savitch_5

{

size_t list_length(const node* head_ptr)

// Library facilities used: cstdlib

{

const node *cursor;

size_t answer;

answer = 0;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))

++answer;

return answer;

}

void list_head_insert(node*& head_ptr, const node::value_type& entry)

{

head_ptr = new node(entry, head_ptr);

}

void list_insert(node* previous_ptr, const node::value_type& entry)

{

node *insert_ptr;

insert_ptr = new node(entry, previous_ptr->link( ));

previous_ptr->set_link(insert_ptr);

}

node* list_search(node* head_ptr, const node::value_type& target)

// Library facilities used: cstdlib

{

node *cursor;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))

if (target == cursor->data( ))

return cursor;

return NULL;

}

const node* list_search(const node* head_ptr, const node::value_type& target)

// Library facilities used: cstdlib

{

const node *cursor;

for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))

if (target == cursor->data( ))

return cursor;

return NULL;

}

node* list_locate(node* head_ptr, size_t position)

// Library facilities used: cassert, cstdlib

{

node *cursor;

size_t i;

assert (0 < position);

cursor = head_ptr;

for (i = 1; (i < position) && (cursor != NULL); i++)

cursor = cursor->link( );

return cursor;

}

const node* list_locate(const node* head_ptr, size_t position)

// Library facilities used: cassert, cstdlib

{

const node *cursor;

size_t i;

assert (0 < position);

cursor = head_ptr;

for (i = 1; (i < position) && (cursor != NULL); i++)

cursor = cursor->link( );

return cursor;

}

void list_head_remove(node*& head_ptr)

{

node *remove_ptr;

remove_ptr = head_ptr;

head_ptr = head_ptr->link( );

delete remove_ptr;

}

void list_remove(node* previous_ptr)

{

node *remove_ptr;

remove_ptr = previous_ptr->link( );

previous_ptr->set_link( remove_ptr->link( ) );

delete remove_ptr;

}

void list_clear(node*& head_ptr)

// Library facilities used: cstdlib

{

while (head_ptr != NULL)

list_head_remove(head_ptr);

}

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)

// Library facilities used: cstdlib

{

head_ptr = NULL;

tail_ptr = NULL;

// Handle the case of the empty list.

if (source_ptr == NULL)

return;

// Make the head node for the newly created list, and put data in it.

list_head_insert(head_ptr, source_ptr->data( ));

tail_ptr = head_ptr;

// Copy the rest of the nodes one at a time, adding at the tail of new list.

source_ptr = source_ptr->link( );

while (source_ptr != NULL)

{

list_insert(tail_ptr, source_ptr->data( ));

tail_ptr = tail_ptr->link( );

source_ptr = source_ptr->link( );

}

}

}

_______________________________________________________________________________

// FILE: sequence3.h

// CLASS PROVIDED: sequence (part of the namespace main_savitch_5)

// This is the header file for the project described in Section 5.4

// of "Data Structures and Other Objects Using C++"

// This is called "sequence3" because some students already implemented

// sequence1 (with a fixed array) and sequence2 (with a dynamic array).

//

// TYPEDEFS and MEMBER CONSTANTS for the sequence class:

// typedef ____ value_type

// sequence::value_type is the data type of the items in the sequence. It

// may be any of the C++ built-in types (int, char, etc.), or a class with a

// default constructor, an assignment operator, and a copy constructor.

//

// typedef ____ size_type

// sequence::size_type is the data type of any variable that keeps track of

// how many items are in a sequence.

//

// CONSTRUCTOR for the sequence class:

// sequence( )

// Postcondition: The sequence has been initialized as an empty sequence.

//

// MODIFICATION MEMBER FUNCTIONS for the sequence class:

// void start( )

// Postcondition: The first item on the sequence becomes the current item

// (but if the sequence is empty, then there is no current item).

//

// void advance( )

// Precondition: is_item returns true.

// Postcondition: If the current item was already the last item in the

// sequence, then there is no longer any current item. Otherwise, the new

// current item is the item immediately after the original current item.

//

// void insert(const value_type& entry)

// Postcondition: A new copy of entry has been inserted in the sequence

// before the current item. If there was no current item, then the new entry

// has been inserted at the front of the sequence. In either case, the newly

// inserted item is now the current item of the sequence.

//

// void attach(const value_type& entry)

// Postcondition: A new copy of entry has been inserted in the sequence after

// the current item. If there was no current item, then the new entry has

// been attached to the end of the sequence. In either case, the newly

// inserted item is now the current item of the sequence.

//

// void remove_current( )

// Precondition: is_item returns true.

// Postcondition: The current item has been removed from the sequence, and

// the item after this (if there is one) is now the new current item.

//

// CONSTANT MEMBER FUNCTIONS for the sequence class:

// size_type size( ) const

// Postcondition: The return value is the number of items in the sequence.

//

// bool is_item( ) const

// Postcondition: A true return value indicates that there is a valid

// "current" item that may be retrieved by activating the current

// member function (listed below). A false return value indicates that

// there is no valid current item.

//

// value_type current( ) const

// Precondition: is_item( ) returns true.

// Postcondition: The item returned is the current item in the sequence.

//

// VALUE SEMANTICS for the sequence class:

// Assignments and the copy constructor may be used with sequence objects.

#ifndef MAIN_SAVITCH_SEQUENCE3_H

#define MAIN_SAVITCH_SEQUENCE3_H

#include // Provides size_t

#include "Node.h" // Provides node class

namespace main_savitch_5

{

class sequence

{

public:

// TYPEDEFS and MEMBER CONSTANTS

typedef double value_type;

typedef std::size_t size_type;

// CONSTRUCTORS and DESTRUCTOR

sequence( );

sequence(const sequence& source);

~sequence( );

// MODIFICATION MEMBER FUNCTIONS

void start( );

void advance( );

void insert(const value_type& entry);

void attach(const value_type& entry);

void operator =(const sequence& source);

void remove_current( );

// CONSTANT MEMBER FUNCTIONS

size_type size( ) const { return many_nodes; }

bool is_item( ) const { return (cursor != NULL); }

value_type current( ) const;

private:

node *head_ptr;

node *tail_ptr;

node *cursor;

node *precursor;

size_type many_nodes;

};

}

#endif

___________________________________________________________________________________

#include #include "sequence3.h" namespace main_savitch_5 {

sequence::sequence() { head_ptr = NULL; tail_ptr = NULL; precursor = NULL; cursor = head_ptr; many_nodes = 0; }

sequence::sequence(const sequence& source) { int pos = 1; for(cursor = source.head_ptr; cursor != source.cursor; cursor = cursor -> link()) { pos++; } list_copy(source.head_ptr,head_ptr,tail_ptr); cursor = list_locate(head_ptr, (size_t) pos); if(pos == 1) { precursor = NULL; } else { precursor = list_locate(head_ptr, (size_t) pos - 1); } many_nodes = source.many_nodes; }

sequence::~sequence() { many_nodes = 0; list_clear(head_ptr); }

void sequence::start() { cursor = head_ptr; }

void sequence::advance() { assert(is_item()); precursor = cursor; cursor = cursor -> link(); }

void sequence::insert(const value_type &entry) { if(head_ptr == NULL) { list_head_insert(head_ptr, entry); cursor = head_ptr; precursor = NULL; } else if(cursor == NULL || cursor == head_ptr) { list_head_insert(head_ptr, entry); cursor = head_ptr; } else { list_insert(precursor, entry); cursor = precursor -> link(); } many_nodes++; }

void sequence::attach(const value_type &entry) { //Implement this function }

void sequence:: operator =(const sequence &source) { if (this == &source) { return; } list_clear(head_ptr); many_nodes = 0; int index = 1;

for(cursor = source.head_ptr; cursor != source.cursor; cursor = cursor -> link()) { index++; } list_copy(source.head_ptr, head_ptr, tail_ptr); cursor = list_locate(head_ptr, (size_t) index);

if(index == 1) { precursor = NULL; } else { precursor = list_locate(head_ptr, (size_t) index - 1); } many_nodes = source.many_nodes; }

void sequence::remove_current() { //Implement this function }

sequence::value_type sequence::current() const { assert(is_item()); return cursor -> data(); }

}

___________________________________________________________________

// FILE: sequence_exam3.cxx // Written by: Michael Main (main@colorado.edu) - Oct 31, 1997 // Non-interactive test program for the sequence class using a linked sequence // // DESCRIPTION: // Each function of this program tests part of the sequence class, returning // some number of points to indicate how much of the test was passed. // A description and result of each test is printed to cout. // Maximum number of points awarded by this program is determined by the // constants POINTS[1], POINTS[2]...

#include // Provides cout. #include // Provides size_t. #include "sequence3.h" // Provides the sequence class with double items. using namespace std; using namespace main_savitch_5;

// Descriptions and points for each of the tests: const size_t MANY_TESTS = 6; const int POINTS[MANY_TESTS+1] = { 18, // Total points for all tests. 4, // Test 1 points 4, // Test 2 points 4, // Test 3 points 2, // Test 4 points 2, // Test 5 points 2 // Test 6 points }; const char DESCRIPTION[MANY_TESTS+1][256] = { "tests for sequence Class with a linked sequence", "Testing insert, attach, and the constant member functions", "Testing situations where the cursor goes off the sequence", "Testing remove_current", "Testing the copy constructor", "Testing the assignment operator", "Testing insert/attach for somewhat larger sequences" };

// ************************************************************************** // bool test_basic(const sequence& test, size_t s, bool has_cursor) // Postcondition: A return value of true indicates: // a. test.size() is s, and // b. test.is_item() is has_cursor. // Otherwise the return value is false. // In either case, a description of the test result is printed to cout. // ************************************************************************** bool test_basic(const sequence& test, size_t s, bool has_cursor) { bool answer;

cout << "Testing that size() returns " << s << " ... "; cout.flush( ); answer = (test.size( ) == s); cout << (answer ? "Passed." : "Failed.") << endl; if (answer) { cout << "Testing that is_item() returns "; cout << (has_cursor ? "true" : "false") << " ... "; cout.flush( ); answer = (test.is_item( ) == has_cursor); cout << (answer ? "Passed." : "Failed.") << endl; }

return answer; }

// ************************************************************************** // bool test_items(sequence& test, size_t s, size_t i, double items[]) // The function determines if the test sequence has the correct items // Precondition: The size of the items array is at least s. // Postcondition: A return value of true indicates that test.current() // is equal to items[i], and after test.advance() the result of // test.current() is items[i+1], and so on through items[s-1]. // At this point, one more advance takes the cursor off the sequence. // If any of this fails, the return value is false. // NOTE: The test sequence has been changed by advancing its cursor. // ************************************************************************** bool test_items(sequence& test, size_t s, size_t i, double items[]) { bool answer = true; cout << "The cursor should be at item [" << i << "]" << " of the sequence "; cout << "(counting the first item as [0]). I will advance the cursor "; cout << "to the end of the sequence, checking that each item is correct..."; cout.flush( ); while ((i < s) && test.is_item( ) && (test.current( ) == items[i])) { i++; test.advance( ); }

if ((i != s) && !test.is_item( )) { // The test.is_item( ) function returns false too soon. cout << " Cursor fell off the sequence too soon." << endl; answer = false; } else if (i != s) { // The test.current( ) function returned a wrong value. cout << " The item [" << i << "] should be " << items[i] << ", "; cout << " but it was " << test.current( ) << " instead. "; answer = false; } else if (test.is_item( )) { // The test.is_item( ) function returns true after moving off the sequence. cout << " The cursor was moved off the sequence,"; cout << " but is_item still returns true." << endl; answer = false; }

cout << (answer ? "Passed." : "Failed.") << endl; return answer; }

// ************************************************************************** // bool correct(sequence& test, size_t s, size_t cursor_spot, double items[]) // This function determines if the sequence (test) is "correct" according to // these requirements: // a. it has exactly s items. // b. the items (starting at the front) are equal to // items[0] ... items[s-1] // c. if cursor_spot < s, then test's cursor must be at // the location given by cursor_spot. // d. if cursor_spot >= s, then test must not have a cursor. // NOTE: The function also moves the cursor off the sequence. // ************************************************************************** bool correct(sequence& test, size_t size, size_t cursor_spot, double items[]) { bool has_cursor = (cursor_spot < size);

// Check the sequence's size and whether it has a cursor. if (!test_basic(test, size, has_cursor)) { cout << "Basic test of size() or is_item() failed." << endl << endl; return false; }

// If there is a cursor, check the items from cursor to end of the sequence. if (has_cursor && !test_items(test, size, cursor_spot, items)) { cout << "Test of the sequence's items failed." << endl << endl; return false; }

// Restart the cursor at the front of the sequence and test items again. cout << "I'll call start() and look at the items one more time..." << endl; test.start( ); if (has_cursor && !test_items(test, size, 0, items)) { cout << "Test of the sequence's items failed." << endl << endl; return false; }

// If the code reaches here, then all tests have been passed. cout << "All tests passed for this sequence." << endl << endl; return true; }

// ************************************************************************** // int test1( ) // Performs some basic tests of insert, attach, and the constant member // functions. Returns POINTS[1] if the tests are passed. Otherwise returns 0. // ************************************************************************** int test1( ) { sequence empty; // An empty sequence sequence test; // A sequence to add items to double items1[4] = { 5, 10, 20, 30 }; // These 4 items are put in a sequence double items2[4] = { 10, 15, 20, 30 }; // These are put in another sequence

// Test that the empty sequence is really empty cout << "Starting with an empty sequence." << endl; if (!correct(empty, 0, 0, items1)) return 0;

// Test the attach function to add something to an empty sequence cout << "I am now using attach to put 10 into an empty sequence." << endl; test.attach(10); if (!correct(test, 1, 0, items2)) return 0; // Test the insert function to add something to an empty sequence cout << "I am now using insert to put 10 into an empty sequence." << endl; test = empty; test.insert(10); if (!correct(test, 1, 0, items2)) return 0; // Test the insert function to add an item at the front of a sequence cout << "I am now using attach to put 10,20,30 in an empty sequence. "; cout << "Then I move the cursor to the start and insert 5." << endl; test = empty; test.attach(10); test.attach(20); test.attach(30); test.start( ); test.insert(5); if (!correct(test, 4, 0, items1)) return 0; // Test the insert function to add an item in the middle of a sequence cout << "I am now using attach to put 10,20,30 in an empty sequence. "; cout << "Then I move the cursor to the start, advance once, "; cout << "and insert 15." << endl; test = empty; test.attach(10); test.attach(20); test.attach(30); test.start( ); test.advance( ); test.insert(15); if (!correct(test, 4, 1, items2)) return 0;

// Test the attach function to add an item in the middle of a sequence cout << "I am now using attach to put 10,20,30 in an empty sequence. "; cout << "Then I move the cursor to the start and attach 15 "; cout << "after the 10." << endl; test = empty; test.attach(10); test.attach(20); test.attach(30); test.start( ); test.attach(15); if (!correct(test, 4, 1, items2)) return 0;

// All tests have been passed cout << "All tests of this first function have been passed." << endl; return POINTS[1]; }

// ************************************************************************** // int test2( ) // Performs a test to ensure that the cursor can correctly be run off the end // of the sequence. Also tests that attach/insert work correctly when there is // no cursor. Returns POINTS[2] if the tests are passed. Otherwise returns 0. // ************************************************************************** int test2( ) { const size_t TESTSIZE = 30; sequence test; size_t i;

// Put three items in the sequence cout << "Using attach to put 20 and 30 in the sequence, and then calling "; cout << "advance, so that is_item should return false ... "; cout.flush( ); test.attach(20); test.attach(30); test.advance( ); if (test.is_item( )) { cout << "failed." << endl; return 0; } cout << "passed." << endl;

// Insert 10 at the front and run the cursor off the end again cout << "Inserting 10, which should go at the sequence's front." << endl; cout << "Then calling advance three times to run cursor off the sequence ..."; cout.flush( ); test.insert(10); test.advance( ); // advance to the 20 test.advance( ); // advance to the 30 test.advance( ); // advance right off the sequence if (test.is_item( )) { cout << " failed." << endl; return false; } cout << " passed." << endl; // Attach more items until the sequence becomes full. // Note that the first attach should attach to the end of the sequence. cout << "Calling attach to put the numbers 40, 50, 60 ..."; cout << TESTSIZE*10 << " at the sequence's end." << endl; for (i = 4; i <= TESTSIZE; i++) test.attach(i*10);

// Test that the sequence is correctly filled. cout << "Now I will test that the sequence has 10, 20, 30, ..."; cout << TESTSIZE*10 << "." << endl; test.start( ); for (i = 1; i <= TESTSIZE; i++) { if ((!test.is_item( )) || test.current( ) != i*10) { cout << " Test failed to find " << i*10 << endl; return 0; } test.advance( ); } if (test.is_item( )) { cout << " There are too many items on the sequence." << endl; return false; }

// All tests passed cout << "All tests of this second function have been passed." << endl; return POINTS[2]; }

// ************************************************************************** // int test3( ) // Performs basic tests for the remove_current function. // Returns POINTS[3] if the tests are passed. // Otherwise returns 0. // ************************************************************************** int test3( ) { const size_t TESTSIZE = 30; sequence test;

// Within this function, I create several different sequences using the // items in these arrays: double items1[1] = { 30 }; double items2[2] = { 10, 30 }; double items3[3] = { 10, 20, 30 }; size_t i; // for-loop control variable

// Build a sequence with three items 10, 20, 30, and remove the middle, // and last and then first. cout << "Using attach to build a sequence with 10,30." << endl; test.attach(10); test.attach(30); cout << "Insert a 20 before the 30, so entire sequence is 10,20,30." << endl; test.insert(20); if (!correct(test, 3, 1, items3)) return 0; cout << "Remove the 20, so entire sequence is now 10,30." << endl; test.start( ); test.advance( ); test.remove_current( ); if (!correct(test, 2, 1, items2)) return 0; cout << "Remove the 30, so entire sequence is now just 10 with no cursor."; cout << endl; test.start( ); test.advance( ); test.remove_current( ); if (!correct(test, 1, 1, items2)) return 0; cout << "Set the cursor to the start and remove the 10." << endl; test.start( ); test.remove_current( ); if (!correct(test, 0, 0, items2)) return 0;

// Build a sequence with three items 10, 20, 30, and remove the middle, // and then first and then last. cout << "Using attach to build another sequence with 10,30." << endl; test.attach(10); test.attach(30); cout << "Insert a 20 before the 30, so entire sequence is 10,20,30." << endl; test.insert(20); if (!correct(test, 3, 1, items3)) return 0; cout << "Remove the 20, so entire sequence is now 10,30." << endl; test.start( ); test.advance( ); test.remove_current( ); if (!correct(test, 2, 1, items2)) return 0; cout << "Set the cursor to the start and remove the 10," << endl; cout << "so the sequence should now contain just 30." << endl; test.start( ); test.remove_current( ); if (!correct(test, 1, 0, items1)) return 0; cout << "Remove the 30 from the sequence, resulting in an empty sequence." << endl; test.start( ); test.remove_current( ); if (!correct(test, 0, 0, items1)) return 0;

// Build a sequence with three items 10, 20, 30, and remove the first. cout << "Build a new sequence by inserting 30, 10, 20 (so the sequence "; cout << "is 20, then 10, then 30). Then remove the 20." << endl; test.insert(30); test.insert(10); test.insert(20); test.remove_current( ); if (!correct(test, 2, 0, items2)) return 0; test.start( ); test.remove_current( ); test.remove_current( );

// Just for fun, fill up the sequence, and empty it! cout << "Just for fun, I'll empty the sequence then fill it up, then "; cout << "empty it again. During this process, I'll try to determine "; cout << "whether any of the sequence's member functions access the "; cout << "array outside of its legal indexes." << endl; for (i = 0; i < TESTSIZE; i++) test.insert(0); for (i = 0; i < TESTSIZE; i++) test.remove_current( );

// All tests passed cout << "All tests of this third function have been passed." << endl; return POINTS[3]; }

// ************************************************************************** // int test4( ) // Performs some tests of the copy constructor. // Returns POINTS[4] if the tests are passed. Otherwise returns 0. // ************************************************************************** int test4( ) { const size_t TESTSIZE = 30; sequence original; // A sequence that we'll copy. double items[2*TESTSIZE]; size_t i;

// Set up the items array to conatin 1...2*TESTSIZE. for (i = 1; i <= 2*TESTSIZE; i++) items[i-1] = i; // Test copying of an empty sequence. After the copying, we change original. cout << "Copy constructor test: for an empty sequence." << endl; sequence copy1(original); original.attach(1); // Changes the original sequence, but not the copy. if (!correct(copy1, 0, 0, items)) return 0;

// Test copying of a sequence with current item at the tail. cout << "Copy constructor test: for a sequence with cursor at tail." << endl; for (i=2; i <= 2*TESTSIZE; i++) original.attach(i); sequence copy2(original); original.remove_current( ); // Delete tail from original, but not the copy original.start( ); original.advance( ); original.remove_current( ); // Delete 2 from original, but not the copy. if (!correct (copy2, 2*TESTSIZE, 2*TESTSIZE-1, items) ) return 0;

// Test copying of a sequence with cursor near the middle. cout << "Copy constructor test: with cursor near middle." << endl; original.insert(2); for (i = 1; i < TESTSIZE; i++) original.advance( ); // Cursor is now at location [TESTSIZE] (counting [0] as the first spot). sequence copy3(original); original.start( ); original.advance( ); original.remove_current( ); // Delete 2 from original, but not the copy. if (!correct (copy3, 2*TESTSIZE-1, TESTSIZE, items) ) return 0;

// Test copying of a sequence with cursor at the front. cout << "Copy constructor test: for a sequence with cursor at front." << endl; original.insert(2); original.start( ); // Cursor is now at the front. sequence copy4(original); original.start( ); original.advance( ); original.remove_current( ); // Delete 2 from original, but not the copy. if (!correct (copy4, 2*TESTSIZE-1, 0, items) ) return 0;

// Test copying of a sequence with no current item. cout << "Copy constructor test: for a sequence with no current item." << endl; original.insert(2); while (original.is_item( )) original.advance( ); // There is now no current item. sequence copy5(original); original.start( ); original.advance( ); original.remove_current( ); // Delete 2 from original, but not the copy. if (!correct (copy5, 2*TESTSIZE-1, 2*TESTSIZE, items) ) return 0;

// All tests passed cout << "All tests of this fourth function have been passed." << endl; return POINTS[4]; }

// ************************************************************************** // int test5( ) // Performs some tests of the assignment operator. // Returns POINTS[5] if the tests are passed. Otherwise returns 0. // ************************************************************************** int test5( ) { const size_t TESTSIZE = 30; sequence original; // A sequence that we'll copy. double items[2*TESTSIZE]; size_t i;

// Set up the items array to conatin 1...2*TESTSIZE. for (i = 1; i <= 2*TESTSIZE; i++) items[i-1] = i; // Test copying of an empty sequence. After the copying, we change original. cout << "Assignment operator test: for an empty sequence." << endl; sequence copy1; copy1 = original; original.attach(1); // Changes the original sequence, but not the copy. if (!correct(copy1, 0, 0, items)) return 0;

// Test copying of a sequence with current item at the tail. cout << "Assignment operator test: cursor at tail." << endl; for (i=2; i <= 2*TESTSIZE; i++) original.attach(i); sequence copy2; copy2 = original; original.remove_current( ); // Delete tail from original, but not the copy original.start( ); original.advance( ); original.remove_current( ); // Delete 2 from original, but not the copy. if (!correct (copy2, 2*TESTSIZE, 2*TESTSIZE-1, items) ) return 0;

// Test copying of a sequence with cursor near the middle. cout << "Assignment operator test: with cursor near middle." << endl; original.insert(2); for (i = 1; i < TESTSIZE; i++) original.advance( ); // Cursor is now at location [TESTSIZE] (counting [0] as the first spot). sequence copy3; copy3 = original; original.start( ); original.advance( ); original.remove_current( ); // Delete 2 from original, but not the copy. if (!correct (copy3, 2*TESTSIZE-1, TESTSIZE, items) ) return 0;

// Test copying of a sequence with cursor at the front. cout << "Assignment operator test: with cursor at front." << endl; original.insert(2); original.start( ); // Cursor is now at the front. sequence copy4; copy4 = original; original.start( ); original.advance( ); original.remove_current( ); // Delete 2 from original, but not the copy. if (!correct (copy4, 2*TESTSIZE-1, 0, items) ) return 0;

// Test copying of a sequence with no current item. cout << "Assignment operator test: with no current item." << endl; original.insert(2); while (original.is_item( )) original.advance( ); // There is now no current item. sequence copy5; copy5 = original; original.start( ); original.advance( ); original.remove_current( ); // Deletes 2 from the original, but not copy. if (!correct (copy5, 2*TESTSIZE-1, 2*TESTSIZE, items) ) return 0;

cout << "Checking correctness of a self-assignment x = x;" << endl; original.insert(2); original = original; if (!correct (original, 2*TESTSIZE-1, 1, items) ) return 0;

// All tests passed cout << "All tests of this fifth function have been passed." << endl; return POINTS[5]; }

// ************************************************************************** // int test6( ) // Performs some basic tests of insert and attach for the case where the // current capacity has been reached. // Returns POINTS[6] if the tests are passed. Otherwise returns 0. // ************************************************************************** int test6( ) { const size_t TESTSIZE = 30; sequence testa, testi; double items[2*TESTSIZE]; size_t i;

// Set up the items array to conatin 1...2*TESTSIZE. for (i = 1; i <= 2*TESTSIZE; i++) items[i-1] = i; cout << "Testing to see that attach works correctly when the "; cout << "current capacity is exceeded." << endl; for (i = 1; i <= 2*TESTSIZE; i++) testa.attach(i); if (!correct (testa, 2*TESTSIZE, 2*TESTSIZE-1, items) ) return 0;

cout << "Testing to see that insert works correctly when the "; cout << "current capacity is exceeded." << endl; for (i = 2*TESTSIZE; i >= 1; i--) testi.insert(i); if (!correct (testi, 2*TESTSIZE, 0, items) ) return 0;

// All tests passed cout << "All tests of this sixth function have been passed." << endl; return POINTS[6]; }

int run_a_test(int number, const char message[], int test_function( ), int max) { int result; cout << endl << "START OF TEST " << number << ":" << endl; cout << message << " (" << max << " points)." << endl; result = test_function( ); if (result > 0) { cout << "Test " << number << " got " << result << " points"; cout << " out of a possible " << max << "." << endl; } else cout << "Test " << number << " failed." << endl; cout << "END OF TEST " << number << "." << endl << endl; return result; }

// ************************************************************************** // int main( ) // The main program calls all tests and prints the sum of all points // earned from the tests. // ************************************************************************** int main( ) { int sum = 0; cout << "Running " << DESCRIPTION[0] << endl;

sum += run_a_test(1, DESCRIPTION[1], test1, POINTS[1]); cout << sum << endl; sum += run_a_test(2, DESCRIPTION[2], test2, POINTS[2]); cout << sum << endl; sum += run_a_test(3, DESCRIPTION[3], test3, POINTS[3]); cout << sum << endl; sum += run_a_test(4, DESCRIPTION[4], test4, POINTS[4]); cout << sum << endl; sum += run_a_test(5, DESCRIPTION[5], test5, POINTS[5]); cout << sum << endl; sum += run_a_test(6, DESCRIPTION[6], test6, POINTS[6]); cout << sum << endl;

cout << "If you submit this sequence to Dora now, you will have "; cout << sum << " points out of the " << POINTS[0]; cout << " points from this test program. "; return EXIT_SUCCESS;

}