You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Stephen Colebourne <sc...@btopenworld.com> on 2003/12/29 22:55:45 UTC
[collections] BinaryHeap and PriorityQueue
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'.
Currently I have moved BinaryHeap and the PriorityQueue decorators into the
buffer subpackage (as they seem related). But is this right???
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.
Stephen
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] BinaryHeap and PriorityQueue
Posted by Phil Steitz <ph...@steitz.com>.
Stephen Colebourne wrote:
> From: "Phil Steitz" <ph...@steitz.com>
>
>>Stephen Colebourne wrote:
>> > Given a choice I would deprecate PQ altogether.
>>That would make things simpler.
>
> If no one else comments, I'll do this.
>
>
>>>I am +1 on renaming to PriorityBuffer.
>
> Done
>
> I was also looking at the heap impl and wondering if the compare method
> could check for ascendingOrder, then removing the need for near duplicate
> methods (one for minHeap, one for maxHeap) elsewhere. Would this be a good
> change?
That would simplify the code, but might cost something in overall
performance (since compare is "hot"). Could be that's why the original
author(s) set it up the way it is? Should be trivial. Might be worth
playing with.
Another solution would be to just have the constructor reverse the
comparator for maxHeaps (using ComparatorUtils.reversedComparator). There
the cost would be stack operations for each compare (calling through to
the reversed comparator).
Another (small?) consideration is backward compatability for anyone who
has subclassed BinaryHeap (assuming we are not going to deprecate), since
all of the percolateXxx methods are protected, not private.
Phil
>
> Stephen
>
>
> ---------------------------------------------------------------------
> 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
Re: [collections] BinaryHeap and PriorityQueue
Posted by Stephen Colebourne <sc...@btopenworld.com>.
From: "Phil Steitz" <ph...@steitz.com>
> Stephen Colebourne wrote:
> > Given a choice I would deprecate PQ altogether.
> That would make things simpler.
If no one else comments, I'll do this.
> > I am +1 on renaming to PriorityBuffer.
Done
I was also looking at the heap impl and wondering if the compare method
could check for ascendingOrder, then removing the need for near duplicate
methods (one for minHeap, one for maxHeap) elsewhere. Would this be a good
change?
Stephen
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] BinaryHeap and PriorityQueue
Posted by Phil Steitz <ph...@steitz.com>.
Stephen Colebourne wrote:
>
> I am happy for Buffer to exist in [collections] (although I wish the
> methods were peek and pop)
Yeah. Like a queue ;-).
> Given a choice I would deprecate PQ altogether.
That would make things simpler.
>
> Your change will need to be applied to both BinaryBuffer and BinaryHeap,
> unless we make BinaryHeap wrap a BinaryBuffer (maintaining the old
> interface).
For now, I am making the change to both (and both tests).
I would like to consider, however either
a) deprecate both PQ and BinaryHeap (rationale: we implement what are
effectivley queues in the buffer package)
b) change BinaryHeap to wrap a BinaryBuffer
I guess I ultimately favor a).
>
> I am +1 on renaming to PriorityBuffer.
I agree.
Phil
>
> Stephen
>
>
> ---------------------------------------------------------------------
> 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
Re: [collections] BinaryHeap and PriorityQueue
Posted by Stephen Colebourne <sc...@btopenworld.com>.
> > 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.
I am happy for Buffer to exist in [collections] (although I wish the
methods were peek and pop) Given a choice I would deprecate PQ altogether.
Your change will need to be applied to both BinaryBuffer and BinaryHeap,
unless we make BinaryHeap wrap a BinaryBuffer (maintaining the old
interface).
I am +1 on renaming to PriorityBuffer.
Stephen
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] BinaryHeap and PriorityQueue
Posted by Phil Steitz <ph...@steitz.com>.
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" <sc...@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
Re: [collections] BinaryHeap and PriorityQueue
Posted by Stephen Colebourne <sc...@btopenworld.com>.
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
- PQ decorators now inner classes of PQUtils
We could go further and actually deprecated PQ. But I'm a little wary of
that.
(And both BinaryHeap and BinaryBuffer still need their remove bug fixing :-)
Stephen
----- Original Message -----
From: "Stephen Colebourne" <sc...@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'.
>
> Currently I have moved BinaryHeap and the PriorityQueue decorators into
the
> buffer subpackage (as they seem related). But is this right???
> 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.
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org