Re: Novice to Generics Trying to Implement a Generic Priority Queue
On Apr 7, 6:32 pm, markspace <-@.> wrote:
This is a bit of a flaw in Java's generics. The generic types aren't
reifiable, so there's actually no type at run time for the JVM to use to
create the array. Sometimes you can go around this limitation.
Sometimes you can't. Here's the case for when you can't.
@SupressWarnings("unchecked")
queue = (Da[]) new Object[size];
Don't use SupressWarnings unless you have to, but in this case you have t=
o.
The rest of the compilation errors seem to be referring to my use of
method
"compareTo< Da>()". Can anyone tell me what I'm doing wrong here?
Comparable is a bit of a weird one. With out going into details, you
need "Comparable<? super Da>" on the class declaration to get the type
right.
I didn't read through the rest of your code, but hopefully this gets you
pointed in the right direction.
markspace, thanks for the pointers. I made the changes you suggested,
or at least I attempted to; maybe you can look at my code and see if I
messed anything up. Anyhow, I try to compile it and get the error
messages I'm attaching. Can you or anyone else tell me what I'm doing
wrong?
Kevin Simonson
###########################################################################=
###
Script started on Fri Apr 8 15:47:37 2011
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)
{
if (0 <= size)
{ @SupressWarnings( "unchecked")
queue = (Da[]) new Object[ size];
nmbrEntries = 0;
}
else
{ throw new BadSizeException();
}
}
private static boolean inOrder ( Da left
, Da right)
{
return left.compareTo< ? super Da>( right) <= 0;
}
public boolean hasEntries ()
{
return 0 < nmbrEntries;
}
public boolean hasRoom ()
{
return nmbrEntries < queue.length;
}
public void addEntry ( Da entry)
{
if (queue.length == nmbrEntries)
{ throw new OverflowException();
}
Da parent;
int index;
int searcher;
for ( searcher = nmbrEntries++
; 0 < searcher
&& inOrder( parent = queue[ index = searcher - 1 >> 1],
entry)
; searcher = index)
{ queue[ searcher] = parent;
}
queue[ searcher] = entry;
}
public Da extract ()
{
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
&& inOrder( queue[ lastborn - 1], queue[ lastborn])
? lastborn
: lastborn - 1;
if (inOrder( queue[ lrgrChld], rplcmnt))
{ break;
}
queue[ searcher] = queue[ lrgrChld];
searcher = lrgrChld;
}
queue[ searcher] = rplcmnt;
return extractee;
}
public void list ()
{
int index;
for (index = 0; index < nmbrEntries; index++)
{ System.out.println( index + ": [" + queue[ index] + ']');
}
}
}
sh-4.1$ javac PriorityQueue.java
PriorityQueue.java:14: <identifier> expected
queue = (Da[]) new Object[ size];
^
PriorityQueue.java:25: illegal start of expression
return left.compareTo< ? super Da>( right) <= 0;
^
PriorityQueue.java:25: '.' expected
return left.compareTo< ? super Da>( right) <= 0;
^
PriorityQueue.java:25: : expected
return left.compareTo< ? super Da>( right) <= 0;
^
PriorityQueue.java:25: ';' expected
return left.compareTo< ? super Da>( right) <= 0;
^
PriorityQueue.java:28: illegal start of expression
public boolean hasEntries ()
^
PriorityQueue.java:28: ';' expected
public boolean hasEntries ()
^
PriorityQueue.java:28: ';' expected
public boolean hasEntries ()
^
PriorityQueue.java:33: illegal start of expression
public boolean hasRoom ()
^
PriorityQueue.java:33: ';' expected
public boolean hasRoom ()
^
PriorityQueue.java:38: illegal start of expression
public void addEntry ( Da entry)
^
PriorityQueue.java:38: illegal start of expression
public void addEntry ( Da entry)
^
PriorityQueue.java:38: ';' expected
public void addEntry ( Da entry)
^
PriorityQueue.java:38: ';' expected
public void addEntry ( Da entry)
^
PriorityQueue.java:55: illegal start of expression
public Da extract ()
^
PriorityQueue.java:55: ';' expected
public Da extract ()
^
PriorityQueue.java:85: illegal start of expression
public void list ()
^
PriorityQueue.java:85: illegal start of expression
public void list ()
^
PriorityQueue.java:85: ';' expected
public void list ()
^
PriorityQueue.java:92: reached end of file while parsing
}
^
20 errors
sh-4.1$ exit
exit
Script done on Fri Apr 8 15:48:01 2011