-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
iterable.dart
400 lines (354 loc) · 11.7 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
// Copyright (c) 2012, 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.collection;
/// This [Iterable] mixin implements all [Iterable] members except `iterator`.
///
/// All other methods are implemented in terms of `iterator`.
abstract class IterableMixin<E> implements Iterable<E> {
// This class has methods copied verbatim into:
// - IterableBase
// - SetMixin
// If changing a method here, also change the other copies.
Iterable<R> cast<R>() => Iterable.castFrom<E, R>(this);
Iterable<T> map<T>(T f(E element)) => MappedIterable<E, T>(this, f);
Iterable<E> where(bool f(E element)) => WhereIterable<E>(this, f);
Iterable<T> whereType<T>() => WhereTypeIterable<T>(this);
Iterable<T> expand<T>(Iterable<T> f(E element)) =>
ExpandIterable<E, T>(this, f);
Iterable<E> followedBy(Iterable<E> other) {
// Type workaround because IterableMixin<E> doesn't promote
// to EfficientLengthIterable<E>.
Iterable<E> self = this;
if (self is EfficientLengthIterable<E>) {
return FollowedByIterable<E>.firstEfficient(self, other);
}
return FollowedByIterable<E>(this, other);
}
bool contains(Object? element) {
for (E e in this) {
if (e == element) return true;
}
return false;
}
void forEach(void f(E element)) {
for (E element in this) f(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;
}
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;
}
bool every(bool f(E element)) {
for (E element in this) {
if (!f(element)) return false;
}
return true;
}
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}");
} while (iterator.moveNext());
} else {
buffer.write("${iterator.current}");
while (iterator.moveNext()) {
buffer.write(separator);
buffer.write("${iterator.current}");
}
}
return buffer.toString();
}
bool any(bool test(E element)) {
for (E element in this) {
if (test(element)) return true;
}
return false;
}
List<E> toList({bool growable = true}) =>
List<E>.from(this, growable: growable);
Set<E> toSet() => Set<E>.from(this);
int get length {
assert(this is! EfficientLengthIterable);
int count = 0;
Iterator it = iterator;
while (it.moveNext()) {
count++;
}
return count;
}
bool get isEmpty => !iterator.moveNext();
bool get isNotEmpty => !isEmpty;
Iterable<E> take(int count) {
return TakeIterable<E>(this, count);
}
Iterable<E> takeWhile(bool test(E value)) {
return TakeWhileIterable<E>(this, test);
}
Iterable<E> skip(int count) {
return SkipIterable<E>(this, count);
}
Iterable<E> skipWhile(bool test(E value)) {
return SkipWhileIterable<E>(this, test);
}
E get first {
Iterator<E> it = iterator;
if (!it.moveNext()) {
throw IterableElementError.noElement();
}
return it.current;
}
E get last {
Iterator<E> it = iterator;
if (!it.moveNext()) {
throw IterableElementError.noElement();
}
E result;
do {
result = it.current;
} while (it.moveNext());
return result;
}
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;
}
E firstWhere(bool test(E value), {E Function()? orElse}) {
for (E element in this) {
if (test(element)) return element;
}
if (orElse != null) return orElse();
throw IterableElementError.noElement();
}
E lastWhere(bool test(E value), {E Function()? 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();
}
E singleWhere(bool test(E element), {E Function()? 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();
}
E elementAt(int index) {
ArgumentError.checkNotNull(index, "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);
}
String toString() => IterableBase.iterableToShortString(this, '(', ')');
}
/// Base class for implementing [Iterable].
///
/// This class implements all methods of [Iterable], except [Iterable.iterator],
/// in terms of `iterator`.
abstract class IterableBase<E> extends Iterable<E> {
const IterableBase();
/// Convert an `Iterable` to a string like [IterableBase.toString].
///
/// Allows using other delimiters than '(' and ')'.
///
/// Handles circular references where converting one of the elements
/// to a string ends up converting [iterable] to a string again.
static String iterableToShortString(Iterable iterable,
[String leftDelimiter = '(', String rightDelimiter = ')']) {
if (_isToStringVisiting(iterable)) {
if (leftDelimiter == "(" && rightDelimiter == ")") {
// Avoid creating a new string in the "common" case.
return "(...)";
}
return "$leftDelimiter...$rightDelimiter";
}
List<String> parts = <String>[];
_toStringVisiting.add(iterable);
try {
_iterablePartsToStrings(iterable, parts);
} finally {
assert(identical(_toStringVisiting.last, iterable));
_toStringVisiting.removeLast();
}
return (StringBuffer(leftDelimiter)
..writeAll(parts, ", ")
..write(rightDelimiter))
.toString();
}
/// Converts an `Iterable` to a string.
///
/// Converts each elements to a string, and separates the results by ", ".
/// Then wraps the result in [leftDelimiter] and [rightDelimiter].
///
/// Unlike [iterableToShortString], this conversion doesn't omit any
/// elements or puts any limit on the size of the result.
///
/// Handles circular references where converting one of the elements
/// to a string ends up converting [iterable] to a string again.
static String iterableToFullString(Iterable iterable,
[String leftDelimiter = '(', String rightDelimiter = ')']) {
if (_isToStringVisiting(iterable)) {
return "$leftDelimiter...$rightDelimiter";
}
StringBuffer buffer = StringBuffer(leftDelimiter);
_toStringVisiting.add(iterable);
try {
buffer.writeAll(iterable, ", ");
} finally {
assert(identical(_toStringVisiting.last, iterable));
_toStringVisiting.removeLast();
}
buffer.write(rightDelimiter);
return buffer.toString();
}
}
/// A collection used to identify cyclic lists during toString() calls.
final List<Object> _toStringVisiting = [];
/// Check if we are currently visiting `o` in a toString call.
bool _isToStringVisiting(Object o) {
for (int i = 0; i < _toStringVisiting.length; i++) {
if (identical(o, _toStringVisiting[i])) return true;
}
return false;
}
/// Convert elements of [iterable] to strings and store them in [parts].
void _iterablePartsToStrings(Iterable<Object?> iterable, List<String> parts) {
/*
* This is the complicated part of [iterableToShortString].
* It is extracted as a separate function to avoid having too much code
* inside the try/finally.
*/
/// Try to stay below this many characters.
const int lengthLimit = 80;
/// Always at least this many elements at the start.
const int headCount = 3;
/// Always at least this many elements at the end.
const int tailCount = 2;
/// Stop iterating after this many elements. Iterables can be infinite.
const int maxCount = 100;
// Per entry length overhead. It's for ", " for all after the first entry,
// and for "(" and ")" for the initial entry. By pure luck, that's the same
// number.
const int overhead = 2;
const int ellipsisSize = 3; // "...".length.
int length = 0;
int count = 0;
Iterator<Object?> it = iterable.iterator;
// Initial run of elements, at least headCount, and then continue until
// passing at most lengthLimit characters.
while (length < lengthLimit || count < headCount) {
if (!it.moveNext()) return;
String next = "${it.current}";
parts.add(next);
length += next.length + overhead;
count++;
}
String penultimateString;
String ultimateString;
// Find last two elements. One or more of them may already be in the
// parts array. Include their length in `length`.
if (!it.moveNext()) {
if (count <= headCount + tailCount) return;
ultimateString = parts.removeLast();
penultimateString = parts.removeLast();
} else {
Object? penultimate = it.current;
count++;
if (!it.moveNext()) {
if (count <= headCount + 1) {
parts.add("$penultimate");
return;
}
ultimateString = "$penultimate";
penultimateString = parts.removeLast();
length += ultimateString.length + overhead;
} else {
Object? ultimate = it.current;
count++;
// Then keep looping, keeping the last two elements in variables.
assert(count < maxCount);
while (it.moveNext()) {
penultimate = ultimate;
ultimate = it.current;
count++;
if (count > maxCount) {
// If we haven't found the end before maxCount, give up.
// This cannot happen in the code above because each entry
// increases length by at least two, so there is no way to
// visit more than ~40 elements before this loop.
// Remove any surplus elements until length, including ", ...)",
// is at most lengthLimit.
while (length > lengthLimit - ellipsisSize - overhead &&
count > headCount) {
length -= parts.removeLast().length + overhead;
count--;
}
parts.add("...");
return;
}
}
penultimateString = "$penultimate";
ultimateString = "$ultimate";
length += ultimateString.length + penultimateString.length + 2 * overhead;
}
}
// If there is a gap between the initial run and the last two,
// prepare to add an ellipsis.
String? elision;
if (count > parts.length + tailCount) {
elision = "...";
length += ellipsisSize + overhead;
}
// If the last two elements were very long, and we have more than
// headCount elements in the initial run, drop some to make room for
// the last two.
while (length > lengthLimit && parts.length > headCount) {
length -= parts.removeLast().length + overhead;
if (elision == null) {
elision = "...";
length += ellipsisSize + overhead;
}
}
if (elision != null) {
parts.add(elision);
}
parts.add(penultimateString);
parts.add(ultimateString);
}