| OLD | NEW |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, 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 /** | 5 /** |
| 6 * This class is the public interface of a set. A set is a collection | 6 * This class is the public interface of a set. A set is a collection |
| 7 * without duplicates. | 7 * without duplicates. |
| 8 */ | 8 */ |
| 9 abstract class Set<E> extends Collection<E> { | 9 abstract class Set<E> extends Collection<E> { |
| 10 factory Set() => new _HashSetImpl<E>(); | 10 factory Set() => new _HashSetImpl<E>(); |
| (...skipping 166 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 177 } | 177 } |
| 178 | 178 |
| 179 bool get isEmpty { | 179 bool get isEmpty { |
| 180 return _backingMap.isEmpty; | 180 return _backingMap.isEmpty; |
| 181 } | 181 } |
| 182 | 182 |
| 183 int get length { | 183 int get length { |
| 184 return _backingMap.length; | 184 return _backingMap.length; |
| 185 } | 185 } |
| 186 | 186 |
| 187 Iterator<E> iterator() { | 187 Iterator<E> get iterator => new _HashSetIterator<E>(this); |
| 188 return new _HashSetIterator<E>(this); | |
| 189 } | |
| 190 | 188 |
| 191 String toString() { | 189 String toString() { |
| 192 return Collections.collectionToString(this); | 190 return Collections.collectionToString(this); |
| 193 } | 191 } |
| 194 | 192 |
| 195 // The map backing this set. The associations in this map are all | 193 // The map backing this set. The associations in this map are all |
| 196 // of the form element -> element. If a value is not in the map, | 194 // of the form element -> element. If a value is not in the map, |
| 197 // then it is not in the set. | 195 // then it is not in the set. |
| 198 _HashMapImpl<E, E> _backingMap; | 196 _HashMapImpl<E, E> _backingMap; |
| 199 } | 197 } |
| 200 | 198 |
| 201 class _HashSetIterator<E> implements Iterator<E> { | 199 class _HashSetIterator<E> implements Iterator<E> { |
| 202 | 200 |
| 203 // TODO(4504458): Replace set_ with set. | 201 _HashSetIterator(_HashSetImpl<E> set) |
| 204 _HashSetIterator(_HashSetImpl<E> set_) | 202 : _keysIterator = set._backingMap._keys.iterator; |
| 205 : _nextValidIndex = -1, | 203 |
| 206 _entries = set_._backingMap._keys { | 204 E get current { |
| 207 _advance(); | 205 var result = _keysIterator.current; |
| 206 if (identical(result, _HashMapImpl._DELETED_KEY)) { |
| 207 // TODO(floitsch): improve the error reporting. |
| 208 throw new StateError("Concurrent modification."); |
| 209 } |
| 210 return result; |
| 208 } | 211 } |
| 209 | 212 |
| 210 bool get hasNext { | 213 bool moveNext() { |
| 211 if (_nextValidIndex >= _entries.length) return false; | 214 bool result; |
| 212 if (identical(_entries[_nextValidIndex], _HashMapImpl._DELETED_KEY)) { | 215 do { |
| 213 // This happens in case the set was modified in the meantime. | 216 result = _keysIterator.moveNext(); |
| 214 // A modification on the set may make this iterator misbehave, | 217 } while (result && |
| 215 // but we should never return the sentinel. | 218 (_keysIterator.current == null || |
| 216 _advance(); | 219 identical(_keysIterator.current, _HashMapImpl._DELETED_KEY))); |
| 217 } | 220 return result; |
| 218 return _nextValidIndex < _entries.length; | |
| 219 } | 221 } |
| 220 | 222 |
| 221 E next() { | 223 Iterator _keysIterator; |
| 222 if (!hasNext) { | |
| 223 throw new StateError("No more elements"); | |
| 224 } | |
| 225 E res = _entries[_nextValidIndex]; | |
| 226 _advance(); | |
| 227 return res; | |
| 228 } | |
| 229 | |
| 230 void _advance() { | |
| 231 int length = _entries.length; | |
| 232 var entry; | |
| 233 final deletedKey = _HashMapImpl._DELETED_KEY; | |
| 234 do { | |
| 235 if (++_nextValidIndex >= length) break; | |
| 236 entry = _entries[_nextValidIndex]; | |
| 237 } while ((entry == null) || identical(entry, deletedKey)); | |
| 238 } | |
| 239 | |
| 240 // The entries in the set. May contain null or the sentinel value. | |
| 241 List<E> _entries; | |
| 242 | |
| 243 // The next valid index in [_entries] or the length of [entries_]. | |
| 244 // If it is the length of [_entries], calling [hasNext] on the | |
| 245 // iterator will return false. | |
| 246 int _nextValidIndex; | |
| 247 } | 224 } |
| OLD | NEW |