Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(89)

Side by Side Diff: sdk/lib/_collection_dev/iterable.dart

Issue 12295009: Recommit changing List.skip/take/revert returns Iterable and remove mappedBy. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Make Future.wait simpler. Created 7 years, 10 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:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
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 part of dart._collection.dev; 5 part of dart._collection.dev;
6 6
7
8 /** 7 /**
9 * An [Iterable] for classes that have efficient [length] and [elementAt]. 8 * An [Iterable] for classes that have efficient [length] and [elementAt].
10 * 9 *
11 * All other methods are implemented in terms of [length] and [elementAt], 10 * All other methods are implemented in terms of [length] and [elementAt],
12 * including [iterator]. 11 * including [iterator].
13 */ 12 */
14 abstract class ListIterable<E> extends Iterable<E> { 13 abstract class ListIterable<E> extends Iterable<E> {
15 int get length; 14 int get length;
16 E elementAt(int i); 15 E elementAt(int i);
17 16
18 Iterator<E> get iterator => new ListIterableIterator<E>(this); 17 Iterator<E> get iterator => new ListIterator<E>(this);
19 18
20 void forEach(void action(E element)) { 19 void forEach(void action(E element)) {
21 int length = this.length; 20 int length = this.length;
22 for (int i = 0; i < length; i++) { 21 for (int i = 0; i < length; i++) {
23 action(elementAt(i)); 22 action(elementAt(i));
24 if (length != this.length) { 23 if (length != this.length) {
25 throw new ConcurrentModificationError(this); 24 throw new ConcurrentModificationError(this);
26 } 25 }
27 } 26 }
28 } 27 }
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after
86 if (length != this.length) { 85 if (length != this.length) {
87 throw new ConcurrentModificationError(this); 86 throw new ConcurrentModificationError(this);
88 } 87 }
89 } 88 }
90 if (orElse != null) return orElse(); 89 if (orElse != null) return orElse();
91 throw new StateError("No matching element"); 90 throw new StateError("No matching element");
92 } 91 }
93 92
94 E lastMatching(bool test(E element), { E orElse() }) { 93 E lastMatching(bool test(E element), { E orElse() }) {
95 int length = this.length; 94 int length = this.length;
96 for (int i = length - 1; i >= 0; i++) { 95 for (int i = length - 1; i >= 0; i--) {
97 E element = elementAt(i); 96 E element = elementAt(i);
98 if (test(element)) return element; 97 if (test(element)) return element;
99 if (length != this.length) { 98 if (length != this.length) {
100 throw new ConcurrentModificationError(this); 99 throw new ConcurrentModificationError(this);
101 } 100 }
102 } 101 }
103 if (orElse != null) return orElse(); 102 if (orElse != null) return orElse();
104 throw new StateError("No matching element"); 103 throw new StateError("No matching element");
105 } 104 }
106 105
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after
189 if (length != this.length) { 188 if (length != this.length) {
190 throw new ConcurrentModificationError(this); 189 throw new ConcurrentModificationError(this);
191 } 190 }
192 } 191 }
193 return buffer.toString(); 192 return buffer.toString();
194 } 193 }
195 } 194 }
196 195
197 Iterable<E> where(bool test(E element)) => super.where(test); 196 Iterable<E> where(bool test(E element)) => super.where(test);
198 197
199 Iterable map(f(E element)) => new MappedIterable(this, f); 198 Iterable map(f(E element)) => new MappedListIterable(this, f);
200
201 Iterable mappedBy(f(E element)) => super.mappedBy(f);
202 199
203 reduce(var initialValue, combine(var previousValue, E element)) { 200 reduce(var initialValue, combine(var previousValue, E element)) {
204 var value = initialValue; 201 var value = initialValue;
205 int length = this.length; 202 int length = this.length;
206 for (int i = 0; i < length; i++) { 203 for (int i = 0; i < length; i++) {
207 value = reduce(value, elementAt(i)); 204 value = combine(value, elementAt(i));
208 if (length != this.length) { 205 if (length != this.length) {
209 throw new ConcurrentModificationError(this); 206 throw new ConcurrentModificationError(this);
210 } 207 }
211 } 208 }
212 return value; 209 return value;
213 } 210 }
214 211
215 Iterable<E> skip(int count) => new SubListIterable(this, count, null); 212 Iterable<E> skip(int count) => new SubListIterable(this, count, null);
216 213
217 Iterable<E> skipWhile(bool test(E element)) => super.skipWhile(test); 214 Iterable<E> skipWhile(bool test(E element)) => super.skipWhile(test);
(...skipping 12 matching lines...) Expand all
230 227
231 Set<E> toSet() { 228 Set<E> toSet() {
232 Set<E> result = new Set<E>(); 229 Set<E> result = new Set<E>();
233 for (int i = 0; i < length; i++) { 230 for (int i = 0; i < length; i++) {
234 result.add(elementAt(i)); 231 result.add(elementAt(i));
235 } 232 }
236 return result; 233 return result;
237 } 234 }
238 } 235 }
239 236
240 abstract class SubListIterable<E> extends ListIterable<E> { 237 class SubListIterable<E> extends ListIterable<E> {
241 final Iterable<E> _iterable; 238 final Iterable<E> _iterable;
242 final int _start; 239 final int _start;
243 /** If null, represents the length of the iterable. */ 240 /** If null, represents the length of the iterable. */
244 final int _endOrLength; 241 final int _endOrLength;
245 242
246 SubListIterable(this._iterable, this._start, this._endOrLength); 243 SubListIterable(this._iterable, this._start, this._endOrLength);
247 244
248 int get _endIndex { 245 int get _endIndex {
249 int length = _iterable.length; 246 int length = _iterable.length;
250 if (_endOrLength == null || _endOrLength > length) return length; 247 if (_endOrLength == null || _endOrLength > length) return length;
(...skipping 26 matching lines...) Expand all
277 Iterable<E> skip(int count) { 274 Iterable<E> skip(int count) {
278 if (count < 0) throw new ArgumentError(count); 275 if (count < 0) throw new ArgumentError(count);
279 return new SubListIterable(_iterable, _start + count, _endOrLength); 276 return new SubListIterable(_iterable, _start + count, _endOrLength);
280 } 277 }
281 278
282 Iterable<E> take(int count) { 279 Iterable<E> take(int count) {
283 if (count < 0) throw new ArgumentError(count); 280 if (count < 0) throw new ArgumentError(count);
284 if (_endOrLength == null) { 281 if (_endOrLength == null) {
285 return new SubListIterable(_iterable, _start, _start + count); 282 return new SubListIterable(_iterable, _start, _start + count);
286 } else { 283 } else {
287 newEnd = _start + count; 284 int newEnd = _start + count;
288 if (_endOrLength < newEnd) return this; 285 if (_endOrLength < newEnd) return this;
289 return new SubListIterable(_iterable, _start, newEnd); 286 return new SubListIterable(_iterable, _start, newEnd);
290 } 287 }
291 } 288 }
292 } 289 }
293 290
294 class ListIterableIterator<E> implements Iterator<E> { 291 /**
292 * An [Iterator] that iterates a list-like [Iterable].
293 *
294 * All iterations is done in terms of [Iterable.length] and
295 * [Iterable.elementAt]. These operations are fast for list-like
296 * iterables.
297 */
298 class ListIterator<E> implements Iterator<E> {
295 final Iterable<E> _iterable; 299 final Iterable<E> _iterable;
296 final int _length; 300 final int _length;
297 int _index; 301 int _index;
298 E _current; 302 E _current;
299 ListIterableIterator(Iterable<E> iterable) 303
304 ListIterator(Iterable<E> iterable)
300 : _iterable = iterable, _length = iterable.length, _index = 0; 305 : _iterable = iterable, _length = iterable.length, _index = 0;
301 306
302 E get current => _current; 307 E get current => _current;
303 308
304 bool moveNext() { 309 bool moveNext() {
305 if (_length != _iterable.length) { 310 if (_length != _iterable.length) {
306 throw new ConcurrentModificationError(_iterable); 311 throw new ConcurrentModificationError(_iterable);
307 } 312 }
308 if (_index == _length) { 313 if (_index == _length) {
309 _current = null; 314 _current = null;
(...skipping 13 matching lines...) Expand all
323 // checked mode. http://dartbug.com/7733 328 // checked mode. http://dartbug.com/7733
324 final /* _Transformation<S, T> */ _f; 329 final /* _Transformation<S, T> */ _f;
325 330
326 MappedIterable(this._iterable, T this._f(S element)); 331 MappedIterable(this._iterable, T this._f(S element));
327 332
328 Iterator<T> get iterator => new MappedIterator<S, T>(_iterable.iterator, _f); 333 Iterator<T> get iterator => new MappedIterator<S, T>(_iterable.iterator, _f);
329 334
330 // Length related functions are independent of the mapping. 335 // Length related functions are independent of the mapping.
331 int get length => _iterable.length; 336 int get length => _iterable.length;
332 bool get isEmpty => _iterable.isEmpty; 337 bool get isEmpty => _iterable.isEmpty;
338
339 // Index based lookup can be done before transforming.
340 T get first => _f(_iterable.first);
341 T get last => _f(_iterable.last);
342 T get single => _f(_iterable.single);
343 T elementAt(int index) => _f(_iterable.elementAt(index));
333 } 344 }
334 345
335
336 class MappedIterator<S, T> extends Iterator<T> { 346 class MappedIterator<S, T> extends Iterator<T> {
337 T _current; 347 T _current;
338 final Iterator<S> _iterator; 348 final Iterator<S> _iterator;
339 // TODO(ahe): Restore type when feature is implemented in dart2js 349 // TODO(ahe): Restore type when feature is implemented in dart2js
340 // checked mode. http://dartbug.com/7733 350 // checked mode. http://dartbug.com/7733
341 final /* _Transformation<S, T> */ _f; 351 final /* _Transformation<S, T> */ _f;
342 352
343 MappedIterator(this._iterator, T this._f(S element)); 353 MappedIterator(this._iterator, T this._f(S element));
344 354
345 bool moveNext() { 355 bool moveNext() {
346 if (_iterator.moveNext()) { 356 if (_iterator.moveNext()) {
347 _current = _f(_iterator.current); 357 _current = _f(_iterator.current);
348 return true; 358 return true;
349 } else {
350 _current = null;
351 return false;
352 } 359 }
360 _current = null;
361 return false;
353 } 362 }
354 363
355 T get current => _current; 364 T get current => _current;
356 } 365 }
357 366
358 /** Specialized alternative to [MappedIterable] for mapped [List]s. */ 367 /** Specialized alternative to [MappedIterable] for mapped [List]s. */
359 class MappedListIterable<S, T> extends Iterable<T> { 368 class MappedListIterable<S, T> extends ListIterable<T> {
360 final List<S> _list; 369 final Iterable<S> _source;
361 /**
362 * Start index of the part of the list to map.
363 *
364 * Allows mapping only a sub-list of an existing list.
365 *
366 * Used to implement lazy skip/take on a [MappedListIterable].
367 */
368 final int _start;
369
370 /**
371 * End index of the part of the list to map.
372 *
373 * If null, always use the length of the list.
374 */
375 final int _end;
376
377 // TODO(ahe): Restore type when feature is implemented in dart2js 370 // TODO(ahe): Restore type when feature is implemented in dart2js
378 // checked mode. http://dartbug.com/7733 371 // checked mode. http://dartbug.com/7733
379 final /* _Transformation<S, T> */ _f; 372 final /* _Transformation<S, T> */ _f;
380 373
381 MappedListIterable(this._list, T this._f(S element), this._start, this._end) { 374 MappedListIterable(this._source, T this._f(S value));
382 if (_end != null && _end < _start) {
383 throw new ArgumentError("End ($_end) before start ($_start)");
384 }
385 }
386 375
387 /** The start index, limited to the current length of the list. */ 376 int get length => _source.length;
388 int get _startIndex { 377 T elementAt(int index) => _f(_source.elementAt(index));
389 if (_start <= _list.length) return _start;
390 return _list.length;
391 }
392
393 /** The end index, if given, limited to the current length of the list. */
394 int get _endIndex {
395 if (_end == null || _end > _list.length) return _list.length;
396 return _end;
397 }
398
399 Iterator<T> get iterator =>
400 new MappedListIterator<S, T>(_list, _f, _startIndex, _endIndex);
401
402 void forEach(void action(T element)) {
403 int length = _list.length;
404 for (int i = _startIndex, n = _endIndex; i < n; i++) {
405 action(_f(_list[i]));
406 if (_list.length != length) {
407 throw new ConcurrentModificationError(_list);
408 }
409 }
410 }
411
412 bool get isEmpty => _startIndex == _endIndex;
413
414 int get length => _endIndex - _startIndex;
415
416 T get first {
417 int start = _startIndex;
418 if (start == _endIndex) {
419 throw new StateError("No elements");
420 }
421 return _f(_list.elementAt(start));
422 }
423
424 T get last {
425 int end = _endIndex;
426 if (end == _startIndex) {
427 throw new StateError("No elements");
428 }
429 return _f(_list.elementAt(end - 1));
430 }
431
432 T get single {
433 int start = _startIndex;
434 int end = _endIndex;
435 if (start != end - 1) {
436 if (start == end) {
437 throw new StateError("No elements");
438 }
439 throw new StateError("Too many elements");
440 }
441 return _f(_list[start]);
442 }
443
444 T elementAt(int index) {
445 index += _startIndex;
446 if (index >= _endIndex) {
447 throw new StateError("No matching element");
448 }
449 return _f(_list.elementAt(index));
450 }
451
452 bool contains(T element) {
453 int length = _list.length;
454 for (int i = _startIndex, n = _endIndex; i < n; i++) {
455 if (_f(_list[i]) == element) {
456 return true;
457 }
458 if (_list.length != length) {
459 throw new ConcurrentModificationError(_list);
460 }
461 }
462 return false;
463 }
464
465 bool every(bool test(T element)) {
466 int length = _list.length;
467 for (int i = _startIndex, n = _endIndex; i < n; i++) {
468 if (!test(_f(_list[i]))) return false;
469 if (_list.length != length) {
470 throw new ConcurrentModificationError(_list);
471 }
472 }
473 return true;
474 }
475
476 bool any(bool test(T element)) {
477 int length = _list.length;
478 for (int i = _startIndex, n = _endIndex; i < n; i++) {
479 if (test(_f(_list[i]))) return true;
480 if (_list.length != length) {
481 throw new ConcurrentModificationError(_list);
482 }
483 }
484 return false;
485 }
486
487 T firstMatching(bool test(T element), { T orElse() }) {
488 int length = _list.length;
489 for (int i = _startIndex, n = _endIndex; i < n; i++) {
490 T value = _f(_list[i]);
491 if (test(value)) return value;
492 if (_list.length != length) {
493 throw new ConcurrentModificationError(_list);
494 }
495 }
496 if (orElse != null) return orElse();
497 throw new StateError("No matching element");
498 }
499
500 T lastMatching(bool test(T element), { T orElse() }) {
501 int length = _list.length;
502 for (int i = _endIndex - 1, start = _startIndex; i >= start; i++) {
503 T value = _f(_list[i]);
504 if (test(value)) return value;
505 if (_list.length != length) {
506 throw new ConcurrentModificationError(_list);
507 }
508 }
509 if (orElse != null) return orElse();
510 throw new StateError("No matching element");
511 }
512
513 T singleMatching(bool test(T element)) {
514 int length = _list.length;
515 T match;
516 bool matchFound = false;
517 for (int i = _startIndex, n = _endIndex; i < n; i++) {
518 T value = _f(_list[i]);
519 if (test(value)) {
520 if (matchFound) {
521 throw new StateError("More than one matching element");
522 }
523 matchFound = true;
524 match = value;
525 }
526 if (_list.length != length) {
527 throw new ConcurrentModificationError(_list);
528 }
529 }
530 if (matchFound) return match;
531 throw new StateError("No matching element");
532 }
533
534 T min([int compare(T a, T b)]) {
535 if (compare == null) {
536 var defaultCompare = Comparable.compare;
537 compare = defaultCompare;
538 }
539 int length = _list.length;
540 int start = _startIndex;
541 int end = _endIndex;
542 if (start == end) return null;
543 T value = _f(_list[start]);
544 if (_list.length != length) {
545 throw new ConcurrentModificationError(_list);
546 }
547 for (int i = start + 1; i < end; i++) {
548 T nextValue = _f(_list[i]);
549 if (compare(value, nextValue) > 0) {
550 value = nextValue;
551 }
552 if (_list.length != length) {
553 throw new ConcurrentModificationError(_list);
554 }
555 }
556 return value;
557 }
558
559 T max([int compare(T a, T b)]) {
560 if (compare == null) {
561 var defaultCompare = Comparable.compare;
562 compare = defaultCompare;
563 }
564 int length = _list.length;
565 int start = _startIndex;
566 int end = _endIndex;
567 if (start == end) return null;
568 T value = _f(_list[start]);
569 if (_list.length != length) {
570 throw new ConcurrentModificationError(_list);
571 }
572 for (int i = start + 1; i < end; i++) {
573 T nextValue = _f(_list[i]);
574 if (compare(value, nextValue) < 0) {
575 value = nextValue;
576 }
577 if (_list.length != length) {
578 throw new ConcurrentModificationError(_list);
579 }
580 }
581 return value;
582 }
583
584 String join([String separator]) {
585 int start = _startIndex;
586 int end = _endIndex;
587 if (start == end) return "";
588 StringBuffer buffer = new StringBuffer("${_f(_list[start])}");
589 if (_list.length != length) {
590 throw new ConcurrentModificationError(_list);
591 }
592 for (int i = start + 1; i < end; i++) {
593 if (separator != null && separator != "") {
594 buffer.add(separator);
595 }
596 buffer.add("${_f(_list[i])}");
597 if (_list.length != length) {
598 throw new ConcurrentModificationError(_list);
599 }
600 }
601 return buffer.toString();
602 }
603
604 Iterable<T> where(bool test(T element)) => super.where(test);
605
606 Iterable map(f(T element)) {
607 return new MappedListIterable(_list, (S v) => f(_f(v)), _start, _end);
608 }
609
610 Iterable mappedBy(f(T element)) => map(f);
611
612 reduce(var initialValue, combine(var previousValue, T element)) {
613 return _list.reduce(initialValue, (v, S e) => combine(v, _f(e)));
614 }
615
616 Iterable<T> skip(int count) {
617 int start = _startIndex + count;
618 if (_end != null && start >= _end) {
619 return new EmptyIterable<T>();
620 }
621 return new MappedListIterable(_list, _f, start, _end);
622 }
623
624 Iterable<T> skipWhile(bool test(T element)) => super.skipWhile(test);
625
626 Iterable<T> take(int count) {
627 int newEnd = _start + count;
628 if (_end == null || newEnd < _end) {
629 return new MappedListIterable(_list, _f, _start, newEnd);
630 }
631 // Equivalent to "this".
632 return new MappedListIterable(_list, _f, _start, _end);
633 }
634
635 Iterable<T> takeWhile(bool test(T element)) => super.takeWhile(test);
636
637 List<T> toList() {
638 List<T> result = new List<T>();
639 forEach(result.add);
640 return result;
641 }
642
643 Set<T> toSet() {
644 Set<T> result = new Set<T>();
645 forEach(result.add);
646 return result;
647 }
648 } 378 }
649 379
650 /**
651 * Iterator for [MappedListIterable].
652 *
653 * A list iterator that iterates over (a sublist of) a list and
654 * returns the values transformed by a function.
655 *
656 * As a list iterator, it throws if the length of the list has
657 * changed during iteration.
658 */
659 class MappedListIterator<S, T> implements Iterator<T> {
660 List<S> _list;
661 // TODO(ahe): Restore type when feature is implemented in dart2js
662 // checked mode. http://dartbug.com/7733
663 final /* _Transformation<S, T> */ _f;
664 final int _endIndex;
665 final int _length;
666 int _index;
667 T _current;
668
669 MappedListIterator(List<S> list, this._f, int start, this._endIndex)
670 : _list = list, _length = list.length, _index = start;
671
672 T get current => _current;
673
674 bool moveNext() {
675 if (_list.length != _length) {
676 throw new ConcurrentModificationError(_list);
677 }
678 if (_index >= _endIndex) {
679 _current = null;
680 return false;
681 }
682 _current = _f(_list[_index]);
683 _index++;
684 return true;
685 }
686 }
687 380
688 typedef bool _ElementPredicate<E>(E element); 381 typedef bool _ElementPredicate<E>(E element);
689 382
690 class WhereIterable<E> extends Iterable<E> { 383 class WhereIterable<E> extends Iterable<E> {
691 final Iterable<E> _iterable; 384 final Iterable<E> _iterable;
692 // TODO(ahe): Restore type when feature is implemented in dart2js 385 // TODO(ahe): Restore type when feature is implemented in dart2js
693 // checked mode. http://dartbug.com/7733 386 // checked mode. http://dartbug.com/7733
694 final /* _ElementPredicate */ _f; 387 final /* _ElementPredicate */ _f;
695 388
696 WhereIterable(this._iterable, bool this._f(E element)); 389 WhereIterable(this._iterable, bool this._f(E element));
(...skipping 265 matching lines...) Expand 10 before | Expand all | Expand 10 after
962 E min([int compare(E a, E b)]) => null; 655 E min([int compare(E a, E b)]) => null;
963 656
964 E max([int compare(E a, E b)]) => null; 657 E max([int compare(E a, E b)]) => null;
965 658
966 String join([String separator]) => ""; 659 String join([String separator]) => "";
967 660
968 Iterable<E> where(bool test(E element)) => this; 661 Iterable<E> where(bool test(E element)) => this;
969 662
970 Iterable map(f(E element)) => const EmptyIterable(); 663 Iterable map(f(E element)) => const EmptyIterable();
971 664
972 Iterable mappedBy(f(E element)) => const EmptyIterable();
973
974 reduce(var initialValue, combine(var previousValue, E element)) { 665 reduce(var initialValue, combine(var previousValue, E element)) {
975 return initialValue; 666 return initialValue;
976 } 667 }
977 668
978 Iterable<E> skip(int count) => this; 669 Iterable<E> skip(int count) => this;
979 670
980 Iterable<E> skipWhile(bool test(E element)) => this; 671 Iterable<E> skipWhile(bool test(E element)) => this;
981 672
982 Iterable<E> take(int count) => this; 673 Iterable<E> take(int count) => this;
983 674
984 Iterable<E> takeWhile(bool test(E element)) => this; 675 Iterable<E> takeWhile(bool test(E element)) => this;
985 676
986 List toList() => <E>[]; 677 List toList() => <E>[];
987 678
988 Set toSet() => new Set<E>(); 679 Set toSet() => new Set<E>();
989 } 680 }
990 681
991 /** The always empty iterator. */ 682 /** The always empty iterator. */
992 class EmptyIterator<E> implements Iterator<E> { 683 class EmptyIterator<E> implements Iterator<E> {
993 const EmptyIterator(); 684 const EmptyIterator();
994 bool moveNext() => false; 685 bool moveNext() => false;
995 E get current => null; 686 E get current => null;
996 } 687 }
997 688
998 /** An [Iterator] that can move in both directions. */ 689 /** An [Iterator] that can move in both directions. */
999 abstract class BiDirectionalIterator<T> implements Iterator<T> { 690 abstract class BiDirectionalIterator<T> implements Iterator<T> {
1000 bool movePrevious(); 691 bool movePrevious();
1001 } 692 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698