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

From:

Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid>

Newsgroups:

comp.lang.java.programmer

Date:

Mon, 11 Apr 2011 21:42:28 +0200

Message-ID:

<invlj0$ibd$1@dont-email.me>

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