Novice to Generics Trying to Implement a Generic Priority Queue

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>)*"); } } }

On 4/7/2011 4:03 PM, KevinSimonson wrote: > 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.

On Apr 7, 6:32=A0pm, markspace <-@.> wrote: > > This is a bit of a flaw in Java's generics. =A0The generic types aren't > reifiable, so there's actually no type at run time for the JVM to use to > create the array. =A0Sometimes you can go around this limitation. > Sometimes you can't. =A0Here's the case for when you can't. > > @SupressWarnings("unchecked") > =A0 =A0queue =3D (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< =A0Da>()". =A0Can anyone tell me what I'm doing wrong here? > > Comparable is a bit of a weird one. =A0With 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 =20 ###########################################################################= ### 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 <=3D size) { @SupressWarnings( "unchecked") queue =3D (Da[]) new Object[ size]; nmbrEntries =3D 0; } else { throw new BadSizeException(); } } private static boolean inOrder ( Da left , Da right) { return left.compareTo< ? super Da>( right) <=3D 0; } public boolean hasEntries () { return 0 < nmbrEntries; } public boolean hasRoom () { return nmbrEntries < queue.length; } public void addEntry ( Da entry) { if (queue.length =3D=3D nmbrEntries) { throw new OverflowException(); } Da parent; int index; int searcher; for ( searcher =3D nmbrEntries++ ; 0 < searcher && inOrder( parent =3D queue[ index =3D searcher - 1 >> 1], entry) ; searcher =3D index) { queue[ searcher] =3D parent; } queue[ searcher] =3D entry; } public Da extract () { if (nmbrEntries =3D=3D 0) { throw new UnderflowException(); } Da extractee =3D queue[ 0]; Da rplcmnt =3D queue[--nmbrEntries]; int searcher =3D 0; int lastborn; int lrgrChld; for (;;) { lastborn =3D searcher + 1 << 1; if (nmbrEntries < lastborn) { break; } lrgrChld =3D lastborn < nmbrEntries && inOrder( queue[ lastborn - 1], queue[ lastborn]) ? lastborn : lastborn - 1; if (inOrder( queue[ lrgrChld], rplcmnt)) { break; } queue[ searcher] =3D queue[ lrgrChld]; searcher =3D lrgrChld; } queue[ searcher] =3D rplcmnt; return extractee; } public void list () { int index; for (index =3D 0; index < nmbrEntries; index++) { System.out.println( index + ": [" + queue[ index] + ']'); } } } sh-4.1$ javac PriorityQueue.java PriorityQueue.java:14: <identifier> expected queue =3D (Da[]) new Object[ size]; ^ PriorityQueue.java:25: illegal start of expression return left.compareTo< ? super Da>( right) <=3D 0; ^ PriorityQueue.java:25: '.' expected return left.compareTo< ? super Da>( right) <=3D 0; ^ PriorityQueue.java:25: : expected return left.compareTo< ? super Da>( right) <=3D 0; ^ PriorityQueue.java:25: ';' expected return left.compareTo< ? super Da>( right) <=3D 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

On 4/8/2011 2:55 PM, KevinSimonson wrote: > 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>> {...

markspace wrote: > KevinSimonson wrote: >> 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! -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

On Fri, 8 Apr 2011, Lew wrote: > 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 -- secular utopianism is based on a belief in an unstoppable human ability to make a better world -- Rt Rev Tom Wright

On Thu, 7 Apr 2011 16:03:50 -0700 (PDT), KevinSimonson <kvnsmnsn@hotmail.com> wrote, quoted or indirectly quoted someone who said : >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. -- Roedy Green Canadian Mind Products http://mindprod.com Doing what the user expects with respect to navigation is absurdly important for user satisfaction. ~ anonymous Google Android developer

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

On 4/11/2011 8:08 AM, KevinSimonson wrote: > > 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.

KevinSimonson <kvnsmnsn@hotmail.com> writes: >Exception in thread "main" java.lang.ClassCastException: >[Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable; ( Da[] )new java.lang.Comparable[ size ]

On Apr 11, 11:52=A0am, r...@zedat.fu-berlin.de (Stefan Ram) wrote: > KevinSimonson <kvnsm...@hotmail.com> writes: > >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 =20 ###########################################################################= ### 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 <=3D size) { queue =3D (Da[]) new java.lang.Comparable[ size]; nmbrEntries =3D 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 =3D=3D nmbrEntries) { throw new OverflowException(); } Da parent; int index; int searcher; for ( searcher =3D nmbrEntries++ ; 0 < searcher && (parent =3D queue[ index =3D searcher - 1 >> 1]).compareTo( entry) <=3D 0 ; searcher =3D index) { queue[ searcher] =3D parent; } queue[ searcher] =3D entry; } public Da extract () throws UnderflowException { if (nmbrEntries =3D=3D 0) { throw new UnderflowException(); } Da extractee =3D queue[ 0]; Da rplcmnt =3D queue[--nmbrEntries]; int searcher =3D 0; int lastborn; int lrgrChld; for (;;) { lastborn =3D searcher + 1 << 1; if (nmbrEntries < lastborn) { break; } lrgrChld =3D lastborn < nmbrEntries && queue[ lastborn - 1].compareTo( queue[ lastborn]) <=3D 0 ? lastborn : lastborn - 1; if (queue[ lrgrChld].compareTo( rplcmnt) <=3D 0) { break; } queue[ searcher] =3D queue[ lrgrChld]; searcher =3D lrgrChld; } queue[ searcher] =3D rplcmnt; return extractee; } private void listTree ( int subroot , int indnttn) { if (subroot < nmbrEntries) { int spc; for (spc =3D indnttn; 0 < spc; spc--) { System.out.print( ' '); } System.out.println( subroot + ": [" + queue[ subroot] + ']'); subroot =3D (subroot << 1) + 1; indnttn +=3D 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

On 11/04/2011 21:10, KevinSimonson allegedly wrote: > On Apr 11, 11:52 am, r...@zedat.fu-berlin.de (Stefan Ram) wrote: >> KevinSimonson<kvnsm...@hotmail.com> writes: >>> 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

On Mon, 11 Apr 2011, Daniele Futtorovic wrote: > On 11/04/2011 21:10, KevinSimonson allegedly wrote: >> On Apr 11, 11:52 am, r...@zedat.fu-berlin.de (Stefan Ram) wrote: >>> KevinSimonson<kvnsm...@hotmail.com> writes: >>>> 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 -- Taking care of business

On 11/04/2011 23:41, Tom Anderson allegedly wrote: > On Mon, 11 Apr 2011, Daniele Futtorovic wrote: > >> On 11/04/2011 21:10, KevinSimonson allegedly wrote: >>> On Apr 11, 11:52 am, r...@zedat.fu-berlin.de (Stefan Ram) wrote: >>>> KevinSimonson<kvnsm...@hotmail.com> writes: >>>>> 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. -- DF. An escaped convict once said to me: "Alcatraz is the place to be"