I expect well-commented and well-documented code. It is a given that the program will work 100% correctly.
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.