Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #2998

Re: Novice to Generics Trying to Implement a Generic Priority Queue

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Novice to Generics Trying to Implement a Generic Priority Queue KevinSimonson <kvnsmnsn@hotmail.com> - 2011-04-07 16:03 -0700
  Re: Novice to Generics Trying to Implement a Generic Priority Queue markspace <-@.> - 2011-04-07 17:32 -0700
    Re: Novice to Generics Trying to Implement a Generic Priority Queue KevinSimonson <kvnsmnsn@hotmail.com> - 2011-04-08 14:55 -0700
      Re: Novice to Generics Trying to Implement a Generic Priority Queue markspace <-@.> - 2011-04-08 15:54 -0700
        Re: Novice to Generics Trying to Implement a Generic Priority Queue Lew <noone@lewscanon.com> - 2011-04-08 20:39 -0400
          Re: Novice to Generics Trying to Implement a Generic Priority Queue Tom Anderson <twic@urchin.earth.li> - 2011-04-09 10:36 +0100
  Re: Novice to Generics Trying to Implement a Generic Priority Queue Roedy Green <see_website@mindprod.com.invalid> - 2011-04-09 05:50 -0700
    Re: Novice to Generics Trying to Implement a Generic Priority Queue KevinSimonson <kvnsmnsn@hotmail.com> - 2011-04-11 08:08 -0700
      Re: Novice to Generics Trying to Implement a Generic Priority Queue markspace <-@.> - 2011-04-11 10:29 -0700
      Re: Novice to Generics Trying to Implement a Generic Priority Queue KevinSimonson <kvnsmnsn@hotmail.com> - 2011-04-11 12:10 -0700
        Re: Novice to Generics Trying to Implement a Generic Priority Queue Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2011-04-11 21:42 +0200
          Re: Novice to Generics Trying to Implement a Generic Priority Queue Tom Anderson <twic@urchin.earth.li> - 2011-04-11 22:41 +0100
            Re: Novice to Generics Trying to Implement a Generic Priority Queue Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2011-04-12 01:07 +0200

csiph-web