Project 1

Project 1 is due Friday October 30 at midnight.

Project 1 is to implement Exercise 2..9 from Chapter 2. That is, implement a RootishArrayDeque which uses \(O(\sqrt{n})\) wasted space and supports add and remove in time \(O(1+\min(i,n-i))\). To do so, you will have to carry out the following steps:

Step 1

Copy my StringArrayStack implementation, put it into a file arraystack.h, and change it into a template which allows storing any type. That is, inside a file arraystack.h, add a definition

template <typename T>
struct ArrayStack {
    //store an array of T instead of string, but otherwise the same code
};

Step 2

Copy the following code into a file sharedarray.h. It is a simpler version of Boost's shared_array, but is enough for our purposes and makes it so that our project does not depend on Boost. Note that C++ never standardized a shared_array because the best practice is just to use the C++ vector instead of arrays. But we are discussing possible implementations of vector so we can't use vector.

#include <memory>
#include <cstdlib>
using namespace std;

template <typename T>
struct shared_array {
    private:
        shared_ptr<T> array;

    public:
        shared_array(int size) {
            array = shared_ptr<T>(new T[size], default_delete<T[]>());
        }

        T &operator[](size_t idx) {
            return array.get()[idx];
        }
};

This implements a shared array that will be deallocated automatically once the last reference to it is removed. Here is some example usage:

int main() {
    shared_array<int> arr(10);

    for (int i = 0; i < 10; i++) {
        arr[i] = i * 100;
    }

    for (int i = 9; i >= 0; i--) {
        cout << "Entry " << i << " is " << arr[i] << endl;
    }
}

In particular, you pass the size to the constructor and then can use it just like any array using the [] syntax. If you want, you can go back to the ArrayStack implementation in Step 1 and switch it to use shared_array instead of an array, but this is not required.

Step 3

Implement a structure RootishArrayDeque into a file rootisharraydeque.h which has at most \(O(\sqrt{n})\) wasted space and where add and remove run in time \(O(1+\min(i,n-i))\). You must implement size, get, set, add, and remove. For grading, we will include the file rootisharraydeque.h and call these methods. To help yourself with testing, I suggest you also implement a print method.

#include <memory>
#include <iostream>
#include "arraystack.h"
#include "sharedarray.h"

template <typename T>
struct RootishArrayDeque {
    //implementation here.  Some useful code snippets:
    //
    //Use an ArrayStack< shared_array<T> > to store a list of blocks, so that each block
    //is a shared_array<T>
    //
    //You can create a new block using:
    //shared_array<T> newBlock(newBlockSize);
    //the above line of code creates a new array of size newBlockSize and places it into a
    //variable called newBlock
    //
    //To access an entry in block b and index j within that block, use
    //someBlockList.get(b)[j]
    //
    //To set an entry in block b and index j, use
    //someBlockList.get(b)[j] = someVal;
};

Hint: There is more than one possible implementation, but you should think about DualArrayDeques. They had the right running time but not the right amount of wasted space.

Step 4

Write a document analyzing your data structure. Explain why it uses at most \(O(\sqrt{n})\) wasted space and describe with proof the amortized cost of each of the methods. This document should be similar to the writups that appear in Chapter 2.

Step 5

Add a comment to your implementation explaining why all memory that is allocated to hold the blocks and entries is deleted. Since C++ memory management is such a big issue, it is common in the real world to have these types of comments, so that we know that the author of the code thought about how memory is stored and how all allocated memory is released.