Novice to Generics Trying to Implement a Generic Priority Queue

Discussion in 'Java' started by KevinSimonson, Apr 8, 2011.

  1. 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>)*");
    }
    }
    }
    KevinSimonson, Apr 8, 2011
    #1
    1. Advertising

  2. KevinSimonson

    markspace Guest

    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.
    markspace, Apr 8, 2011
    #2
    1. Advertising

  3. 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 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
    KevinSimonson, Apr 8, 2011
    #3
  4. KevinSimonson

    markspace Guest

    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, Apr 8, 2011
    #4
  5. KevinSimonson

    Lew Guest

    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
    Lew, Apr 9, 2011
    #5
  6. KevinSimonson

    Tom Anderson Guest

    Re: Novice to Generics Trying to Implement a Generic PriorityQueue

    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
    Tom Anderson, Apr 9, 2011
    #6
  7. KevinSimonson

    Roedy Green Guest

    On Thu, 7 Apr 2011 16:03:50 -0700 (PDT), KevinSimonson
    <> 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
    Roedy Green, Apr 9, 2011
    #7
  8. 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
    KevinSimonson, Apr 11, 2011
    #8
  9. KevinSimonson

    markspace Guest

    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.
    markspace, Apr 11, 2011
    #9
  10. KevinSimonson

    Stefan Ram Guest

    KevinSimonson <> 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 Ram, Apr 11, 2011
    #10
  11. On Apr 11, 11:52 am, -berlin.de (Stefan Ram) wrote:
    > KevinSimonson <> 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


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

    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
    KevinSimonson, Apr 11, 2011
    #11
  12. On 11/04/2011 21:10, KevinSimonson allegedly wrote:
    > On Apr 11, 11:52 am, -berlin.de (Stefan Ram) wrote:
    >> KevinSimonson<> 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
    Daniele Futtorovic, Apr 11, 2011
    #12
  13. KevinSimonson

    Tom Anderson Guest

    Re: Novice to Generics Trying to Implement a Generic PriorityQueue

    On Mon, 11 Apr 2011, Daniele Futtorovic wrote:

    > On 11/04/2011 21:10, KevinSimonson allegedly wrote:
    >> On Apr 11, 11:52 am, -berlin.de (Stefan Ram) wrote:
    >>> KevinSimonson<> 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
    Tom Anderson, Apr 11, 2011
    #13
  14. 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, -berlin.de (Stefan Ram) wrote:
    >>>> KevinSimonson<> 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"
    Daniele Futtorovic, Apr 12, 2011
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Navhpf

    priority queue

    Navhpf, Feb 23, 2004, in forum: Java
    Replies:
    3
    Views:
    978
    Navhpf
    Feb 23, 2004
  2. Aaron W. LaFramboise

    Stable priority queue

    Aaron W. LaFramboise, Apr 5, 2004, in forum: C++
    Replies:
    19
    Views:
    1,521
    Claudio Puviani
    Apr 7, 2004
  3. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    659
    Russell Warren
    Jun 27, 2006
  4. Marcel Müller
    Replies:
    3
    Views:
    532
    Marcel Müller
    Apr 27, 2009
  5. Kris
    Replies:
    0
    Views:
    461
Loading...

Share This Page