The assignment is to do problem 17 on page 392 of the text. C++ please, Use the STL stack class, sequence4.h, and sequence_exam4.cpp.

Here's a new idea for implementing the sequence class from section 3.2. Instead of the items being stored on a linked list they will be stored using two stacks as private member variables with the following:

1. The bottom of the first stack is the beginning of the sequence.

2. The elements of the sequence continue up to the top of the first stack.

3. The next element of the sequence is then the top of the second stack.

4. And the elements of the sequence is then the top of the sequence then continues down to the bottom of the second sequence (which is the end of the sequence)

5. If there is a current element, then that element is at the top of the first stack.

============================================================================

********* deque.h ************

#ifndef _DEQUE_H_ #define _DEQUE_H_

#include #include #include "node2.h"

using namespace main_savitch_6B;

template class deque { public: typedef std::size_t size_type; //postcondition: empty deque has been created deque(); // postcondition: all resouroces allocated to the deque // have been deallocated ~deque(); // postcondition: newly created deque is a copy of dq deque(const deque& dq); // postcondition: current deque is a copy of dq deque& operator = (const deque& dq); //precondition: deque is not empty // postcondition: reference to element at front of deque // has been returned T& front(); // precondition: deque is not empty // postcondition: copy of element at front of deque // has been returned T front() const; // precondition: deque is not empty // postcondition: reference to element at front of deque // has been returned T& back(); // precondition: deque is not empty // postcondition: copy of element at back of deque // has been returned T back() const; // postcondition: entry has been inserted at the front // of the deque void push_front (const T& entry); // postcondition: entry has been inserted at the back // of the deque void push_back (const T& entry); // precondition: deque is not empty // postcondition: element at front of deque has been removed void pop_front(); // precondition: deque is not empty // postcondition: element at back of deque has been removed void pop_back(); // postcondition: number of elements in deque has been returned size_type size() const; // postcondition: whether deque is empty has been returned bool empty() const; // postcondition: returned whether 2 deques are equal - equal is defined // as the deques have the same number of elements & // corresponding elements are equal template friend bool operator == (const deque& dq1, const deque& dq2);

// postcondition: dq has been display from front to rear on out template friend std::ostream& operator<< (std::ostream& out, const deque& dq);

private: size_type count; // Total number of items in the queue node* first; node* last; };

#include "deque.template"

#endif

============================================================================

******* Sequence.h ********

// FILE: sequence4.h // CLASS PROVIDED: sequence // TYPEDEFS and MEMBER CONSTANTS for the sequence class: // 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 _STACK_SEQUENCE_H_ #define _STACK_SAVITCH_SEQUENCE_H_ #include // Provides size_t #include namespace stack_sequence_4 { template class sequence { public: // TYPEDEFS and MEMBER CONSTANTS typedef std::size_t size_type; // CONSTRUCTOR sequence( ); // MODIFICATION MEMBER FUNCTIONS void start( ); void advance( ); void insert(const T& entry); void attach(const T& entry); void remove_current( ); // CONSTANT MEMBER FUNCTIONS size_type size( ) const; bool is_item( ) const; T current( ) const; private: std::stack first; std::stack second; }; }

#include "sequence4.template" #endif

============================================================================

********* Sequence_Exam.cpp ***********

// FILE: sequenceexam.cxx // Written by: Michael Main (main@colorado.edu) - Oct 22, 1997 // Non-interactive test program for the sequence class from Section 3.2 of // "Data Structures and Other Objects". // // 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 "sequence4.h" // Provides the sequence class with double items. using namespace std; using namespace stack_sequence_4;

// Descriptions and points for each of the tests: const size_t MANY_TESTS = 3; const int POINTS[MANY_TESTS+1] = { 100, // Total points for all tests. 50, // Test 1 points 25, // Test 2 points 25 // Test 3 points }; const char DESCRIPTION[MANY_TESTS+1][256] = { "tests for Chapter 3 sequence Class", "Testing insert, attach, and the constant member functions", "Testing situations where the cursor goes off the sequence", "Testing remove_current" };

// ************************************************************************** // 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 // double[0] ... double[size-1] // c. if cursor_spot < size, then test's cursor must be at // the location given by cursor_spot. // d. if cursor_spot >= size, 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( ) { 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 << test.CAPACITY*10 << " at the sequence's end." << endl; for (i = 4; i <= test.CAPACITY; 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 << test.CAPACITY*10 << "." << endl; test.start( ); for (i = 1; i <= test.CAPACITY; 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. Returns POINTS[3] / 4 if almost // all the tests are passed. Otherwise returns 0. // ************************************************************************** int test3( ) { // In the next declarations, I am declaring a sequence called test. // Both before and after the sequence, I declare a small array of characters, // and I put the character 'x' into each spot of these arrays. // Later, if I notice that one of the x's has been changed, or if // I notice an 'x' inside of the sequence, then the most // likely reason was that one of the sequence's member functions accessed // the sequence's array outside of its legal indexes. char prefix[4] = {'x', 'x', 'x', 'x'}; sequence test; char suffix[4] = {'x', 'x', 'x', 'x'};

// 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 char *char_ptr; // Variable to loop at each character in a sequence's memory

// 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 < test.CAPACITY; i++) test.insert(0); for (i = 0; i < test.CAPACITY; i++) test.remove_current( );

// Make sure that the character 'x' didn't somehow get into the sequence, // as that would indicate that the sequence member functions are // copying data from before or after the sequence into the sequence. char_ptr = (char *) &test; for (i = 0; i < sizeof(sequence); i++) if (char_ptr[i] == 'x') { cout << "Illegal array access detected." << endl; return POINTS[3] / 4; } */ // Make sure that the prefix and suffix arrays still have four // x's each. Otherwise one of the sequence operations wrote outside of // the legal boundaries of its array. for (i = 0; i < 4; i++) if ((suffix[i] != 'x') || (prefix[i] != 'x')) { cout << "Illegal array access detected." << endl; return POINTS[3] / 4; } // All tests passed cout << "All tests of this third function have been passed." << endl; return POINTS[3]; }

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]); sum += run_a_test(2, DESCRIPTION[2], test2, POINTS[2]); sum += run_a_test(3, DESCRIPTION[3], test3, POINTS[3]);

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

}

============================================================================

********* node2.h ************

// FILE: node2.h (part of the namespace main_savitch_6B) // PROVIDES: A template class for a node in a linked list, and list manipulation // functions. The template parameter is the type of the data in each node. // This file also defines a template class: node_iterator. // The node_iterator is a forward iterators with two constructors: // (1) A constructor (with a node* parameter) that attaches the iterator // to the specified node in a linked list, and (2) a default constructor that // creates a special iterator that marks the position that is beyond the end of a // linked list. There is also a const_node_iterator for use with // const node* . // // TYPEDEF for the node template class: // Each node of the list contains a piece of data and a pointer to the // next node. The type of the data (node::value_type) is the Item type // from the template parameter. The type may be any of the built-in C++ classes // (int, char, ...) or a class with a default constructor, an assignment // operator, and a test for equality (x == y). // NOTE: // Many compilers require the use of the new keyword typename before using // the expression node::value_type. Otherwise // the compiler doesn't have enough information to realize that it is the // name of a data type. // // CONSTRUCTOR for the node class: // node( // const Item& init_data = Item(), // 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 Item. 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 about two versions of some functions: // The data function returns a reference to the data field of a node and // the link function returns a copy of the link field of a node. // Each of these functions comes in two versions: a const version and a // non-const version. If the function is activated by a const node, then the // compiler choses the const version (and the return value is const). // If the function is activated by a non-const node, then the compiler choses // the non-const version (and the return value will be non-const). // EXAMPLES: // const node *c; // c->link( ) activates the const version of link returning const node* // c->data( ) activates the const version of data returning const Item& // c->data( ) = 42; ... is forbidden // node *p; // p->link( ) activates the non-const version of link returning node* // p->data( ) activates the non-const version of data returning Item& // p->data( ) = 42; ... actually changes the data in p's node // // MEMBER FUNCTIONS for the node class: // const Item& data( ) const <----- const version // and // Item& data( ) <----------------- non-const version // See the note (above) about the const version and non-const versions: // Postcondition: The return value is a reference to the data from this node. // // const node* link( ) const <----- const version // and // 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. // // void set_data(const Item& 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. // // FUNCTIONS in the linked list toolkit: // template  // 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. // // template  // 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. // // template  // void list_head_insert(node*& head_ptr, const Item& 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. // // template  // 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. // // template  // void list_insert(node* previous_ptr, const Item& 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. // // template  // 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. // // template  // NodePtr list_locate(NodePtr head_ptr, SizeType position) // The NodePtr may be either node* or const node* // Precondition: head_ptr is the head pointer of a linked list, and // position > 0. // Postcondition: The return value is a pointer that 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. // // template  // 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. // // template  // NodePtr list_search // (NodePtr head_ptr, const Item& target) // The NodePtr may be either node* or const node* // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: The return value is a pointer that points to the first // node containing the specified target in its data member. If there is no // such node, the null pointer is returned. // // 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. #ifndef MAIN_SAVITCH_NODE2_H #define MAIN_SAVITCH_NODE2_H #include  // Provides NULL and size_t #include  // Provides iterator and forward_iterator_tag namespace main_savitch_6B { template  class node { public: // TYPEDEF typedef Item value_type; // CONSTRUCTOR node(const Item& init_data=Item( ), node* init_link=NULL) { data_field = init_data; link_field = init_link; } // MODIFICATION MEMBER FUNCTIONS Item& data( ) { return data_field; } node* link( ) { return link_field; } void set_data(const Item& new_data) { data_field = new_data; } void set_link(node* new_link) { link_field = new_link; } // CONST MEMBER FUNCTIONS const Item& data( ) const { return data_field; } const node* link( ) const { return link_field; } private: Item data_field; node *link_field; }; // FUNCTIONS to manipulate a linked list: template  void list_clear(node*& head_ptr); template  void list_copy (const node* source_ptr, node*& head_ptr, node*& tail_ptr); template  void list_head_insert(node*& head_ptr, const Item& entry); template  void list_head_remove(node*& head_ptr); template  void list_insert(node* previous_ptr, const Item& entry); template  std::size_t list_length(const node* head_ptr); template  NodePtr list_locate(NodePtr head_ptr, SizeType position); template  void list_remove(node* previous_ptr); template  NodePtr list_search(NodePtr head_ptr, const Item& target); // FORWARD ITERATORS to step through the nodes of a linked list // A node_iterator of can change the underlying linked list through the // * operator, so it may not be used with a const node. The // node_const_iterator cannot change the underlying linked list // through the * operator, so it may be used with a const node. // WARNING: // This classes use std::iterator as its base class; // Older compilers that do not support the std::iterator class can // delete everything after the word iterator in the second line: template  class node_iterator : public std::iterator { public: node_iterator(node* initial = NULL) { current = initial; } Item& operator *( ) const { return current->data( ); } node_iterator& operator ++( ) // Prefix ++ { current = current->link( ); return *this; } node_iterator operator ++(int) // Postfix ++ { node_iterator original(current); current = current->link( ); return original; } bool operator ==(const node_iterator other) const { return current == other.current; } bool operator !=(const node_iterator other) const { return current != other.current; } private: node* current; }; template  class const_node_iterator : public std::iterator { public: const_node_iterator(const node* initial = NULL) { current = initial; } const Item& operator *( ) const { return current->data( ); } const_node_iterator& operator ++( ) // Prefix ++ { current = current->link( ); return *this; } const_node_iterator operator ++(int) // Postfix ++ { const_node_iterator original(current); current = current->link( ); return original; } bool operator ==(const const_node_iterator other) const { return current == other.current; } bool operator !=(const const_node_iterator other) const { return current != other.current; } private: const node* current; }; } #include "node2.template" #endif 

============================================================================