heap algorithm

R=rsc
DELTA=196  (194 added, 0 deleted, 2 changed)
OCL=34234
CL=34263

5 files changed, 196 insertions, 2 deletions

diff --git a/src/pkg/Make.deps b/src/pkg/Make.deps
index 38e3dd621..bae576564 100644
--- a/src/pkg/Make.deps
+++ b/src/pkg/Make.deps
@@ -3,10 +3,11 @@ base64.install: bytes.install io.install os.install strconv.install
 big.install:
 bignum.install: fmt.install
 bufio.install: io.install os.install strconv.install utf8.install
-bytes.install: os.install utf8.install
+bytes.install: os.install unicode.install utf8.install
 compress/flate.install: bufio.install io.install os.install strconv.install
 compress/gzip.install: bufio.install compress/flate.install hash.install hash/crc32.install io.install os.install
 compress/zlib.install: bufio.install compress/flate.install hash.install hash/adler32.install io.install os.install
+container/heap.install: sort.install
 container/list.install:
 container/ring.install:
 container/vector.install:
@@ -53,7 +54,7 @@ rpc.install: bufio.install fmt.install gob.install http.install io.install log.i
 runtime.install:
 sort.install:
 strconv.install: bytes.install math.install os.install unicode.install utf8.install
-strings.install: utf8.install
+strings.install: unicode.install utf8.install
 sync.install:
 syscall.install: sync.install
 tabwriter.install: bytes.install container/vector.install io.install os.install utf8.install
diff --git a/src/pkg/Makefile b/src/pkg/Makefile
index 7d0b76e11..73dde239b 100644
--- a/src/pkg/Makefile
+++ b/src/pkg/Makefile
@@ -21,6 +21,7 @@ DIRS=\
 	compress/flate\
 	compress/gzip\
 	compress/zlib\
+	container/heap\
 	container/list\
 	container/ring\
 	container/vector\
diff --git a/src/pkg/container/heap/Makefile b/src/pkg/container/heap/Makefile
new file mode 100644
index 000000000..2625d19ca
--- /dev/null
+++ b/src/pkg/container/heap/Makefile
@@ -0,0 +1,11 @@
+# Copyright 2009 The Go Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style
+# license that can be found in the LICENSE file.
+
+include $(GOROOT)/src/Make.$(GOARCH)
+
+TARG=container/heap
+GOFILES=\
+	heap.go\
+
+include $(GOROOT)/src/Make.pkg
diff --git a/src/pkg/container/heap/heap.go b/src/pkg/container/heap/heap.go
new file mode 100644
index 000000000..d35f4d133
--- /dev/null
+++ b/src/pkg/container/heap/heap.go
@@ -0,0 +1,82 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This package provides heap operations for any type that implements
+// HeapInterface.
+//
+package heap
+
+import "sort"
+
+// Any type that implements HeapInterface may be used as a
+// heap with the following invariants (established after Init
+// has been called):
+//
+//	h.Less(i, j) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len()
+//
+type HeapInterface interface {
+	sort.SortInterface;
+	Push(x interface{});
+	Pop() interface{};
+}
+
+
+// A heaper must be initialized before any of the heap operations
+// can be used. Init is idempotent with respect to the heap invariants
+// and may be called whenever the heap invariants may have been invalidated.
+// Its complexity is O(n*log(n)) where n = h.Len().
+//
+func Init(h HeapInterface) {
+	sort.Sort(h);
+}
+
+
+// Push pushes the element x onto the heap. The complexity is
+// O(log(n)) where n = h.Len().
+//
+func Push(h HeapInterface, x interface{}) {
+	h.Push(x);
+	up(h, h.Len()-1);
+}
+
+
+// Pop removes the minimum element (according to Less) from the heap
+// and returns it. The complexity is O(log(n)) where n = h.Len().
+//
+func Pop(h HeapInterface) interface{} {
+	n := h.Len()-1;
+	h.Swap(0, n);
+	down(h, 0, n);
+	return h.Pop();
+}
+
+
+func up(h HeapInterface, j int) {
+	for {
+		i := (j-1)/2;
+		if i == j || h.Less(i, j) {
+			break;
+		}
+		h.Swap(i, j);
+		j = i;
+	}
+}
+
+
+func down(h HeapInterface, i, n int) {
+	for {
+		j := 2*i + 1;
+		if j >= n {
+			break;
+		}
+		if j1 := j+1; j1 < n && !h.Less(j, j1) {
+			j = j1;  // = 2*i + 2
+		}
+		if h.Less(i, j) {
+			break;
+		}
+		h.Swap(i, j);
+		i = j;
+	}
+}
diff --git a/src/pkg/container/heap/heap_test.go b/src/pkg/container/heap/heap_test.go
new file mode 100644
index 000000000..99722f2e9
--- /dev/null
+++ b/src/pkg/container/heap/heap_test.go
@@ -0,0 +1,99 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package heap
+
+import (
+	"testing";
+	"container/vector";
+)
+
+
+type myHeap struct {
+	vector.IntVector;
+}
+
+
+func newHeap() *myHeap {
+	var h myHeap;
+	h.IntVector.Init(0);
+	return &h;
+}
+
+
+func (h *myHeap) verify(t *testing.T, i int) {
+	n := h.Len();
+	j1 := 2*i + 1;
+	j2 := 2*i + 2;
+	if j1 < n {
+		if h.Less(j1, i) {
+			t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j1));
+			return;
+		}
+		h.verify(t, j1);
+	}
+	if j2 < n {
+		if h.Less(j2, i) {
+			t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j2));
+			return;
+		}
+		h.verify(t, j2);
+	}
+}
+
+
+func (h *myHeap) Push(x interface{}) {
+	h.IntVector.Push(x.(int));
+}
+
+
+func (h *myHeap) Pop() interface{} {
+	return h.IntVector.Pop();
+}
+
+
+func TestInit(t *testing.T) {
+	h := newHeap();
+	for i := 20; i > 0; i-- {
+		h.Push(i);
+	}
+	Init(h);
+	h.verify(t, 0);
+
+	for i := 1; h.Len() > 0; i++ {
+		x := Pop(h).(int);
+		h.verify(t, 0);
+		if x != i {
+			t.Errorf("%d.th pop got %d; want %d", i, x, i);
+		}
+	}
+}
+
+
+func Test(t *testing.T) {
+	h := newHeap();
+	h.verify(t, 0);
+
+	for i := 20; i > 10; i-- {
+		h.Push(i);
+	}
+	Init(h);
+	h.verify(t, 0);
+
+	for i := 10; i > 0; i-- {
+		Push(h, i);
+		h.verify(t, 0);
+	}
+
+	for i := 1; h.Len() > 0; i++ {
+		x := Pop(h).(int);
+		if i < 20 {
+			Push(h, 20+i);
+		}
+		h.verify(t, 0);
+		if x != i {
+			t.Errorf("%d.th pop got %d; want %d", i, x, i);
+		}
+	}
+}