diff options
Diffstat (limited to 'src/pkg/container/heap')
| -rw-r--r-- | src/pkg/container/heap/example_intheap_test.go | 47 | ||||
| -rw-r--r-- | src/pkg/container/heap/example_pq_test.go | 97 | ||||
| -rw-r--r-- | src/pkg/container/heap/heap.go | 117 | ||||
| -rw-r--r-- | src/pkg/container/heap/heap_test.go | 213 |
4 files changed, 0 insertions, 474 deletions
diff --git a/src/pkg/container/heap/example_intheap_test.go b/src/pkg/container/heap/example_intheap_test.go deleted file mode 100644 index 02d3d8668..000000000 --- a/src/pkg/container/heap/example_intheap_test.go +++ /dev/null @@ -1,47 +0,0 @@ -// Copyright 2012 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 example demonstrates an integer heap built using the heap interface. -package heap_test - -import ( - "container/heap" - "fmt" -) - -// An IntHeap is a min-heap of ints. -type IntHeap []int - -func (h IntHeap) Len() int { return len(h) } -func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } -func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } - -func (h *IntHeap) Push(x interface{}) { - // Push and Pop use pointer receivers because they modify the slice's length, - // not just its contents. - *h = append(*h, x.(int)) -} - -func (h *IntHeap) Pop() interface{} { - old := *h - n := len(old) - x := old[n-1] - *h = old[0 : n-1] - return x -} - -// This example inserts several ints into an IntHeap, checks the minimum, -// and removes them in order of priority. -func Example_intHeap() { - h := &IntHeap{2, 1, 5} - heap.Init(h) - heap.Push(h, 3) - fmt.Printf("minimum: %d\n", (*h)[0]) - for h.Len() > 0 { - fmt.Printf("%d ", heap.Pop(h)) - } - // Output: - // minimum: 1 - // 1 2 3 5 -} diff --git a/src/pkg/container/heap/example_pq_test.go b/src/pkg/container/heap/example_pq_test.go deleted file mode 100644 index 7017095cb..000000000 --- a/src/pkg/container/heap/example_pq_test.go +++ /dev/null @@ -1,97 +0,0 @@ -// Copyright 2012 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 example demonstrates a priority queue built using the heap interface. -package heap_test - -import ( - "container/heap" - "fmt" -) - -// An Item is something we manage in a priority queue. -type Item struct { - value string // The value of the item; arbitrary. - priority int // The priority of the item in the queue. - // The index is needed by update and is maintained by the heap.Interface methods. - index int // The index of the item in the heap. -} - -// A PriorityQueue implements heap.Interface and holds Items. -type PriorityQueue []*Item - -func (pq PriorityQueue) Len() int { return len(pq) } - -func (pq PriorityQueue) Less(i, j int) bool { - // We want Pop to give us the highest, not lowest, priority so we use greater than here. - return pq[i].priority > pq[j].priority -} - -func (pq PriorityQueue) Swap(i, j int) { - pq[i], pq[j] = pq[j], pq[i] - pq[i].index = i - pq[j].index = j -} - -func (pq *PriorityQueue) Push(x interface{}) { - n := len(*pq) - item := x.(*Item) - item.index = n - *pq = append(*pq, item) -} - -func (pq *PriorityQueue) Pop() interface{} { - old := *pq - n := len(old) - item := old[n-1] - item.index = -1 // for safety - *pq = old[0 : n-1] - return item -} - -// update modifies the priority and value of an Item in the queue. -func (pq *PriorityQueue) update(item *Item, value string, priority int) { - item.value = value - item.priority = priority - heap.Fix(pq, item.index) -} - -// This example creates a PriorityQueue with some items, adds and manipulates an item, -// and then removes the items in priority order. -func Example_priorityQueue() { - // Some items and their priorities. - items := map[string]int{ - "banana": 3, "apple": 2, "pear": 4, - } - - // Create a priority queue, put the items in it, and - // establish the priority queue (heap) invariants. - pq := make(PriorityQueue, len(items)) - i := 0 - for value, priority := range items { - pq[i] = &Item{ - value: value, - priority: priority, - index: i, - } - i++ - } - heap.Init(&pq) - - // Insert a new item and then modify its priority. - item := &Item{ - value: "orange", - priority: 1, - } - heap.Push(&pq, item) - pq.update(item, item.value, 5) - - // Take the items out; they arrive in decreasing priority order. - for pq.Len() > 0 { - item := heap.Pop(&pq).(*Item) - fmt.Printf("%.2d:%s ", item.priority, item.value) - } - // Output: - // 05:orange 04:pear 03:banana 02:apple -} diff --git a/src/pkg/container/heap/heap.go b/src/pkg/container/heap/heap.go deleted file mode 100644 index c467a1191..000000000 --- a/src/pkg/container/heap/heap.go +++ /dev/null @@ -1,117 +0,0 @@ -// 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 provides heap operations for any type that implements -// heap.Interface. A heap is a tree with the property that each node is the -// minimum-valued node in its subtree. -// -// The minimum element in the tree is the root, at index 0. -// -// A heap is a common way to implement a priority queue. To build a priority -// queue, implement the Heap interface with the (negative) priority as the -// ordering for the Less method, so Push adds items while Pop removes the -// highest-priority item from the queue. The Examples include such an -// implementation; the file example_pq_test.go has the complete source. -// -package heap - -import "sort" - -// Any type that implements heap.Interface may be used as a -// min-heap with the following invariants (established after -// Init has been called or if the data is empty or sorted): -// -// !h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len() -// -// Note that Push and Pop in this interface are for package heap's -// implementation to call. To add and remove things from the heap, -// use heap.Push and heap.Pop. -type Interface interface { - sort.Interface - Push(x interface{}) // add x as element Len() - Pop() interface{} // remove and return element Len() - 1. -} - -// A heap 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) where n = h.Len(). -// -func Init(h Interface) { - // heapify - n := h.Len() - for i := n/2 - 1; i >= 0; i-- { - down(h, i, n) - } -} - -// Push pushes the element x onto the heap. The complexity is -// O(log(n)) where n = h.Len(). -// -func Push(h Interface, 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(). -// It is equivalent to Remove(h, 0). -// -func Pop(h Interface) interface{} { - n := h.Len() - 1 - h.Swap(0, n) - down(h, 0, n) - return h.Pop() -} - -// Remove removes the element at index i from the heap. -// The complexity is O(log(n)) where n = h.Len(). -// -func Remove(h Interface, i int) interface{} { - n := h.Len() - 1 - if n != i { - h.Swap(i, n) - down(h, i, n) - up(h, i) - } - return h.Pop() -} - -// Fix re-establishes 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(). -func Fix(h Interface, i int) { - down(h, i, h.Len()) - up(h, i) -} - -func up(h Interface, j int) { - for { - i := (j - 1) / 2 // parent - if i == j || !h.Less(j, i) { - break - } - h.Swap(i, j) - j = i - } -} - -func down(h Interface, i, n int) { - for { - j1 := 2*i + 1 - if j1 >= n || j1 < 0 { // j1 < 0 after int overflow - break - } - j := j1 // left child - if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) { - j = j2 // = 2*i + 2 // right child - } - if !h.Less(j, i) { - 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 deleted file mode 100644 index b3d054c5f..000000000 --- a/src/pkg/container/heap/heap_test.go +++ /dev/null @@ -1,213 +0,0 @@ -// 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 ( - "math/rand" - "testing" -) - -type myHeap []int - -func (h *myHeap) Less(i, j int) bool { - return (*h)[i] < (*h)[j] -} - -func (h *myHeap) Swap(i, j int) { - (*h)[i], (*h)[j] = (*h)[j], (*h)[i] -} - -func (h *myHeap) Len() int { - return len(*h) -} - -func (h *myHeap) Pop() (v interface{}) { - *h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1] - return -} - -func (h *myHeap) Push(v interface{}) { - *h = append(*h, v.(int)) -} - -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[i], j1, h[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[i], j1, h[j2]) - return - } - h.verify(t, j2) - } -} - -func TestInit0(t *testing.T) { - h := new(myHeap) - for i := 20; i > 0; i-- { - h.Push(0) // all elements are the same - } - Init(h) - h.verify(t, 0) - - for i := 1; h.Len() > 0; i++ { - x := Pop(h).(int) - h.verify(t, 0) - if x != 0 { - t.Errorf("%d.th pop got %d; want %d", i, x, 0) - } - } -} - -func TestInit1(t *testing.T) { - h := new(myHeap) - for i := 20; i > 0; i-- { - h.Push(i) // all elements are different - } - 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 := new(myHeap) - 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) - } - } -} - -func TestRemove0(t *testing.T) { - h := new(myHeap) - for i := 0; i < 10; i++ { - h.Push(i) - } - h.verify(t, 0) - - for h.Len() > 0 { - i := h.Len() - 1 - x := Remove(h, i).(int) - if x != i { - t.Errorf("Remove(%d) got %d; want %d", i, x, i) - } - h.verify(t, 0) - } -} - -func TestRemove1(t *testing.T) { - h := new(myHeap) - for i := 0; i < 10; i++ { - h.Push(i) - } - h.verify(t, 0) - - for i := 0; h.Len() > 0; i++ { - x := Remove(h, 0).(int) - if x != i { - t.Errorf("Remove(0) got %d; want %d", x, i) - } - h.verify(t, 0) - } -} - -func TestRemove2(t *testing.T) { - N := 10 - - h := new(myHeap) - for i := 0; i < N; i++ { - h.Push(i) - } - h.verify(t, 0) - - m := make(map[int]bool) - for h.Len() > 0 { - m[Remove(h, (h.Len()-1)/2).(int)] = true - h.verify(t, 0) - } - - if len(m) != N { - t.Errorf("len(m) = %d; want %d", len(m), N) - } - for i := 0; i < len(m); i++ { - if !m[i] { - t.Errorf("m[%d] doesn't exist", i) - } - } -} - -func BenchmarkDup(b *testing.B) { - const n = 10000 - h := make(myHeap, n) - for i := 0; i < b.N; i++ { - for j := 0; j < n; j++ { - Push(&h, 0) // all elements are the same - } - for h.Len() > 0 { - Pop(&h) - } - } -} - -func TestFix(t *testing.T) { - h := new(myHeap) - h.verify(t, 0) - - for i := 200; i > 0; i -= 10 { - Push(h, i) - } - h.verify(t, 0) - - if (*h)[0] != 10 { - t.Fatalf("Expected head to be 10, was %d", (*h)[0]) - } - (*h)[0] = 210 - Fix(h, 0) - h.verify(t, 0) - - for i := 100; i > 0; i-- { - elem := rand.Intn(h.Len()) - if i&1 == 0 { - (*h)[elem] *= 2 - } else { - (*h)[elem] /= 2 - } - Fix(h, elem) - h.verify(t, 0) - } -} |