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

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

Issue 180047: code review 180047: 1) Change default gofmt default settings for (Closed)
Patch Set: code review 180047: 1) Change default gofmt default settings for Created 15 years, 3 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/heap.go ('k') | src/pkg/container/list/list.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 2009 The Go Authors. All rights reserved. 1 // Copyright 2009 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 package heap 5 package heap
6 6
7 import ( 7 import (
8 » "testing"; 8 » "testing"
9 » "container/vector"; 9 » "container/vector"
10 ) 10 )
11 11
12 12
13 type myHeap struct { 13 type myHeap struct {
14 // A vector.Vector implements sort.Interface except for Less, 14 // A vector.Vector implements sort.Interface except for Less,
15 // and it implements Push and Pop as required for heap.Interface. 15 // and it implements Push and Pop as required for heap.Interface.
16 » vector.Vector; 16 » vector.Vector
17 } 17 }
18 18
19 19
20 func (h *myHeap) Less(i, j int) bool» { return h.At(i).(int) < h.At(j).(int) } 20 func (h *myHeap) Less(i, j int) bool { return h.At(i).(int) < h.At(j).(int) }
21 21
22 22
23 func (h *myHeap) verify(t *testing.T, i int) { 23 func (h *myHeap) verify(t *testing.T, i int) {
24 » n := h.Len(); 24 » n := h.Len()
25 » j1 := 2*i + 1; 25 » j1 := 2*i + 1
26 » j2 := 2*i + 2; 26 » j2 := 2*i + 2
27 if j1 < n { 27 if j1 < n {
28 if h.Less(j1, i) { 28 if h.Less(j1, i) {
29 » » » t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j1)); 29 » » » t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j1))
30 » » » return; 30 » » » return
31 } 31 }
32 » » h.verify(t, j1); 32 » » h.verify(t, j1)
33 } 33 }
34 if j2 < n { 34 if j2 < n {
35 if h.Less(j2, i) { 35 if h.Less(j2, i) {
36 » » » t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j2)); 36 » » » t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j2))
37 » » » return; 37 » » » return
38 } 38 }
39 » » h.verify(t, j2); 39 » » h.verify(t, j2)
40 } 40 }
41 } 41 }
42 42
43 43
44 func TestInit0(t *testing.T) { 44 func TestInit0(t *testing.T) {
45 » h := new(myHeap); 45 » h := new(myHeap)
46 for i := 20; i > 0; i-- { 46 for i := 20; i > 0; i-- {
47 » » h.Push(0)» // all elements are the same 47 » » h.Push(0) // all elements are the same
48 } 48 }
49 » Init(h); 49 » Init(h)
50 » h.verify(t, 0); 50 » h.verify(t, 0)
51 51
52 for i := 1; h.Len() > 0; i++ { 52 for i := 1; h.Len() > 0; i++ {
53 » » x := Pop(h).(int); 53 » » x := Pop(h).(int)
54 » » h.verify(t, 0); 54 » » h.verify(t, 0)
55 if x != 0 { 55 if x != 0 {
56 t.Errorf("%d.th pop got %d; want %d", i, x, 0) 56 t.Errorf("%d.th pop got %d; want %d", i, x, 0)
57 } 57 }
58 } 58 }
59 } 59 }
60 60
61 61
62 func TestInit1(t *testing.T) { 62 func TestInit1(t *testing.T) {
63 » h := new(myHeap); 63 » h := new(myHeap)
64 for i := 20; i > 0; i-- { 64 for i := 20; i > 0; i-- {
65 » » h.Push(i)» // all elements are different 65 » » h.Push(i) // all elements are different
66 } 66 }
67 » Init(h); 67 » Init(h)
68 » h.verify(t, 0); 68 » h.verify(t, 0)
69 69
70 for i := 1; h.Len() > 0; i++ { 70 for i := 1; h.Len() > 0; i++ {
71 » » x := Pop(h).(int); 71 » » x := Pop(h).(int)
72 » » h.verify(t, 0); 72 » » h.verify(t, 0)
73 if x != i { 73 if x != i {
74 t.Errorf("%d.th pop got %d; want %d", i, x, i) 74 t.Errorf("%d.th pop got %d; want %d", i, x, i)
75 } 75 }
76 } 76 }
77 } 77 }
78 78
79 79
80 func Test(t *testing.T) { 80 func Test(t *testing.T) {
81 » h := new(myHeap); 81 » h := new(myHeap)
82 » h.verify(t, 0); 82 » h.verify(t, 0)
83 83
84 for i := 20; i > 10; i-- { 84 for i := 20; i > 10; i-- {
85 h.Push(i) 85 h.Push(i)
86 } 86 }
87 » Init(h); 87 » Init(h)
88 » h.verify(t, 0); 88 » h.verify(t, 0)
89 89
90 for i := 10; i > 0; i-- { 90 for i := 10; i > 0; i-- {
91 » » Push(h, i); 91 » » Push(h, i)
92 » » h.verify(t, 0); 92 » » h.verify(t, 0)
93 } 93 }
94 94
95 for i := 1; h.Len() > 0; i++ { 95 for i := 1; h.Len() > 0; i++ {
96 » » x := Pop(h).(int); 96 » » x := Pop(h).(int)
97 if i < 20 { 97 if i < 20 {
98 Push(h, 20+i) 98 Push(h, 20+i)
99 } 99 }
100 » » h.verify(t, 0); 100 » » h.verify(t, 0)
101 if x != i { 101 if x != i {
102 t.Errorf("%d.th pop got %d; want %d", i, x, i) 102 t.Errorf("%d.th pop got %d; want %d", i, x, i)
103 } 103 }
104 } 104 }
105 } 105 }
106 106
107 107
108 func TestRemove0(t *testing.T) { 108 func TestRemove0(t *testing.T) {
109 » h := new(myHeap); 109 » h := new(myHeap)
110 for i := 0; i < 10; i++ { 110 for i := 0; i < 10; i++ {
111 h.Push(i) 111 h.Push(i)
112 } 112 }
113 » h.verify(t, 0); 113 » h.verify(t, 0)
114 114
115 for h.Len() > 0 { 115 for h.Len() > 0 {
116 » » i := h.Len() - 1; 116 » » i := h.Len() - 1
117 » » x := Remove(h, i).(int); 117 » » x := Remove(h, i).(int)
118 if x != i { 118 if x != i {
119 t.Errorf("Remove(%d) got %d; want %d", i, x, i) 119 t.Errorf("Remove(%d) got %d; want %d", i, x, i)
120 } 120 }
121 » » h.verify(t, 0); 121 » » h.verify(t, 0)
122 } 122 }
123 } 123 }
124 124
125 125
126 func TestRemove1(t *testing.T) { 126 func TestRemove1(t *testing.T) {
127 » h := new(myHeap); 127 » h := new(myHeap)
128 for i := 0; i < 10; i++ { 128 for i := 0; i < 10; i++ {
129 h.Push(i) 129 h.Push(i)
130 } 130 }
131 » h.verify(t, 0); 131 » h.verify(t, 0)
132 132
133 for i := 0; h.Len() > 0; i++ { 133 for i := 0; h.Len() > 0; i++ {
134 » » x := Remove(h, 0).(int); 134 » » x := Remove(h, 0).(int)
135 if x != i { 135 if x != i {
136 t.Errorf("Remove(0) got %d; want %d", x, i) 136 t.Errorf("Remove(0) got %d; want %d", x, i)
137 } 137 }
138 » » h.verify(t, 0); 138 » » h.verify(t, 0)
139 } 139 }
140 } 140 }
141 141
142 142
143 func TestRemove2(t *testing.T) { 143 func TestRemove2(t *testing.T) {
144 » N := 10; 144 » N := 10
145 145
146 » h := new(myHeap); 146 » h := new(myHeap)
147 for i := 0; i < N; i++ { 147 for i := 0; i < N; i++ {
148 h.Push(i) 148 h.Push(i)
149 } 149 }
150 » h.verify(t, 0); 150 » h.verify(t, 0)
151 151
152 » m := make(map[int]int); 152 » m := make(map[int]int)
153 for h.Len() > 0 { 153 for h.Len() > 0 {
154 » » m[Remove(h, (h.Len()-1)/2).(int)] = 1; 154 » » m[Remove(h, (h.Len()-1)/2).(int)] = 1
155 » » h.verify(t, 0); 155 » » h.verify(t, 0)
156 } 156 }
157 157
158 if len(m) != N { 158 if len(m) != N {
159 t.Errorf("len(m) = %d; want %d", len(m), N) 159 t.Errorf("len(m) = %d; want %d", len(m), N)
160 } 160 }
161 for i := 0; i < len(m); i++ { 161 for i := 0; i < len(m); i++ {
162 if _, exists := m[i]; !exists { 162 if _, exists := m[i]; !exists {
163 t.Errorf("m[%d] doesn't exist", i) 163 t.Errorf("m[%d] doesn't exist", i)
164 } 164 }
165 } 165 }
166 } 166 }
OLDNEW
« no previous file with comments | « src/pkg/container/heap/heap.go ('k') | src/pkg/container/list/list.go » ('j') | no next file with comments »

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