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 |