Re: Novice to Generics Trying to Implement a Generic Priority Queue
Okay, I followed everybody's advice, and changed my constructor to:
public PriorityQueue ( int size)
throws BadSizeException
{
if (0 <= size)
{ System.out.println( "Immediately before problem.");
@SuppressWarnings( "unchecked")
Da[] temp = (Da[]) new Object[ size];
System.out.println( "Immediately after problem.");
queue = temp;
nmbrEntries = 0;
}
else
{ throw new BadSizeException();
}
}
just as suggested, and I changed all my calls to
inOrder( left, right)
to calls to
left.compareTo( right) <= 0
more or less as suggested. That compiled, but when I ran it with an
argument of
a single "10" string, I got a run-time error between the two
"println"s above,
since as you can see in the script file below the "Immediately before
problem."
string got printed but the "Immediately after problem." string did
not. So I'm
still stuck. It compiles now, and that's good, but what use is Java
generics if
I can't get my generic code to run? Anybody have any ideas?
Kevin Simonson
##############################################################################
Script started on Sun Apr 10 20:22:52 2011
sh-4.1$ ls -F
IntPq.java PriorityQueue.java Problem
sh-4.1$ cat PriorityQueue.java
public class PriorityQueue< Da extends Comparable>
{
public static class BadSizeException extends Exception {}
public static class UnderflowException extends Exception {}
public static class OverflowException extends Exception {}
Da[] queue;
int nmbrEntries;
public PriorityQueue ( int size)
throws BadSizeException
{
if (0 <= size)
{ System.out.println( "Immediately before problem.");
@SuppressWarnings( "unchecked")
Da[] temp = (Da[]) new Object[ size];
System.out.println( "Immediately after problem.");
queue = temp;
nmbrEntries = 0;
}
else
{ throw new BadSizeException();
}
}
public boolean hasEntries ()
{
return 0 < nmbrEntries;
}
public boolean hasRoom ()
{
return nmbrEntries < queue.length;
}
public void addEntry ( Da entry)
throws OverflowException
{
if (queue.length == nmbrEntries)
{ throw new OverflowException();
}
Da parent;
int index;
int searcher;
for ( searcher = nmbrEntries++
; 0 < searcher
&& (parent = queue[ index = searcher - 1 >>
1]).compareTo( entry) <= 0
; searcher = index)
{ queue[ searcher] = parent;
}
queue[ searcher] = entry;
}
public Da extract ()
throws UnderflowException
{
if (nmbrEntries == 0)
{ throw new UnderflowException();
}
Da extractee = queue[ 0];
Da rplcmnt = queue[--nmbrEntries];
int searcher = 0;
int lastborn;
int lrgrChld;
for (;;)
{ lastborn = searcher + 1 << 1;
if (nmbrEntries < lastborn)
{ break;
}
lrgrChld
= lastborn < nmbrEntries
&& queue[ lastborn - 1].compareTo( queue[ lastborn]) <= 0
? lastborn
: lastborn - 1;
if (queue[ lrgrChld].compareTo( rplcmnt) <= 0)
{ break;
}
queue[ searcher] = queue[ lrgrChld];
searcher = lrgrChld;
}
queue[ searcher] = rplcmnt;
return extractee;
}
private void listTree ( int subroot
, int indnttn)
{
if (subroot < nmbrEntries)
{ int spc;
for (spc = indnttn; 0 < spc; spc--)
{ System.out.print( ' ');
}
System.out.println( subroot + ": [" + queue[ subroot] + ']');
subroot = (subroot << 1) + 1;
indnttn += 2;
listTree( subroot , indnttn);
listTree( subroot + 1, indnttn);
}
}
public void list ()
{
listTree( 0, 0);
}
}
sh-4.1$ cat IntPq.java
public class IntPq
{
public static void main ( String[] arguments)
{
if (0 < arguments.length)
{ int arg = 0;
try
{ PriorityQueue< Integer> intPq
= new PriorityQueue< Integer>
( Integer.parseInt( arguments[ 0]));
Integer entry;
String argmnt;
for (arg = 1; arg < arguments.length; arg++)
{ argmnt = arguments[ arg];
if (argmnt.equals( "x"))
{ entry = intPq.extract();
System.out.println( "Extracted value " + entry + '.');
}
else if (argmnt.equals( "l"))
{ intPq.list();
}
else if (argmnt.equals( "hE"))
{ System.out.println
( "Priority queue has entries == " + intPq.hasEntries()
+ '.');
}
else if (argmnt.equals( "hR"))
{ System.out.println
( "Priority queue has room == " + intPq.hasRoom()
+ '.');
}
else
{ entry = new Integer( argmnt);
intPq.addEntry( entry);
System.out.println( "Added entry " + entry + '.');
}
}
}
catch (NumberFormatException excptn)
{ System.err.println
( "Couldn't convert string \"" + arguments[ arg]
+ "\" to an integer!");
}
catch (PriorityQueue.OverflowException excptn)
{ System.err.println( "Overflow occurred!");
}
catch (PriorityQueue.UnderflowException excptn)
{ System.err.println( "Underflow occurred!");
}
catch (PriorityQueue.BadSizeException excptn)
{ System.err.println( "First number entered must be non-
negative!");
}
}
else
{ System.out.println
( "Usage is\n java IntPq <queue-size> (x l hE hR <int-
entry>)*");
}
}
}
sh-4.1$ javac PriorityQueue.java
Note: PriorityQueue.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
sh-4.1$ javac IntPq.java
sh-4.1$ java IntPq 10
Immediately before problem.
Exception in thread "main" java.lang.ClassCastException:
[Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;
at PriorityQueue.<init>(PriorityQueue.java:16)
at IntPq.main(IntPq.java:8)
sh-4.1$ exit
exit
Script done on Sun Apr 10 20:23:46 2011