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.h"

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

    void MakeEmpty( );
    void Insert( const Etype & X );
    void DeleteMin( Etype & X );
    void DeleteMax( Etype & X );
    void DeleteMin( );
    void DeleteMax( );
    const Etype & FindMin( ) const;
    const Etype & FindMax( ) const;
    bool IsEmpty( ) const;

  private:
    int CurrentSize;
    Vector<Etype> Element;  // the array

        // Disable copy constructor and copy assignment
    const DoubleEnded & operator=( const DoubleEnded & )
        { return *this; }
};
You must use the Vector class that is described in Chapter 3 and available online. You will need Vector.h, and Vector.cpp. (Note that the DoubleEnded constructor will require an initializer list to construct the Element data member). You must use separate compilation. You must double the Element vector when it becomes full. You must do something reasonable for accesses or deletions on an empty DoubleEnded object. I suggest using the EXCEPTION routine (Exception.h, Exception.cpp) that is also described in the text (and is needed by Vector anyway). Make sure to include a comment section that explains the properties that Etype must have in order for the DoubleEnded template to correctly instantiate. For instance, Etype 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. Your program must be available for inspection on solix. You should not in any way alter the program until it has been graded and returned (in other words, the program should have a time stamp in case submissions are lost). Failure to follow these instructions will adversely affect your grade for the assignment.

Due Date

This assignment is due on Wednesday, September 2.

System Things

All projects must run on solix. Make sure you have the current compiler. When you type the command 
which CC
the correct answer is 
/opt/SUNWspro/bin/CC

You may develop on other systems, but then you will have to make arrangements to get templates to work correctly. Futhermore, since Exception.h is too long a filename for 8.3 formats, you may need to rename a shortened filename back to Exception.h after you download it. Also, when you upload, you may need to tinker, and you will probably need to reformat to have proper indenting. In any event, it is your responsibility to give yourself enough lead time.

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.