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 // Patch file for dart:collection classes. | |
6 import 'dart:_foreign_helper' show JS; | |
7 | |
8 patch class HashMap<K, V> { | |
9 // BUG(9368): We're currently unable to pass the type arguments to | |
10 // the construction of the JSMap instance. | |
11 patch factory HashMap() => new JSMap(); | |
12 } | |
13 | |
14 class JSMap<K, V> implements HashMap<K, V> { | |
15 int _length = 0; | |
16 var _strings, _nums, _rest; | |
ahe
2013/03/22 16:18:31
Each of these should be on their own line, and eac
| |
17 List _keys; | |
18 | |
19 int get length => _length; | |
20 bool get isEmpty => _length == 0; | |
21 | |
22 Iterable<K> get keys { | |
23 return new JSMapKeyIterable<K>(this); | |
24 } | |
25 | |
26 Iterable<V> get values { | |
27 return keys.map((each) => this[each]); | |
28 } | |
29 | |
30 bool containsKey(K key) { | |
31 if (key is String && key != '__proto__') { | |
32 var strings = _strings; | |
ahe
2013/03/22 16:18:31
Would this work:
var strings = JS('JavaScriptInde
| |
33 if (strings == null) return false; | |
34 var probe = JS('var', '#[#]', strings, key); | |
35 return JS('bool', '# != null', probe); | |
ahe
2013/03/22 16:18:31
Why not simply:
return probe != null;
| |
36 } else if (key is num) { | |
37 var nums = _nums; | |
38 if (nums == null) return false; | |
39 var probe = JS('var', '#[#]', nums, key); | |
40 return JS('bool', '# != null', probe); | |
41 } else { | |
42 var rest = _rest; | |
43 if (rest == null) return false; | |
44 var hash = key.hashCode; | |
45 var bucket = JS('var', '#[#]', rest, hash); | |
ahe
2013/03/22 16:18:31
Do you know if open addressing would be better in
| |
46 if (bucket != null) { | |
47 int bucketLength = JS('int', '#.length', bucket); | |
ahe
2013/03/22 16:18:31
Could you tell compiler that bucket is a List and
| |
48 for (int i = 0; i < bucketLength; i += 2) { | |
49 if (JS('var', '#[#]', bucket, i) == key) { | |
50 return true; | |
51 } | |
52 } | |
53 } | |
54 return false; | |
55 } | |
56 } | |
57 | |
58 bool containsValue(V value) { | |
59 return _computeKeys().any((each) => this[each] == value); | |
ahe
2013/03/22 16:18:31
This looks slow. Wouldn't this always be faster:
| |
60 } | |
61 | |
62 V operator[](K key) { | |
63 if (key is String && key != '__proto__') { | |
64 var strings = _strings; | |
65 if (strings == null) return null; | |
66 var probe = JS('var', '#[#]', strings, key); | |
67 return JS('bool', '# === #', probe, strings) ? null : probe; | |
ahe
2013/03/22 16:18:31
You're using _strings as a sentinel object? Comme
| |
68 } else if (key is num) { | |
69 var nums = _nums; | |
70 if (nums == null) return null; | |
71 var probe = JS('var', '#[#]', nums, key); | |
72 return JS('bool', '# === #', probe, nums) ? null : probe; | |
73 } else { | |
74 var rest = _rest; | |
75 if (rest == null) return null; | |
76 var hash = JS('num', 'Number(#)', key.hashCode); | |
ahe
2013/03/22 16:18:31
Shouldn't you throw some kind of exception if hash
| |
77 var bucket = JS('var', '#[#]', rest, hash); | |
78 if (bucket != null) { | |
79 int bucketLength = JS('int', '#.length', bucket); | |
80 for (int i = 0; i < bucketLength; i += 2) { | |
81 if (JS('var', '#[#]', bucket, i) == key) { | |
82 return JS('var', '#[# + 1]', bucket, i); | |
83 } | |
84 } | |
85 } | |
86 return null; | |
87 } | |
88 } | |
89 | |
90 void operator[]=(K key, V value) { | |
91 if (key is String && key != '__proto__') { | |
92 var strings = _strings; | |
93 if (strings == null) { | |
94 _strings = strings = _newHashTable(); | |
95 _length++; | |
96 _keys = null; | |
ahe
2013/03/22 16:18:31
This might be more readable:
addedNewKey = true;
| |
97 } else if (JS('bool', '#[#] == null', strings, key)) { | |
98 _length++; | |
99 _keys = null; | |
100 } | |
101 if (value == null) value = strings; | |
102 JS('void', '#[#] = #', strings, key, value); | |
103 } else if (key is num) { | |
104 var nums = _nums; | |
105 if (nums == null) { | |
106 _nums = nums = _newHashTable(); | |
107 _length++; | |
108 _keys = null; | |
109 } else if (JS('bool', '#[#] == null', nums, key)) { | |
110 _length++; | |
111 _keys = null; | |
112 } | |
113 if (value == null) value = nums; | |
114 JS('void', '#[#] = #', nums, key, value); | |
115 } else { | |
116 var rest = _rest; | |
117 var hash = JS('num', 'Number(#)', key.hashCode); | |
ahe
2013/03/22 16:18:31
Exception?
| |
118 var bucket; | |
119 if (rest == null) { | |
120 _rest = rest = _newHashTable(); | |
121 } else { | |
122 bucket = JS('var', '#[#]', rest, hash); | |
123 } | |
124 if (bucket == null) { | |
125 JS('void', '#[#] = [#, #]', rest, hash, key, value); | |
126 _length++; | |
127 _keys = null; | |
128 } else { | |
129 int bucketLength = JS('int', '#.length', bucket); | |
130 for (int i = 0; i < bucketLength; i += 2) { | |
131 if (JS('var', '#[#]', bucket, i) == key) { | |
132 JS('void', '#[# + 1] = #', bucket, i, value); | |
133 return; | |
134 } | |
135 } | |
136 JS('void', '#.push(#, #)', bucket, key, value); | |
137 _length++; | |
138 _keys = null; | |
139 } | |
140 } | |
141 } | |
142 | |
143 V remove(K key) { | |
144 if (key is String && key != '__proto__') { | |
145 var strings = _strings; | |
146 if (strings == null) return null; | |
147 var probe = JS('var', '#[#]', strings, key); | |
148 if (probe == null) return null; | |
149 JS('void', 'delete #[#]', strings, key); | |
150 _length--; | |
151 _keys = null; | |
152 return JS('bool', '# === #', probe, strings) ? null : probe; | |
153 } else if (key is num) { | |
154 var nums = _nums; | |
155 if (nums == null) return null; | |
156 var probe = JS('var', '#[#]', nums, key); | |
157 if (probe == null) return null; | |
158 JS('void', 'delete #[#]', nums, key); | |
159 _length--; | |
160 _keys = null; | |
161 return JS('bool', '# === #', probe, nums) ? null : probe; | |
162 } else { | |
163 var rest = _rest; | |
164 if (rest == null) return null; | |
165 var hash = JS('num', 'Number(#)', key.hashCode); | |
166 var bucket = JS('var', '#[#]', rest, hash); | |
167 if (bucket == null) return null; | |
168 int bucketLength = JS('int', '#.length', bucket); | |
169 for (int i = 0; i < bucketLength; i += 2) { | |
170 if (JS('var', '#[#]', bucket, i) == key) { | |
171 var value = JS('var', '#[# + 1]', bucket, i); | |
172 int last = bucketLength - 2; | |
173 if (i != last) { | |
174 JS('void', '#[#] = #[#]', bucket, i, bucket, last); | |
175 JS('void', '#[# + 1] = #[# + 1]', bucket, i, bucket, last); | |
176 } | |
177 JS('void', '#.length = #', bucket, last); | |
178 _length--; | |
179 _keys = null; | |
180 return value; | |
181 } | |
182 } | |
183 return null; | |
184 } | |
185 } | |
186 | |
187 void clear() { | |
188 if (_length > 0) { | |
189 _strings = _nums = _rest = _keys = null; | |
190 _length = 0; | |
191 } | |
192 } | |
193 | |
194 void forEach(void f(K key, V value)) { | |
195 List keys = _computeKeys(); | |
196 for (int i = 0, length = keys.length; i < length; i++) { | |
197 var key = keys[i]; | |
198 f(key, this[key]); | |
199 if (!identical(keys, _keys)) { | |
200 throw new ConcurrentModificationError(this); | |
ahe
2013/03/22 16:18:31
This means there are situations where a concurrent
| |
201 } | |
202 } | |
203 } | |
204 | |
205 V putIfAbsent(K key, V ifAbsent()) { | |
206 if (containsKey(key)) return this[key]; | |
207 V value = ifAbsent(); | |
208 this[key] = value; | |
209 return value; | |
210 } | |
211 | |
212 void addAll(Map<K, V> other) { | |
213 other.forEach((K key, V value) { | |
214 this[key] = value; | |
215 }); | |
216 } | |
217 | |
218 String toString() => Maps.mapToString(this); | |
219 | |
220 List _computeKeys() { | |
221 if (_keys != null) return _keys; | |
222 | |
223 List result = new List(_length); | |
224 int index = 0; | |
225 var strings = _strings; | |
226 if (strings != null) { | |
227 var names = JS('var', 'Object.getOwnPropertyNames(#)', strings); | |
ahe
2013/03/22 16:18:31
There is a comment in the emitter about an Opera b
ahe
2013/03/22 16:18:31
If the type of the JS expression is '=List' can't
| |
228 int length = JS('int', '#.length', names); | |
229 for (int i = 0; i < length; i++) { | |
230 String key = JS('String', '#[#]', names, i); | |
231 result[index++] = key; | |
232 } | |
233 } | |
234 | |
235 var nums = _nums; | |
236 if (_nums != null) { | |
237 var names = JS('var', 'Object.getOwnPropertyNames(#)', nums); | |
ahe
2013/03/22 16:18:31
Use =List?
| |
238 int length = JS('int', '#.length', names); | |
239 for (int i = 0; i < length; i++) { | |
240 num key = JS('num', 'Number(#[#])', names, i); | |
ahe
2013/03/22 16:18:31
A comment explaining why Number is necessary would
| |
241 result[index++] = key; | |
242 } | |
243 } | |
244 | |
245 var rest = _rest; | |
246 if (rest != null) { | |
247 var names = JS('var', 'Object.getOwnPropertyNames(#)', rest); | |
ahe
2013/03/22 16:18:31
Use =List?
| |
248 int length = JS('int', '#.length', names); | |
249 for (int i = 0; i < length; i++) { | |
250 var key = JS('String', '#[#]', names, i); | |
251 var bucket = JS('var', '#[#]', rest, key); | |
252 int bucketLength = JS('int', '#.length', bucket); | |
253 for (int i = 0; i < bucketLength; i += 2) { | |
254 var key = JS('var', '#[#]', bucket, i); | |
255 result[index++] = key; | |
256 } | |
257 } | |
258 } | |
259 return _keys = result; | |
260 } | |
261 | |
262 _newHashTable() { | |
263 var table = JS('var', 'Object.create(null)'); | |
264 var temporaryKey = '<non-identifier-key>'; | |
265 JS('void', '#[#] = #', table, temporaryKey, table); | |
266 JS('void', 'delete #[#]', table, temporaryKey); | |
ahe
2013/03/22 16:18:31
Add a comment explaining the purpose of <non-ident
| |
267 return table; | |
268 } | |
269 } | |
270 | |
271 | |
272 class JSMapKeyIterable<E> extends Iterable<E> { | |
273 final JSMap _map; | |
274 JSMapKeyIterable(this._map); | |
275 | |
276 int get length => _map._length; | |
277 bool get isEmpty => _map._length == 0; | |
278 | |
279 Iterator<E> get iterator { | |
280 return new JSMapKeyIterator<E>(_map, _map._computeKeys()); | |
281 } | |
282 | |
283 void forEach(void f(E element)) { | |
284 List keys = _map._computeKeys(); | |
285 for (int i = 0, length = keys.length; i < length; i++) { | |
286 f(keys[i]); | |
287 if (!identical(keys, _map._keys)) { | |
288 throw new ConcurrentModificationError(_map); | |
289 } | |
290 } | |
291 } | |
292 } | |
293 | |
294 class JSMapKeyIterator<E> implements Iterator<E> { | |
295 final JSMap _map; | |
296 final List _keys; | |
297 int _offset = 0; | |
298 E _current; | |
299 | |
300 JSMapKeyIterator(this._map, this._keys); | |
301 | |
302 E get current => _current; | |
303 | |
304 bool moveNext() { | |
305 if (!identical(_keys, _map._keys)) { | |
306 throw new ConcurrentModificationError(_map); | |
307 } else if (_offset >= _keys.length) { | |
308 _current = null; | |
309 return false; | |
310 } else { | |
311 _current = _keys[_offset++]; | |
312 return true; | |
313 } | |
314 } | |
315 } | |
OLD | NEW |