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

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

Issue 2771453003: Format all tests. (Closed)
Patch Set: Format files Created 3 years, 8 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
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 // Tests of hash map behavior, with focus in iteration and concurrent 5 // Tests of hash map behavior, with focus in iteration and concurrent
6 // modification errors. 6 // modification errors.
7 7
8 library hash_map2_test; 8 library hash_map2_test;
9
9 import "package:expect/expect.dart"; 10 import "package:expect/expect.dart";
10 import 'dart:collection'; 11 import 'dart:collection';
11 12
12 testMap(Map newMap(), Map newMapFrom(Map map)) { 13 testMap(Map newMap(), Map newMapFrom(Map map)) {
13 Map gen(int from, int to) { 14 Map gen(int from, int to) {
14 Map map = new LinkedHashMap(); 15 Map map = new LinkedHashMap();
15 for (int i = from; i < to; i++) map[i] = i; 16 for (int i = from; i < to; i++) map[i] = i;
16 return map; 17 return map;
17 } 18 }
18 19
19 bool odd(int n) => (n & 1) == 1; 20 bool odd(int n) => (n & 1) == 1;
20 bool even(int n) => (n & 1) == 0; 21 bool even(int n) => (n & 1) == 0;
21 void addAll(Map toMap, Map fromMap) { 22 void addAll(Map toMap, Map fromMap) {
22 fromMap.forEach((k, v) { toMap[k] = v; }); 23 fromMap.forEach((k, v) {
24 toMap[k] = v;
25 });
23 } 26 }
24 27
25 { // Test growing to largish capacity. 28 {
29 // Test growing to largish capacity.
26 Map map = newMap(); 30 Map map = newMap();
27 31
28 for (int i = 0; i < 256; i++) { 32 for (int i = 0; i < 256; i++) {
29 map[i] = i; 33 map[i] = i;
30 } 34 }
31 addAll(map, gen(256, 512)); 35 addAll(map, gen(256, 512));
32 addAll(map, newMapFrom(gen(512, 1000))); 36 addAll(map, newMapFrom(gen(512, 1000)));
33 Expect.equals(1000, map.length); 37 Expect.equals(1000, map.length);
34 38
35 // Remove half. 39 // Remove half.
36 for (int i = 0; i < 1000; i += 2) map.remove(i); 40 for (int i = 0; i < 1000; i += 2) map.remove(i);
37 Expect.equals(500, map.length); 41 Expect.equals(500, map.length);
38 Expect.isFalse(map.keys.any(even)); 42 Expect.isFalse(map.keys.any(even));
39 Expect.isTrue(map.keys.every(odd)); 43 Expect.isTrue(map.keys.every(odd));
40 44
41 // Re-add all. 45 // Re-add all.
42 addAll(map, gen(0, 1000)); 46 addAll(map, gen(0, 1000));
43 Expect.equals(1000, map.length); 47 Expect.equals(1000, map.length);
44 } 48 }
45 49
46 { // Test having many deleted elements. 50 {
51 // Test having many deleted elements.
47 Map map = newMap(); 52 Map map = newMap();
48 map[0] = 0; 53 map[0] = 0;
49 for (int i = 0; i < 1000; i++) { 54 for (int i = 0; i < 1000; i++) {
50 map[i + 1] = i + 1; 55 map[i + 1] = i + 1;
51 map.remove(i); 56 map.remove(i);
52 Expect.equals(1, map.length); 57 Expect.equals(1, map.length);
53 } 58 }
54 } 59 }
55 60
56 { // Test having many elements with same hashCode 61 {
62 // Test having many elements with same hashCode
57 Map map = newMap(); 63 Map map = newMap();
58 for (int i = 0; i < 1000; i++) { 64 for (int i = 0; i < 1000; i++) {
59 map[new BadHashCode()] = 0; 65 map[new BadHashCode()] = 0;
60 } 66 }
61 Expect.equals(1000, map.length); 67 Expect.equals(1000, map.length);
62 } 68 }
63 69
64 { // Check concurrent modification 70 {
65 Map map = newMap()..[0] = 0..[1] = 1; 71 // Check concurrent modification
72 Map map = newMap()
73 ..[0] = 0
74 ..[1] = 1;
66 75
67 { // Test adding before a moveNext. 76 {
77 // Test adding before a moveNext.
68 Iterator iter = map.keys.iterator; 78 Iterator iter = map.keys.iterator;
69 iter.moveNext(); 79 iter.moveNext();
70 map[1] = 9; // Updating existing key isn't a modification. 80 map[1] = 9; // Updating existing key isn't a modification.
71 iter.moveNext(); 81 iter.moveNext();
72 map[2] = 2; 82 map[2] = 2;
73 Expect.throws(iter.moveNext, (e) => e is Error); 83 Expect.throws(iter.moveNext, (e) => e is Error);
74 } 84 }
75 85
76 { // Test adding after last element. 86 {
87 // Test adding after last element.
77 Iterator iter = map.keys.iterator; 88 Iterator iter = map.keys.iterator;
78 Expect.equals(3, map.length); 89 Expect.equals(3, map.length);
79 iter.moveNext(); 90 iter.moveNext();
80 iter.moveNext(); 91 iter.moveNext();
81 iter.moveNext(); 92 iter.moveNext();
82 map[3] = 3; 93 map[3] = 3;
83 Expect.throws(iter.moveNext, (e) => e is Error); 94 Expect.throws(iter.moveNext, (e) => e is Error);
84 } 95 }
85 96
86 { // Test removing during iteration. 97 {
98 // Test removing during iteration.
87 Iterator iter = map.keys.iterator; 99 Iterator iter = map.keys.iterator;
88 iter.moveNext(); 100 iter.moveNext();
89 map.remove(1000); // Not a modification if it's not there. 101 map.remove(1000); // Not a modification if it's not there.
90 iter.moveNext(); 102 iter.moveNext();
91 int n = iter.current; 103 int n = iter.current;
92 map.remove(n); 104 map.remove(n);
93 // Removing doesn't change current. 105 // Removing doesn't change current.
94 Expect.equals(n, iter.current); 106 Expect.equals(n, iter.current);
95 Expect.throws(iter.moveNext, (e) => e is Error); 107 Expect.throws(iter.moveNext, (e) => e is Error);
96 } 108 }
97 109
98 { // Test removing after last element. 110 {
111 // Test removing after last element.
99 Iterator iter = map.keys.iterator; 112 Iterator iter = map.keys.iterator;
100 Expect.equals(3, map.length); 113 Expect.equals(3, map.length);
101 iter.moveNext(); 114 iter.moveNext();
102 iter.moveNext(); 115 iter.moveNext();
103 iter.moveNext(); 116 iter.moveNext();
104 int n = iter.current; 117 int n = iter.current;
105 map.remove(n); 118 map.remove(n);
106 // Removing doesn't change current. 119 // Removing doesn't change current.
107 Expect.equals(n, iter.current); 120 Expect.equals(n, iter.current);
108 Expect.throws(iter.moveNext, (e) => e is Error); 121 Expect.throws(iter.moveNext, (e) => e is Error);
109 } 122 }
110 123
111 { // Test that updating value of existing key doesn't cause concurrent 124 {
112 // modification error. 125 // Test that updating value of existing key doesn't cause concurrent
126 // modification error.
113 Iterator iter = map.keys.iterator; 127 Iterator iter = map.keys.iterator;
114 Expect.equals(2, map.length); 128 Expect.equals(2, map.length);
115 iter.moveNext(); 129 iter.moveNext();
116 int n = iter.current; 130 int n = iter.current;
117 map[n] = n * 2; 131 map[n] = n * 2;
118 iter.moveNext(); 132 iter.moveNext();
119 Expect.equals(map[iter.current], iter.current); 133 Expect.equals(map[iter.current], iter.current);
120 } 134 }
121 135
122 { // Test that modification during putIfAbsent is not an error. 136 {
137 // Test that modification during putIfAbsent is not an error.
123 map.putIfAbsent(4, () { 138 map.putIfAbsent(4, () {
124 map[5] = 5; 139 map[5] = 5;
125 map[4] = -1; 140 map[4] = -1;
126 return 4; 141 return 4;
127 }); 142 });
128 Expect.equals(4, map[4]); 143 Expect.equals(4, map[4]);
129 Expect.equals(5, map[5]); 144 Expect.equals(5, map[5]);
130 } 145 }
131 146
132 { // Check adding many existing keys isn't considered modification. 147 {
148 // Check adding many existing keys isn't considered modification.
133 Map map2 = newMap(); 149 Map map2 = newMap();
134 for (var key in map.keys) { 150 for (var key in map.keys) {
135 map2[key] = map[key] + 1; 151 map2[key] = map[key] + 1;
136 } 152 }
137 Iterator iter = map.keys.iterator; 153 Iterator iter = map.keys.iterator;
138 addAll(map, map2); 154 addAll(map, map2);
139 // Shouldn't throw. 155 // Shouldn't throw.
140 iter.moveNext(); 156 iter.moveNext();
141 } 157 }
142 } 158 }
143 159
144 { // Regression test for bug in putIfAbsent where adding an element 160 {
145 // that make the table grow, can be lost. 161 // Regression test for bug in putIfAbsent where adding an element
162 // that make the table grow, can be lost.
146 Map map = newMap(); 163 Map map = newMap();
147 map.putIfAbsent("S", () => 0); 164 map.putIfAbsent("S", () => 0);
148 map.putIfAbsent("T", () => 0); 165 map.putIfAbsent("T", () => 0);
149 map.putIfAbsent("U", () => 0); 166 map.putIfAbsent("U", () => 0);
150 map.putIfAbsent("C", () => 0); 167 map.putIfAbsent("C", () => 0);
151 map.putIfAbsent("a", () => 0); 168 map.putIfAbsent("a", () => 0);
152 map.putIfAbsent("b", () => 0); 169 map.putIfAbsent("b", () => 0);
153 map.putIfAbsent("n", () => 0); 170 map.putIfAbsent("n", () => 0);
154 Expect.isTrue(map.containsKey("n")); 171 Expect.isTrue(map.containsKey("n"));
155 } 172 }
156 173
157 { // Check that putIfAbsent works just as well as put. 174 {
175 // Check that putIfAbsent works just as well as put.
158 Map map = newMap(); 176 Map map = newMap();
159 for (int i = 0; i < 128; i++) { 177 for (int i = 0; i < 128; i++) {
160 map.putIfAbsent(i, () => i); 178 map.putIfAbsent(i, () => i);
161 Expect.isTrue(map.containsKey(i)); 179 Expect.isTrue(map.containsKey(i));
162 map.putIfAbsent(i >> 1, () => -1); // Never triggers. 180 map.putIfAbsent(i >> 1, () => -1); // Never triggers.
163 } 181 }
164 for (int i = 0; i < 128; i++) { 182 for (int i = 0; i < 128; i++) {
165 Expect.equals(i, map[i]); 183 Expect.equals(i, map[i]);
166 } 184 }
167 } 185 }
168 186
169 { // Check that updating existing elements is not a modification. 187 {
170 // This must be the case even if the underlying data structure is 188 // Check that updating existing elements is not a modification.
171 // nearly full. 189 // This must be the case even if the underlying data structure is
172 for (int i = 1; i < 128; i++) { 190 // nearly full.
173 // Create maps of different sizes, some of which should be 191 for (int i = 1; i < 128; i++) {
174 // at a limit of the underlying data structure. 192 // Create maps of different sizes, some of which should be
175 Map map = newMapFrom(gen(0, i)); 193 // at a limit of the underlying data structure.
194 Map map = newMapFrom(gen(0, i));
176 195
177 // ForEach-iteration. 196 // ForEach-iteration.
178 map.forEach((key, v) { 197 map.forEach((key, v) {
179 Expect.equals(key, map[key]); 198 Expect.equals(key, map[key]);
180 map[key] = key + 1; 199 map[key] = key + 1;
181 map.remove(1000); // Removing something not there. 200 map.remove(1000); // Removing something not there.
182 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT")); 201 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT"));
183 // Doesn't cause ConcurrentModificationError. 202 // Doesn't cause ConcurrentModificationError.
184 }); 203 });
185 204
186 // for-in iteration. 205 // for-in iteration.
187 for (int key in map.keys) { 206 for (int key in map.keys) {
188 Expect.equals(key + 1, map[key]); 207 Expect.equals(key + 1, map[key]);
189 map[key] = map[key] + 1; 208 map[key] = map[key] + 1;
190 map.remove(1000); // Removing something not there. 209 map.remove(1000); // Removing something not there.
191 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT")); 210 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT"));
192 // Doesn't cause ConcurrentModificationError. 211 // Doesn't cause ConcurrentModificationError.
193 } 212 }
194 213
195 // Raw iterator. 214 // Raw iterator.
196 Iterator iter = map.keys.iterator; 215 Iterator iter = map.keys.iterator;
197 for (int key = 0; key < i; key++) { 216 for (int key = 0; key < i; key++) {
198 Expect.equals(key + 2, map[key]); 217 Expect.equals(key + 2, map[key]);
199 map[key] = key + 3; 218 map[key] = key + 3;
200 map.remove(1000); // Removing something not there. 219 map.remove(1000); // Removing something not there.
201 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT")); 220 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT"));
202 // Doesn't cause ConcurrentModificationError on the moveNext. 221 // Doesn't cause ConcurrentModificationError on the moveNext.
203 } 222 }
204 iter.moveNext(); // Should not throw. 223 iter.moveNext(); // Should not throw.
205 224
206 // Remove a lot of elements, which can cause a re-tabulation. 225 // Remove a lot of elements, which can cause a re-tabulation.
207 for (int key = 1; key < i; key++) { 226 for (int key = 1; key < i; key++) {
208 Expect.equals(key + 3, map[key]); 227 Expect.equals(key + 3, map[key]);
209 map.remove(key); 228 map.remove(key);
210 } 229 }
211 iter = map.keys.iterator; 230 iter = map.keys.iterator;
212 map[0] = 2; 231 map[0] = 2;
213 iter.moveNext(); // Should not throw. 232 iter.moveNext(); // Should not throw.
214 } 233 }
215 } 234 }
216 235
217 236 {
218 { // Check that null can be in the map. 237 // Check that null can be in the map.
219 Map map = newMap(); 238 Map map = newMap();
220 map[null] = 0; 239 map[null] = 0;
221 Expect.equals(1, map.length); 240 Expect.equals(1, map.length);
222 Expect.isTrue(map.containsKey(null)); 241 Expect.isTrue(map.containsKey(null));
223 Expect.isNull(map.keys.first); 242 Expect.isNull(map.keys.first);
224 Expect.isNull(map.keys.last); 243 Expect.isNull(map.keys.last);
225 map[null] = 1; 244 map[null] = 1;
226 Expect.equals(1, map.length); 245 Expect.equals(1, map.length);
227 Expect.isTrue(map.containsKey(null)); 246 Expect.isTrue(map.containsKey(null));
228 map.remove(null); 247 map.remove(null);
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after
274 Expect.isTrue(new LinkedHashMap<int, String>() is Map<int, String>); 293 Expect.isTrue(new LinkedHashMap<int, String>() is Map<int, String>);
275 Expect.isTrue(new HashMap<String, int>.from({}) is Map<String, int>); 294 Expect.isTrue(new HashMap<String, int>.from({}) is Map<String, int>);
276 Expect.isTrue(new LinkedHashMap<String, int>.from({}) is Map<String, int>); 295 Expect.isTrue(new LinkedHashMap<String, int>.from({}) is Map<String, int>);
277 Expect.isTrue(<String, int>{} is Map<String, int>); 296 Expect.isTrue(<String, int>{} is Map<String, int>);
278 Expect.isTrue(const <String, int>{} is Map<String, int>); 297 Expect.isTrue(const <String, int>{} is Map<String, int>);
279 298
280 testMap(() => new HashMap(), (m) => new HashMap.from(m)); 299 testMap(() => new HashMap(), (m) => new HashMap.from(m));
281 testMap(() => new LinkedHashMap(), (m) => new LinkedHashMap.from(m)); 300 testMap(() => new LinkedHashMap(), (m) => new LinkedHashMap.from(m));
282 } 301 }
283 302
284
285 class BadHashCode { 303 class BadHashCode {
286 static int idCounter = 0; 304 static int idCounter = 0;
287 final int id; 305 final int id;
288 BadHashCode() : id = idCounter++; 306 BadHashCode() : id = idCounter++;
289 int get hashCode => 42; 307 int get hashCode => 42;
290 } 308 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698