commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Phil Steitz" <>
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" <>
>>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.

>>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.


> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message