code review 12265043: container/heap: add Fix and document the min is element 0.

container/heap: add Fix and document the min is element 0.

Fixes issue 5372.
Fixes issue 5577.

[peted, 2013-08-01 15:42:16]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://code.google.com/p/go

[rsc, 2013-08-01 15:55:20]

s/()// in the description.
Functions are just names, no need for a () suffix.

[peted, 2013-08-01 15:58:43]

On 2013/08/01 15:55:20, rsc wrote:
> s/()// in the description.
> Functions are just names, no need for a () suffix.

Understood and done.

[rsc, 2013-08-02 20:05:51]

https://codereview.appspot.com/12265043/diff/11001/src/pkg/container/heap/hea...
File src/pkg/container/heap/heap.go (right):

https://codereview.appspot.com/12265043/diff/11001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:9: // This means the minimum element of the
entire heap is the root,
// The minimum element in the tree is the root, at index 0.

https://codereview.appspot.com/12265043/diff/11001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:82: // Fix the element at position i, restoring
the heap if the value
// Fix reestablishes the heap ordering after the element at index i has changed
its value.
// Changing the value of the element at index i and then calling Fix is
equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new
value.
// The complexity is O(log(n)) where n = h.Len().

https://codereview.appspot.com/12265043/diff/11001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:86: if i != n {
Why this test?
Callers should not be passing i >= n.

[peted, 2013-08-02 21:54:10]

https://codereview.appspot.com/12265043/diff/11001/src/pkg/container/heap/hea...
File src/pkg/container/heap/heap.go (right):

https://codereview.appspot.com/12265043/diff/11001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:9: // This means the minimum element of the
entire heap is the root,
On 2013/08/02 20:05:51, rsc wrote:
> // The minimum element in the tree is the root, at index 0.

Done.

https://codereview.appspot.com/12265043/diff/11001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:82: // Fix the element at position i, restoring
the heap if the value
On 2013/08/02 20:05:51, rsc wrote:
> // Fix reestablishes the heap ordering after the element at index i has
changed
> its value.
> // Changing the value of the element at index i and then calling Fix is
> equivalent to,
> // but less expensive than, calling Remove(h, i) followed by a Push of the new
> value.
> // The complexity is O(log(n)) where n = h.Len().

Done.

https://codereview.appspot.com/12265043/diff/11001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:86: if i != n {
On 2013/08/02 20:05:51, rsc wrote:
> Why this test?
> Callers should not be passing i >= n.

Done.

[peted, 2013-08-02 21:54:27]

Hello gri@golang.org, rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.

[bradfitz, 2013-08-05 16:56:29]

LGTM

Will defer to others on docs.

https://codereview.appspot.com/12265043/diff/20001/src/pkg/container/heap/hea...
File src/pkg/container/heap/heap.go (right):

https://codereview.appspot.com/12265043/diff/20001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:9: // This means the minimum element in the tree
is the root, at index 0.
I would drop "This means". It sounds weird starting a paragraph.

[rsc, 2013-08-05 17:33:58]

https://codereview.appspot.com/12265043/diff/20001/src/pkg/container/heap/hea...
File src/pkg/container/heap/heap.go (right):

https://codereview.appspot.com/12265043/diff/20001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:9: // This means the minimum element in the tree
is the root, at index 0.
On 2013/08/05 16:56:29, bradfitz wrote:
> I would drop "This means". It sounds weird starting a paragraph.

Indeed. The text I suggested had that edit.

[rsc, 2013-08-05 17:34:06]

Leaving final sign-off for gri.

[peted, 2013-08-05 22:13:50]

Hello gri@golang.org, rsc@golang.org, bradfitz@golang.org (cc:
golang-dev@googlegroups.com),

Please take another look.

[peted, 2013-08-05 22:15:09]

Thank you gentlemen.

https://codereview.appspot.com/12265043/diff/20001/src/pkg/container/heap/hea...
File src/pkg/container/heap/heap.go (right):

https://codereview.appspot.com/12265043/diff/20001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:9: // This means the minimum element in the tree
is the root, at index 0.
On 2013/08/05 17:33:58, rsc wrote:
> On 2013/08/05 16:56:29, bradfitz wrote:
> > I would drop "This means". It sounds weird starting a paragraph.
> 
> Indeed. The text I suggested had that edit.

Done.

[r, 2013-08-05 22:21:40]

LGTM

https://codereview.appspot.com/12265043/diff/27001/src/pkg/container/heap/hea...
File src/pkg/container/heap/heap.go (right):

https://codereview.appspot.com/12265043/diff/27001/src/pkg/container/heap/hea...
src/pkg/container/heap/heap.go:59: // Same as Remove(h, 0).
It is equivalent to Remove(h, 0).

(while you're here, please make this a sentence.)

[peted, 2013-08-05 22:24:37]

Hello gri@golang.org, rsc@golang.org, bradfitz@golang.org, r@golang.org (cc:
golang-dev@googlegroups.com),

Please take another look.

[peted, 2013-08-05 22:26:30]

On 2013/08/05 22:21:40, r wrote:
> LGTM
> 
>
https://codereview.appspot.com/12265043/diff/27001/src/pkg/container/heap/hea...
> File src/pkg/container/heap/heap.go (right):
> 
>
https://codereview.appspot.com/12265043/diff/27001/src/pkg/container/heap/hea...
> src/pkg/container/heap/heap.go:59: // Same as Remove(h, 0).
> It is equivalent to Remove(h, 0).
> 
> (while you're here, please make this a sentence.)

Heh, there you go.

When I make small changes like this, is is sufficient to hg upload and then
Publish & Mail comments? I keep doing hg mail, and end up sending two mails each
time.

[gri, 2013-08-05 22:38:22]

If you say hg mail CL it will automatically send another mail. Just hg
upload, and reply to the comments via Rietveld.
- gri


On Mon, Aug 5, 2013 at 3:26 PM, <pieter@binky.org.uk> wrote:

> On 2013/08/05 22:21:40, r wrote:
>
>> LGTM
>>
>
>
> https://codereview.appspot.**com/12265043/diff/27001/src/**
>
pkg/container/heap/heap.go<https://codereview.appspot.com/12265043/diff/27001/src/pkg/container/heap/heap.go>
>
>> File src/pkg/container/heap/heap.go (right):
>>
>
>
> https://codereview.appspot.**com/12265043/diff/27001/src/**
>
pkg/container/heap/heap.go#**newcode59<https://codereview.appspot.com/12265043/diff/27001/src/pkg/container/heap/heap.go#newcode59>
>
>> src/pkg/container/heap/heap.**go:59: // Same as Remove(h, 0).
>> It is equivalent to Remove(h, 0).
>>
>
>  (while you're here, please make this a sentence.)
>>
>
> Heh, there you go.
>
> When I make small changes like this, is is sufficient to hg upload and
> then Publish & Mail comments? I keep doing hg mail, and end up sending
> two mails each time.
>
>
https://codereview.appspot.**com/12265043/<https://codereview.appspot.com/122...
>

[peted, 2013-08-05 22:40:25]

On 2013/08/05 22:38:22, gri wrote:
> If you say hg mail CL it will automatically send another mail. Just hg
> upload, and reply to the comments via Rietveld.
> - gri

I know, I was just wondering what the protocol was. I'll do as you say in the
future, thank you.

[gri, 2013-08-05 22:44:46]

LGTM

[gri, 2013-08-05 22:45:43]

*** Submitted as https://code.google.com/p/go/source/detail?r=b2b6f8df031e ***

container/heap: add Fix and document the min is element 0.

Fixes issue 5372.
Fixes issue 5577.

R=gri, rsc, bradfitz, r
CC=golang-dev
https://codereview.appspot.com/12265043

Committer: Robert Griesemer <gri@golang.org>