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