| 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 library map_test; | 5 library map_test; |
| 6 import 'dart:collection'; | 6 import 'dart:collection'; |
| 7 | 7 |
| 8 // Test that length/isEmpty opertions are constant time on | 8 // Test that length/isEmpty opertions are constant time on |
| 9 // maps, strings and collections. | 9 // maps, strings and collections. |
| 10 | 10 |
| (...skipping 23 matching lines...) Expand all Loading... |
| 34 } | 34 } |
| 35 | 35 |
| 36 void testCollection(Collection collection, n) { | 36 void testCollection(Collection collection, n) { |
| 37 for (int i = 0; i < n; i++) { | 37 for (int i = 0; i < n; i++) { |
| 38 collection.add(i); | 38 collection.add(i); |
| 39 } | 39 } |
| 40 testLength(collection, n); | 40 testLength(collection, n); |
| 41 } | 41 } |
| 42 | 42 |
| 43 void testList(List list, n) { | 43 void testList(List list, n) { |
| 44 // Works even if list is fixed-length. |
| 44 for (int i = 0; i < n; i++) { | 45 for (int i = 0; i < n; i++) { |
| 45 list[i] = i; | 46 list[i] = i; |
| 46 } | 47 } |
| 47 testLength(list, n); | 48 testLength(list, n); |
| 48 } | 49 } |
| 49 | 50 |
| 50 | 51 |
| 51 void testLength(var lengthable, int size) { | 52 void testLength(var lengthable, int size) { |
| 52 print(lengthable.runtimeType); // Show what hangs the test. | 53 print(lengthable.runtimeType); // Show what hangs the test. |
| 53 int length = 0; | 54 int length = 0; |
| 54 // If length or isEmpty is not a constant-time (or very fast) operation, | 55 // If length or isEmpty is not a constant-time (or very fast) operation, |
| 55 // this will timeout. | 56 // this will timeout. |
| 56 for (int i = 0; i < 100000; i++) { | 57 for (int i = 0; i < 100000; i++) { |
| 57 if (!lengthable.isEmpty) length += lengthable.length; | 58 if (!lengthable.isEmpty) length += lengthable.length; |
| 58 } | 59 } |
| 59 if (length != size * 100000) throw "Bad length: $length / size: $size"; | 60 if (length != size * 100000) throw "Bad length: $length / size: $size"; |
| 60 } | 61 } |
| 61 | 62 |
| 62 | 63 |
| 63 main() { | 64 main() { |
| 64 const int N = 100000; | 65 const int N = 100000; |
| 65 testMap(new HashMap(), N); | 66 testMap(new HashMap(), N); |
| 66 testMap(new LinkedHashMap(), N); | 67 testMap(new LinkedHashMap(), N); |
| 67 testMap(new SplayTreeMap(), N); | 68 testMap(new SplayTreeMap(), N); |
| 68 testCollection(new HashSet(), N); | 69 testCollection(new HashSet(), N); |
| 69 testCollection(new LinkedHashSet(), N); | 70 testCollection(new LinkedHashSet(), N); |
| 70 testCollection(new ListQueue(), N); | 71 testCollection(new ListQueue(), N); |
| 72 testCollection(new DoubleLinkedQueue(), N); |
| 71 testList(new List()..length = N, N); | 73 testList(new List()..length = N, N); |
| 72 testList(new List(N), N); | 74 testList(new List(N), N); |
| 73 testString(N); | 75 testString(N); |
| 74 // DoubleLinkedQueue has linear length, but fast isEmpty. | |
| 75 } | 76 } |
| OLD | NEW |