CS24, Fall 2016

Lab04:
Converting a class to use a dynamic array

Goals for this lab

By the time you have completed this lab, you should be able to

Step by Step Instructions

Step 1: Choose initial roles, create a directory and get files

Get together with your lab partner, and decide who will be the first pilot. Switch roles after awhile - before either of you gets tired, bored or distracted. If your regular partner is more than 5 minutes late, ask the TA to pair you with someone else for this week.

Log onto the pilot's account. If the pilot's account is not working, allow the navigator to log in instead. You will (both) work in this account for the rest of the lab.

Create a ~/cs24/lab04 directory and make it your current directory:

mkdir ~/cs24/lab04
cd ~/cs24/lab04

Now copy all of the files for this lab from ~cs24/labs/lab04/ in the class account to your cs24/lab04 directory: 

cp ~cs24/labs/lab04/* ~/cs24/lab04

Step 2: Study the fixed-size array version of class Words

Later in this lab you will convert this version into one that uses a dynamic array and does not have a fixed capacity. But first you should make sure that you understand the basic version.

The class is defined in words1.h, it is implemented in words1.cpp, and it can be tested by the interactive test program named wordstest1.cpp.

Use the following command to compile this version: 

g++ -o wordstest1 wordstest1.cpp words1.cpp
Then run the test program. If you append more than 10 words, it will fail an assertion test and exit abnormally. The same will happen if you attempt to get or modify an element past the used portion of the array.

After playing with the test program for (hopefully) a short while, study the code of the class itself, and study its implementation and use.

As you can see in the private section of the class, the data are stored in a fixed size array of strings that can never hold more than 10 strings. The constructor does not have to create this array, but it does set the value of capacity to 10, and the initial value of used to 0.

The append function will halt the program with an assertion if the used part of the array is already at capacity. The size and get_capacity functions work as expected. Although not important for this lab, you should notice the two different operator[] functions - the one not declared const is invoked when this operator is used on the left side of an assignment statement, and the other one is invoked in other situations.

Step 3: Learn what needs to be done, and why

The version of the class that you must implement is in words2.h.

This class redefines the basic default constructor to include a parameter to specify the container's initial capacity. As this parameter has a default value, it can be used with either zero or one argument. Your implementation will use the value of this argument to set the capacity instance variable. Also, you should use the new operator to allocate sufficient memory to store the number of strings specified by this parameter, and store a pointer to this memory in the data variable.

The new version defines a copy constructor that must make a "deep copy" of the data from the source Words object. This copy constructor must also insure that it sets both used and capacity to equal the corresponding values in the source, and that it copies all of the data items from the source into the new data array.

You must implement the destructor to deallocate the dynamic memory.

The other major part you must implement is the new assignment operator. This function will be invoked whenever an existing Words object appears on the left side of an assignment, and whenever a Words object is a value parameter or is returned by value from a function. Like the copy constructor, it must make a deep copy of the data from the source object, but first it should: (a) verify the source is not the same as the object on which it is invoked (just return *this if this == &source); (b) if the capacity of the source differs from the capacity of the object on which it is invoked, then you must (b.1) allocate new memory to match the source capactiy, (b.2) use delete to deallocate the memory used by the existing data, and (b.3) point the data instance variable at this new memory; and finally (c) copy all of the strings from the source data into this new memory. The function must return the object *this.

The append function will have no precondition anymore - so the assertion must be removed. Instead it must check whether or not the used portion of the array is at capacity though, and if it is, then this function must work to resize the array before appending the new item. We suggest you make the new capacity equal to twice the number of current items ("used * 2"). This process will require many of the same steps as the assignment operator to copy the existing data to new memory and deallocate the original data array.

It should not be necessary to change the implementations of any of the other functions.

Discuss the meaning of the necessary changes with your lab partner, to make sure you both understand (at least generally) what you are to do, and hopefully gain an appreciation for why these changes must be made. You might also want to refer to the textbook author's implementation of similar functions in his bag2.cxx file.

Step 4: Implement words2.h in a new file named words2.cpp

Start by copying our implementation of the first version of class Words: 

cp words1.cpp words2.cpp

Now it is time to edit the program with emacs or another editor of your choice. Lab01 had a link to some emacs help if you need it.

emacs words2.cpp

Make the following edits, then save, and quit the editor.

  1. Change the header comment at the top to show the correct file name (words2.cpp), and that now it will be a dynamic array version. Also add your name(s) and the date you are doing this lab.
  2. It must include "words2.h" now, instead of "words1.h", and it must become part of namespace lab04_2 instead of lab04_1.
  3. The existing constructor must take one unsigned int argument for the initial capacity (remember not to specify a default argument value in the implementation). Set the capacity instance variable to the value of this argument, and use the new operator to allocate sufficient memory for that many strings. Point data at this new memory.
  4. Implement the copy constructor and the assignment operator as discussed above.
  5. For the destructor, just copy the following and paste it into your implementation: 
    Words::~Words() {
    delete [] data;
}
  6. Revise the append function as discussed above too.

Step 5: Compile and test

After making two very small changes, you can use wordstest1.cpp to test parts of your new version of the class. Using an editor, change the line "#include words1.h" to "#include words2.h", and change the line "using namespace lab04_1" to "using namespace lab04_2" - that's it. Now you can compile as above (substituting "words2.cpp" for "words1.cpp" in the command). Use this program to perform unit tests of append at least, and try to append more than 10 items to find out how that part is working. Verify that capacity increases too.

When you are satisfied with your unit tests, you can perform slightly more complete tests with wordsexam.cpp, the same program we will use when you submit your implementation. Compile it as follows: 

g++ -o wordsexam wordsexam.cpp words2.cpp
Then run it three times to execute all three tests: 
./wordsexam 1
./wordsexam 2
./wordsexam 3
If all three tests say "PASS ALL" then proceed to Step 6.

Step 6: Submit words2.cpp

Submit Lab04 at https://submit.cs.ucsb.edu/, or use the following command from a CS terminal: 

~submit/submit -p 563 words2.cpp
Wait for the results of the 3 tests.

If you are working with a partner, be sure that both partners' names are in a comment at the top of the source code file, and be sure to properly form a group for this project in the submit.cs system.

After completing the required lab work

Done early, but still some lab time left? If you see students who are struggling, and the TA is busy helping other struggling students, then please offer your help to them. Did you know that teaching someone else to do something is considered to be the surest way for you to learn that something yourself?

PA3 is ready to work on now. And you are ready to work on it!

Evaluation and Grading

Each student must accomplish the following to earn full credit [50 total points] for this lab:

Prepared by Michael Costanzo.