Novice to Generics Trying to Implement a Generic Priority Queue

[KevinSimonson]

I've been trying to teach myself Generics, so I read through the
tutorial at
"http://download.oracle.com/javase/tutorial/java/generics/index.html",
and it
looked pretty straightforward. I thought to myself, priority queues
might be a
good example of a data structure one might want to genericize, since
the idea
behind a priority queue is pretty independent of the base data type.
So I wrote
"PriorityQueue.java" that I'm attaching below, where I use a heap to
represent
the priority queue. I also wrote "IntPq.java" that instantiates
"PriorityQueue"
for integers (or rather, values of type "Integer").

But I can't get it to compile. The first error message I get is
"generic array creation". Is it illegal to use arrays of the type
passed in?
How would I implement a heap _without_ being able to declare an array
of the
type passed in?

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?

Kevin Simonson


##########################################################################################

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)
{ queue = new Da[ size];
nmbrEntries = 0;
}
else
{ throw new BadSizeException();
}
}

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
&& (parent = queue[ index = searcher - 1 >>
1]).compareTo< Da>
( entry)
<= 0
; 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
&& queue[ lastborn - 1].compareTo< Da>( queue[ lastborn])
<= 0
? lastborn
: lastborn - 1;
if (queue[ lrgrChld].compareTo< Da>( rplcmnt) <= 0)
{ 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] + ']');
}
}
}


##########################################################################################

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;
int index;
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 (OverflowException excptn)
{ System.err.println( "Overflow occurred!");
}
catch (UnderflowException excptn)
{ System.err.println( "Underflow occurred!");
}
catch (BadSizeException excptn)
{ System.err.println( "First number entered must be non-
negative!");
}
}
else
{ System.out.println
( "Usage is\n jave IntPq <queue-size> (x l hE hR <int-
entry>)*");
}
}
}

 

[markspace]

How would I implement a heap _without_ being able to declare an array
of the
type passed in?

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 to.

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.

 

[KevinSimonson]

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 to.

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

 

[markspace]

public PriorityQueue ( int size)
{
if (0<= size)
{ @SupressWarnings( "unchecked")
queue = (Da[]) new Object[ size];

PriorityQueue.java:14:<identifier> expected
queue = (Da[]) new Object[ size];
^

Interesting. I thought I could put that annotaion on an assignment. I
guess not. Oh well.


public PriorityQueue(int size) throws BadSizeException {
if (0 <= size) {
@SuppressWarnings("unchecked")
Da[] temp = (Da[]) new Object[ size ];
queue = temp;
nmbrEntries = 0;
} else {...

private static boolean inOrder ( Da left
, Da right)
{
return left.compareTo< ? super Da>( right)<= 0;
}

PriorityQueue.java:25: illegal start of expression
return left.compareTo< ? super Da>( right)<= 0;

This bit goes on the declaration, not the invocation ;-)

public class PriorityQueue<Da extends Comparable<? super Da>> {...

 

[Lew]

public PriorityQueue ( int size)
{
if (0<= size)
{ @SupressWarnings( "unchecked")
queue = (Da[]) new Object[ size];

PriorityQueue.java:14:<identifier> expected
queue = (Da[]) new Object[ size];

Kevin, you really do a fine job of posting a question with a good example,
well presented.

Interesting. I thought I could put that annotaion on an assignment. I guess
not. Oh well.

Annotations are allowed only at declarations.

public PriorityQueue(int size) throws BadSizeException {
if (0 <= size) {
@SuppressWarnings("unchecked")
Da[] temp = (Da[]) new Object[ size ];
queue = temp;
nmbrEntries = 0;
} else {...

private static boolean inOrder ( Da left
, Da right)
{
return left.compareTo< ? super Da>( right)<= 0;
}

PriorityQueue.java:25: illegal start of expression
return left.compareTo< ? super Da>( right)<= 0;

This bit goes on the declaration, not the invocation ;-)

public class PriorityQueue<Da extends Comparable<? super Da>> {...

In the actual use, you don't need any angle-brackety stuff:

private static boolean inOrder( Da left, Da right)
{
return left.compareTo( right ) <= 0;
}

You do, however, have to guard against a possible 'NullPointerException'. The
method is 'private', so it's up to its callers not to screw that up. You
enforce that with an assertion:

private static boolean inOrder( Da left, Da right)
{
assert left != null;
return left.compareTo( right ) <= 0;
}

If the method were 'public' you'd need to add an explicit guard against the
'NullPointerException':

public static boolean inOrder( Da left, Da right)
{
if ( left == null )
{
return true;
}
assert left != null;
return left.compareTo( right ) <= 0;
}

The assertion is rather trivial here, so you could simply:

public static boolean inOrder( Da left, Da right)
{
return left == null || left.compareTo( right ) <= 0;
}

Don't forget your Javadocs!

 

[Tom Anderson]

You do, however, have to guard against a possible
'NullPointerException'. The method is 'private', so it's up to its
callers not to screw that up. You enforce that with an assertion:

private static boolean inOrder( Da left, Da right)
{
assert left != null;
return left.compareTo( right ) <= 0;
}

compareTo will (or at least should) throw a NullPointerException if right
is null (from Comparable's javadoc - "Note that null is not an instance of
any class, and e.compareTo(null) should throw a NullPointerException even
though e.equals(null) returns false"), so if you're going to check left,
you ought to check right too.

But i don't see why you would check either. It is right and proper that if
a method which requires non-null arguments is passed nulls, it should
throw a NullPointerException (from NullPointerException's javadoc:
"Applications should throw instances of this class to indicate other
illegal uses of the null object"). This method will do that. The assertion
is unnecessary.

A method which is going to handle a parameter in such a way that it will
not naturally blow up if it is null, but which requires that it be
non-null, should of course make the assertion you describe, or an
equivalent explicit guard.

If the method were 'public' you'd need to add an explicit guard against
the 'NullPointerException':

public static boolean inOrder( Da left, Da right)
{
if ( left == null )
{
return true;
}
assert left != null;
return left.compareTo( right ) <= 0;
}

This means something different to the assertion. This says that nulls are
smaller than any other element - and so implies that nulls are a
permissible element, whereas the assertion rejected them. That would be a
logically consistent thing to do, but in that case, the method also needs
to deal with a null right, by inserting "if (right == null) return false;"
after the first guard and before the compareTo call.

The other option would be to check both left and right for nullity, and
throw a NullPointerException (or IllegalArgumentException if you prefer)
if either is null. That would require all elements to be non-null. You can
do this by omitting any guard clauses - the compareTo call will do it.

Don't forget your Javadocs!

Sage advice.

tom

 

[Roedy Green]

How would I implement a heap _without_ being able to declare an array
of the
type passed in?

you can't do it without reflection without generating an error
message. Look at the code inside ArrayList. Even it cheats.

I hope these squirrelynesses will eventually go away when Java gives
up on the notion of type erasure.

 

[KevinSimonson]

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

 

[markspace]

sh-4.1$ javac PriorityQueue.java
Note: PriorityQueue.java uses unchecked or unsafe operations.

Note: Recompile with -Xlint:unchecked for details.

When you get this warning, you should follow its advice. Please
re-compile with -Xlint:unchecked and show us the output for that step.

I tested it myself with a different, simpler test harness and it worked,
so I'm not sure exactly where the error might be. I'll give it another
once-over after the -Xlint:unchecked output is posted.

 

[Stefan Ram]

Exception in thread "main" java.lang.ClassCastException:
[Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;

( Da[] )new java.lang.Comparable[ size ]

 

[KevinSimonson]

Exception in thread "main" java.lang.ClassCastException:
[Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;

( Da[] )new java.lang.Comparable[ size ]

Stefan, thanks! That solved the problem and my program works just
fine now.

Kevin Simonson


##############################################################################

Script started on Mon Apr 11 13:03:16 2011
sh-4.1$ java IntPq 10 314 159 265 358 979 323 846 264 338 327 l
Added entry 314.
Added entry 159.
Added entry 265.
Added entry 358.
Added entry 979.
Added entry 323.
Added entry 846.
Added entry 264.
Added entry 338.
Added entry 327.
0: [979]
1: [358]
3: [338]
7: [159]
8: [264]
4: [327]
9: [314]
2: [846]
5: [265]
6: [323]
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)
{ queue = (Da[]) new java.lang.Comparable[ size];
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$ exit
exit
Script done on Mon Apr 11 13:04:29 2011

 

[Daniele Futtorovic]

Exception in thread "main" java.lang.ClassCastException:
[Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;

( Da[] )new java.lang.Comparable[ size ]

Stefan, thanks! That solved the problem and my program works just
fine now.

This might be somewhat OK in this case, but it's hardly advisable.

A Comparable[] /is not a/ Da[].

You'd normally pass the Class object around in such cases:

public PriorityQueue( Class<Da> component, int size )
throws BadSizeException
{
if (0<= size)
{ queue = (Da[]) Array.newInstance( component, size );
nmbrEntries = 0;
}
else {
throw new BadSizeException();
}
}

Since the construction becomes a bit awkward, you can add a factory method:

public static <T extends Comparable> PriorityQueue<T> newQueue( Class<T>
type, int size )
throws BadSizeException
{
return new PriorityQueue<T>( type, size );
}

(Not compiled.)

Kevin Simonson


##############################################################################

Script started on Mon Apr 11 13:03:16 2011
sh-4.1$ java IntPq 10 314 159 265 358 979 323 846 264 338 327 l
Added entry 314.
Added entry 159.
Added entry 265.
Added entry 358.
Added entry 979.
Added entry 323.
Added entry 846.
Added entry 264.
Added entry 338.
Added entry 327.
0: [979]
1: [358]
3: [338]
7: [159]
8: [264]
4: [327]
9: [314]
2: [846]
5: [265]
6: [323]
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)
{ queue = (Da[]) new java.lang.Comparable[ size];
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$ exit
exit
Script done on Mon Apr 11 13:04:29 2011

 

[Tom Anderson]

Exception in thread "main" java.lang.ClassCastException:
[Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;

( Da[] )new java.lang.Comparable[ size ]

Stefan, thanks! That solved the problem and my program works just
fine now.

This might be somewhat OK in this case, but it's hardly advisable.

A Comparable[] /is not a/ Da[].

You'd normally pass the Class object around in such cases:

public PriorityQueue( Class<Da> component, int size )
throws BadSizeException
{
if (0<= size)
{ queue = (Da[]) Array.newInstance( component, size );

I'm not sure about 'normally'. That is certainly a known technique (for
those who haven't seen it, this use of a Class is called a 'type token'),
and whilst it may be advisable, i don't think it's more common than making
an array of some suitable static type and casting it uncheckedly [sic].
Does the JDK use it anywhere?

tom

 

[Daniele Futtorovic]

On Apr 11, 11:52 am, (e-mail address removed)-berlin.de (Stefan Ram) wrote:
Exception in thread "main" java.lang.ClassCastException:
[Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;

( Da[] )new java.lang.Comparable[ size ]

Stefan, thanks! That solved the problem and my program works just
fine now.

This might be somewhat OK in this case, but it's hardly advisable.

A Comparable[] /is not a/ Da[].

You'd normally pass the Class object around in such cases:

public PriorityQueue( Class<Da> component, int size )
throws BadSizeException
{
if (0<= size)
{ queue = (Da[]) Array.newInstance( component, size );

I'm not sure about 'normally'. That is certainly a known technique (for
those who haven't seen it, this use of a Class is called a 'type token'),
and whilst it may be advisable, i don't think it's more common than making
an array of some suitable static type and casting it uncheckedly [sic].
Does the JDK use [hic] anywhere?

None that I'd know of. Some hackingry [sob] to overcome type erasure,
yeah, but nothing so outright type-unsafy [ham] as that.