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

Be sure to read through Section 6.3 in your textbook before starting this assignment. Be sure that your program meets the requirements listed on the Professional Programming Stype page (see link on the main assignments page). Implement a List class that uses a dynamic array to store the items in a list. Your list class will include the ability to "grow" when it becomes full, as described below. For background information, refer to Section 6.3 of your text book, An Array-Based Implementation of Lists with Dynamic Allocation, and the first solution to Deficiency #1 on page 85.

Start with the List class from Figure 6.2 on pages 270 - 274 of your book. You can download the code here:

http://cs.calvin.edu/activities/books/c++/ds/2e/SourcePrograms/

The code in the textbook tends to display messages in class functions, so I am providing an edited copy of the class implementation file here:

DList.cpp

Add a public function member called resize( ) as follows:

   /***** resize operation *****/
   void resize( int newCapacity);
   /*----------------------------------------------------------------------
     Change the capacity of a list

     Precondition:  None.
     Postcondition: The list's current capacity is changed to newCapacity
         (but not less than the number of items already in the list).
   -----------------------------------------------------------------------*/

Pseudocode:

If newCapacity < current size
   Set newCapacity to current size
If newCapacity is the same as the current capacity
   Do nothing (return)
Dynamically allocate a new array with size newCapacity
Copy the data from the current array to the new array
Free the memory allocated to the current (old) array
Make the list point to the new array
Update the capacity of the list

Then modify the insert( ) function as follows. Remove the precondition that there is room in the array for the item to be inserted. If the array is full, double its capacity using resize( ) and then perform the insertion.

Be sure to update your class documentation as required.

Test your class using a list of integers. I want you to use a menu-driven program for testing where the user can specify which command to test and the data to store in the list. Here is some sample code to help you get started on your test program.

#include <cctype>       // Provides toupper
#include <iostream>     // Provides cout and cin
#include <cstdlib>      // Provides EXIT_SUCCESS
using namespace std;
#include "DList.h"  

// PROTOTYPES:
void print_menu( );
// Postcondition: A menu of choices has been printed.

int get_number( );
// Postcondition: The user has been prompted to enter an integer number. The
// number has been read, echoed to the screen, and returned by the function.


int main( )
{
    List test;     // A List to perform tests on
    char choice;   // Command entered by the user
    
    cout << "I have initialized an empty list of integers." << endl;

    do
    {
        print_menu( );
        cout << "Enter choice: ";
        cin >> command; 
        choice = toupper(choice);
        
        switch (choice)
        {
            case 'C': // add code to change the capacity of the list
                      break;
            case 'E': // add code to print result of empty( )
                      break;
            case 'P': // add code to print the list
                      break;
            case 'I': // add code to input an item and position, and insert item into the list
                      break;
            case 'R': // add code to input a position, and erase the item at that position
                      break;     
            case 'Q': cout << "Test program ended." << endl;
                      break;
            default:  cout << choice << " is invalid." << endl;
        }
    }
    while ((choice != 'Q'));

    return EXIT_SUCCESS;
}

void print_menu( )
{
    cout << endl; 
    cout << "The following choices are available: " << endl;
    cout << " C   Change the capacity of the list using resize( )" << endl;
    cout << " E   Print the result from the empty( ) function" << endl;
    cout << " P   Print a copy of the entire list" << endl;
    cout << " I   Insert a new number with the insert(...) function" << endl;
    cout << " R   Remove a number with the erase( ) function" << endl;
    cout << " Q   Quit this test program" << endl;
}

char get_user_command( )
// Library facilities used: iostream
{
    char command;

    cout << "Enter choice: ";
    cin >> command; // Input of characters skips blanks and newline character

    return command;
}

int get_number( )
// Library facilities used: iostream
{
    int result;
    
    cout << "Please enter an integer number for the list: ";
    cin  >> result;
    cout << result << " has been read." << endl;
    return result;
}