COSC 2415 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies

After reading Chapter 3 in your textbook, you can begin this assignment by completing the sequence class implementation from Chapter 3 (see below). Be sure to read through the section in Chapter 4 covering the Bag Class with a Dynamic Array before converting your sequence class to use a dynamic array.

Do Programming Project 2 part (a) at the end of Chapter 4 of the Main and Savitch book (page 209).

First, you need to complete the sequence class from Chapter 3. I have included code for most of the member functions below. You will need to write the insert( ) function. You can use the driver program from Chapter 3 to test this first version of the sequence class.

Then convert your sequence class to use a dynamic array. Be sure to add a reserve( ) function. Since your class objects will allocate dynamic memory, be sure to include all the standard functions that a class using dynamic memory needs (destructor, copy constructor, overloaded assignment operator).

Below is a partial implementation of the sequence member functions from Chapter 3 (static array version).

#include <cstdlib> // Provides size_t
#include <cassert> // Provides assert()

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

namespace main_savitch_3

{
// CONSTRUCTOR
   sequence::sequence( )
   {
      used = 0;
      current_index = 0;
   }

// MODIFICATION MEMBER FUNCTIONS
   void sequence::start( )
   {
      current_index = 0;
   }

   void sequence::advance( )
   {
      assert( is_item( ) );
      ++current_index;
   }

   void sequence::insert(const value_type& entry);

   void sequence::attach(const value_type& entry)
   {
      size_type i;

      assert( size( ) < CAPACITY );

      if ( !is_item( ) )
         current_index = used - 1;
      for ( i=used; i > current_index + 1; --i )
         data[i] = data[i-1];
      ++current_index;
      data[current_index] = entry;
      ++used;
   }

   void sequence::remove_current( )
   {
      size_type i;

      assert( is_item( ) );

      for ( i = current_index + 1; i < used; ++i )
         data[i-1] = data[i];
      --used;
   }

// CONSTANT MEMBER FUNCTIONS
   sequence::size_type sequence::size( ) const
   {
      return used;
   }

   bool sequence::is_item( ) const
   {
      return (current_index < used);
   }

   sequence::value_type sequence::current( ) const
   {
      assert( is_item( ) );
      return data[current_index];
   }
}