| 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 * A [Queue] is a collection that can be manipulated at both ends. One | 6 * A [Queue] is a collection that can be manipulated at both ends. One |
| 7 * can iterate over the elements of a queue through [forEach] or with | 7 * can iterate over the elements of a queue through [forEach] or with |
| 8 * an [Iterator]. | 8 * an [Iterator]. |
| 9 */ | 9 */ |
| 10 abstract class Queue<E> extends Collection<E> { | 10 abstract class Queue<E> extends Collection<E> { |
| (...skipping 152 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 163 } | 163 } |
| 164 } | 164 } |
| 165 | 165 |
| 166 /** | 166 /** |
| 167 * Implementation of a double linked list that box list elements into | 167 * Implementation of a double linked list that box list elements into |
| 168 * DoubleLinkedQueueEntry objects. | 168 * DoubleLinkedQueueEntry objects. |
| 169 * | 169 * |
| 170 * WARNING: This class is temporary located in dart:core. It'll be removed | 170 * WARNING: This class is temporary located in dart:core. It'll be removed |
| 171 * at some point in the near future. | 171 * at some point in the near future. |
| 172 */ | 172 */ |
| 173 class DoubleLinkedQueue<E> implements Queue<E> { | 173 class DoubleLinkedQueue<E> extends Iterable<E> implements Queue<E> { |
| 174 _DoubleLinkedQueueEntrySentinel<E> _sentinel; | 174 _DoubleLinkedQueueEntrySentinel<E> _sentinel; |
| 175 | 175 |
| 176 DoubleLinkedQueue() { | 176 DoubleLinkedQueue() { |
| 177 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); | 177 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); |
| 178 } | 178 } |
| 179 | 179 |
| 180 factory DoubleLinkedQueue.from(Iterable<E> other) { | 180 factory DoubleLinkedQueue.from(Iterable<E> other) { |
| 181 Queue<E> list = new DoubleLinkedQueue(); | 181 Queue<E> list = new DoubleLinkedQueue(); |
| 182 for (final e in other) { | 182 for (final e in other) { |
| 183 list.addLast(e); | 183 list.addLast(e); |
| (...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 220 } | 220 } |
| 221 | 221 |
| 222 DoubleLinkedQueueEntry<E> lastEntry() { | 222 DoubleLinkedQueueEntry<E> lastEntry() { |
| 223 return _sentinel.previousEntry(); | 223 return _sentinel.previousEntry(); |
| 224 } | 224 } |
| 225 | 225 |
| 226 DoubleLinkedQueueEntry<E> firstEntry() { | 226 DoubleLinkedQueueEntry<E> firstEntry() { |
| 227 return _sentinel.nextEntry(); | 227 return _sentinel.nextEntry(); |
| 228 } | 228 } |
| 229 | 229 |
| 230 int get length { | |
| 231 int counter = 0; | |
| 232 forEach((E element) { counter++; }); | |
| 233 return counter; | |
| 234 } | |
| 235 | |
| 236 bool get isEmpty { | 230 bool get isEmpty { |
| 237 return (identical(_sentinel._next, _sentinel)); | 231 return (identical(_sentinel._next, _sentinel)); |
| 238 } | 232 } |
| 239 | 233 |
| 240 void clear() { | 234 void clear() { |
| 241 _sentinel._next = _sentinel; | 235 _sentinel._next = _sentinel; |
| 242 _sentinel._previous = _sentinel; | 236 _sentinel._previous = _sentinel; |
| 243 } | 237 } |
| 244 | 238 |
| 245 void forEach(void f(E element)) { | |
| 246 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | |
| 247 while (!identical(entry, _sentinel)) { | |
| 248 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | |
| 249 f(entry._element); | |
| 250 entry = nextEntry; | |
| 251 } | |
| 252 } | |
| 253 | |
| 254 void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { | 239 void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { |
| 255 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | 240 DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
| 256 while (!identical(entry, _sentinel)) { | 241 while (!identical(entry, _sentinel)) { |
| 257 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | 242 DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
| 258 f(entry); | 243 f(entry); |
| 259 entry = nextEntry; | 244 entry = nextEntry; |
| 260 } | 245 } |
| 261 } | 246 } |
| 262 | 247 |
| 263 bool every(bool f(E element)) { | |
| 264 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | |
| 265 while (!identical(entry, _sentinel)) { | |
| 266 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | |
| 267 if (!f(entry._element)) return false; | |
| 268 entry = nextEntry; | |
| 269 } | |
| 270 return true; | |
| 271 } | |
| 272 | |
| 273 bool some(bool f(E element)) { | |
| 274 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | |
| 275 while (!identical(entry, _sentinel)) { | |
| 276 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | |
| 277 if (f(entry._element)) return true; | |
| 278 entry = nextEntry; | |
| 279 } | |
| 280 return false; | |
| 281 } | |
| 282 | |
| 283 Queue mappedBy(f(E element)) { | |
| 284 Queue other = new Queue(); | |
| 285 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | |
| 286 while (!identical(entry, _sentinel)) { | |
| 287 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | |
| 288 other.addLast(f(entry._element)); | |
| 289 entry = nextEntry; | |
| 290 } | |
| 291 return other; | |
| 292 } | |
| 293 | |
| 294 Dynamic reduce(Dynamic initialValue, | |
| 295 Dynamic combine(Dynamic previousValue, E element)) { | |
| 296 return Collections.reduce(this, initialValue, combine); | |
| 297 } | |
| 298 | |
| 299 Queue<E> where(bool f(E element)) { | |
| 300 Queue<E> other = new Queue<E>(); | |
| 301 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | |
| 302 while (!identical(entry, _sentinel)) { | |
| 303 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | |
| 304 if (f(entry._element)) other.addLast(entry._element); | |
| 305 entry = nextEntry; | |
| 306 } | |
| 307 return other; | |
| 308 } | |
| 309 | |
| 310 _DoubleLinkedQueueIterator<E> get iterator { | 248 _DoubleLinkedQueueIterator<E> get iterator { |
| 311 return new _DoubleLinkedQueueIterator<E>(_sentinel); | 249 return new _DoubleLinkedQueueIterator<E>(_sentinel); |
| 312 } | 250 } |
| 313 | 251 |
| 314 String toString() { | 252 String toString() { |
| 315 return Collections.collectionToString(this); | 253 return Collections.collectionToString(this); |
| 316 } | 254 } |
| 317 } | 255 } |
| 318 | 256 |
| 319 class _DoubleLinkedQueueIterator<E> implements Iterator<E> { | 257 class _DoubleLinkedQueueIterator<E> implements Iterator<E> { |
| (...skipping 12 matching lines...) Expand all Loading... |
| 332 } | 270 } |
| 333 | 271 |
| 334 E get current { | 272 E get current { |
| 335 if (_currentEntry != null && !identical(_currentEntry, _sentinel)) { | 273 if (_currentEntry != null && !identical(_currentEntry, _sentinel)) { |
| 336 return _currentEntry.element; | 274 return _currentEntry.element; |
| 337 } | 275 } |
| 338 // TODO(floitsch): adapt error message. | 276 // TODO(floitsch): adapt error message. |
| 339 throw new StateError("No more elements"); | 277 throw new StateError("No more elements"); |
| 340 } | 278 } |
| 341 } | 279 } |
| OLD | NEW |