OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 // | 4 // |
5 // VMOptions= | 5 // VMOptions= |
6 | 6 |
7 // Tests of hash set behavior, with focus in iteration and concurrent | 7 // Tests of hash set behavior, with focus in iteration and concurrent |
8 // modification errors. | 8 // modification errors. |
9 | 9 |
10 library hash_map2_test; | 10 library hash_map2_test; |
11 | |
12 import "package:expect/expect.dart"; | 11 import "package:expect/expect.dart"; |
13 import 'dart:collection'; | 12 import 'dart:collection'; |
14 import 'dart:math' as math; | 13 import 'dart:math' as math; |
15 | 14 |
16 testSet(Set newSet(), Set newSetFrom(Iterable from)) { | 15 testSet(Set newSet(), Set newSetFrom(Iterable from)) { |
| 16 |
17 Set gen(int from, int to) => | 17 Set gen(int from, int to) => |
18 new Set.from(new Iterable.generate(to - from, (n) => n + from)); | 18 new Set.from(new Iterable.generate(to - from, (n) => n + from)); |
19 | 19 |
20 bool odd(int n) => (n & 1) == 1; | 20 bool odd(int n) => (n & 1) == 1; |
21 bool even(int n) => (n & 1) == 0; | 21 bool even(int n) => (n & 1) == 0; |
22 | 22 |
23 { | 23 { // Test growing to largish capacity. |
24 // Test growing to largish capacity. | |
25 Set set = newSet(); | 24 Set set = newSet(); |
26 | 25 |
27 for (int i = 0; i < 256; i++) { | 26 for (int i = 0; i < 256; i++) { |
28 set.add(i); | 27 set.add(i); |
29 } | 28 } |
30 | 29 |
31 set.addAll(gen(256, 512)); | 30 set.addAll(gen(256, 512)); |
32 set.addAll(newSetFrom(gen(512, 1000))); | 31 set.addAll(newSetFrom(gen(512, 1000))); |
33 Expect.equals(1000, set.length); | 32 Expect.equals(1000, set.length); |
34 | 33 |
35 // Remove half. | 34 // Remove half. |
36 for (int i = 0; i < 1000; i += 2) set.remove(i); | 35 for (int i = 0; i < 1000; i += 2) set.remove(i); |
37 Expect.equals(500, set.length); | 36 Expect.equals(500, set.length); |
38 Expect.isFalse(set.any(even)); | 37 Expect.isFalse(set.any(even)); |
39 Expect.isTrue(set.every(odd)); | 38 Expect.isTrue(set.every(odd)); |
40 | 39 |
41 // Re-add all. | 40 // Re-add all. |
42 set.addAll(gen(0, 1000)); | 41 set.addAll(gen(0, 1000)); |
43 Expect.equals(1000, set.length); | 42 Expect.equals(1000, set.length); |
44 } | 43 } |
45 | 44 |
46 { | 45 { // Test having many deleted elements. |
47 // Test having many deleted elements. | |
48 Set set = newSet(); | 46 Set set = newSet(); |
49 set.add(0); | 47 set.add(0); |
50 for (int i = 0; i < 1000; i++) { | 48 for (int i = 0; i < 1000; i++) { |
51 set.add(i + 1); | 49 set.add(i + 1); |
52 set.remove(i); | 50 set.remove(i); |
53 Expect.equals(1, set.length); | 51 Expect.equals(1, set.length); |
54 } | 52 } |
55 } | 53 } |
56 | 54 |
57 { | 55 { // Test having many elements with same hashCode |
58 // Test having many elements with same hashCode | |
59 Set set = newSet(); | 56 Set set = newSet(); |
60 for (int i = 0; i < 1000; i++) { | 57 for (int i = 0; i < 1000; i++) { |
61 set.add(new BadHashCode()); | 58 set.add(new BadHashCode()); |
62 } | 59 } |
63 Expect.equals(1000, set.length); | 60 Expect.equals(1000, set.length); |
64 } | 61 } |
65 | 62 |
66 { | 63 { // Check concurrent modification |
67 // Check concurrent modification | |
68 Set set = newSet()..add(0)..add(1); | 64 Set set = newSet()..add(0)..add(1); |
69 | 65 |
70 { | 66 { // Test adding before a moveNext. |
71 // Test adding before a moveNext. | |
72 Iterator iter = set.iterator; | 67 Iterator iter = set.iterator; |
73 iter.moveNext(); | 68 iter.moveNext(); |
74 set.add(1); // Updating existing key isn't a modification. | 69 set.add(1); // Updating existing key isn't a modification. |
75 iter.moveNext(); | 70 iter.moveNext(); |
76 set.add(2); | 71 set.add(2); |
77 Expect.throws(iter.moveNext, (e) => e is Error); | 72 Expect.throws(iter.moveNext, (e) => e is Error); |
78 } | 73 } |
79 | 74 |
80 { | 75 { // Test adding after last element. |
81 // Test adding after last element. | |
82 Iterator iter = set.iterator; | 76 Iterator iter = set.iterator; |
83 Expect.equals(3, set.length); | 77 Expect.equals(3, set.length); |
84 iter.moveNext(); | 78 iter.moveNext(); |
85 iter.moveNext(); | 79 iter.moveNext(); |
86 iter.moveNext(); | 80 iter.moveNext(); |
87 set.add(3); | 81 set.add(3); |
88 Expect.throws(iter.moveNext, (e) => e is Error); | 82 Expect.throws(iter.moveNext, (e) => e is Error); |
89 } | 83 } |
90 | 84 |
91 { | 85 { // Test removing during iteration. |
92 // Test removing during iteration. | |
93 Iterator iter = set.iterator; | 86 Iterator iter = set.iterator; |
94 iter.moveNext(); | 87 iter.moveNext(); |
95 set.remove(1000); // Not a modification if it's not there. | 88 set.remove(1000); // Not a modification if it's not there. |
96 iter.moveNext(); | 89 iter.moveNext(); |
97 int n = iter.current; | 90 int n = iter.current; |
98 set.remove(n); | 91 set.remove(n); |
99 // Removing doesn't change current. | 92 // Removing doesn't change current. |
100 Expect.equals(n, iter.current); | 93 Expect.equals(n, iter.current); |
101 Expect.throws(iter.moveNext, (e) => e is Error); | 94 Expect.throws(iter.moveNext, (e) => e is Error); |
102 } | 95 } |
103 | 96 |
104 { | 97 { // Test removing after last element. |
105 // Test removing after last element. | |
106 Iterator iter = set.iterator; | 98 Iterator iter = set.iterator; |
107 Expect.equals(3, set.length); | 99 Expect.equals(3, set.length); |
108 iter.moveNext(); | 100 iter.moveNext(); |
109 iter.moveNext(); | 101 iter.moveNext(); |
110 iter.moveNext(); | 102 iter.moveNext(); |
111 int n = iter.current; | 103 int n = iter.current; |
112 set.remove(n); | 104 set.remove(n); |
113 // Removing doesn't change current. | 105 // Removing doesn't change current. |
114 Expect.equals(n, iter.current); | 106 Expect.equals(n, iter.current); |
115 Expect.throws(iter.moveNext, (e) => e is Error); | 107 Expect.throws(iter.moveNext, (e) => e is Error); |
116 } | 108 } |
117 | 109 |
118 { | 110 { // Test that updating value doesn't cause error. |
119 // Test that updating value doesn't cause error. | |
120 Iterator iter = set.iterator; | 111 Iterator iter = set.iterator; |
121 Expect.equals(2, set.length); | 112 Expect.equals(2, set.length); |
122 iter.moveNext(); | 113 iter.moveNext(); |
123 int n = iter.current; | 114 int n = iter.current; |
124 set.add(n); | 115 set.add(n); |
125 iter.moveNext(); | 116 iter.moveNext(); |
126 Expect.isTrue(set.contains(iter.current)); | 117 Expect.isTrue(set.contains(iter.current)); |
127 } | 118 } |
128 | 119 |
129 { | 120 { // Check adding many existing values isn't considered modification. |
130 // Check adding many existing values isn't considered modification. | |
131 Set set2 = newSet(); | 121 Set set2 = newSet(); |
132 for (var value in set) { | 122 for (var value in set) { |
133 set2.add(value); | 123 set2.add(value); |
134 } | 124 } |
135 Iterator iter = set.iterator; | 125 Iterator iter = set.iterator; |
136 set.addAll(set2); | 126 set.addAll(set2); |
137 // Shouldn't throw. | 127 // Shouldn't throw. |
138 iter.moveNext(); | 128 iter.moveNext(); |
139 } | 129 } |
140 } | 130 } |
141 | 131 |
142 { | 132 { // Check that updating existing elements is not a modification. |
143 // Check that updating existing elements is not a modification. | 133 // This must be the case even if the underlying data structure is |
144 // This must be the case even if the underlying data structure is | 134 // nearly full. |
145 // nearly full. | 135 for (int i = 1; i < 128; i++) { |
146 for (int i = 1; i < 128; i++) { | 136 // Create maps of different sizes, some of which should be |
147 // Create maps of different sizes, some of which should be | 137 // at a limit of the underlying data structure. |
148 // at a limit of the underlying data structure. | 138 Set set = newSetFrom(gen(0, i)); |
149 Set set = newSetFrom(gen(0, i)); | 139 Iterator iter = set.iterator; |
150 Iterator iter = set.iterator; | 140 for (int j = 0; j < i; j++) { |
151 for (int j = 0; j < i; j++) { | 141 set.add(j); |
152 set.add(j); | 142 } |
153 } | 143 iter.moveNext(); // Should not throw. |
154 iter.moveNext(); // Should not throw. | |
155 | 144 |
156 for (int j = 1; j < i; j++) { | 145 for (int j = 1; j < i; j++) { |
157 set.remove(j); | 146 set.remove(j); |
158 } | 147 } |
159 iter = set.iterator; | 148 iter = set.iterator; |
160 set.add(0); | 149 set.add(0); |
161 iter.moveNext(); // Should not throw. | 150 iter.moveNext(); // Should not throw. |
162 } | 151 } |
163 } | 152 } |
164 | 153 |
165 { | 154 { // Check that null can be in the set. |
166 // Check that null can be in the set. | |
167 Set set = newSet(); | 155 Set set = newSet(); |
168 set.add(null); | 156 set.add(null); |
169 Expect.equals(1, set.length); | 157 Expect.equals(1, set.length); |
170 Expect.isTrue(set.contains(null)); | 158 Expect.isTrue(set.contains(null)); |
171 Expect.isNull(set.first); | 159 Expect.isNull(set.first); |
172 Expect.isNull(set.last); | 160 Expect.isNull(set.last); |
173 set.add(null); | 161 set.add(null); |
174 Expect.equals(1, set.length); | 162 Expect.equals(1, set.length); |
175 Expect.isTrue(set.contains(null)); | 163 Expect.isTrue(set.contains(null)); |
176 set.remove(null); | 164 set.remove(null); |
(...skipping 22 matching lines...) Expand all Loading... |
199 Expect.equals(128, set.length); | 187 Expect.equals(128, set.length); |
200 Expect.isTrue(set.contains(null)); | 188 Expect.isTrue(set.contains(null)); |
201 set.add(null); | 189 set.add(null); |
202 Expect.equals(128, set.length); | 190 Expect.equals(128, set.length); |
203 Expect.isTrue(set.contains(null)); | 191 Expect.isTrue(set.contains(null)); |
204 set.remove(null); | 192 set.remove(null); |
205 Expect.equals(127, set.length); | 193 Expect.equals(127, set.length); |
206 Expect.isFalse(set.contains(null)); | 194 Expect.isFalse(set.contains(null)); |
207 } | 195 } |
208 | 196 |
209 { | 197 { // Check that addAll and clear works. |
210 // Check that addAll and clear works. | |
211 Set set = newSet(); | 198 Set set = newSet(); |
212 set.addAll([]); | 199 set.addAll([]); |
213 Expect.isTrue(set.isEmpty); | 200 Expect.isTrue(set.isEmpty); |
214 set.addAll([1, 3, 2]); | 201 set.addAll([1, 3, 2]); |
215 Expect.equals(3, set.length); | 202 Expect.equals(3, set.length); |
216 Expect.isTrue(set.contains(1)); | 203 Expect.isTrue(set.contains(1)); |
217 Expect.isTrue(set.contains(3)); | 204 Expect.isTrue(set.contains(3)); |
218 Expect.isTrue(set.contains(2)); | 205 Expect.isTrue(set.contains(2)); |
219 Expect.isFalse(set.contains(4)); | 206 Expect.isFalse(set.contains(4)); |
220 set.clear(); | 207 set.clear(); |
221 Expect.isTrue(set.isEmpty); | 208 Expect.isTrue(set.isEmpty); |
222 } | 209 } |
223 | 210 |
224 { | 211 { // Check that removeWhere and retainWhere work. |
225 // Check that removeWhere and retainWhere work. | |
226 Set set = newSetFrom([1, 2, 3]); | 212 Set set = newSetFrom([1, 2, 3]); |
227 set.removeWhere((each) => each == 2); | 213 set.removeWhere((each) => each == 2); |
228 Expect.equals(2, set.length); | 214 Expect.equals(2, set.length); |
229 Expect.isTrue(set.contains(1)); | 215 Expect.isTrue(set.contains(1)); |
230 Expect.isFalse(set.contains(2)); | 216 Expect.isFalse(set.contains(2)); |
231 Expect.isTrue(set.contains(3)); | 217 Expect.isTrue(set.contains(3)); |
232 set.retainWhere((each) => each == 3); | 218 set.retainWhere((each) => each == 3); |
233 Expect.equals(1, set.length); | 219 Expect.equals(1, set.length); |
234 Expect.isFalse(set.contains(1)); | 220 Expect.isFalse(set.contains(1)); |
235 Expect.isFalse(set.contains(2)); | 221 Expect.isFalse(set.contains(2)); |
236 Expect.isTrue(set.contains(3)); | 222 Expect.isTrue(set.contains(3)); |
237 } | 223 } |
238 | 224 |
239 { | 225 { // Test lookup |
240 // Test lookup | |
241 Set set = newSet(); | 226 Set set = newSet(); |
242 var m1a = new Mutable(1); | 227 var m1a = new Mutable(1); |
243 var m1b = new Mutable(1); | 228 var m1b = new Mutable(1); |
244 var m2a = new Mutable(2); | 229 var m2a = new Mutable(2); |
245 var m2b = new Mutable(2); | 230 var m2b = new Mutable(2); |
246 Expect.isNull(set.lookup(m1a)); | 231 Expect.isNull(set.lookup(m1a)); |
247 Expect.isNull(set.lookup(m1b)); | 232 Expect.isNull(set.lookup(m1b)); |
248 set.add(m1a); | 233 set.add(m1a); |
249 Expect.identical(m1a, set.lookup(m1a)); | 234 Expect.identical(m1a, set.lookup(m1a)); |
250 Expect.identical(m1a, set.lookup(m1b)); | 235 Expect.identical(m1a, set.lookup(m1b)); |
251 | 236 |
252 Expect.isNull(set.lookup(m2a)); | 237 Expect.isNull(set.lookup(m2a)); |
253 Expect.isNull(set.lookup(m2b)); | 238 Expect.isNull(set.lookup(m2b)); |
254 set.add(m2a); | 239 set.add(m2a); |
255 Expect.identical(m2a, set.lookup(m2a)); | 240 Expect.identical(m2a, set.lookup(m2a)); |
256 Expect.identical(m2a, set.lookup(m2b)); | 241 Expect.identical(m2a, set.lookup(m2b)); |
257 | 242 |
258 set.add(m2b); // Adding doesn't change element. | 243 set.add(m2b); // Adding doesn't change element. |
259 Expect.identical(m2a, set.lookup(m2a)); | 244 Expect.identical(m2a, set.lookup(m2a)); |
260 Expect.identical(m2a, set.lookup(m2b)); | 245 Expect.identical(m2a, set.lookup(m2b)); |
261 | 246 |
262 set.remove(m1a); | 247 set.remove(m1a); |
263 set.add(m1b); | 248 set.add(m1b); |
264 Expect.identical(m1b, set.lookup(m1a)); | 249 Expect.identical(m1b, set.lookup(m1a)); |
265 Expect.identical(m1b, set.lookup(m1b)); | 250 Expect.identical(m1b, set.lookup(m1b)); |
266 | 251 |
267 set.add(1); | 252 set.add(1); |
268 Expect.identical(1, set.lookup(1.0)); | 253 Expect.identical(1, set.lookup(1.0)); |
269 set.add(-0.0); | 254 set.add(-0.0); |
270 Expect.identical(-0.0, set.lookup(0.0)); | 255 Expect.identical(-0.0, set.lookup(0.0)); |
271 } | 256 } |
272 | 257 |
273 { | 258 { // Test special hash codes |
274 // Test special hash codes | |
275 Set set = newSet(); | 259 Set set = newSet(); |
276 List keys = []; | 260 List keys = []; |
277 // Powers of two | 261 // Powers of two |
278 for (int i = 65; i >= 2; --i) { | 262 for (int i = 65; i >= 2; --i) { |
279 keys.add(new Mutable(math.pow(2, i))); | 263 keys.add(new Mutable(math.pow(2, i))); |
280 } | 264 } |
281 for (var key in keys) { | 265 for (var key in keys) { |
282 Expect.isTrue(set.add(key)); | 266 Expect.isTrue(set.add(key)); |
283 } | 267 } |
284 for (var key in keys) { | 268 for (var key in keys) { |
285 Expect.isTrue(set.contains(key)); | 269 Expect.isTrue(set.contains(key)); |
286 } | 270 } |
287 } | 271 } |
288 } | 272 } |
289 | 273 |
| 274 |
290 void testIdentitySet(Set create()) { | 275 void testIdentitySet(Set create()) { |
291 Set set = create(); | 276 Set set = create(); |
292 set.add(1); | 277 set.add(1); |
293 set.add(2); | 278 set.add(2); |
294 set.add(1); // Integers are identical if equal. | 279 set.add(1); // Integers are identical if equal. |
295 Expect.equals(2, set.length); | 280 Expect.equals(2, set.length); |
296 var complex = 4; | 281 var complex = 4; |
297 complex = set.length == 2 ? complex ~/ 4 : 87; // Avoid compile-time constant. | 282 complex = set.length == 2 ? complex ~/ 4 : 87; // Avoid compile-time constant
. |
298 Expect.isTrue(set.contains(complex)); // 1 is in set, even if computed. | 283 Expect.isTrue(set.contains(complex)); // 1 is in set, even if computed. |
299 set.clear(); | 284 set.clear(); |
300 | 285 |
301 // All compile time constants are identical to themselves. | 286 // All compile time constants are identical to themselves. |
302 var constants = [ | 287 var constants = [double.INFINITY, |
303 double.INFINITY, | |
304 double.NAN, -0.0, //# 01: ok | 288 double.NAN, -0.0, //# 01: ok |
305 0.0, 42, "", null, false, true, #bif, testIdentitySet | 289 0.0, 42, "", null, false, true, #bif, testIdentitySet]; |
306 ]; | |
307 set.addAll(constants); | 290 set.addAll(constants); |
308 Expect.equals(constants.length, set.length); | 291 Expect.equals(constants.length, set.length); |
309 for (var c in constants) { | 292 for (var c in constants) { |
310 Expect.isTrue(set.contains(c), "constant: $c"); | 293 Expect.isTrue(set.contains(c), "constant: $c"); |
311 } | 294 } |
312 Expect.isTrue(set.containsAll(constants), "constants: $set"); | 295 Expect.isTrue(set.containsAll(constants), "constants: $set"); |
313 set.clear(); | 296 set.clear(); |
314 | 297 |
315 var m1 = new Mutable(1); | 298 var m1 = new Mutable(1); |
316 var m2 = new Mutable(2); | 299 var m2 = new Mutable(2); |
317 var m3 = new Mutable(3); | 300 var m3 = new Mutable(3); |
318 var m4 = new Mutable(2); // Equal to m2, but not identical. | 301 var m4 = new Mutable(2); // Equal to m2, but not identical. |
319 set.addAll([m1, m2, m3, m4]); | 302 set.addAll([m1, m2, m3, m4]); |
320 Expect.equals(4, set.length); | 303 Expect.equals(4, set.length); |
321 Expect.equals(3, m3.hashCode); | 304 Expect.equals(3, m3.hashCode); |
322 m3.id = 1; | 305 m3.id = 1; |
323 Expect.equals(1, m3.hashCode); | 306 Expect.equals(1, m3.hashCode); |
324 // Changing hashCode doesn't affect lookup. | 307 // Changing hashCode doesn't affect lookup. |
325 Expect.isTrue(set.contains(m3)); | 308 Expect.isTrue(set.contains(m3)); |
326 Expect.isTrue(set.contains(m1)); | 309 Expect.isTrue(set.contains(m1)); |
327 set.remove(m3); | 310 set.remove(m3); |
328 Expect.isFalse(set.contains(m3)); | 311 Expect.isFalse(set.contains(m3)); |
329 Expect.isTrue(set.contains(m1)); | 312 Expect.isTrue(set.contains(m1)); |
330 | 313 |
331 Expect.identical(m1, set.lookup(m1)); | 314 Expect.identical(m1, set.lookup(m1)); |
332 Expect.identical(null, set.lookup(m3)); | 315 Expect.identical(null, set.lookup(m3)); |
333 } | 316 } |
334 | 317 |
| 318 |
335 void main() { | 319 void main() { |
336 testSet(() => new Set(), (m) => new Set.from(m)); | 320 testSet(() => new Set(), (m) => new Set.from(m)); |
337 testSet(() => new HashSet(), (m) => new HashSet.from(m)); | 321 testSet(() => new HashSet(), (m) => new HashSet.from(m)); |
338 testSet(() => new LinkedHashSet(), (m) => new LinkedHashSet.from(m)); | 322 testSet(() => new LinkedHashSet(), (m) => new LinkedHashSet.from(m)); |
339 testIdentitySet(() => new Set.identity()); | 323 testIdentitySet(() => new Set.identity()); |
340 testIdentitySet(() => new HashSet.identity()); | 324 testIdentitySet(() => new HashSet.identity()); |
341 testIdentitySet(() => new LinkedHashSet.identity()); | 325 testIdentitySet(() => new LinkedHashSet.identity()); |
342 testIdentitySet(() => new HashSet( | 326 testIdentitySet(() => new HashSet(equals: (x, y) => identical(x, y), |
343 equals: (x, y) => identical(x, y), hashCode: (x) => identityHashCode(x))); | 327 hashCode: (x) => identityHashCode(x))); |
344 testIdentitySet(() => new LinkedHashSet( | 328 testIdentitySet( |
345 equals: (x, y) => identical(x, y), hashCode: (x) => identityHashCode(x))); | 329 () => new LinkedHashSet(equals: (x, y) => identical(x, y), |
| 330 hashCode: (x) => identityHashCode(x))); |
346 } | 331 } |
347 | 332 |
| 333 |
348 class BadHashCode { | 334 class BadHashCode { |
349 static int idCounter = 0; | 335 static int idCounter = 0; |
350 final int id; | 336 final int id; |
351 BadHashCode() : id = idCounter++; | 337 BadHashCode() : id = idCounter++; |
352 int get hashCode => 42; | 338 int get hashCode => 42; |
353 // operator == is identity. | 339 // operator == is identity. |
354 // Can't make a bad compareTo that isn't invalid. | 340 // Can't make a bad compareTo that isn't invalid. |
355 int compareTo(BadHashCode other) => id - other.id; | 341 int compareTo(BadHashCode other) => id - other.id; |
356 } | 342 } |
357 | 343 |
358 class Mutable { | 344 class Mutable { |
359 int id; | 345 int id; |
360 Mutable(this.id); | 346 Mutable(this.id); |
361 int get hashCode => id; | 347 int get hashCode => id; |
362 bool operator ==(other) => other is Mutable && id == other.id; | 348 bool operator==(other) => other is Mutable && id == other.id; |
363 } | 349 } |
OLD | NEW |