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

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

Novice to Generics Trying to Implement a Generic Priority Queue

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — 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