tests/corelib/hash_map2_test.dart - Issue 3004073002: Remove corelib/corelib_strong and migrate last two remaining tests.

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

Issue 3004073002: Remove corelib/corelib_strong and migrate last two remaining tests. (Closed)

Patch Set: Created 3 years, 3 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:

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 // Tests of hash map behavior, with focus in iteration and concurrent

6 // modification errors.

7

8 library hash_map2_test;

9

10 import "package:expect/expect.dart";

11 import 'dart:collection';

12

13 testMap(Map newMap(), Map newMapFrom(Map map)) {

14 Map gen(int from, int to) {

15 Map map = new LinkedHashMap();

16 for (int i = from; i < to; i++) map[i] = i;

17 return map;

18 }

19

20 bool odd(int n) => (n & 1) == 1;

21 bool even(int n) => (n & 1) == 0;

22 void addAll(Map toMap, Map fromMap) {

23 fromMap.forEach((k, v) {

24 toMap[k] = v;

25 });

26 }

27

28 {

29 // Test growing to largish capacity.

30 Map map = newMap();

31

32 for (int i = 0; i < 256; i++) {

33 map[i] = i;

34 }

35 addAll(map, gen(256, 512));

36 addAll(map, newMapFrom(gen(512, 1000)));

37 Expect.equals(1000, map.length);

38

39 // Remove half.

40 for (int i = 0; i < 1000; i += 2) map.remove(i);

41 Expect.equals(500, map.length);

42 Expect.isFalse(map.keys.any(even));

43 Expect.isTrue(map.keys.every(odd));

44

45 // Re-add all.

46 addAll(map, gen(0, 1000));

47 Expect.equals(1000, map.length);

48 }

49

50 {

51 // Test having many deleted elements.

52 Map map = newMap();

53 map[0] = 0;

54 for (int i = 0; i < 1000; i++) {

55 map[i + 1] = i + 1;

56 map.remove(i);

57 Expect.equals(1, map.length);

58 }

59 }

60

61 {

62 // Test having many elements with same hashCode

63 Map map = newMap();

64 for (int i = 0; i < 1000; i++) {

65 map[new BadHashCode()] = 0;

66 }

67 Expect.equals(1000, map.length);

68 }

69

70 {

71 // Check concurrent modification

72 Map map = newMap()

73 ..[0] = 0

74 ..[1] = 1;

75

76 {

77 // Test adding before a moveNext.

78 Iterator iter = map.keys.iterator;

79 iter.moveNext();

80 map[1] = 9; // Updating existing key isn't a modification.

81 iter.moveNext();

82 map[2] = 2;

83 Expect.throws(iter.moveNext, (e) => e is Error);

84 }

85

86 {

87 // Test adding after last element.

88 Iterator iter = map.keys.iterator;

89 Expect.equals(3, map.length);

90 iter.moveNext();

91 iter.moveNext();

92 iter.moveNext();

93 map[3] = 3;

94 Expect.throws(iter.moveNext, (e) => e is Error);

95 }

96

97 {

98 // Test removing during iteration.

99 Iterator iter = map.keys.iterator;

100 iter.moveNext();

101 map.remove(1000); // Not a modification if it's not there.

102 iter.moveNext();

103 int n = iter.current;

104 map.remove(n);

105 // Removing doesn't change current.

106 Expect.equals(n, iter.current);

107 Expect.throws(iter.moveNext, (e) => e is Error);

108 }

109

110 {

111 // Test removing after last element.

112 Iterator iter = map.keys.iterator;

113 Expect.equals(3, map.length);

114 iter.moveNext();

115 iter.moveNext();

116 iter.moveNext();

117 int n = iter.current;

118 map.remove(n);

119 // Removing doesn't change current.

120 Expect.equals(n, iter.current);

121 Expect.throws(iter.moveNext, (e) => e is Error);

122 }

123

124 {

125 // Test that updating value of existing key doesn't cause concurrent

126 // modification error.

127 Iterator iter = map.keys.iterator;

128 Expect.equals(2, map.length);

129 iter.moveNext();

130 int n = iter.current;

131 map[n] = n * 2;

132 iter.moveNext();

133 Expect.equals(map[iter.current], iter.current);

134 }

135

136 {

137 // Test that modification during putIfAbsent is not an error.

138 map.putIfAbsent(4, () {

139 map[5] = 5;

140 map[4] = -1;

141 return 4;

142 });

143 Expect.equals(4, map[4]);

144 Expect.equals(5, map[5]);

145 }

146

147 {

148 // Check adding many existing keys isn't considered modification.

149 Map map2 = newMap();

150 for (var key in map.keys) {

151 map2[key] = map[key] + 1;

152 }

153 Iterator iter = map.keys.iterator;

154 addAll(map, map2);

155 // Shouldn't throw.

156 iter.moveNext();

157 }

158 }

159

160 {

161 // Regression test for bug in putIfAbsent where adding an element

162 // that make the table grow, can be lost.

163 Map map = newMap();

164 map.putIfAbsent("S", () => 0);

165 map.putIfAbsent("T", () => 0);

166 map.putIfAbsent("U", () => 0);

167 map.putIfAbsent("C", () => 0);

168 map.putIfAbsent("a", () => 0);

169 map.putIfAbsent("b", () => 0);

170 map.putIfAbsent("n", () => 0);

171 Expect.isTrue(map.containsKey("n"));

172 }

173

174 {

175 // Check that putIfAbsent works just as well as put.

176 Map map = newMap();

177 for (int i = 0; i < 128; i++) {

178 map.putIfAbsent(i, () => i);

179 Expect.isTrue(map.containsKey(i));

180 map.putIfAbsent(i >> 1, () => -1); // Never triggers.

181 }

182 for (int i = 0; i < 128; i++) {

183 Expect.equals(i, map[i]);

184 }

185 }

186

187 {

188 // Check that updating existing elements is not a modification.

189 // This must be the case even if the underlying data structure is

190 // nearly full.

191 for (int i = 1; i < 128; i++) {

192 // Create maps of different sizes, some of which should be

193 // at a limit of the underlying data structure.

194 Map map = newMapFrom(gen(0, i));

195

196 // ForEach-iteration.

197 map.forEach((key, v) {

198 Expect.equals(key, map[key]);

199 map[key] = key + 1;

200 map.remove(1000); // Removing something not there.

201 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT"));

202 // Doesn't cause ConcurrentModificationError.

203 });

204

205 // for-in iteration.

206 for (int key in map.keys) {

207 Expect.equals(key + 1, map[key]);

208 map[key] = map[key] + 1;

209 map.remove(1000); // Removing something not there.

210 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT"));

211 // Doesn't cause ConcurrentModificationError.

212 }

213

214 // Raw iterator.

215 Iterator iter = map.keys.iterator;

216 for (int key = 0; key < i; key++) {

217 Expect.equals(key + 2, map[key]);

218 map[key] = key + 3;

219 map.remove(1000); // Removing something not there.

220 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT"));

221 // Doesn't cause ConcurrentModificationError on the moveNext.

222 }

223 iter.moveNext(); // Should not throw.

224

225 // Remove a lot of elements, which can cause a re-tabulation.

226 for (int key = 1; key < i; key++) {

227 Expect.equals(key + 3, map[key]);

228 map.remove(key);

229 }

230 iter = map.keys.iterator;

231 map[0] = 2;

232 iter.moveNext(); // Should not throw.

233 }

234 }

235

236 {

237 // Check that null can be in the map.

238 Map map = newMap();

239 map[null] = 0;

240 Expect.equals(1, map.length);

241 Expect.isTrue(map.containsKey(null));

242 Expect.isNull(map.keys.first);

243 Expect.isNull(map.keys.last);

244 map[null] = 1;

245 Expect.equals(1, map.length);

246 Expect.isTrue(map.containsKey(null));

247 map.remove(null);

248 Expect.isTrue(map.isEmpty);

249 Expect.isFalse(map.containsKey(null));

250

251 // Created using map.from.

252 map = newMapFrom(new Map()..[null] = 0);

253 Expect.equals(1, map.length);

254 Expect.isTrue(map.containsKey(null));

255 Expect.isNull(map.keys.first);

256 Expect.isNull(map.keys.last);

257 map[null] = 1;

258 Expect.equals(1, map.length);

259 Expect.isTrue(map.containsKey(null));

260 map.remove(null);

261 Expect.isTrue(map.isEmpty);

262 Expect.isFalse(map.containsKey(null));

263

264 Map fromMap = new Map();

265 fromMap[1] = 0;

266 fromMap[2] = 0;

267 fromMap[3] = 0;

268 fromMap[null] = 0;

269 fromMap[4] = 0;

270 fromMap[5] = 0;

271 fromMap[6] = 0;

272 Expect.equals(7, fromMap.length);

273

274 // map that grows with null in it.

275 map = newMapFrom(fromMap);

276 Expect.equals(7, map.length);

277 for (int i = 7; i < 128; i++) {

278 map[i] = 0;

279 }

280 Expect.equals(128, map.length);

281 Expect.isTrue(map.containsKey(null));

282 map[null] = 1;

283 Expect.equals(128, map.length);

284 Expect.isTrue(map.containsKey(null));

285 map.remove(null);

286 Expect.equals(127, map.length);

287 Expect.isFalse(map.containsKey(null));

288 }

289 }

290

291 void main() {

292 Expect.isTrue(new HashMap<int, String>() is Map<int, String>);

293 Expect.isTrue(new LinkedHashMap<int, String>() is Map<int, String>);

294 Expect.isTrue(new HashMap<String, int>.from({}) is Map<String, int>);

295 Expect.isTrue(new LinkedHashMap<String, int>.from({}) is Map<String, int>);

296 Expect.isTrue(<String, int>{} is Map<String, int>);

297 Expect.isTrue(const <String, int>{} is Map<String, int>);

298

299 testMap(() => new HashMap(), (m) => new HashMap.from(m));

300 testMap(() => new LinkedHashMap(), (m) => new LinkedHashMap.from(m));

301 }

302

303 class BadHashCode {

304 static int idCounter = 0;

305 final int id;

306 BadHashCode() : id = idCounter++;

307 int get hashCode => 42;

308 }

OLD	NEW

« no previous file with comments | « tests/corelib/growable_list_test.dart ('k') | tests/corelib/linked_hash_map_from_iterable_test.dart » ('j') | tests/corelib_2/corelib_2.status » ('J')