assignment 1

Programming Assignment #1

Due: Fri, Feb 2

Objective

This assignment will provide practice with a templated vector class, along with practice on the basic concept of an iterator over a container.

Task

In your prior course, you should have seen examples of building array-based classes with dynamically managed arrays inside. This is the core concept of a vector class -- a container that stores a dynamically managed array internally.

For this assignment you will implement a templated vector class, along with an associated iterator class for helping with generic container traversals. The following starter files are provided for you:

tvector.h -- provides the declarations of the template classes TVector (the vector class) and TVectorIterator (an associated class to help with traversal of the container).
driver.cpp -- contains some sample test calls to the vector class functions, but should NOT be considered a complete or thorough set of tests. You will need to create more test cases to fully test your class features. This driver is provided to help illustrate some of the basic class features and concepts, including the use of iterators. Note that this driver does not exercise all functions in the vector class. Write your own calls to test them all!
driver_output.txt -- contains the output from running the above sample driver program

Your job will be to finish this templated set of classes by defining each of the functions in the tvector.h file. These should be defined in a file called:

tvector.hpp

Note that there is already a #include at the bottom of tvector.h where your definition file will be brought in. This illustrates a pretty standard format for setting up a templated class.

Iterators

The small class called TVectorIterator is a helper class that can be used in conjunction with the vector class. This is a common feature used in container classes like this. The purpose of an iterator is to provide a common and non-implementation-specific way of traversing a container, so that mulitple containers could potentially use common algorithms (like sorting and searching functions, for example). This will be explored and explained more in the course. For the iterator class in this assignment, here is a brief sample use:

  // suppose that V is a vector storing ints, and it has 
  //   already been populated with the values 3, 6, 9, 12, 15, 18, 21

  // this call would retrieve a vector iterator over the container V
  TVectorIterator<int> itr = V.GetIterator();

  // at this point, itr currently is positioned at the first element in 
  // the list (the 3).

  int x = itr.GetValue();		// x would now store 3
  itr.Next();				// itr has advanced to the 6
  int y = itr.GetValue();		// y would now store 6
  itr.Next();
  itr.Next();				// we have now advanced to the 12
  int z = itr.GetValue();		// z now stores 12
 
  itr.Previous();			// now we have moved backwards, to the 9
  int a = itr.GetValue();		// a stores 9.    etc.

This class essentially helps us walk through the container in a fairly easy way, with calls to Next() and Previous() to move around.

Program Details

Here are general descriptions of the two classes you are to define, along with a general description of each function's task.

1) class TVector

The member data of this class consists of a pointer to a dynamically managed array, along with tracking variables for the capacity and the size. Note that the capacity refers to how much space is currently allocated, and size refers to how many data items are currently stored. There is also a dummy variable of type T that can be used for error-checking situations. Specifically, some of the functions specify to return a stored data item, but if you encounter a situation like an empty container or other situation where there would not BE a valid data item, you can return a reference to the dummy object instead. This is needed because some such functions are pass-by-reference (so that the retrieved item can be modified by the caller under normal situations). There is also a static constant called SPARECAPACITY, which will be used to add some extra capacity when constructing vector objects.

Function descriptions

Default constructor -- creates an empty vector (no data elements), with capacity SPARECAPACITY.
TVector(T val, int num) -- creates a vector containing "num" copies of the data element "val", and the capacity should be set to whatever is needed for the stored data, plus the SPARECAPACITY amount.
Clear -- clear out the vector so that it represents an empty container (no data elements).
Big Five
- Destructor -- appropriate clean-up, no memory leaks
- Copy constructor -- deep copy
- Copy assignment operator -- deep copy
- Move constructor -- constructor with standard move semantics
- Move assignment operator -- assignment with standard move semantics
Accessors
- IsEmpty -- returns true if the container is empty, false otherwise
- GetSize -- returns the size (number of data elements)
- GetFirst -- returns the first data element (by reference)
- GetLast -- returns the last data element (by reference)
Note that error situations in the last two functions would occur if the container was empty (this what the "dummy" item is for).
Endpoint insert/removes
- InsertBack -- insert the data (parameter) as the last item in the container
- RemoveBack -- remove the last element in the container. If it is empty, just leave it empty
Iterator retrieval
- GetIterator -- create and return an iterator that is positioned on the first data item in the vector. If empty, return default iterator
- GetIteratorEnd -- create and return an iterator that is positioned on the last data item in the vector. If empty, return default iterator
SetCapacity
Change the vector's capacity (i.e. grow or shrink it) to the parameter value. IF this would result in a smaller capacity than the current number of data elements, then update the size to match the new capacity. (For example, if there are 10 items in the vector, but the capacity is set to 7, then we will lose the last three data items).
Insert (2 parameters)
The new data element (second parameter) should be inserted into the vector just before the spot referred to by the iterator (the first parameter). If the container is empty, just insert the single item. If the iterator does not refer to a valid spot, then insert at the end of the vector. Function should return an iterator to the newly inserted piece of data. Make sure to update this iterator appropriately before returning, as any change in capacity would change the location of the physical array.
Remove (1 parameter)
This function should remove the data item that is given by the iterator (the parameter). The function should return an iterator to the next data item (the one that was after the deleted data item). If the initial vector was empty, there's nothing to delete -- so just leave it empty and return a default iterator.
Remove (2 parameters)
This function should remove the data items in the RANGE that starts at the first iterator (pos1), up through but not including the second iterator (pos2). The function should return an iterator to the next data item (the one that was after the deleted data items). If the initial vector was empty, there's nothing to delete -- so just leave it empty and return a default iterator. If the first iterator is after the second iterator (error situation), don't delete anything, and just return the first iterator (pos1).
Print
Should print the entire vector contents, front to back, separated by the delimiter given in the second parameter. This function may assume that the stored type T has an available insertion << operator available for printing. Print to the stream given in the first parameter.
operator+
This is a standalone function that should return a TVector object that is the result of concatenating two TVector objects together -- in parameter order. See driver.cpp program for examples. (No, this function is NOT intended as a friend function.)

2) class TVectorIterator

The TVectorIterator class has three member data variables -- a pointer to the data to which it currently refers, the size of the associated vector, and the index from the associated vector. Note that the iterator is not intended to be built as a stand-alone item, but rather is created and returned BY member functions in the TVector class, so that it is associated with the vector. We need data variables for size and index, because the array itself is not inside an iterator object. The pointer will be used to access the data (i.e. it will be needed by the GetData function!)

Default constructor -- a default iterator should just store the null pointer internally, as well as assume it is referring to an empty vector. We'll call this the "null iterator".
HasNext -- returns true if there is another data element after the current one (in the vector), false otherwise
HasPrevious -- returns true if there is another data element before the current one, false otherwise
Next -- advances the iterator to the next data element after the current one (unless currently storing nullptr). Returns an iterator to the new position.
Previous -- moves the iterator to the previous data element before the current one (unless currently storing nullptr). Returns an iterator to the new position.
GetData -- return the data item at the current iterator position. If the iterator is not pointing to a valid spot (i.e. null pointer), you can use the "dummy" that was defined previously. Note that this is a return by reference.

A few general rules!

Define all of the functions for these classes in the file tvector.hpp
Always make sure there is ROOM in the array before inserting a new item. If you ever try to insert data, and the array is full (to capacity), then increase the capacity by doubling it
Do NOT change any of the prototypes or member data declarations in the tvector.h file at all. All current declarations have the intended prototypes, and they will need to work with my main programs.
Clean up dynamic memory in appropriate places and do not leave any memory leaks

3) Test Program

Create a test program of your own in the file mydriver.cpp. You can use my provided driver.cpp as a general model of how to populate a vector. Your test program should contain the following tests/illustrations at a minimum:

Tests of all of the functions
Tests that involve vectors of at least two different stored types. Suggested types: int, double, char, string
At least 10 tests of each of the following
- InsertBack
- RemoveBack
- Insert (single item, iterator-based)
- Remove (single item, iterator-based)
- Remove (range, iterator-based
The tests for each of these should not be all in a row for any single one. I.e. for best testing, make sure that insert/remove calls of a single function type are frequently interspersed between other types. (This way, a mistake in one will often be revealed by later calls to others)
Clear illustrations of vector contents with Print before and after major sets of insert/delete tests. Make your outputs readable and easy to follow for best testing/results.
At least one test that uses an iterator to traverse a vector front to back
At least one test that uses an iterator to traverse a vector back to front

4) makefile

Create a makefile that configures a build of both my provided driver (driver.cpp) and your test program (mydriver.cpp). i.e. when you type "make" in the directory, it should compile and build both executables. Make your executables named "driver.x" and "mydriver.x", respectively.

5) General Requirements

Document your code appropriately so that it is readable and easy to navigate
You may use standard C++ I/O libraries, as well as class libraries like string. You may NOT use any of the container class libraries from the STL
If you wish to add any helper functions to the TVector class, you may modify the tvector.h file for this purpose. But do NOT change any of the expected interface function prototypes or add extra member data. Any helper functions you write should be in the private section
Make sure your files compile and run on linprog.cs.fsu.edu with g++, using the C++11 standard compilation flag, or use "g++6", which has the C++11 features as a baseline. This is where they will be tested and graded

Deliverables and submitting

These are the deliverable files you should submit:

  tvector.h
  tvector.hpp
  mydriver.cpp
  makefile

To submit, package up your files in a tar archive and upload this at the assignment submission link on the Canvas course site (in the "Assignments" section). Your tar file should be named in this format, all lowercase:

   lastname_firstname_p1.tar

   Example:  My tar file would be:    myers_bob_p1.tar

Note that in addition to the provided test cases, we will also test your program/classes using additional test programs. Your program must be able to pass all such test cases to obtain a full score for the corresponding components.