Mastery 1.1: CPS 108, Spring 1997

This is similar to the mastery from CPS 108 in the fall of 1996, but NOT identical.
Due: March 1, no extensions (there will be a group project started during this time)

Mastery exams are solo projects, this mastery is required.

Templated Deques

You are to implement a templated class for double-ended queues, also called deques. There is a deque class in the C++ standard template library, the class described here is modeled loosely on that class.

You must implement the following operations for your deque class (as member functions).

Append: add an element to the end of the deque, this is an O(1) operation.
Prepend: add an element to the front of a deque, this is an O(1) operation.
Poplast: remove the last element of a deque, this is an O(1) operation.
Popfirst: remove the first element of a deque, this is an O(1) operation.
Size: returns the number of elements stored in a deque
operator []: returns the k-th element of a deque, this should be an expected time O(1) operation. There should const and non-const versions of this operation. The first element of a deque has index 0, it is an error to index before 0 or past Size()-1.
Insert: given an element and an index insert the element at the indicated position. This is an O(n) operation for an n-element deque, but you should try to make it as efficient as possible.
Delete: given an index, delete the element at the indicated position. This is an O(n) operation for an n-element deque.

In addition, you must implement a destructor, assignment operator, and copy constructor. You must also supply forward and reverse iterators accessible via MakeIterator and MakeReverseIterator member functions (these should return pointers to Iterators.)

Finally, you must overload += and + to merge two deques. Merging two deques is NOT commutative, the operation a += b for deques causes all of b's elements to be appended to a. The deque b is unchanged. This should be an O(m) operation where b has m elements.

Implementation Details

You cannot use any classes in your implementation, the deque must be implemented using only built-in types (e.g., no vector class, no list class). In other words, you'll use raw C-style arrays. You should feel free to borrow/steal code from the vector and list classes (on acpub see ~ola/courses/lib on cs machines see /usr/project/courses/cps008/lib.) You must implement these classes on your own.

Perhaps the easiest way to meet the requirements for O(1) append and prepend and expected O(1) access is to use an array of blocks Each block contains a pointer to an array (or struct containing an array) of (say 20) elements. Initially the middle cell of the block array is the only non-NULL pointer. To prepend you can add within a block, or add a new block before the leftmost block. A new block is added at the right when appending/inserting causes the rightmost block to fill. full. You'll only need to grow the block array when all its blocks are allocated. You might try using blocks of size 1 initially, it makes the coding easier. You might also try making each block a class with some intelligence.

Inherited Interface

Your class must be implemented by inheriting from the abstract base class ADeque declared below and accessible from ~ola/cps108/deque/adeque.h

#ifndef _ADEQUE_H #define _ADEQUE_H // abstract base class for implementing double-ended queues // (dequeues) // template <class Type> class ADeque { public: virtual ~ADeque(){}; // mutator functions virtual void Append(const Type & elt) = 0; // add element to end virtual void Prepend(const Type & elt) = 0; // add element to front virtual void Poplast() = 0; // pop last element virtual void Popfirst() = 0; // pop first element virtual Type & operator [](int index) = 0; // returns index-th entry virtual void Insert(int k, const Type & elt) = 0; // insert elt at index k virtual void Delete(int k, Type & elt) = 0; // delete and return elt virtual ADeque& operator += (const ADeque & rhs) = 0; // append rhs // accessor functions virtual const Type & operator[](int index) const = 0; // const version virtual int Size() const = 0; // returns #elts }; #endif

You may find it easier to implement a non-templated version of this class first (e.g., for ints or strings) and then change the implementation to be templated.

An example (not correct, not fully functional, but perhaps useful) of a templated implementation using a vector is accessible . Note that all member functions are implemented inline, inside the class declaration. This makes the example easier, but you should not do this.

Submission

Submit as shown below. You must submit .h and .cc files for your dequeue class. You must inherit from ADeque to facilitate our test programs. You should also submit your own test program testdeq.cc along with an explanation (in your README) of what your test program does and how well you think it tests the correctness of your implementation. Your makefile should be able to make the test program. (submit either a compressed tar file or all files as shown below)

  submit108 deque README Makefile *.cc *.h

Grading

This assignment is worth 25 points awarded as follows.

Behavior	Points
Works Correctly (performance irrelevant)	5
Meets Performance Specs	5
Style/Coding standards	5
Test Programs	5
README, Writeup	5

For extra credit, your deqeue class should handle it's own memory allocation, e.g., nodes that are deleted should be kept on a per-class (e.g., static) freelist and these nodes should be used when allocating new nodes. This can earn an aditional 10 points.