Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(352)

Side by Side Diff: tests/corelib/hash_set_test.dart

Issue 2770063002: Revert "Format all multitests" (Closed)
Patch Set: Created 3 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « tests/corelib/double_parse_test.dart ('k') | tests/corelib/int_modulo_arith_test.dart » ('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 (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
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 }
OLDNEW
« no previous file with comments | « tests/corelib/double_parse_test.dart ('k') | tests/corelib/int_modulo_arith_test.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698