I have the program working up to the point where at the end of every test it fails and get. where do I need to look to start fixing the failed tests.(files are attached at the bottom)


This is my output:

START OF TEST 1:
Testing insert, attach, and the constant member functions (4 points).
Starting with an empty sequence.
Testing that size() returns 0 ... Passed.
Testing that is_item() returns false ... Passed.
I'll call start() and look at the items one more time...
All tests passed for this sequence.

I am now using attach to put 10 into an empty sequence.
Testing that size() returns 1 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...
The cursor was moved off the sequence, but is_item still returns true.
Failed.
Test of the sequence's items failed.

Test 1 failed.
END OF TEST 1.

0

START OF TEST 2:
Testing situations where the cursor goes off the sequence (4 points).
Using attach to put 20 and 30 in the sequence, and then calling
advance, so that is_item should return false ... failed.
Test 2 failed.
END OF TEST 2.

0

START OF TEST 3:
Testing remove_current (4 points).
Using attach to build a sequence with 10,30.
Insert a 20 before the 30, so entire sequence is 10,20,30.
Testing that size() returns 3 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [1] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...
The item [1] should be 20,
but it was 10 instead.
Failed.
Test of the sequence's items failed.

Test 3 failed.
END OF TEST 3.

0

START OF TEST 4:
Testing the copy constructor (2 points).
Copy constructor test: for an empty sequence.
Testing that size() returns 0 ... Passed.
Testing that is_item() returns false ... Passed.
I'll call start() and look at the items one more time...
All tests passed for this sequence.

Copy constructor test: for a sequence with cursor at tail.
Testing that size() returns 60 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [59] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...
The cursor was moved off the sequence, but is_item still returns true.
Failed.
Test of the sequence's items failed.

Test 4 failed.
END OF TEST 4.

0

START OF TEST 5:
Testing the assignment operator (2 points).
Assignment operator test: for an empty sequence.
Testing that size() returns 0 ... Passed.
Testing that is_item() returns false ... Passed.
I'll call start() and look at the items one more time...
All tests passed for this sequence.

Assignment operator test: cursor at tail.
Testing that size() returns 60 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [59] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...
The cursor was moved off the sequence, but is_item still returns true.
Failed.
Test of the sequence's items failed.

Test 5 failed.
END OF TEST 5.

0

START OF TEST 6:
Testing insert/attach for somewhat larger sequences (2 points).
Testing to see that attach works correctly when the
current capacity is exceeded.
Testing that size() returns 60 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [59] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...
The cursor was moved off the sequence, but is_item still returns true.
Failed.
Test of the sequence's items failed.

Test 6 failed.
END OF TEST 6.

0
If you submit this sequence to Dora now, you will have
0 points out of the 18 points from this test program.


sequence header file

// FILE: sequence3.h^M
// CLASS PROVIDED: sequence (part of the namespace main_savitch_5)^M
// This is the header file for the project described in Section 5.4^M
// of "Data Structures and Other Objects Using C++"^M
//^M
// TYPEDEFS and MEMBER CONSTANTS for the sequence class:^M
//   typedef ____ value_type^M
//     sequence::value_type is the data type of the items in the sequence. It^M
//     may be any of the C++ built-in types (int, char, etc.), or a class with a^M
//     default constructor, an assignment operator, and a copy constructor.^M
//^M
//   typedef ____ size_type^M
//     sequence::size_type is the data type of any variable that keeps track of^M
//     how many items are in a sequence.^M
//^M
// CONSTRUCTOR for the sequence class:^M
//   sequence( )^M
//     Postcondition: The sequence has been initialized as an empty sequence.^M
//^M
// MODIFICATION MEMBER FUNCTIONS for the sequence class:^M
//   void start( )^M
//     Postcondition: The first item on the sequence becomes the current item^M
//     (but if the sequence is empty, then there is no current item).^M
//^M
//   void advance( )^M
//     Precondition: is_item returns true.^M
//     Postcondition: If the current item was already the last item in the^M
//     sequence, then there is no longer any current item. Otherwise, the new^M
//     current item is the item immediately after the original current item.^M
//^M
//   void insert(const value_type& entry)^M
//     Postcondition: A new copy of entry has been inserted in the sequence^M
//     before the current item. If there was no current item, then the new entry^M
//     has been inserted at the front of the sequence. In either case, the newly^M
//     inserted item is now the current item of the sequence.^M
//^M
//   void attach(const value_type& entry)^M
//     Postcondition: A new copy of entry has been inserted in the sequence after^M
//     the current item. If there was no current item, then the new entry has^M
//     been attached to the end of the sequence. In either case, the newly^M
//     inserted item is now the current item of the sequence.^M
//^M
//   void remove_current( )^M
//     Precondition: is_item returns true.^M
//     Postcondition: The current item has been removed from the sequence, and^M
//     the item after this (if there is one) is now the new current item.^M
//^M
// CONSTANT MEMBER FUNCTIONS for the sequence class:^M
//   size_type size( ) const^M
//     Postcondition: The return value is the number of items in the sequence.^M
//^M
//   bool is_item( ) const^M
//     Postcondition: A true return value indicates that there is a valid^M
//     "current" item that may be retrieved by activating the current^M
//     member function (listed below). A false return value indicates that^M
//     there is no valid current item.^M
//^M
//   value_type current( ) const^M
//     Precondition: is_item( ) returns true.^M
//     Postcondition: The item returned is the current item in the sequence.^M
//^M
// VALUE SEMANTICS for the sequence class:^M
//    Assignments and the copy constructor may be used with sequence objects.^M
^M
#ifndef MAIN_SAVITCH_SEQUENCE3_H^M
#define MAIN_SAVITCH_SEQUENCE3_H^M
#include <cstdlib>  // Provides size_t^M
#include "node1.h"  // Provides node class^M
^M
namespace main_savitch_5^M
{^M
    class sequence^M
    {^M
    public:^M
        // TYPEDEFS and MEMBER CONSTANTS^M
        typedef double value_type;^M
        typedef std::size_t size_type;^M
        // CONSTRUCTORS and DESTRUCTOR^M
        sequence( );^M
        sequence(const sequence& source);^M
        ~sequence( );^M
        // MODIFICATION MEMBER FUNCTIONS^M
        void start( );^M
        void advance( );^M
        void insert(const value_type& entry);^M
        void attach(const value_type& entry);^M
        void operator =(const sequence& source);^M
        void remove_current( );^M

        // CONSTANT MEMBER FUNCTIONS^M
        size_type size( ) const;^M
        bool is_item( ) const; ^M
        value_type current( ) const;^M
    private:^M
        node *head_ptr;^M
        node *tail_ptr;^M
        node *cursor;^M
        node *precursor;^M
        size_type many_nodes;^M
    };^M
}^M
^M
#endif^M
^M

implementation file

#include <cassert>
#include <cstdlib>
#include "sequence3.h"
#include "node1.h"

using namespace std;

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


    sequence::sequence(const sequence& source)
    {
        node *tail_ptr;

        list_copy(source.head_ptr, head_ptr, tail_ptr);

        many_nodes = source.many_nodes;

        cursor = source.cursor;

        precursor = source.precursor;
    }

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

    //MODIFICATION MEMBER FUNCTIONS                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
    void sequence::start()
    {
        if(head_ptr == NULL)
        {
            return;
        }

        else
        {
            precursor = NULL;
            cursor = head_ptr;
        }
    }

    void sequence::advance()
    {
        assert(is_item());

        if(cursor == tail_ptr)
        {
            cursor = NULL;
            precursor = NULL;
        }

        else
        {
            precursor = cursor;
            cursor = cursor -> link();
        }
    }

    void sequence::insert(const value_type& entry)
    {
        if (is_item( ))
        {
            if(precursor == NULL || cursor == NULL)
            {
                list_head_insert(head_ptr, entry);

                cursor = head_ptr;
                precursor = NULL;
            }

            else
            {
                list_insert(precursor, entry);

                cursor = head_ptr;
            }
        }
        else
        {
            list_head_insert(head_ptr, entry);

            cursor = head_ptr;

            precursor = NULL;
        }

            many_nodes++;
    }

        void sequence::attach(const value_type& entry)
        {
            if(is_item())
            {
                precursor = cursor;

                list_insert(cursor, entry);

                cursor = cursor -> link();
            }

            else
            {
                if(head_ptr == NULL)
                {
                    list_head_insert(head_ptr, entry);

                    cursor = head_ptr;

                    precursor = NULL;
                }
                else
                {
                    precursor = list_locate(head_ptr, list_length(head_ptr));

                    list_insert(precursor, entry);

                    cursor = precursor -> link();
                }
            }

            many_nodes++;
        }

        void sequence::remove_current()
        {
            if(cursor == head_ptr)
            {
                cursor = cursor -> link();
                list_head_remove(head_ptr);
            }
            else
            {
                cursor = cursor -> link();
                list_remove(head_ptr);
            }

            --many_nodes;
        }

        void sequence::operator =(const sequence& source)
        {
            if(this == &source)
            {
                return;
            }
            else
            {
                list_copy(source.head_ptr, head_ptr, tail_ptr);

                if(source.precursor == NULL)
                {
                    if(source.cursor == NULL)
                    {
                        cursor = NULL;
                        precursor = NULL;
                    }
                    else
                    {
                        cursor = head_ptr;
                        precursor = NULL;
                    }
                }
                else
                {
                    node *tmp_ptr = head_ptr;
                    node *source_ptr = source.head_ptr;

                    while(source_ptr != source.precursor)
                    {
                        source_ptr = source_ptr -> link();

                        tmp_ptr = tmp_ptr -> link();
                    }

                    cursor = tmp_ptr -> link();
                    precursor = tmp_ptr;
                }
            }

            many_nodes = source.many_nodes;
        }
        //CONSTANT MEMBER FUNCTIONS                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
        sequence::size_type sequence::size() const
        {
            return many_nodes;
        }

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

        bool sequence::is_item() const
        {
            return(size()>0);

        }
}

main file

// 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 <iostream>     // Provides cout.
#include <cstdlib>      // 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\n";
    cout << "(counting the first item as [0]). I will advance the cursor\n";
    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 << "\n    Cursor fell off the sequence too soon." << endl;
        answer = false;
    }
    else if (i != s)
    {   // The test.current( ) function returned a wrong value.
        cout << "\n    The item [" << i << "] should be " << items[i] << ",\n";
        cout << "    but it was " << test.current( ) << " instead.\n";
        answer = false;
    }
    else if (test.is_item( ))
    {   // The test.is_item( ) function returns true after moving off the sequence.
        cout << "\n    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.\n";
    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.\n";
    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.\n";
    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\n";
    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\n";
    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\n";
    cout << "empty it again. During this process, I'll try to determine\n";
    cout << "whether any of the sequence's member functions access the\n";
    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\n";
    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\n";
    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\n";
    cout << sum << " points out of the " << POINTS[0];
    cout << " points from this test program.\n";

    return EXIT_SUCCESS;

}

other files that you will need
node1.h

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

node1.cxx

// 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 <cassert>    // Provides assert

#include <cstdlib>    // 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( );

        }

    }



}

Edited 6 Years Ago by Eagles36: n/a

Attachments
// 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 <cassert>    // Provides assert
#include <cstdlib>    // 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: 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 <cstdlib> // 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
#include <cassert>
#include <cstdlib>
#include "sequence3.h"
#include "node1.h"

using namespace std;

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


    sequence::sequence(const sequence& source)
    {
        node *tail_ptr;

        list_copy(source.head_ptr, head_ptr, tail_ptr);

        many_nodes = source.many_nodes;

        cursor = source.cursor;

        precursor = source.precursor;
    }

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

    //MODIFICATION MEMBER FUNCTIONS                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
    void sequence::start()
    {
        if(head_ptr == NULL)
        {
            return;
        }

        else
        {
            precursor = NULL;
            cursor = head_ptr;
        }
    }

    void sequence::advance()
    {
        assert(is_item());

        if(cursor == tail_ptr)
        {
            cursor = NULL;
            precursor = NULL;
        }

        else
        {
            precursor = cursor;
            cursor = cursor -> link();
        }
    }

    void sequence::insert(const value_type& entry)
    {
        if (is_item( ))
        {
            if(precursor == NULL || cursor == NULL)
            {
                list_head_insert(head_ptr, entry);

                cursor = head_ptr;
                precursor = NULL;
            }

            else
            {
                list_insert(precursor, entry);

                cursor = head_ptr;
            }
        }
        else
        {
            list_head_insert(head_ptr, entry);

            cursor = head_ptr;

            precursor = NULL;
        }

            many_nodes++;
    }

        void sequence::attach(const value_type& entry)
        {
            if(is_item())
            {
                precursor = cursor;

                list_insert(cursor, entry);

                cursor = cursor -> link();
            }

            else
            {
                if(head_ptr == NULL)
                {
                    list_head_insert(head_ptr, entry);

                    cursor = head_ptr;

                    precursor = NULL;
                }
                else
                {
                    precursor = list_locate(head_ptr, list_length(head_ptr));

                    list_insert(precursor, entry);

                    cursor = precursor -> link();
                }
            }

            many_nodes++;
        }

        void sequence::remove_current()
        {
            if(cursor == head_ptr)
            {
                cursor = cursor -> link();
                list_head_remove(head_ptr);
            }
            else
            {
                cursor = cursor -> link();
                list_remove(head_ptr);
            }

            --many_nodes;
        }

        void sequence::operator =(const sequence& source)
        {
            if(this == &source)
            {
                return;
            }
            else
            {
                list_copy(source.head_ptr, head_ptr, tail_ptr);

                if(source.precursor == NULL)
                {
                    if(source.cursor == NULL)
                    {
                        cursor = NULL;
                        precursor = NULL;
                    }
                    else
                    {
                        cursor = head_ptr;
                        precursor = NULL;
                    }
                }
                else
                {
                    node *tmp_ptr = head_ptr;
                    node *source_ptr = source.head_ptr;

                    while(source_ptr != source.precursor)
                    {
                        source_ptr = source_ptr -> link();

                        tmp_ptr = tmp_ptr -> link();
                    }

                    cursor = tmp_ptr -> link();
                    precursor = tmp_ptr;
                }
            }

            many_nodes = source.many_nodes;
        }
        //CONSTANT MEMBER FUNCTIONS                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
        sequence::size_type sequence::size() const
        {
            return many_nodes;
        }

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

        bool sequence::is_item() const
        {
            return(size()>0);

        }
}
// 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++"
//
// 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 <cstdlib>  // Provides size_t
#include "node1.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;
        bool is_item( ) const; 
        value_type current( ) const;
   
    private:
        node *head_ptr;
        node *tail_ptr;
        node *cursor;
        node *precursor;
        size_type many_nodes;
    };
}

#endif
// 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 <iostream>     // Provides cout.
#include <cstdlib>      // 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\n";
    cout << "(counting the first item as [0]). I will advance the cursor\n";
    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 << "\n    Cursor fell off the sequence too soon." << endl;
        answer = false;
    }
    else if (i != s)
    {   // The test.current( ) function returned a wrong value.
        cout << "\n    The item [" << i << "] should be " << items[i] << ",\n";
        cout << "    but it was " << test.current( ) << " instead.\n";
        answer = false;
    }
    else if (test.is_item( ))
    {   // The test.is_item( ) function returns true after moving off the sequence.
        cout << "\n    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.\n";
    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.\n";
    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.\n";
    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\n";
    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

Word of advice :
1) Don't post such huge codes,just tag the file as an attachment and post your question.
2) For solving any problem try to break it into parts and solve some smaller test case. As far as i can see your Test Case 1 itself can be broken down into smaller test cases. Solve them first so that you get to know all the minute problems.Then you can deal with entire test cases.
3) Try to keep your question concentrated on a smaller part of the code so that we can analyze and help you out with your problem faster.

Edited 6 Years Ago by csurfer: n/a

I got it all to work but test 4 fails from the start and test 2 fails when it cant find the number 40 in the sequence. What function should i look at with the issue

MY Output of where the problems occur


START OF TEST 2:
Testing situations where the cursor goes off the sequence (4 points).
Using attach to put 20 and 30 in the sequence, and then calling
advance, so that is_item should return false ... passed.
Inserting 10, which should go at the sequence's front.
Then calling advance three times to run cursor off the sequence ... passed.
Calling attach to put the numbers 40, 50, 60 ...300 at the sequence's end.
Now I will test that the sequence has 10, 20, 30, ...300.
Test failed to find 40
Test 2 failed.
END OF TEST 2.

START OF TEST 4:
Testing the copy constructor (2 points).
Copy constructor test: for an empty sequence.
Testing that size() returns 0 ... Failed.
Basic test of size() or is_item() failed.

Test 4 failed.
END OF TEST 4.

12
If you submit this sequence to Dora now, you will have
12 points out of the 18 points from this test program.

Edited 6 Years Ago by Eagles36: n/a

Attachments
// 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 <cassert>    // Provides assert
#include <cstdlib>    // 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: 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 <cstdlib> // 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
#include <cassert>
#include <cstdlib>
#include "node1.h"
#include "sequence3.h"

using namespace std;

namespace main_savitch_5

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

    sequence::sequence(const sequence& source)
    {
	list_copy(source.head_ptr, head_ptr, tail_ptr);

	if(source.precursor == NULL)
	{
	    if(source.cursor == NULL)
	    {
		cursor = NULL;
		precursor = NULL;
	    }
	    else
	    {
		cursor = head_ptr;
		precursor = NULL;
	    }
	}
	else
	{
	    node* tmp_ptr = head_ptr;
	    node* source_ptr = source.head_ptr;

	    while(source_ptr != source.precursor)
	    {
		source_ptr = source_ptr -> link();
		tmp_ptr = tmp_ptr -> link();
	    }
	}
    }

    sequence::~sequence()
    {
	list_clear(head_ptr);
    }

    void sequence::start()
    {
	if(head_ptr==NULL)
	{
	    cursor=NULL;

	    precursor=NULL;
	}

	else
	{
	    precursor = NULL;



	    cursor=head_ptr;
	}
    }

    void sequence::advance()
    {
	assert(is_item());

	precursor=cursor;

	cursor = cursor->link();
    }

    void sequence::insert(const value_type& entry)
    {
	if (is_item( ))
	{
	    if(precursor==NULL || cursor==NULL)
	    {

		list_head_insert(head_ptr, entry);

		cursor=head_ptr;

		precursor=NULL;

	    }
	    else
	    {
		list_insert(precursor, entry);

		cursor= precursor->link();
	    }
	}
	else
	{
	    list_head_insert(head_ptr, entry);
	    
	    cursor = head_ptr;

	    precursor=NULL;
	}

	many_nodes++;
    }

    void sequence::attach(const value_type& entry)
    {
	if (is_item( ))
	{
	    precursor = cursor;

	    list_insert(cursor, entry);

	    cursor=cursor->link();
	}
	else
	{
	    if(head_ptr==NULL)
	    {
		list_head_insert(head_ptr, entry);

		cursor = head_ptr;

		precursor=NULL;

	    }
	    else
	    {
		precursor=list_locate(head_ptr,list_length(head_ptr));

		list_insert(precursor,entry);

		cursor=precursor;
	    }

	}

	many_nodes++;
    }

    void sequence::remove_current()
    {

	assert(is_item());

	if(cursor == head_ptr)
	{
	    if(many_nodes == 1)
	    {
		list_head_remove(head_ptr);
		precursor = NULL;
		cursor = NULL;
		head_ptr = NULL;
	    }
	    else
	    {
		node* tmp = head_ptr;
		head_ptr = head_ptr->link();
		delete (tmp);
		cursor = head_ptr;
		precursor = NULL;
	    }
	}
	else
	{
	    cursor = cursor -> link();
	    list_remove(precursor);
	}

	 
	--many_nodes;
    }

    void sequence::operator =(const sequence& source)
    {
	if(this == &source)
	{
	    return;
	}
	else
	{
	    list_copy(source.head_ptr, head_ptr, tail_ptr);

	    if(source.precursor == NULL)
	    {
		if(source.cursor == NULL)
		{
		    cursor = NULL;
		    precursor = NULL;
		}
		else
		{
		    cursor = head_ptr;
		    precursor = NULL;
		}
	    }
	    else
	    {
		node *tmp_ptr = head_ptr;
		node *source_ptr = source.head_ptr;

		while(source_ptr != source.precursor)
		{
		    source_ptr = source_ptr -> link();

		    tmp_ptr = tmp_ptr -> link();
		}

		cursor = tmp_ptr -> link();
		precursor = tmp_ptr;
	    }
	}

	many_nodes = source.many_nodes;
	
    }
    
    sequence::value_type sequence::current() const
    {
	assert(is_item());

	return cursor->data();
    }

}
// 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++"
//
// 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 <cstdlib>  // Provides size_t
#include "node1.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
// 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 <iostream>     // Provides cout.
#include <cstdlib>      // 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\n";
    cout << "(counting the first item as [0]). I will advance the cursor\n";
    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 << "\n    Cursor fell off the sequence too soon." << endl;
        answer = false;
    }
    else if (i != s)
    {   // The test.current( ) function returned a wrong value.
        cout << "\n    The item [" << i << "] should be " << items[i] << ",\n";
        cout << "    but it was " << test.current( ) << " instead.\n";
        answer = false;
    }
    else if (test.is_item( ))
    {   // The test.is_item( ) function returns true after moving off the sequence.
        cout << "\n    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.\n";
    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.\n";
    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.\n";
    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\n";
    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

Hello eagles36, were you able to solve your problem for test # 4? I am having a similar issue. What did you do to fix it?

In test2, where it fails to find the value of 40 in the node after 30, print out what it did find (or "no next node" if is_item() fails). Same for other tests.

A useful debug method might be printEntireList(), which can avoid using the other methods (so as not to upset cursor, just start a temporary pointer at head, and move it along until it's NULL) and just print the value at each node, and if the node is the one cursor is pointed at, maybe put the value in square-brackets or something.

This article has been dead for over six months. Start a new discussion instead.