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 216 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
227 return _sentinel.nextEntry(); | 227 return _sentinel.nextEntry(); |
228 } | 228 } |
229 | 229 |
230 int get length { | 230 int get length { |
231 int counter = 0; | 231 int counter = 0; |
232 forEach(void _(E element) { counter++; }); | 232 forEach(void _(E element) { counter++; }); |
233 return counter; | 233 return counter; |
234 } | 234 } |
235 | 235 |
236 bool get isEmpty { | 236 bool get isEmpty { |
237 return (_sentinel._next === _sentinel); | 237 return (identical(_sentinel._next, _sentinel)); |
238 } | 238 } |
239 | 239 |
240 void clear() { | 240 void clear() { |
241 _sentinel._next = _sentinel; | 241 _sentinel._next = _sentinel; |
242 _sentinel._previous = _sentinel; | 242 _sentinel._previous = _sentinel; |
243 } | 243 } |
244 | 244 |
245 void forEach(void f(E element)) { | 245 void forEach(void f(E element)) { |
246 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | 246 DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
247 while (entry !== _sentinel) { | 247 while (!identical(entry, _sentinel)) { |
248 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | 248 DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
249 f(entry._element); | 249 f(entry._element); |
250 entry = nextEntry; | 250 entry = nextEntry; |
251 } | 251 } |
252 } | 252 } |
253 | 253 |
254 void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { | 254 void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { |
255 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | 255 DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
256 while (entry !== _sentinel) { | 256 while (!identical(entry, _sentinel)) { |
257 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | 257 DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
258 f(entry); | 258 f(entry); |
259 entry = nextEntry; | 259 entry = nextEntry; |
260 } | 260 } |
261 } | 261 } |
262 | 262 |
263 bool every(bool f(E element)) { | 263 bool every(bool f(E element)) { |
264 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | 264 DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
265 while (entry !== _sentinel) { | 265 while (!identical(entry, _sentinel)) { |
266 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | 266 DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
267 if (!f(entry._element)) return false; | 267 if (!f(entry._element)) return false; |
268 entry = nextEntry; | 268 entry = nextEntry; |
269 } | 269 } |
270 return true; | 270 return true; |
271 } | 271 } |
272 | 272 |
273 bool some(bool f(E element)) { | 273 bool some(bool f(E element)) { |
274 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | 274 DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
275 while (entry !== _sentinel) { | 275 while (!identical(entry, _sentinel)) { |
276 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | 276 DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
277 if (f(entry._element)) return true; | 277 if (f(entry._element)) return true; |
278 entry = nextEntry; | 278 entry = nextEntry; |
279 } | 279 } |
280 return false; | 280 return false; |
281 } | 281 } |
282 | 282 |
283 Queue map(f(E element)) { | 283 Queue map(f(E element)) { |
284 Queue other = new Queue(); | 284 Queue other = new Queue(); |
285 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | 285 DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
286 while (entry !== _sentinel) { | 286 while (!identical(entry, _sentinel)) { |
287 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | 287 DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
288 other.addLast(f(entry._element)); | 288 other.addLast(f(entry._element)); |
289 entry = nextEntry; | 289 entry = nextEntry; |
290 } | 290 } |
291 return other; | 291 return other; |
292 } | 292 } |
293 | 293 |
294 Dynamic reduce(Dynamic initialValue, | 294 Dynamic reduce(Dynamic initialValue, |
295 Dynamic combine(Dynamic previousValue, E element)) { | 295 Dynamic combine(Dynamic previousValue, E element)) { |
296 return Collections.reduce(this, initialValue, combine); | 296 return Collections.reduce(this, initialValue, combine); |
297 } | 297 } |
298 | 298 |
299 Queue<E> filter(bool f(E element)) { | 299 Queue<E> filter(bool f(E element)) { |
300 Queue<E> other = new Queue<E>(); | 300 Queue<E> other = new Queue<E>(); |
301 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | 301 DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
302 while (entry !== _sentinel) { | 302 while (!identical(entry, _sentinel)) { |
303 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | 303 DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
304 if (f(entry._element)) other.addLast(entry._element); | 304 if (f(entry._element)) other.addLast(entry._element); |
305 entry = nextEntry; | 305 entry = nextEntry; |
306 } | 306 } |
307 return other; | 307 return other; |
308 } | 308 } |
309 | 309 |
310 _DoubleLinkedQueueIterator<E> iterator() { | 310 _DoubleLinkedQueueIterator<E> iterator() { |
311 return new _DoubleLinkedQueueIterator<E>(_sentinel); | 311 return new _DoubleLinkedQueueIterator<E>(_sentinel); |
312 } | 312 } |
313 | 313 |
314 String toString() { | 314 String toString() { |
315 return Collections.collectionToString(this); | 315 return Collections.collectionToString(this); |
316 } | 316 } |
317 } | 317 } |
318 | 318 |
319 class _DoubleLinkedQueueIterator<E> implements Iterator<E> { | 319 class _DoubleLinkedQueueIterator<E> implements Iterator<E> { |
320 final _DoubleLinkedQueueEntrySentinel<E> _sentinel; | 320 final _DoubleLinkedQueueEntrySentinel<E> _sentinel; |
321 DoubleLinkedQueueEntry<E> _currentEntry; | 321 DoubleLinkedQueueEntry<E> _currentEntry; |
322 | 322 |
323 _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel this._sentinel) { | 323 _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel this._sentinel) { |
324 _currentEntry = _sentinel; | 324 _currentEntry = _sentinel; |
325 } | 325 } |
326 | 326 |
327 bool get hasNext { | 327 bool get hasNext { |
328 return _currentEntry._next !== _sentinel; | 328 return !identical(_currentEntry._next, _sentinel); |
329 } | 329 } |
330 | 330 |
331 E next() { | 331 E next() { |
332 if (!hasNext) { | 332 if (!hasNext) { |
333 throw new StateError("No more elements"); | 333 throw new StateError("No more elements"); |
334 } | 334 } |
335 _currentEntry = _currentEntry._next; | 335 _currentEntry = _currentEntry._next; |
336 return _currentEntry.element; | 336 return _currentEntry.element; |
337 } | 337 } |
338 } | 338 } |
OLD | NEW |