-
Notifications
You must be signed in to change notification settings - Fork 1.5k
/
iterable.dart
711 lines (669 loc) · 25 KB
/
iterable.dart
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
part of dart.core;
/**
* A collection of values, or "elements", that can be accessed sequentially.
*
* The elements of the iterable are accessed by getting an [Iterator]
* using the [iterator] getter, and using it to step through the values.
* Stepping with the iterator is done by calling [Iterator.moveNext],
* and if the call returns `true`,
* the iterator has now moved to the next element,
* which is then available as [Iterator.current].
* If the call returns `false`, there are no more elements.
* The [Iterator.current] value must only be used when the most
* recent call to [Iterator.moveNext] has returned `true`.
* If it is used before calling [Iterator.moveNext] the first time
* on an iterator, or after a call has returned false or has thrown an error,
* reading [Iterator.current] may throw or may return an arbitrary value.
*
* You can create more than one iterator from the same `Iterable`.
* Each time `iterator` is read, it returns a new iterator,
* and different iterators can be stepped through independently,
* each giving access to all the elements of the iterable.
* The iterators of the same iterable *should* provide the same values
* in the same order (unless the underlying collection is modified between
* the iterations, which some collections allow).
*
* You can also iterate over the elements of an `Iterable`
* using the for-in loop construct, which uses the `iterator` getter behind the
* scenes.
* For example, you can iterate over all of the keys of a [Map],
* because `Map` keys are iterable.
*
* Map kidsBooks = {'Matilda': 'Roald Dahl',
* 'Green Eggs and Ham': 'Dr Seuss',
* 'Where the Wild Things Are': 'Maurice Sendak'};
* for (var book in kidsBooks.keys) {
* print('$book was written by ${kidsBooks[book]}');
* }
*
* The [List] and [Set] classes are both `Iterable`,
* as are most classes in the `dart:collection` library.
*
* Some [Iterable] collections can be modified.
* Adding an element to a `List` or `Set` will change which elements it
* contains, and adding a new key to a `Map` changes the elements of [Map.keys].
* Iterators created after the change will provide the new elements, and may
* or may not preserve the order of existing elements
* (for example, a [HashSet] may completely change its order when a single
* element is added).
*
* Changing a collection *while* it is being iterated
* is generally *not* allowed.
* Doing so will break the iteration, which is typically signalled
* by throwing a [ConcurrentModificationError]
* the next time [Iterator.moveNext] is called.
* The current value of [Iterator.current] getter
* should not be affected by the change in the collection,
* the `current` value was set by the previous call to [Iterator.moveNext].
*
* Some iterables compute their elements dynamically every time they are
* iterated, like the one returned by [Iterable.generate] or the iterable
* returned by a `sync*` generator function. If the computation doesn't depend
* on other objects that may change, then the generated sequence should be
* the same one every time it's iterated.
*
* The members of `Iterable`, other than `iterator` itself,
* work by looking at the elements of the iterable.
* This can be implemented by running through the [iterator], but some classes
* may have more efficient ways of finding the result
* (like [last] or [length] on a [List], or [contains] on a [Set]).
*
* The methods that return another `Iterable` (like [map] and [where])
* are all *lazy* - they will iterate the original (as necessary)
* every time the returned iterable is iterated, and not before.
*
* Since an iterable may be iterated more than once, it's not recommended to
* have detectable side-effects in the iterator.
* For methods like [map] and [where], the returned iterable will execute the
* argument function on every iteration, so those functions should also not
* have side effects.
*/
abstract class Iterable<E> {
// TODO(lrn): When we allow forwarding const constructors through
// mixin applications, make this class implement [IterableMixin].
const Iterable();
/**
* Creates an `Iterable` which generates its elements dynamically.
*
* The generated iterable has [count] elements,
* and the element at index `n` is computed by calling `generator(n)`.
* Values are not cached, so each iteration computes the values again.
*
* If [generator] is omitted, it defaults to an identity function
* on integers `(int x) => x`, so it may only be omitted if the type
* parameter allows integer values. That is, if [E] is a super-type
* of [int].
*
* As an `Iterable`, `new Iterable.generate(n, generator))` is equivalent to
* `const [0, ..., n - 1].map(generator)`.
*/
factory Iterable.generate(int count, [E generator(int index)?]) {
if (count <= 0) return EmptyIterable<E>();
return _GeneratorIterable<E>(count, generator);
}
/**
* Creates an empty iterable.
*
* The empty iterable has no elements, and iterating it always stops
* immediately.
*/
const factory Iterable.empty() = EmptyIterable<E>;
/**
* Adapts [source] to be an `Iterable<T>`.
*
* Any time the iterable would produce an element that is not a [T],
* the element access will throw. If all elements of [source] are actually
* instances of [T], or if only elements that are actually instances of [T]
* are accessed, then the resulting iterable can be used as an `Iterable<T>`.
*/
static Iterable<T> castFrom<S, T>(Iterable<S> source) =>
CastIterable<S, T>(source);
/**
* Returns a new `Iterator` that allows iterating the elements of this
* `Iterable`.
*
* Iterable classes may specify the iteration order of their elements
* (for example [List] always iterate in index order),
* or they may leave it unspecified (for example a hash-based [Set]
* may iterate in any order).
*
* Each time `iterator` is read, it returns a new iterator,
* which can be used to iterate through all the elements again.
* The iterators of the same iterable can be stepped through independently,
* but should return the same elements in the same order,
* as long as the underlying collection isn't changed.
*
* Modifying the collection may cause new iterators to produce
* different elements, and may change the order of existing elements.
* A [List] specifies its iteration order precisely,
* so modifying the list changes the iteration order predictably.
* A hash-based [Set] may change its iteration order completely
* when adding a new element to the set.
*
* Modifying the underlying collection after creating the new iterator
* may cause an error the next time [Iterator.moveNext] is called
* on that iterator.
* Any *modifiable* iterable class should specify which operations will
* break iteration.
*/
Iterator<E> get iterator;
/**
* Provides a view of this iterable as an iterable of [R] instances.
*
* If this iterable only contains instances of [R], all operations
* will work correctly. If any operation tries to access an element
* that is not an instance of [R], the access will throw instead.
*
* When the returned iterable creates a new object that depends on
* the type [R], e.g., from [toList], it will have exactly the type [R].
*/
Iterable<R> cast<R>() => Iterable.castFrom<E, R>(this);
/**
* Returns the lazy concatenation of this iterable and [other].
*
* The returned iterable will provide the same elements as this iterable,
* and, after that, the elements of [other], in the same order as in the
* original iterables.
*/
Iterable<E> followedBy(Iterable<E> other) {
var self = this; // TODO(lrn): Remove when we can promote `this`.
if (self is EfficientLengthIterable<E>) {
return FollowedByIterable<E>.firstEfficient(self, other);
}
return FollowedByIterable<E>(this, other);
}
/**
* Returns a new lazy [Iterable] with elements that are created by
* calling `f` on each element of this `Iterable` in iteration order.
*
* This method returns a view of the mapped elements. As long as the
* returned [Iterable] is not iterated over, the supplied function [f] will
* not be invoked. The transformed elements will not be cached. Iterating
* multiple times over the returned [Iterable] will invoke the supplied
* function [f] multiple times on the same element.
*
* Methods on the returned iterable are allowed to omit calling `f`
* on any element where the result isn't needed.
* For example, [elementAt] may call `f` only once.
*/
Iterable<T> map<T>(T f(E e)) => MappedIterable<E, T>(this, f);
/**
* Returns a new lazy [Iterable] with all elements that satisfy the
* predicate [test].
*
* The matching elements have the same order in the returned iterable
* as they have in [iterator].
*
* This method returns a view of the mapped elements.
* As long as the returned [Iterable] is not iterated over,
* the supplied function [test] will not be invoked.
* Iterating will not cache results, and thus iterating multiple times over
* the returned [Iterable] may invoke the supplied
* function [test] multiple times on the same element.
*/
Iterable<E> where(bool test(E element)) => WhereIterable<E>(this, test);
/**
* Returns a new lazy [Iterable] with all elements that have type [T].
*
* The matching elements have the same order in the returned iterable
* as they have in [iterator].
*
* This method returns a view of the mapped elements.
* Iterating will not cache results, and thus iterating multiple times over
* the returned [Iterable] may yield different results,
* if the underlying elements change between iterations.
*/
Iterable<T> whereType<T>() => WhereTypeIterable<T>(this);
/**
* Expands each element of this [Iterable] into zero or more elements.
*
* The resulting Iterable runs through the elements returned
* by [f] for each element of this, in iteration order.
*
* The returned [Iterable] is lazy, and calls [f] for each element
* of this every time it's iterated.
*
* Example:
*
* var pairs = [[1, 2], [3, 4]];
* var flattened = pairs.expand((pair) => pair).toList();
* print(flattened); // => [1, 2, 3, 4];
*
* var input = [1, 2, 3];
* var duplicated = input.expand((i) => [i, i]).toList();
* print(duplicated); // => [1, 1, 2, 2, 3, 3]
*
*/
Iterable<T> expand<T>(Iterable<T> f(E element)) =>
ExpandIterable<E, T>(this, f);
/**
* Returns true if the collection contains an element equal to [element].
*
* This operation will check each element in order for being equal to
* [element], unless it has a more efficient way to find an element
* equal to [element].
*
* The equality used to determine whether [element] is equal to an element of
* the iterable defaults to the [Object.==] of the element.
*
* Some types of iterable may have a different equality used for its elements.
* For example, a [Set] may have a custom equality
* (see [Set.identity]) that its `contains` uses.
* Likewise the `Iterable` returned by a [Map.keys] call
* should use the same equality that the `Map` uses for keys.
*/
bool contains(Object? element) {
for (E e in this) {
if (e == element) return true;
}
return false;
}
/**
* Applies the function [f] to each element of this collection in iteration
* order.
*/
void forEach(void f(E element)) {
for (E element in this) f(element);
}
/**
* Reduces a collection to a single value by iteratively combining elements
* of the collection using the provided function.
*
* The iterable must have at least one element.
* If it has only one element, that element is returned.
*
* Otherwise this method starts with the first element from the iterator,
* and then combines it with the remaining elements in iteration order,
* as if by:
*
* E value = iterable.first;
* iterable.skip(1).forEach((element) {
* value = combine(value, element);
* });
* return value;
*
* Example of calculating the sum of an iterable:
*
* iterable.reduce((value, element) => value + element);
*
*/
E reduce(E combine(E value, E element)) {
Iterator<E> iterator = this.iterator;
if (!iterator.moveNext()) {
throw IterableElementError.noElement();
}
E value = iterator.current;
while (iterator.moveNext()) {
value = combine(value, iterator.current);
}
return value;
}
/**
* Reduces a collection to a single value by iteratively combining each
* element of the collection with an existing value
*
* Uses [initialValue] as the initial value,
* then iterates through the elements and updates the value with
* each element using the [combine] function, as if by:
*
* var value = initialValue;
* for (E element in this) {
* value = combine(value, element);
* }
* return value;
*
* Example of calculating the sum of an iterable:
*
* iterable.fold(0, (prev, element) => prev + element);
*
*/
T fold<T>(T initialValue, T combine(T previousValue, E element)) {
var value = initialValue;
for (E element in this) value = combine(value, element);
return value;
}
/**
* Checks whether every element of this iterable satisfies [test].
*
* Checks every element in iteration order, and returns `false` if
* any of them make [test] return `false`, otherwise returns `true`.
*/
bool every(bool test(E element)) {
for (E element in this) {
if (!test(element)) return false;
}
return true;
}
/**
* Converts each element to a [String] and concatenates the strings.
*
* Iterates through elements of this iterable,
* converts each one to a [String] by calling [Object.toString],
* and then concatenates the strings, with the
* [separator] string interleaved between the elements.
*/
String join([String separator = ""]) {
Iterator<E> iterator = this.iterator;
if (!iterator.moveNext()) return "";
StringBuffer buffer = StringBuffer();
if (separator == null || separator == "") {
do {
buffer.write(iterator.current.toString());
} while (iterator.moveNext());
} else {
buffer.write(iterator.current.toString());
while (iterator.moveNext()) {
buffer.write(separator);
buffer.write(iterator.current.toString());
}
}
return buffer.toString();
}
/**
* Checks whether any element of this iterable satisfies [test].
*
* Checks every element in iteration order, and returns `true` if
* any of them make [test] return `true`, otherwise returns false.
*/
bool any(bool test(E element)) {
for (E element in this) {
if (test(element)) return true;
}
return false;
}
/**
* Creates a [List] containing the elements of this [Iterable].
*
* The elements are in iteration order.
* The list is fixed-length if [growable] is false.
*/
List<E> toList({bool growable = true}) {
return List<E>.of(this, growable: growable);
}
/**
* Creates a [Set] containing the same elements as this iterable.
*
* The set may contain fewer elements than the iterable,
* if the iterable contains an element more than once,
* or it contains one or more elements that are equal.
* The order of the elements in the set is not guaranteed to be the same
* as for the iterable.
*/
Set<E> toSet() => Set<E>.of(this);
/**
* Returns the number of elements in [this].
*
* Counting all elements may involve iterating through all elements and can
* therefore be slow.
* Some iterables have a more efficient way to find the number of elements.
*/
int get length {
assert(this is! EfficientLengthIterable);
int count = 0;
Iterator it = iterator;
while (it.moveNext()) {
count++;
}
return count;
}
/**
* Returns `true` if there are no elements in this collection.
*
* May be computed by checking if `iterator.moveNext()` returns `false`.
*/
bool get isEmpty => !iterator.moveNext();
/**
* Returns true if there is at least one element in this collection.
*
* May be computed by checking if `iterator.moveNext()` returns `true`.
*/
bool get isNotEmpty => !isEmpty;
/**
* Returns a lazy iterable of the [count] first elements of this iterable.
*
* The returned `Iterable` may contain fewer than `count` elements, if `this`
* contains fewer than `count` elements.
*
* The elements can be computed by stepping through [iterator] until [count]
* elements have been seen.
*
* The `count` must not be negative.
*/
Iterable<E> take(int count) {
return TakeIterable<E>(this, count);
}
/**
* Returns a lazy iterable of the leading elements satisfying [test].
*
* The filtering happens lazily. Every new iterator of the returned
* iterable starts iterating over the elements of `this`.
*
* The elements can be computed by stepping through [iterator] until an
* element is found where `test(element)` is false. At that point,
* the returned iterable stops (its `moveNext()` returns false).
*/
Iterable<E> takeWhile(bool test(E value)) {
return TakeWhileIterable<E>(this, test);
}
/**
* Returns an [Iterable] that provides all but the first [count] elements.
*
* When the returned iterable is iterated, it starts iterating over `this`,
* first skipping past the initial [count] elements.
* If `this` has fewer than `count` elements, then the resulting Iterable is
* empty.
* After that, the remaining elements are iterated in the same order as
* in this iterable.
*
* Some iterables may be able to find later elements without first iterating
* through earlier elements, for example when iterating a [List].
* Such iterables are allowed to ignore the initial skipped elements.
*
* The [count] must not be negative.
*/
Iterable<E> skip(int count) {
return SkipIterable<E>(this, count);
}
/**
* Returns an `Iterable` that skips leading elements while [test] is satisfied.
*
* The filtering happens lazily. Every new [Iterator] of the returned
* iterable iterates over all elements of `this`.
*
* The returned iterable provides elements by iterating this iterable,
* but skipping over all initial elements where `test(element)` returns
* true. If all elements satisfy `test` the resulting iterable is empty,
* otherwise it iterates the remaining elements in their original order,
* starting with the first element for which `test(element)` returns `false`.
*/
Iterable<E> skipWhile(bool test(E value)) {
return SkipWhileIterable<E>(this, test);
}
/**
* Returns the first element.
*
* Throws a [StateError] if `this` is empty.
* Otherwise returns the first element in the iteration order,
* equivalent to `this.elementAt(0)`.
*/
E get first {
Iterator<E> it = iterator;
if (!it.moveNext()) {
throw IterableElementError.noElement();
}
return it.current;
}
/**
* Returns the last element.
*
* Throws a [StateError] if `this` is empty.
* Otherwise may iterate through the elements and returns the last one
* seen.
* Some iterables may have more efficient ways to find the last element
* (for example a list can directly access the last element,
* without iterating through the previous ones).
*/
E get last {
Iterator<E> it = iterator;
if (!it.moveNext()) {
throw IterableElementError.noElement();
}
E result;
do {
result = it.current;
} while (it.moveNext());
return result;
}
/**
* Checks that this iterable has only one element, and returns that element.
*
* Throws a [StateError] if `this` is empty or has more than one element.
*/
E get single {
Iterator<E> it = iterator;
if (!it.moveNext()) throw IterableElementError.noElement();
E result = it.current;
if (it.moveNext()) throw IterableElementError.tooMany();
return result;
}
/**
* Returns the first element that satisfies the given predicate [test].
*
* Iterates through elements and returns the first to satisfy [test].
*
* If no element satisfies [test], the result of invoking the [orElse]
* function is returned.
* If [orElse] is omitted, it defaults to throwing a [StateError].
*/
E firstWhere(bool test(E element), {E orElse()?}) {
for (E element in this) {
if (test(element)) return element;
}
if (orElse != null) return orElse();
throw IterableElementError.noElement();
}
/**
* Returns the last element that satisfies the given predicate [test].
*
* An iterable that can access its elements directly may check its
* elements in any order (for example a list starts by checking the
* last element and then moves towards the start of the list).
* The default implementation iterates elements in iteration order,
* checks `test(element)` for each,
* and finally returns that last one that matched.
*
* If no element satisfies [test], the result of invoking the [orElse]
* function is returned.
* If [orElse] is omitted, it defaults to throwing a [StateError].
*/
E lastWhere(bool test(E element), {E orElse()?}) {
late E result;
bool foundMatching = false;
for (E element in this) {
if (test(element)) {
result = element;
foundMatching = true;
}
}
if (foundMatching) return result;
if (orElse != null) return orElse();
throw IterableElementError.noElement();
}
/**
* Returns the single element that satisfies [test].
*
* Checks elements to see if `test(element)` returns true.
* If exactly one element satisfies [test], that element is returned.
* If more than one matching element is found, throws [StateError].
* If no matching element is found, returns the result of [orElse].
* If [orElse] is omitted, it defaults to throwing a [StateError].
*/
E singleWhere(bool test(E element), {E orElse()?}) {
late E result;
bool foundMatching = false;
for (E element in this) {
if (test(element)) {
if (foundMatching) {
throw IterableElementError.tooMany();
}
result = element;
foundMatching = true;
}
}
if (foundMatching) return result;
if (orElse != null) return orElse();
throw IterableElementError.noElement();
}
/**
* Returns the [index]th element.
*
* The [index] must be non-negative and less than [length].
* Index zero represents the first element (so `iterable.elementAt(0)` is
* equivalent to `iterable.first`).
*
* May iterate through the elements in iteration order, ignoring the
* first [index] elements and then returning the next.
* Some iterables may have a more efficient way to find the element.
*/
E elementAt(int index) {
RangeError.checkNotNegative(index, "index");
int elementIndex = 0;
for (E element in this) {
if (index == elementIndex) return element;
elementIndex++;
}
throw RangeError.index(index, this, "index", null, elementIndex);
}
/**
* Returns a string representation of (some of) the elements of `this`.
*
* Elements are represented by their own `toString` results.
*
* The default representation always contains the first three elements.
* If there are less than a hundred elements in the iterable, it also
* contains the last two elements.
*
* If the resulting string isn't above 80 characters, more elements are
* included from the start of the iterable.
*
* The conversion may omit calling `toString` on some elements if they
* are known to not occur in the output, and it may stop iterating after
* a hundred elements.
*/
String toString() => IterableBase.iterableToShortString(this, '(', ')');
}
class _GeneratorIterable<E> extends ListIterable<E> {
/// The length of the generated iterable.
final int length;
/// The function mapping indices to values.
final E Function(int) _generator;
/// Creates the generated iterable.
///
/// If [generator] is `null`, it is checked that `int` is assignable to [E].
_GeneratorIterable(this.length, E generator(int index)?)
: // The `as` below is used as check to make sure that `int` is assignable
// to [E].
_generator = generator ?? (_id as E Function(int));
E elementAt(int index) {
RangeError.checkValidIndex(index, this);
return _generator(index);
}
/// Helper function used as default _generator function.
static int _id(int n) => n;
}
/**
* An [Iterator] that allows moving backwards as well as forwards.
*/
abstract class BidirectionalIterator<E> implements Iterator<E> {
/**
* Move back to the previous element.
*
* Returns true and updates [current] if successful. Returns false
* and updates [current] to an implementation defined state if there is no
* previous element
*/
bool movePrevious();
}