deleteMin method in DoubleEndedPriorityQueue (BinarySearchTree)
Is the problem in deleteMin or is the program testing for the UnderflowException
Thank You
After the program prints:
"Completed first round of insertions"
I get the following:
OOPS!!!! 234584 234581 234586 234585
OOPS!!!! 234578 234564 234584 234583
OOPS!!!! 234450 234197 234582 234581
OOPS!!!! 233944 233046 234580 234579
OOPS!!!! 232148 155579 234578 234577
Completed first round of deletions
Completed second round of insertions
Exception in thread "main" cop3530.UnderflowException: Double-Ended Priority Queue is empty
at cop3530.TreeDoubleEndedPriorityQueue.deleteMin(TreeDoubleEndedPriorityQueue.java:68)
at Assign4.test3(Assign4.java:68)
at Assign4.main(Assign4.java:127)
deleteMin
//public deleteMin method
public AnyType deleteMin ()
{
if( root == null )
throw new UnderflowException ("Double-Ended Priority Queue is empty");
AnyType min = findMin ( );
root = deleteMin ( root);
theSize--;
return min;
}
//private recursive deleteMin method
private Node<AnyType> deleteMin ( Node<AnyType> t)
{
if( t.left == null )
{
if(t.items.next != null)
{
for(Node.ListNode p = t.items; p != null; p = p.next)
{
if(p.next.next == null)
p.next = null;
}
return t;
}
else
return t.right;
}
else
{
t.left = deleteMin( t.left );
return t;
}
}
Test Class -
import cop3530.*;
import java.io.PrintStream;
class Assign4
{
Assign4()
{
}
private static void test1(DoubleEndedPriorityQueue doubleendedpriorityqueue)
{
doubleendedpriorityqueue.insert("Afdc");
doubleendedpriorityqueue.insert("fda");
doubleendedpriorityqueue.insert("Da");
doubleendedpriorityqueue.insert("afdc");
doubleendedpriorityqueue.insert("Fda");
doubleendedpriorityqueue.insert("Da");
System.out.println((new StringBuilder()).append("q1: ").append(doubleendedpriorityqueue).toString());
}
private static void test2(DoubleEndedPriorityQueue doubleendedpriorityqueue)
{
doubleendedpriorityqueue.insert("Afdc");
doubleendedpriorityqueue.insert("fda");
doubleendedpriorityqueue.insert("Da");
doubleendedpriorityqueue.insert("afdc");
doubleendedpriorityqueue.insert("Fda");
doubleendedpriorityqueue.insert("Da");
System.out.println((new StringBuilder()).append("q2: ").append(doubleendedpriorityqueue).toString());
}
private static void test3(DoubleEndedPriorityQueue doubleendedpriorityqueue, int i, int j)
{
for(int k = i; k != 0; k = (k + i) % j)
{
doubleendedpriorityqueue.insert(Integer.valueOf(k));
}
System.out.println("Completed first round of insertions");
for(int l = 1; !doubleendedpriorityqueue.isEmpty(); l += 2)
{
int k1 = ((Integer)doubleendedpriorityqueue.findMin()).intValue();
doubleendedpriorityqueue.deleteMin();
int l1 = ((Integer)doubleendedpriorityqueue.deleteMin()).intValue();
if(k1 != l || l1 != l + 1)
{
System.out.println((new StringBuilder()).append("OOPS!!!! ").append(k1).append(" ").append(l1).append(" ").append(l).append(" ").append(l + 1).toString());
}
int i2 = ((Integer)doubleendedpriorityqueue.findMax()).intValue();
doubleendedpriorityqueue.deleteMax();
int j2 = ((Integer)doubleendedpriorityqueue.deleteMax()).intValue();
if(i2 != j - l || j2 != j - l - 1)
{
System.out.println((new StringBuilder()).append("OOPS!!!! ").append(i2).append(" ").append(j2).append(" ").append(j - l).append(" ").append(j - l - 1).toString());
}
}
System.out.println("Completed first round of deletions");
for(int i1 = i; i1 != 0; i1 = (i1 + i) % j)
{
doubleendedpriorityqueue.insert(Integer.valueOf(i1));
}
System.out.println("Completed second round of insertions");
for(int j1 = 0; j1 < j - 5; j1 += 2)
{
doubleendedpriorityqueue.deleteMin();
doubleendedpriorityqueue.deleteMax();
}
for(; !doubleendedpriorityqueue.isEmpty(); doubleendedpriorityqueue.deleteMax())
{
System.out.println((new StringBuilder()).append(doubleendedpriorityqueue.findMin()).append("\n").append(doubleendedpriorityqueue.findMax()).toString());
doubleendedpriorityqueue.deleteMin();
}
}
private static void test4(DoubleEndedPriorityQueue doubleendedpriorityqueue, int i, int j)
{
for(int k = 0; k < j; k++)
{
for(int i1 = j; i1 != 0; i1 = (i1 + j) % i)
{
doubleendedpriorityqueue.insert(Integer.valueOf(i1));
}
}
for(int l = 1; l < i; l++)
{
for(int j1 = 0; j1 < j; j1++)
{
if(((Integer)doubleendedpriorityqueue.deleteMin()).intValue() != l)
{
System.out.println("OOPS!!!");
}
}
}
System.out.println("Completed duplicate test");
}
private static void test5(DoubleEndedPriorityQueue doubleendedpriorityqueue, int i, int j)
{
for(int k = i; k != 0; k = (k + i) % j)
{
doubleendedpriorityqueue.insert(Integer.valueOf(k));
}
System.out.println(doubleendedpriorityqueue.toString().length());
}
public static void main(String args[])
{
long l = System.currentTimeMillis();
test1(new ListDoubleEndedPriorityQueue());
test2(new ListDoubleEndedPriorityQueue(String.CASE_INSENSITIVE_ORDER));
test3(new ListDoubleEndedPriorityQueue(), 1787, 2357);
test4(new ListDoubleEndedPriorityQueue(), 211, 101);
test5(new ListDoubleEndedPriorityQueue(), 1787, 2357);
test1(new TreeDoubleEndedPriorityQueue());
test2(new TreeDoubleEndedPriorityQueue(String.CASE_INSENSITIVE_ORDER));
System.out.println ("Starting Test#3");
test3(new TreeDoubleEndedPriorityQueue(), 0x25fbb, 0x3945d);
test4(new TreeDoubleEndedPriorityQueue(), 1423, 1009);
test5(new TreeDoubleEndedPriorityQueue(), 0x25fbb, 0x3945d);
long l1 = System.currentTimeMillis();
System.out.println("Program reached end");
System.out.println((new StringBuilder()).append("ELAPSED TIME IS ").append(l1 - l).append(" MILLISECONDS").toString());
}
}
