On 06/25/2012 01:17 PM, David Holmes wrote:
Hi Remi,
On 25/06/2012 7:01 PM, Rémi Forax wrote:
Hi David,
I think the test
if (n > 0) {
should not be in siftDown* but should be done at all callsites,
by example in heapify, you can hoist the test outside of the loop.
I originally had it at the call-site (it already exists in a number of
them) but Doug prefers it to be internalized. He wrote:
"... a better strategy is to move the n > 0 check to the siftDown code
itself, so (existing and potential) callers don't need the check. "
This can be mitigated by modifying the doc comment to say that n should
be strictly positive.
"... an explicit n > 0 check acts to hoist array index checks in loop
so turns out to be faster in general."
also true if n > 0 is done at callsites and methods shiftDown* is
inlined, but this is not something
that is easy to guarantee because it depends on the complexity of the
comparator implementation.
so thumb up :)
In dequeue, it's a matter of style but the 'else' is not needed anymore.
Otherwise the changes looks ok for me.
Thanks,
David
cheers,
Rémi
