[go] container/heap: use sort.Interface where possible
Gerrit Bot (Gerrit)
Gerrit Bot has uploaded the change for review![]( "Open in Gerrit")
Commit message
container/heap: use sort.Interface where possible
Functions heap.Pop(), heap.Push() and heap.Remove() use type heap.Interface. This type is equal to sort.Interface, with Push() and Pop() methods added. This is necessary, because these functions affect the size of the resulting heap.
Functions heap.Fix() and heap.Init() are different. They may compare and swap elements in the underlying container, but never alter its size. It is therefore possible to just use sort.Interface. This would make these functions a lot more pleasant to use in situations where you know the number of elements in the heap is fixed.
Consider the case where you use these functions to merge the results of n infinitely long monotonically increasing sequences. For example, logs received from multiple sources that need to be turned into a single stream of events sorted by time. This can now be implemented as follows:
type Value ...
type Sequence <-chan Value
type PeekedSequence struct {
First Value
Remainder Sequence
}
type SequenceHeap []PeekedSequence
func (h SequenceHeap) Len() int { return len(h) }
func (h SequenceHeap) Less(i, j int) bool { return h[i].First < h[j].First }
func (h SequenceHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func MergeSequences(sequences []Sequence, out chan<- Value) {
h := make(SequenceHeap, 0, len(sequences))
for _, s := range sequences {
h = append(h, PeekedSequence{
First: <-s,
Remainder: s,
})
}
heap.Init(h)
for {
out <- h[0].First
h[0].First = <-h[0].Remainder
heap.Fix(h, 0)
}
}
Before this change was made, SequenceHeap had to provide Pop() and Push() methods that are known to be unused.
Change diff
diff --git a/src/container/heap/heap.go b/src/container/heap/heap.go
index 3ad218e..56a268c 100644
--- a/src/container/heap/heap.go
+++ b/src/container/heap/heap.go
@@ -38,7 +38,7 @@
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
-func Init(h Interface) {
+func Init(h sort.Interface) {
// heapify
n := h.Len()
for i := n/2 - 1; i >= 0; i-- {
@@ -80,13 +80,13 @@
// 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().
-func Fix(h Interface, i int) {
+func Fix(h sort.Interface, i int) {
if !down(h, i, h.Len()) {
up(h, i)
}
}
-func up(h Interface, j int) {
+func up(h sort.Interface, j int) {
for {
i := (j - 1) / 2 // parent
if i == j || !h.Less(j, i) {
@@ -97,7 +97,7 @@
}
}
-func down(h Interface, i0, n int) bool {
+func down(h sort.Interface, i0, n int) bool {
i := i0
for {
j1 := 2*i + 1
Change information
- M src/container/heap/heap.go
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gopher Robot (Gerrit)
Gopher Robot added 1 comment![]( "Open in Gerrit")
I spotted some possible problems.
These findings are based on simple heuristics. If a finding appears wrong, briefly reply here saying so. Otherwise, please address any problems and update the GitHub PR. When complete, mark this comment as 'Done' and click the [blue 'Reply' button](https://go.dev/wiki/GerritBot#i-left-a-reply-to-a-comment-in-gerrit-but-no-one-but-me-can-see-it) above.
Possible problems detected:
1. Lines in the commit message should be wrapped at ~76 characters unless needed for things like URLs or tables. You have a 327 character line.
2. You usually need to reference a bug number for all but trivial or cosmetic fixes. For this repo, the format is usually 'Fixes #12345' or 'Updates #12345' at the end of the commit message. Should you have a bug reference?
The commit title and commit message body come from the GitHub PR title and description, and must be edited in the GitHub web interface (not via git). For instructions, see [here](https://go.dev/wiki/GerritBot/#how-does-gerritbot-determine-the-final-commit-message). For guidelines on commit messages for the Go project, see [here](https://go.dev/doc/contribute#commit_messages).
(In general for Gerrit code reviews, the change author is expected to [log in to Gerrit](https://go-review.googlesource.com/login/) with a Gmail or other Google account and then close out each piece of feedback by marking it as 'Done' if implemented as suggested or otherwise reply to each review comment. See the [Review](https://go.dev/doc/contribute#review) section of the Contributing Guide for details.)
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer added 1 comment![]( "Open in Gerrit")
Thanks, but we cannot make this change in a backward-compatible way: if some code depends on the current signature of, say heap.Init, specifically that the argument is of type heap.Interface, changing it to sort.Interface changes that signature type which in turn may break clients (unlikely but possible).
Furthermore, we're not making changes to container/* packages except for bug fixes. These packages need to be essentially rewritten, with generic APIs. Specifically, container/heap is hard to use and needs to be replaced eventually.
You're of course welcome to copy this code and change it as you please for your own purposes.
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Sean Liao (Gerrit)
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |