| 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 library map_test; | |
| 6 | |
| 7 import 'dart:collection'; | |
| 8 | |
| 9 // Test that length/isEmpty opertions are constant time on | |
| 10 // maps, strings and collections. | |
| 11 | |
| 12 void testString(int n) { | |
| 13 String s = "x"; | |
| 14 String string = ""; | |
| 15 int length = n; | |
| 16 while (true) { | |
| 17 if ((length & 1) == 1) { | |
| 18 string += s; | |
| 19 } | |
| 20 length >>= 1; | |
| 21 if (length == 0) break; | |
| 22 s += s; | |
| 23 } | |
| 24 testLength(string, n); | |
| 25 testLength(string.codeUnits, n); | |
| 26 } | |
| 27 | |
| 28 void testMap(Map map, int n) { | |
| 29 for (int i = 0; i < n; i++) { | |
| 30 map[i] = i; | |
| 31 } | |
| 32 testLength(map, n); | |
| 33 testLength(map.keys, n); | |
| 34 testLength(map.values, n); | |
| 35 } | |
| 36 | |
| 37 void testCollection(var collection, n) { | |
| 38 for (int i = 0; i < n; i++) { | |
| 39 collection.add(i); | |
| 40 } | |
| 41 testLength(collection, n); | |
| 42 } | |
| 43 | |
| 44 void testList(List list, n) { | |
| 45 // Works even if list is fixed-length. | |
| 46 for (int i = 0; i < n; i++) { | |
| 47 list[i] = i; | |
| 48 } | |
| 49 testLength(list, n); | |
| 50 } | |
| 51 | |
| 52 void testLength(var lengthable, int size) { | |
| 53 print(lengthable.runtimeType); // Show what hangs the test. | |
| 54 int length = 0; | |
| 55 // If length, isEmpty or isNotEmpty is not a constant-time (or very fast) | |
| 56 // operation, this will timeout. | |
| 57 for (int i = 0; i < 100000; i++) { | |
| 58 if (!lengthable.isEmpty) length += lengthable.length; | |
| 59 if (lengthable.isNotEmpty) length += lengthable.length; | |
| 60 } | |
| 61 if (length != size * 200000) throw "Bad length: $length / size: $size"; | |
| 62 } | |
| 63 | |
| 64 main() { | |
| 65 const int N = 100000; | |
| 66 testMap(new HashMap(), N); | |
| 67 testMap(new LinkedHashMap(), N); | |
| 68 testMap(new SplayTreeMap(), N); | |
| 69 testCollection(new HashSet(), N); | |
| 70 testCollection(new LinkedHashSet(), N); | |
| 71 testCollection(new ListQueue(), N); | |
| 72 testCollection(new DoubleLinkedQueue(), N); | |
| 73 testList(new List()..length = N, N); | |
| 74 testList(new List(N), N); | |
| 75 testString(N); | |
| 76 } | |
| OLD | NEW |