Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(32)

Side by Side Diff: src/pkg/container/heap/example_pq_test.go

Issue 7068048: code review 7068048: container/heap: revise example and add a si... (Closed)
Patch Set: diff -r 49db9317937c https://code.google.com/p/go Created 11 years, 2 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/pkg/container/heap/example_intheap_test.go ('k') | src/pkg/container/heap/heap.go » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2012 The Go Authors. All rights reserved. 1 // Copyright 2012 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style 2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file. 3 // license that can be found in the LICENSE file.
4 4
5 // This example demonstrates a priority queue built using the heap interface. 5 // This example demonstrates a priority queue built using the heap interface.
6 package heap_test 6 package heap_test
7 7
8 import ( 8 import (
9 "container/heap" 9 "container/heap"
10 "fmt" 10 "fmt"
(...skipping 12 matching lines...) Expand all
23 23
24 func (pq PriorityQueue) Len() int { return len(pq) } 24 func (pq PriorityQueue) Len() int { return len(pq) }
25 25
26 func (pq PriorityQueue) Less(i, j int) bool { 26 func (pq PriorityQueue) Less(i, j int) bool {
27 // We want Pop to give us the highest, not lowest, priority so we use gr eater than here. 27 // We want Pop to give us the highest, not lowest, priority so we use gr eater than here.
28 return pq[i].priority > pq[j].priority 28 return pq[i].priority > pq[j].priority
29 } 29 }
30 30
31 func (pq PriorityQueue) Swap(i, j int) { 31 func (pq PriorityQueue) Swap(i, j int) {
32 pq[i], pq[j] = pq[j], pq[i] 32 pq[i], pq[j] = pq[j], pq[i]
33 » pq[i].index = i 33 » pq[i].index, pq[j].index = i, j
rsc 2013/01/18 20:08:24 Please restore the old code. This is not a swap.
cespare 2013/01/18 21:00:29 Done.
34 » pq[j].index = j
35 } 34 }
36 35
37 func (pq *PriorityQueue) Push(x interface{}) { 36 func (pq *PriorityQueue) Push(x interface{}) {
38 // Push and Pop use pointer receivers because they modify the slice's le ngth,
39 // not just its contents.
40 n := len(*pq) 37 n := len(*pq)
41 item := x.(*Item) 38 item := x.(*Item)
42 item.index = n 39 item.index = n
43 *pq = append(*pq, item) 40 *pq = append(*pq, item)
44 } 41 }
45 42
46 func (pq *PriorityQueue) Pop() interface{} { 43 func (pq *PriorityQueue) Pop() interface{} {
47 » a := *pq 44 » old := *pq
48 » n := len(a) 45 » n := len(old)
49 » item := a[n-1] 46 » item := old[n-1]
50 item.index = -1 // for safety 47 item.index = -1 // for safety
51 » *pq = a[0 : n-1] 48 » *pq = old[0 : n-1]
52 return item 49 return item
53 } 50 }
54 51
55 // update is not used by the example but shows how to take the top item from 52 // update modifies the priority and value of an Item in the queue.
56 // the queue, update its priority and value, and put it back. 53 func (pq *PriorityQueue) update(item *Item, value string, priority int) {
57 func (pq *PriorityQueue) update(value string, priority int) { 54 » heap.Remove(pq, item.index)
58 » item := heap.Pop(pq).(*Item)
59 item.value = value 55 item.value = value
60 item.priority = priority 56 item.priority = priority
61 heap.Push(pq, item) 57 heap.Push(pq, item)
62 } 58 }
63 59
64 // changePriority is not used by the example but shows how to change the 60 // This example inserts some items into a PriorityQueue, manipulates an item,
65 // priority of an arbitrary item. 61 // and then removes the items in priority order.
66 func (pq *PriorityQueue) changePriority(item *Item, priority int) { 62 func Example_priorityQueue() {
67 » heap.Remove(pq, item.index) 63 » // Some items and their priorities.
68 » item.priority = priority 64 » items := map[string]int{
65 » » "banana": 3, "apple": 2, "pear": 4,
66 » }
67
68 » // Create a priority queue and put the items in it.
69 » pq := &PriorityQueue{}
70 » heap.Init(pq)
71 » for value, priority := range items {
72 » » item := &Item{
73 » » » value: value,
74 » » » priority: priority,
75 » » }
76 » » heap.Push(pq, item)
77 » }
78
79 » // Insert a new item and then modify its priority.
80 » item := &Item{
81 » » value: "orange",
82 » » priority: 1,
83 » }
69 heap.Push(pq, item) 84 heap.Push(pq, item)
70 } 85 » pq.update(item, item.value, 5)
71 86
72 // This example pushes 10 items into a PriorityQueue and takes them out in 87 » // Take the items out; they arrive in decreasing priority order.
73 // order of priority. 88 » for pq.Len() > 0 {
74 func Example() { 89 » » item := heap.Pop(pq).(*Item)
75 » const nItem = 10
76 » // Random priorities for the items (a permutation of 0..9, times 11)).
77 » priorities := [nItem]int{
78 » » 77, 22, 44, 55, 11, 88, 33, 99, 00, 66,
79 » }
80 » values := [nItem]string{
81 » » "zero", "one", "two", "three", "four", "five", "six", "seven", " eight", "nine",
82 » }
83 » // Create a priority queue and put some items in it.
84 » pq := make(PriorityQueue, 0, nItem)
85 » for i := 0; i < cap(pq); i++ {
86 » » item := &Item{
87 » » » value: values[i],
88 » » » priority: priorities[i],
89 » » }
90 » » heap.Push(&pq, item)
91 » }
92 » // Take the items out; should arrive in decreasing priority order.
93 » // For example, the highest priority (99) is the seventh item, so output starts with 99:"seven".
94 » for i := 0; i < nItem; i++ {
95 » » item := heap.Pop(&pq).(*Item)
96 fmt.Printf("%.2d:%s ", item.priority, item.value) 90 fmt.Printf("%.2d:%s ", item.priority, item.value)
97 } 91 }
98 // Output: 92 // Output:
99 » // 99:seven 88:five 77:zero 66:nine 55:three 44:two 33:six 22:one 11:fou r 00:eight 93 » // 05:orange 04:pear 03:banana 02:apple
100 } 94 }
OLDNEW
« no previous file with comments | « src/pkg/container/heap/example_intheap_test.go ('k') | src/pkg/container/heap/heap.go » ('j') | no next file with comments »

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b