You will implement and test a revised sequence class that uses a linked list to store the items.

1) write a sequence3.cpp file 2) write sequence3.h file 3) add node.h & node.cpp file 4) test it 5) finally show your results that your codes passed all those tests.

sequence3 files you have to write cpp file

// FILE: sequence3.h

// CLASS PROVIDED: sequence (a container class for a sequence of items,

// where each sequence may have a designated item called the current item)

//

// TYPEDEF 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.

//

// 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 on 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_t size( ) const

// Postcondition: The return value is the number of items on 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 on the sequence.

//

// VALUE SEMANTICS for the sequence class:

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

//

// DYNAMIC MEMORY USAGE by the sequence:

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

// new_handler: The constructors, insert, attach, and the

// assignment operator.

#ifndef MAIN_SAVITCH_SEQUENCE3_H

#define MAIN_SAVITCH_SEQUENCE3_H

#include // Provides size_t and NULL

#include "node1.h" // Provides linked list toolkit

namespace main_savitch_5

{

class sequence

{

public:

// TYPEDEF

typedef size_t size_type; //typedef std::size_t size_type;

typedef node::value_type value_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 remove_current( );

void operator =(const sequence& source);

// CONSTANT MEMBER FUNCTIONS

size_t size( ) const;

bool is_item( ) const;

value_type current( ) const;

private:

-- Declare your private members here. I suggest that

-- you have the five private member variables that are

-- described in Section 5.4 (page 259) of the textbook.

};

}

#endif

2) node.h (just add this)

// 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

3) node.cpp (Copy these files to your sub-directory. They contain the linked list toolkit from Section 5.2. You may use these files without changing them. However we only provide the documentation for the function list_piece (see Self-Test Exercise 17 on page 239). You may need to write an implementation of this function if you are going to use it in writing your copy constructor and overloading your assignment operator. If you do make changes, please turn them in.)

// 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 "node1.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( );

}

}

}

5) sequence3.test

// FILE: sequence_test.cxx

// An interactive test program for the new sequence class

#include // Provides toupper

#include // Provides cout and cin

#include // Provides EXIT_SUCCESS

#include "sequence3.h" // With value_type defined as double

using namespace std;

using namespace main_savitch_5;

// PROTOTYPES for functions used by this test program:

void print_menu( );

// Postcondition: A menu of choices for this program has been written to cout.

char get_user_command( );

// Postcondition: The user has been prompted to enter a one character command.

// The next character has been read (skipping blanks and newline characters),

// and this character has been returned.

void show_sequence(sequence display);

// Postcondition: The items on display have been printed to cout (one per line).

double get_number( );

// Postcondition: The user has been prompted to enter a real number. The

// number has been read, echoed to the screen, and returned by the function.

int main( )

{

sequence test; // A sequence that well perform tests on

char choice; // A command character entered by the user

cout << "I have initialized an empty sequence of real numbers." << endl;

do

{

print_menu( );

choice = toupper(get_user_command( ));

switch (choice)

{

case '!': test.start( );

break;

case '+': test.advance( );

break;

case '?': if (test.is_item( ))

cout << "There is an item." << endl;

else

cout << "There is no current item." << endl;

break;

case 'C': if (test.is_item( ))

cout << "Current item is: " << test.current( ) << endl;

else

cout << "There is no current item." << endl;

break;

case 'P': show_sequence(test);

break;

case 'S': cout << "Size is " << test.size( ) << '.' << endl;

break;

case 'I': test.insert(get_number( ));

break;

case 'A': test.attach(get_number( ));

break;

case 'R': test.remove_current( );

cout << "The current item has been removed." << endl;

break;

case 'Q': cout << "Ridicule is the best test of truth." << endl;

break;

default: cout << choice << " is invalid." << endl;

}

}

while ((choice != 'Q'));

return EXIT_SUCCESS;

}

void print_menu( )

// Library facilities used: iostream.h

{

cout << endl; // Print blank line before the menu

cout << "The following choices are available: " << endl;

cout << " ! Activate the start( ) function" << endl;

cout << " + Activate the advance( ) function" << endl;

cout << " ? Print the result from the is_item( ) function" << endl;

cout << " C Print the result from the current( ) function" << endl;

cout << " P Print a copy of the entire sequence" << endl;

cout << " S Print the result from the size( ) function" << endl;

cout << " I Insert a new number with the insert(...) function" << endl;

cout << " A Attach a new number with the attach(...) function" << endl;

cout << " R Activate the remove_current( ) function" << endl;

cout << " Q Quit this test program" << endl;

}

char get_user_command( )

// Library facilities used: iostream

{

char command;

cout << "Enter choice: ";

cin >> command; // Input of characters skips blanks and newline character

return command;

}

void show_sequence(sequence display)

// Library facilities used: iostream

{

for (display.start( ); display.is_item( ); display.advance( ))

cout << display.current( ) << endl;

}

double get_number( )

// Library facilities used: iostream

{

double result;

cout << "Please enter a real number for the sequence: ";

cin >> result;

cout << result << " has been read." << endl;

return result;

}