Question

The purpose of this program is to help reinforce container class concepts and linked list concepts in C++. Specifically, the task is to implement the sequence class using a linked list. You need to use the author's file sequence3.h to create your implementation file named sequence3.cpp. Please make your code as efficient and reusable as possible.

Please make sure code can pass any tests.

sequence3.h

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

#ifndef MAIN_SAVITCH_SEQUENCE3_H
#define MAIN_SAVITCH_SEQUENCE3_H
#include <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

Answer 1

#include <cstdlib>
#include <cassert>
#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) {
           node *tail_ptr;
           list_copy(source.head_ptr, head_ptr, tail_ptr);
           many_nodes = source.many_nodes;
        }
        
        sequence::~sequence() {
                list_clear(head_ptr);
                many_nodes = 0;
        }
        
        void sequence::start() {
           if(many_nodes != 0){
                        cursor = head_ptr;
                        precursor = NULL;
           }
        }
        
        void sequence::advance() {
                if(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->link();
                    }
            }
                ++many_nodes;
        }
        
        void sequence::remove_current () {
                if (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::size_type sequence::size() const {
                return many_nodes;
        }
        
        sequence::value_type sequence::current() const {
                if(is_item()){
                        return cursor->data();
                }
        }
        
        bool sequence:: is_item() const {
                return (cursor != NULL);
        }
}