OLD | NEW |
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 } |
OLD | NEW |