Project 3: Dynamic Arrays

Assigned:  16 October 2001

Homework Due:  21 October 2001

Project Due: 28 October 2001

Modified: 21 October 2001

Clarification -- 21 Oct 2001

Some students have asked if the user is able to randomly insert elements in the array. Such random access is possible, but only within the first "size" elements of the array, not within the "capacity" of the array. Because this class supports functions such as GetBack(), InsertAtBack(), etc. all user access to the array must be limited to the first "size" elements of the array, otherwise there is no easy way to tell where "Back" is. Please note the comment regarding the constructors. Both constructors cause the array to be completely filled, with no free memory -- i.e. the size and the capacity are initially the same. The net result is that all user elements of the array are always contiguous at the front of the array from index 0 to size-1.

Objective

The objective of this assignment is to practice writing C++ classes which use dynamic memory allocation/deallocation and overloaded operators.

Background

We want to write a class which will mimic the behavior of C++ int arrays, but whose size will grow and shrink dynamically in order to better manage memory.  The array should never be less than half full; if it becomes less than half full after an element is removed, then the memory allocated to the array should be halved.  When halving an odd-capacity array, the new capacity should be (old capacity + 1) / 2; this means that capacity should never be less than 1 unless it was zero at the time of construction. (19 Oct 2001)  Similarly, the array should double in size if an element needs to be added and there is no more free memory.  (The capacity should only change upon an insertion or a removal (16 Oct 2001).)  You must use this memory management scheme; we will be checking that your program is allocating and deallocating the correct amounts of memory.

 

Assignment

You will implement the class whose definition is shown below.  You may add whatever private members and functions you see fit; you may not change the public section of the class definition in any way (except that you may omit member function parameter names, and you need not include exactly the same comments).  We will be linking your compiled code in with our own main function for testing purposes, so although you will be submitting a main function definition as part of the project, you must also make sure that the file implementing your class compiles on its own into an object code file.

class DynamicArray
{

        // Note: all functions below should exit gracefully if an attempt is made to access a Dynamic
        //  Array outside of bounds -- that is, out of the bounds representing values actually stored
        //  in the structure, not just out of the bounds representing the memory allocated.
        //  None of your functions should cause a core dump, seg fault, bus error, etc. if such an 
        //  access is attempted.

        // All arrays are considered to be full immediately after a constructor is called (ie, there
        //  is no free memory remaining in the array).


    public:
              ~DynamicArray ( );  // destructor; destroys all dynamically-allocated memory


              DynamicArray ( int size = 1, int value = 0 ); // constructs a new Dynamic Array with size elements
                                                                                //  each element is initialized to value
                                                                                //  size ints total are allocated to the array


              DynamicArray ( int array [ ], int size = 1 ); // constructs a new Dynamic Array with size elements
                                                                              //   the elements are the first size elements of array
                                                                              //  size ints total are allocated to the array
                                                                              //  array is guaranteed to contain at least size elements

              DynamicArray ( const DynamicArray & ); // copy constructor; new DynamicArray will
                                                                            // have same allocation and elements as copied object

            DynamicArray& operator = ( const DynamicArray & );   // assignment operator
                                                                                                   //  same behavior as copy constructor

            int& operator [ ] ( int index );  // array access; same behavior as built-in array access

            friend ostream& operator << ( ostream&, const DynamicArray& ); // prints out array
                                                                            // elements in same order as stored in memory

            int GetFront ( void ) const; // returns first element of DynamicArray object
            int GetBack ( void ) const; // returns last element of DynamicArray object


            void InsertAtIndex ( int value, int index );  // inserts value into dynamic array at position index 
                                                                           //  existing elements pushed to back (end) of array
            void InsertAtIndex ( int array [ ], int size, int i );  
                                    // inserts the first size elements of array into the DynamicArray beginning at index i
                                   //  existing elements pushed to back (end) of array
            void InsertInFront ( int value );  // value becomes first element of DynamicArray object
                                                            //  existing elements pushed toward back (end) of array
            void InsertInBack ( int value );  // value becomes last element of DynamicArray object


            int RemoveFromIndex ( int i );  // removes and returns Dynamic Array element at position i 
                                                                  //  remaining elements pulled to front (start) of array
            void RemoveFromIndex ( int size, int i ); // removes size elements of Dynamic Array beginning at
                                                                          //  index i
            int RemoveFromFront ( void ); // returns and removes first element of DynamicArray object
                                                           //   remaining elements pulled to front (start) of array
            int RemoveFromBack ( void ); // returns and removes last element of DynamicArray object

 

            int GetCapacity ( void ) const;    // returns total number of ints allocated to the array member
            int GetSize ( void ) const;  // returns total number of elements actually stored in the array member

    private:
               

};

Error Conditions and Behavior (added 19 October)

Your class should handle any errors it is capable of detecting (array access out of bounds, etc.)  The following should be the behavior of your member functions if an error is detected:

Functions of return type int, int&:

    Print (to cout) the message: "Error in function of return type int"
    Return the value 0
    Do nothing else

Functions of return type void:

    Print (to cout) the message: "Error in function of return type void"
    Do nothing else

Constructors:

    Print (to cout) the message: "Error in constructor"
    Allocate no dynamic memory
    Set up any member fields correctly (ie, size and capacity will be 0, etc.)

Homework Portion

The homework portion of this project will be worth 10% of the project grade.  For the homework, create a plain text file (end the filename in .txt) which includes a list of exceptional test cases you think your class should be able to handle (like accessing arrays out of bounds, etc.)  This file is not intended to be compiled; it is only for you to express your test cases. Each test should indicate which public member function(s)/operator(s) is/are being tested. (17 Oct 2001)  When you submit your class header and implementation, you will also be submitting a main function which should test for all these cases and run correctly.  Your homework will be graded both on the completeness of your test case set and on the extent to which you correctly handle these test cases in the implementation of your program.  Remember to submit your homework file by the homework due date.  Late homework submissions are not accepted.

Requirements

  1. Write your program in C++, using the g++ compiler installed on the linux systems at UMBC (linux.gl.umbc.edu). Use C++ input and output, not printf and scanf.  The graders will compile your code using the -ansi and -Wall switches, so make sure to test your program with these, and to use these in your makefile.
  2. As per the syllabus, your project must compile (under the above-mentioned compiler) in order to receive credit.  See the syllabus for more details.
  3. You must follow the course style guidelines listed on the course web page.
  4. Write and submit separate header, class implementation, and main files, as discussed in lecture along with your makefile.  Make sure that your class implementation compiles on its own also.
  5. Your makefile must produce an executable named proj3 which tests your class implementation with the test cases you mentioned in your homework.  There's no need to include another rule in the makefile to generate the object code for your class implementation, however.
  6. When designing your program, pay attention to the design considerations discussed in class.
  7. Be sure that in your class definition and implementation, you have spelled the names of all public member functions listed above, and the name of the class, correctly!  Failure to do so will cause your code not to compile with the main function used for grading.
  8. You must use new and delete for dynamic memory allocation and deallocation (not malloc and free).
  9. None of your public member functions should, directly or indirectly, print anything to the screen, except in the cases of the error messages mentioned above. Each function should simply perform the appropriate task and return any appropriate value. The one exception to this is the output operator, of course.
  10. You must name your Dynamic Array header file DynamicArray.h and you must name your DynamicArray implementation file DynamicArray.cpp .  If you do not, we will not be able to link your code in with the main function used for grading.

 

Turning in your program

You must include the following statement in a comment section of each file of your program:

 

I have read and I understand the course policy on cheating. By submitting the following program, I am stating that the program was produced by my individual effort.

Turn in your program using the UNIX submit utility, by using the following command at the unix prompt:

submit cs202 proj3 filename

where filename is the name of the file you wish to submit.  Remember to submit a plain text file for the homework assignment, your C++ source and header files for the project, and your makefile.  After entering this command, you should get a confirmation that submit was successful:

Submitting filename...OK

You can check your submission by entering the command:

submitls cs202 proj3

This will show the names of all files you have submitted for this project, along with the size and submission date and time of each.  You should use submitls after each submission.  Make sure that you are submitting your assignments under the correct course name and project name, especially if you are taking more than one course which uses the submit utility.  Note that repeat submissions of the same filename cause only the latest version to be submitted, and that file will be marked with the time and date of the last submission.

Late Policy Reminder

This project is due by midnight (1 minute after 11:59pm) on Sunday, 28 October 2001. We will use the linux.gl system clock as the final arbiter of time and date. Projects turned in up to 24 hours late will receive a 10% penalty; project submitted between 24 and 48 hours late will receive a 25% penalty.  Projects will not be accepted past 48 hours after the due date.  Late homework submissions are not accepted.