Assignment #1: Java 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.

Testing the Class

I will provide a program to test your implementation. Compile the program, 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 for cop3530.DoubleEndedPriorityQueue. You will implement your class as cop3530.ArrayDoubleEndedPriorityQueue. You may not change the interface in any way whatsoever. You should not add any new public methods to your implementation, but you can add private member functions as needed to avoid replication of code.

package cop3530;

public interface DoubleEndedPriorityQueue
{
    void makeEmpty( );
    void insert( Object x );
    Object deleteMin( );
    Object deleteMax( );
    Object findMin( );
    Object findMax( );
    boolean isEmpty( );
}

Here is the rough outline of the implementation:

package cop3530;

import java.util.Comparator;

public class ArrayDoubleEndedPriorityQueue implements DoubleEndedPriorityQueue
{
    public ArrayDoubleEndedPriorityQueue( )
      { /* Implementation not shown */ }

    public ArrayDoubleEndedPriorityQueue( Comparator c )
      { /* Implementation not shown */ }

    public void makeEmpty( )
      { /* Implementation not shown */ }

    public boolean isEmpty( )
      { /* Implementation not shown */ }

    public Object findMin( )
      { /* Implementation not shown */ }

    public Object findMax( )
      { /* Implementation not shown */ }

    public Object deleteMin( )
      { /* Implementation not shown */ }

    public Object deleteMax( )
      { /* Implementation not shown */ }

    public void insert( Object x )
      { /* Implementation not shown */ }

    public String toString( )
      { /* Implementation not shown */ }

    private Comparator cmp;
    private int size = 0;
    private Object [ ] items = new Object[ 5 ];
}

In implementing this interface you must use an array of Object as the private data (shown as items), along with a size field. You must double the array when it becomes full. You should throw a runtime exception for accesses or deletions on an empty DoubleEndedPriorityQueue object (define a class cop3530.UnderflowException).

Observe that signatures all refer to objects of type Object. A DoubleEndedPriorityQueue object is created by supplying a java.util.Comparator (i.e. a function object); if none is given, it is assumed that the items in the double-ended priority queue all implement the java.lang.Comparable interface and can be compared by calling compareTo. The private data field cmp stores a reference to the comparator. You will need to create a private nested class that implements the default comparator, and have the zero-parameter constructor initialize cmp to an instance of the default comparator.

Make sure to run your code through Javadoc and have a good comment section.

Submission Procedure

Submit all your source code, the Javadoc output, 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, January 22.

System Things

Make sure you have a current compiler. java.util.Comparator is not defined in Java 1.1.

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.