Project 5: Containers and Iterators

Due: Thursday, May 5, 2016 by 9:00 pm

Objectives

The objectives of this project are:

To create a templated container class
To implement iterators for a container class
To implement copy constructors and overloaded operator=

Secondarily, through implementation of the container and iterator classes, to gain additional experience with pointers.

Background

The class my_array is a simple container class with a const_iterator. The code for the class and a simple driver are provided:

You can compile and run the driver program:

   g++ -g -Wall -ansi my_array_driver.cpp my_array.cpp -o my_array_driver
   ./my_array_driver

The functionality of my_array is very limited:

It can only store int values; we would like to be able to store most any type of value.
It has a fixed maximum number of elements it can hold; we would like to be able to add or remove items and have the underlying array be re-sized automatically.
It doesn't store items in any order; we would like to store items in ascending order.

In addition, we'd like to be able to iterate over the container in a pseudo-random order (the pseudo-random order should be a permutation, meaning we visit each element exactly once). With these improvements the class could be used, say, to store songs in a playlist, and the random iterator would allow us to 'shuffle' the songs. Or I could use it to store a class roster, and the random iterator would allow me to call on students in a pseudo-random order.

Assignment

Your assignment is to implement a templated class called sorted<T> that stores items in increasing order within a dynamically-allocated array. The elements of sorted<T> can be of any type that implements operator< and operator>. In addition, you must create two iterators: a constant iterator const_iterator that iterates over the elements in sorted order, and a pseudo-random iterator rand_iterator that iterates over the elements according to a pseudo-randomly generated permutation.

The container class sorted<T> and the iterator classes should be defined in the file sorted.h and implemented in sorted.cpp. You must also thoroughly test the classes and submit your tests in the main program mytest.cpp.

Although the my_array class and iterator are very basic, you should study them well as their structure is similar to the container and iterators that you will write.

`sorted<T>` Container Requirements

The container must be able to store elements of any type that implements operator> and operator<, and must store the items in ascending order.

The container should not have any fixed limits on the number of items that it can hold; to achieve this, it must use a dynamically-allocated storage array. (Clearly, the number of items that can be stored is limited by the amount of memory in the computer, but we're not worried about that.) The storage array must be re-sized as elements are inserted or erased from the container, but it is inefficient to re-size the array every time an element is inserted or erased. One approach is to initialize the array to a small length n; once the number of elements in the array equals n, double the size of the array to 2n; if the number of elements increases to 2n, double the size again to 4n, etc. Similarly, if after erasing elements, at most one-quarter of the capacity of the array is used, it should be re-sized to half the current capacity, but never to less than n elements. The choice of n is up to you, but something like 10 (or 8 if you prefer powers of two) would be reasonable.

Note that you will have to keep track of both the capacity of the array, that is, it's allocated length, and it's size, the number of items stored in the array. In the remainder of the project description, the term 'capacity' will always refer to the allocated storage in the container and 'size' will refer to the number of items stored in the container.

Since the class must use dynamically allocated memory, you must implement a copy constructor and overload operator=.

See the Required Functions section below for a list of functions that must be implemented in the sorted<T> class; additional functions may implemented as needed.

`const_iterator` and `rand_iterator` Iterator Requirements

You must implement two iterators for the sorted<T> class:

A constant iterator const_iterator that iterates over the elements of a sorted<T> object in sorted order. We use a const_iterator rather than a plain iterator because we do not want to be able to change a value by dereferencing the iterator since this would potentially store elements out of the proper order.
A random iterator rand_iterator that iterates over the elements of a sorted<T> object in order of a pseudo-random permutation; that is, the iterator access each item of the object exactly once, but in a pseudo-random order.

For rand_iterator constructors that do not accept a seed for the random number generator as a parameter, you may use either a fixed seed or time(NULL).

The rand_iterator will need to construct a permutation, and since the size of the permutation depends on the container it is being used with, the permutation array will need to be allocated dynamically. Therefore, rand_iterator needs a copy constructor and overloaded operator=.

See the Required Functions section below for a list of functions that must be implemented for each of the iterator classes. You will probably need to implement additional functions, either helper functions or non-default constructors.

Implementation Issues

[4/27] When a rand_iterator operator determines that the container has changed, and so the rand_iterator is invalid, it should throw an exception rather than re-initialize itself. This applies to pre- and post-increment, dereference, and operator!=. You will need to write a small exception class, which must be declared in the file iterator_ex.h and implemented in iterator_ex.cpp. The exception class must be derived from the exception class, so you will need to #include <exception>. The exception class must have a single private variable of type const char* and must implement the following functions:
1. default constructor — sets the private variable to the empty C-string.
2. non-default constructor — sets the private variable to a user-supplied C-string.
3. const char* what() const throw() which returns the C-string stored in the private variable. Note: here throw() indicates that the what() function will not throw an exception.
Here is a simple example of an exception class. (In this example, the implemenation is in-line, and there is no non-default constructor.) So long as you follow these conventions, you may name your exception whatever you like (I understand Prof. Chang's section has already discussed 'interesting' exception names!).
Background: You should never perform an operation on an invalid rand_iterator, so the operators must check whether the associatd container has been modified before attempting to increment or dereference the iterator. Also, if the iterator is invalid, the results of operator!= will be nonsense. Initially, we said that if the iterator becomes invalid, you should re-initialize the iterator by generating a new random permutation, but this could cause weird things to happen, e.g. you could iterate over some of the elements more than once. Also, throwing an exception allows higher-level code to decide how to deal with the error.
[4/27] Use of typename. In a template implemenation, it is possible that the compiler can not tell the difference between a variable and a type. For example:
```
    template <class T>
    sorted<T>::const_iterator sorted<T>::begin() {
      // Implementation goes here...
    }
```
We want sorted<T>::const_iterator to be interpreted as a type, but the compiler can't be sure that it isn't meant to be a const_iterator variable, and so it produces an error:
```
    sorted.cpp:76: error: expected constructor, destructor, or type conversion before ‘sorted’
```
We can fix this by telling the compiler explicitly that this is meant to be a type by adding the typename keyword:
```
    template <class T>
    typename sorted<T>::const_iterator sorted<T>::begin() {
      // Implementation goes here...
    }
```
See the Wikipedia Article for a concise description of the uses of typename.
Re-sizing of the storage array in sorted<T> should occur whenever insert() would cause the size to exceed the capacity or whenever erase() causes the size to fall to one-quarter the capacity or less. Since arrays can not be re-sized, this will require that a new storage array of the appropriate capacity be created, the data from the old storage array be copied to the new storage array, the old storage array be deleted, and the storage array pointer in the object be set to point to the new array. Pay particular attention to the iterator returned by erase() in the event that the storage array is re-sized.
Since sorted<T> must store items in ascending order, the rand_iterator implementation may not shuffle the items in place. One approach is to create an array of indices into the storage array and permute the indices; then using the permuted indices in order will have the effect of iterating through the data in a pseudo-random order. The shuffling techniqe from the Cruno project can be used to permute an array of indices to generate a pseudo-random permutation.
A rand_iterator is fully-initialized if it is associated with a container object and has a permutation that can be used to iterate through the elements in pseudo-random order. A rand_iterator created with the default constructor can not be fully-initialized because it is not associated with a container object, and therefore cannot determine the size of permutation that is needed.
The rndbegin() function creates a fully-initizialized rand_iterator. rndbegin() is a function of the container class, and therefore has access to the size of the container and the data in the container.
Remember that the end() and rndend() functions should return an iterator that is "one past the end of the storage array" to indicate that an iterator has reached the end of the container. For end() this is simple: return an iterator that points to the memory address just beyond the end of the storage array. For rndend(), it is a bit trickier; think about this when you are designing your permutation generation method.
If the sorted<T> container object is modified by insert() or erase(), then any rand_iterator associated with the object becomes invalid ~~and must be re-initialized~~. This makes sense because the pseudo-random permutation created when the iterator is initialized depends upon the number of elements in the container. Your sorted<T> class must have a way to track when an object of the class is modified, and any initialized random iterator must have a way to check whether its associated container has been modified.
To re-initialize a rand_iterator means to generate a new pseudo-random permutation of the appropriate size using the same seed that was used to generate the original permutation.
Be sure to run valgrind to check for memory leaks; likely culprits are the destructors for sorted<T> and rand_iterator and code used to re-size the storage array.

Submitting Your Program

A minimal test program sorted_driver.cpp is provided as an example. Your sorted<T> class should work with this program, but you should also implement more extensive tests in mytest.cpp.

You should submit the following files to the proj5 directory:

sorted.h
sorted.cpp
mytest.cpp
iterator_ex.h [added 4/27]
iterator_ex.cpp [added 4/27]

If you followed the directions in setting up shared directories, then you can copy your code to the submission directory with:

    cp sorted.h sorted.cpp mytest.cpp iterator_ex.h iterator_ex.cpp  ~/cs202proj/proj5/

You can check that your program compiles and runs in the proj5 directory, but please clean up any .o and executable files. Again, do not develop your code in this directory, and do not keep the only copy of your program here.

If you are submitting late, you need to copy to proj5-late1, or proj5-late2 instead of proj5. Make sure you understand the course late submission policy.

Required Functions

The following public functions are required. You may implement additional constructors or other private or public functions.

`sorted<T>` required functions

  //Default constructor
  sorted();

  // Non-default constructor copies data from array to sorted
  sorted( T* data, int len );

  // Copy constructor
  sorted( const sorted<T>& srtd );

  // Destructor
  ~sorted();

  // Overloaded assignment operator
  sorted<T> operator=(const sorted<T>& srtd);

  // Return the capacity of the storage array
  int capacity() const;

  // Return number of items stored
  int size() const;

  // Return the address of the storage array;
  // for use in grading programs
  T* getStorageArray() const;

  // Insert an item in sorted; return iterator to inserted item
  const_iterator insert(T data);

  // Remove an item from sorted; return iterator to next item
  // after the erased item
  const_iterator erase(const_iterator itr);

  // Get element at indx position                                                  
  const T& at(int indx);

  // Starting iterator value for const_iterator
  const_iterator begin();

  // Ending iterator value for const_iterator; typically,
  // one element beyond the last valid element in the array.
  const_iterator end();

  // Starting iterator value for rand_iterator.  Should use constant
  // value or time(NULL) as seed value for srand().
  rand_iterator rndbegin();

  // Starting iterator value for rand_iterator with seed for
  // srand() specified.  Given a sorted<T> object x, repeated 
  // use of rndbegin( unsigned seed ) with the same seed value
  // must produce the same permutation of the elements of x.
  rand_iterator rndbegin( unsigned seed );

  // Ending iterator value for rand_iterator
  rand_iterator rndend();

`const_iterator` required functions

  // Default constructor
  const_iterator();

  // Non-default constructor sets value to given address
  const_iterator(T* addr);

  // Pre-increment, e.g. ++itr
  const_iterator operator++();

  // Post-increment, e.g. itr++
  const_iterator operator++(int);

  // operator!= needed for loop control, e.g. itr != x.end()
  bool operator!=(const const_iterator& itr);

  // Unary dereference operator; returns element currently pointed
  // to by the const_iterator
  const T& operator*();

`rand_iterator` required functions

  // Default constructor
  rand_iterator();

  // Non-default constructor; pointer to sorted<T> object passed 
  // as a parameter, which allows the rand_iterator to access 
  // variables of the associated sorted<T>> container
  rand_iterator( sorted<T>* srtdPtr );

  // Non-default constructor; pointer to sorted<T> passed as in
  // previous constructor, but also passes seed for random number
  // generator
  rand_iterator( sorted<T>* srtdPtr, unsigned seed );

  // Copy constructor
  rand_iterator( const rand_iterator& itr );

  // Destructor
  ~rand_iterator();

  // pre-increment
  rand_iterator operator++();

  // post-increment
  rand_iterator operator++(int);

  // operator!= needed for loop control, e.g. itr != x.end()
  bool operator!=(const rand_iterator& itr);

  // Unary dereference operator
  const T& operator*();

  // Overloaded assignment operator
  rand_iterator operator=(const rand_iterator& itr);

Exception class required functions [added 4/27]

You may name your exception class whatever you like so long as you put the definition in iterator_ex.h, the implemenation in iterator_ex.cpp, and provide the required functionality; in the following, we use iterator_ex as an example.

  // Default constructor
  iterator_ex();
  
  // Non-default constructor
  iterator_ex(const char* message);

  // Accessor function
  const char* what() const throw();

CMSC 202 — Spring 2016 — Prof. Marron