Re: [collections] BinaryHeap and PriorityQueue
from:Phil Steitz [EMAIL PROTECTED] 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. Its hassle vs absolute performance. Always tricky in collections. 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). The comparator is returned by a method in PriorityBuffer, so this might cause problems. (Of course the null comparator could similarly be represented by a ComparableComparator at the cost of an object creation) 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. No backwards compatability issues - BinaryHeap is final, PriorityBuffer is new :-) Stephen - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] BinaryHeap and PriorityQueue
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 [EMAIL PROTECTED] 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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] BinaryHeap and PriorityQueue
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 [EMAIL PROTECTED] 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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] BinaryHeap and PriorityQueue
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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] BinaryHeap and PriorityQueue
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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] BinaryHeap and PriorityQueue
Stephen Colebourne wrote: From: Phil Steitz [EMAIL PROTECTED] 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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
[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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
