Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Novice to Generics Trying to Implement a Generic Priority Queue

Reply
Thread Tools

Novice to Generics Trying to Implement a Generic Priority Queue

 
 
KevinSimonson
Guest
Posts: n/a
 
      04-11-2011
On Apr 11, 11:52*am, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
> KevinSimonson <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Daniele Futtorovic
Guest
Posts: n/a
 
      04-11-2011
On 11/04/2011 21:10, KevinSimonson allegedly wrote:
> On Apr 11, 11:52 am, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
>> KevinSimonson<(E-Mail Removed)> 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


 
Reply With Quote
 
 
 
 
Tom Anderson
Guest
Posts: n/a
 
      04-11-2011
On Mon, 11 Apr 2011, Daniele Futtorovic wrote:

> On 11/04/2011 21:10, KevinSimonson allegedly wrote:
>> On Apr 11, 11:52 am, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
>>> KevinSimonson<(E-Mail Removed)> 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
 
Reply With Quote
 
Daniele Futtorovic
Guest
Posts: n/a
 
      04-11-2011
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, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
>>>> KevinSimonson<(E-Mail Removed)> 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"
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Program blocked in Queue.Queue.get and Queue.Queue.put Kris Python 0 01-04-2012 03:46 PM
efficient priority queue for a few descrete priority levels Marcel Müller C++ 3 04-27-2009 03:22 PM
Is Queue.Queue.queue.clear() thread-safe? Russell Warren Python 4 06-27-2006 03:03 PM
Should I use shutter-priority or appurature-priority? ½ Confused Digital Photography 4 02-22-2006 09:48 AM
Question about Aperture priority and Shutter Priority John Edwards Digital Photography 8 01-05-2005 04:58 PM



Advertisments