Assignment #1: C++ Review

Implement a data structure that supports the following operations: insert, findMin, findMax, deleteMin, deleteMax, isEmpty, makeEmpty. You must use the following algorithm: maintain a sorted array. Insert new items into the correct position in the array, sliding elements over one position to the right, as needed. findMin and findMax, and deleteMax are trivial. For deleteMin remove the item in position 0, and slide over all the other items one position to the left. There are two forms: one informs the caller what item was removed, and the other does not.

Testing the Class

I will provide a program to test your package. Compile the program with the package, and give me the output. Warning: you should probably write another program to make sure everything works. Even if your package works with the test program, if I detect a bug, you will lose points.

I expect well-commented and well-documented code. It is a given that the program will work 100% correctly.

Requirements

Here is the class interface, which would be placed in a file named DoubleEnded.h. Note that you can and should add private member functions as needed to avoid replication of code.

#include <vector>
using std::vector;

template <class Comparable>
class DoubleEnded
{
  public:
    DoubleEnded( int maxSize = 3 );
    ~DoubleEnded( ) { }

    void makeEmpty( );
    void insert( const Comparable & x );
    void deleteMin( Comparable & x );
    void deleteMax( Comparable & x );
    void deleteMin( );
    void deleteMax( );
    const Comparable & findMin( ) const;
    const Comparable & findMax( ) const;
    bool isEmpty( ) const;

  private:
    int currentSize;
    vector<Comparable> theArray;  // the array
};

You must use the STL vector class. You must use separate compilation. You must double the theArray vector when it becomes full. You should throw an exception for accesses or deletions on an empty DoubleEnded object. Make sure to include a comment section that explains the properties that Comparable must have in order for the DoubleEnded template to correctly instantiate. For instance, Comparable objects must be comparable in some way.

Submission Procedure

Submit all your source code, and the results of running the program on the data I will specify. Your source code should include a signed disclaimer that states the work is your own. Your submission must be stapled or otherwise bound together. Failure to follow these instructions will adversely affect your grade for the assignment.

Due Date

This assignment is due on Tuesday, September 7.

System Things

Make sure you have a current compiler.

Collaboration Rules

This project is an individual project. Everyone should submit their own work. If I determine that two or more students have collaborated, then those students will all fail the course immediately, regardless of who copied from whom.

Quiz

There will be a quiz at the start of class on the due date. You will be asked to write an interface and/or implementation for a similar data structure.