commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Phil Steitz" <p...@steitz.com>
Subject Re: [collections] BinaryHeap and PriorityQueue
Date Thu, 01 Jan 2004 20:17:31 GMT
Sorry to respond first to the commit message (must be all the "oversight 
talk" ;)  See interspersed.

Stephen Colebourne wrote:
> I have made the following changes:
> - PriorityQueue now disapproved (not deprecated, but the language indicates
> it is)
> - BinaryHeap in main package is not deprecated, as it is the only
> implementation of PQ
> - BinaryHeap in buffer subpackage renamed to BinaryBuffer. No longer
> implements PQ
It might be better named something like "PriorityBuffer" since that 
matches the behavior.

> - PQ decorators now inner classes of PQUtils
> 
> We could go further and actually deprecated PQ. But I'm a little wary of
> that.

We should decide whether or not Queue implementations belong in 
[collections].  I am +0 on this (the "+" is because BinaryHeap/Buffer 
exists). If no, we should deprecate.  See below.
> 
> (And both BinaryHeap and BinaryBuffer still need their remove bug fixing :-)

As noted in bug report, I have a fix ready to commit.  What I don't like 
about the setup above is that this and all other fixes / enhancements need 
to be applied to both classes.
> 
> Stephen
> 
> 
> ----- Original Message -----
> From: "Stephen Colebourne" <scolebourne@btopenworld.com>
> 
>>BinaryHeap is a very old collections class, originally from Avalon. It
>>implements PriorityQueue interface.
>>
>>PQ is an interface that does not extend Collection, Buffer is effectively
>>the replacement that does. They use different terms though - PQ
>>insert/peek/pop - Buffer add/get/remove. PQ is also badly named as the
>>interface specifies nothing about 'priority'.

Ack. Maybe should just be called "Queue."  As noted below, however, the 
only impl in [collections] is a heap-backed priority queue.

>>
>>Currently I have moved BinaryHeap and the PriorityQueue decorators into
> 
> the
> 
>>buffer subpackage (as they seem related). But is this right???

Sorry to respond late on this, but it does not seem right to me.  I see 
the BinaryHeap/Buffer impl as a array-heap-backed implementation of a 
priority queue.  The interface is a Queue interface, which, as you point 
out is different from a buffer interface.

>>Possibilities:
>>
>>a) BinaryHeap and PQ decorators in buffer subpackage
>>
>>b) BinaryHeap and PQ decorators in (new) priorityqueue subpackage
>>
>>c) BinaryHeap left in main package where it always was, PQ decorators as
>>hidden inner classes on PriorityQueueUtils.
>>
>>I think I favour (c), as I'm not a fan of the PQ interface, and this would
>>avoid change for this dubious (but probably useful) class/interface.
> 

Here is a logical alternative:

1) Deprecate PriorityQueue interface in favor of Queue.

2) Create a queue package and put BinaryHeap there (maybe renamed 
something like HeapPriorityQueue or BinaryPriorityQueue or even 
PriorityQueue).  This would open the door for other queue implementations.

I understand that this departs from the general pattern of sticking with 
things that extend collection, but it is more natural to me at least.

Phil

> 
> 
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> 



---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message