/
list.dart
722 lines (680 loc) · 24.1 KB
/
list.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
712
713
714
715
716
717
718
719
720
721
722
// 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.core;
/**
* An indexable collection of objects with a length.
*
* Subclasses of this class implement different kinds of lists.
* The most common kinds of lists are:
*
* * Fixed-length list.
* An error occurs when attempting to use operations
* that can change the length of the list.
*
* * Growable list. Full implementation of the API defined in this class.
*
* The default growable list, as returned by `new List()` or `[]`, keeps
* an internal buffer, and grows that buffer when necessary. This guarantees
* that a sequence of [add] operations will each execute in amortized constant
* time. Setting the length directly may take time proportional to the new
* length, and may change the internal capacity so that a following add
* operation will need to immediately increase the buffer capacity.
* Other list implementations may have different performance behavior.
*
* The following code illustrates that some List implementations support
* only a subset of the API.
*
* List<int> fixedLengthList = new List(5);
* fixedLengthList.length = 0; // Error
* fixedLengthList.add(499); // Error
* fixedLengthList[0] = 87;
* List<int> growableList = [1, 2];
* growableList.length = 0;
* growableList.add(499);
* growableList[0] = 87;
*
* Lists are [Iterable]. Iteration occurs over values in index order. Changing
* the values does not affect iteration, but changing the valid
* indices—that is, changing the list's length—between iteration
* steps causes a [ConcurrentModificationError]. This means that only growable
* lists can throw ConcurrentModificationError. If the length changes
* temporarily and is restored before continuing the iteration, the iterator
* does not detect it.
*
* It is generally not allowed to modify the list's length (adding or removing
* elements) while an operation on the list is being performed,
* for example during a call to [forEach] or [sort].
* Changing the list's length while it is being iterated, either by iterating it
* directly or through iterating an [Iterable] that is backed by the list, will
* break the iteration.
*/
abstract class List<E> implements EfficientLengthIterable<E> {
/**
* Creates a list of the given length.
*
* The created list is fixed-length if [length] is provided.
*
* List fixedLengthList = new List(3);
* fixedLengthList.length; // 3
* fixedLengthList.length = 1; // Error
*
* The list has length 0 and is growable if [length] is omitted.
*
* List growableList = new List();
* growableList.length; // 0;
* growableList.length = 3;
*
* To create a growable list with a given length, just assign the length
* right after creation:
*
* List growableList = new List()..length = 500;
*
* The [length] must not be negative or null, if it is provided.
*/
external factory List([int length]);
/**
* Creates a list of the given length with [fill] at each position.
*
* The [length] must be a non-negative integer.
*
* Example:
* ```dart
* new List<int>.filled(3, 0, growable: true); // [0, 0, 0]
* ```
*
* The created list is fixed-length if [growable] is false (the default)
* and growable if [growable] is true.
* If the list is growable, changing its length will not initialize new
* entries with [fill].
* After being created and filled, the list is no different from any other
* growable or fixed-length list created using [List].
*
* All elements of the returned list share the same [fill] value.
* ```
* var shared = new List.filled(3, []);
* shared[0].add(499);
* print(shared); // => [[499], [499], [499]]
* ```
*
* You can use [List.generate] to create a list with a new object at
* each position.
* ```
* var unique = new List.generate(3, (_) => []);
* unique[0].add(499);
* print(unique); // => [[499], [], []]
* ```
*/
external factory List.filled(int length, E fill, {bool growable = false});
/**
* Creates a list containing all [elements].
*
* The [Iterator] of [elements] provides the order of the elements.
*
* All the [elements] should be instances of [E].
* The `elements` iterable itself may have any element type, so this
* constructor can be used to down-cast a `List`, for example as:
* ```dart
* List<SuperType> superList = ...;
* List<SubType> subList =
* new List<SubType>.from(superList.whereType<SubType>());
* ```
*
* This constructor creates a growable list when [growable] is true;
* otherwise, it returns a fixed-length list.
*/
external factory List.from(Iterable elements, {bool growable = true});
/**
* Creates a list from [elements].
*
* The [Iterator] of [elements] provides the order of the elements.
*
* This constructor creates a growable list when [growable] is true;
* otherwise, it returns a fixed-length list.
*/
factory List.of(Iterable<E> elements, {bool growable = true}) =>
List<E>.from(elements, growable: growable);
/**
* Generates a list of values.
*
* Creates a list with [length] positions and fills it with values created by
* calling [generator] for each index in the range `0` .. `length - 1`
* in increasing order.
*
* new List<int>.generate(3, (int index) => index * index); // [0, 1, 4]
*
* The created list is fixed-length unless [growable] is true.
*/
factory List.generate(int length, E generator(int index),
{bool growable = true}) {
List<E> result;
if (growable) {
result = <E>[]..length = length;
} else {
result = List<E>(length);
}
for (int i = 0; i < length; i++) {
result[i] = generator(i);
}
return result;
}
/**
* Creates an unmodifiable list containing all [elements].
*
* The [Iterator] of [elements] provides the order of the elements.
*
* An unmodifiable list cannot have its length or elements changed.
* If the elements are themselves immutable, then the resulting list
* is also immutable.
*/
external factory List.unmodifiable(Iterable elements);
/**
* Adapts [source] to be a `List<T>`.
*
* Any time the list would produce an element that is not a [T],
* the element access will throw.
*
* Any time a [T] value is attempted stored into the adapted list,
* the store will throw unless the value is also an instance of [S].
*
* If all accessed elements of [source] are actually instances of [T],
* and if all elements stored into the returned list are actually instance
* of [S],
* then the returned list can be used as a `List<T>`.
*/
static List<T> castFrom<S, T>(List<S> source) => CastList<S, T>(source);
/**
* Copy a range of one list into another list.
*
* This is a utility function that can be used to implement methods like
* [setRange].
*
* The range from [start] to [end] must be a valid range of [source],
* and there must be room for `end - start` elements from position [at].
* If [start] is omitted, it defaults to zero.
* If [end] is omitted, it defaults to [source.length].
*
* If [source] and [target] is the same list, overlapping source and target
* ranges are respected so that the target range ends up containing the
* initial content of the source range.
* Otherwise the order of element copying is not guaranteed.
*/
static void copyRange<T>(List<T> target, int at, List<T> source,
[int start, int end]) {
start ??= 0;
end = RangeError.checkValidRange(start, end, source.length);
int length = end - start;
if (target.length < at + length) {
throw ArgumentError.value(target, "target",
"Not big enough to hold $length elements at position $at");
}
if (!identical(source, target) || start >= at) {
for (int i = 0; i < length; i++) {
target[at + i] = source[start + i];
}
} else {
for (int i = length; --i >= 0;) {
target[at + i] = source[start + i];
}
}
}
/**
* Write the elements of an iterable into a list.
*
* This is a utility function that can be used to implement methods like
* [setAll].
*
* The elements of [source] are written into [target] from position [at].
* The [source] must not contain more elements after writing the last
* position of [target].
*
* If the source is a list, the [copyRange] function is likely to be more
* efficient.
*/
static void writeIterable<T>(List<T> target, int at, Iterable<T> source) {
RangeError.checkValueInInterval(at, 0, target.length, "at");
int index = at;
int targetLength = target.length;
for (var element in source) {
if (index == targetLength) {
throw IndexError(targetLength, target);
}
target[index] = element;
index++;
}
}
/**
* Returns a view of this list as a list of [R] instances.
*
* If this list contains only instances of [R], all read operations
* will work correctly. If any operation tries to access an element
* that is not an instance of [R], the access will throw instead.
*
* Elements added to the list (e.g., by using [add] or [addAll])
* must be instance of [R] to be valid arguments to the adding function,
* and they must be instances of [E] as well to be accepted by
* this list as well.
*
* Typically implemented as `List.castFrom<E, R>(this)`.
*/
List<R> cast<R>();
/**
* Returns the object at the given [index] in the list
* or throws a [RangeError] if [index] is out of bounds.
*/
E operator [](int index);
/**
* Sets the value at the given [index] in the list to [value]
* or throws a [RangeError] if [index] is out of bounds.
*/
void operator []=(int index, E value);
/**
* Updates the first position of the list to contain [value].
*
* Equivalent to `theList[0] = value;`.
*
* The list must be non-empty.
*/
void set first(E value);
/**
* Updates the last position of the list to contain [value].
*
* Equivalent to `theList[theList.length - 1] = value;`.
*
* The list must be non-empty.
*/
void set last(E value);
/**
* Returns the number of objects in this list.
*
* The valid indices for a list are `0` through `length - 1`.
*/
int get length;
/**
* Changes the length of this list.
*
* If [newLength] is greater than
* the current length, entries are initialized to [:null:].
*
* Throws an [UnsupportedError] if the list is fixed-length.
*/
set length(int newLength);
/**
* Adds [value] to the end of this list,
* extending the length by one.
*
* Throws an [UnsupportedError] if the list is fixed-length.
*/
void add(E value);
/**
* Appends all objects of [iterable] to the end of this list.
*
* Extends the length of the list by the number of objects in [iterable].
* Throws an [UnsupportedError] if this list is fixed-length.
*/
void addAll(Iterable<E> iterable);
/**
* Returns an [Iterable] of the objects in this list in reverse order.
*/
Iterable<E> get reversed;
/**
* Sorts this list according to the order specified by the [compare] function.
*
* The [compare] function must act as a [Comparator].
*
* List<String> numbers = ['two', 'three', 'four'];
* // Sort from shortest to longest.
* numbers.sort((a, b) => a.length.compareTo(b.length));
* print(numbers); // [two, four, three]
*
* The default List implementations use [Comparable.compare] if
* [compare] is omitted.
*
* List<int> nums = [13, 2, -11];
* nums.sort();
* print(nums); // [-11, 2, 13]
*
* A [Comparator] may compare objects as equal (return zero), even if they
* are distinct objects.
* The sort function is not guaranteed to be stable, so distinct objects
* that compare as equal may occur in any order in the result:
*
* List<String> numbers = ['one', 'two', 'three', 'four'];
* numbers.sort((a, b) => a.length.compareTo(b.length));
* print(numbers); // [one, two, four, three] OR [two, one, four, three]
*/
void sort([int compare(E a, E b)]);
/**
* Shuffles the elements of this list randomly.
*/
void shuffle([Random random]);
/**
* Returns the first index of [element] in this list.
*
* Searches the list from index [start] to the end of the list.
* The first time an object [:o:] is encountered so that [:o == element:],
* the index of [:o:] is returned.
*
* List<String> notes = ['do', 're', 'mi', 're'];
* notes.indexOf('re'); // 1
* notes.indexOf('re', 2); // 3
*
* Returns -1 if [element] is not found.
*
* notes.indexOf('fa'); // -1
*/
int indexOf(E element, [int start = 0]);
/**
* Returns the first index in the list that satisfies the provided [test].
*
* Searches the list from index [start] to the end of the list.
* The first time an object `o` is encountered so that `test(o)` is true,
* the index of `o` is returned.
*
* ```
* List<String> notes = ['do', 're', 'mi', 're'];
* notes.indexWhere((note) => note.startsWith('r')); // 1
* notes.indexWhere((note) => note.startsWith('r'), 2); // 3
* ```
*
* Returns -1 if [element] is not found.
* ```
* notes.indexWhere((note) => note.startsWith('k')); // -1
* ```
*/
int indexWhere(bool test(E element), [int start = 0]);
/**
* Returns the last index in the list that satisfies the provided [test].
*
* Searches the list from index [start] to 0.
* The first time an object `o` is encountered so that `test(o)` is true,
* the index of `o` is returned.
*
* ```
* List<String> notes = ['do', 're', 'mi', 're'];
* notes.lastIndexWhere((note) => note.startsWith('r')); // 3
* notes.lastIndexWhere((note) => note.startsWith('r'), 2); // 1
* ```
*
* Returns -1 if [element] is not found.
* ```
* notes.lastIndexWhere((note) => note.startsWith('k')); // -1
* ```
*/
int lastIndexWhere(bool test(E element), [int start]);
/**
* Returns the last index of [element] in this list.
*
* Searches the list backwards from index [start] to 0.
*
* The first time an object [:o:] is encountered so that [:o == element:],
* the index of [:o:] is returned.
*
* List<String> notes = ['do', 're', 'mi', 're'];
* notes.lastIndexOf('re', 2); // 1
*
* If [start] is not provided, this method searches from the end of the
* list./Returns
*
* notes.lastIndexOf('re'); // 3
*
* Returns -1 if [element] is not found.
*
* notes.lastIndexOf('fa'); // -1
*/
int lastIndexOf(E element, [int start]);
/**
* Removes all objects from this list;
* the length of the list becomes zero.
*
* Throws an [UnsupportedError], and retains all objects, if this
* is a fixed-length list.
*/
void clear();
/**
* Inserts the object at position [index] in this list.
*
* This increases the length of the list by one and shifts all objects
* at or after the index towards the end of the list.
*
* The list must be growable.
* The [index] value must be non-negative and no greater than [length].
*/
void insert(int index, E element);
/**
* Inserts all objects of [iterable] at position [index] in this list.
*
* This increases the length of the list by the length of [iterable] and
* shifts all later objects towards the end of the list.
*
* The list must be growable.
* The [index] value must be non-negative and no greater than [length].
*/
void insertAll(int index, Iterable<E> iterable);
/**
* Overwrites objects of `this` with the objects of [iterable], starting
* at position [index] in this list.
*
* List<String> list = ['a', 'b', 'c'];
* list.setAll(1, ['bee', 'sea']);
* list.join(', '); // 'a, bee, sea'
*
* This operation does not increase the length of `this`.
*
* The [index] must be non-negative and no greater than [length].
*
* The [iterable] must not have more elements than what can fit from [index]
* to [length].
*
* If `iterable` is based on this list, its values may change /during/ the
* `setAll` operation.
*/
void setAll(int index, Iterable<E> iterable);
/**
* Removes the first occurrence of [value] from this list.
*
* Returns true if [value] was in the list, false otherwise.
*
* List<String> parts = ['head', 'shoulders', 'knees', 'toes'];
* parts.remove('head'); // true
* parts.join(', '); // 'shoulders, knees, toes'
*
* The method has no effect if [value] was not in the list.
*
* // Note: 'head' has already been removed.
* parts.remove('head'); // false
* parts.join(', '); // 'shoulders, knees, toes'
*
* An [UnsupportedError] occurs if the list is fixed-length.
*/
bool remove(Object value);
/**
* Removes the object at position [index] from this list.
*
* This method reduces the length of `this` by one and moves all later objects
* down by one position.
*
* Returns the removed object.
*
* The [index] must be in the range `0 ≤ index < length`.
*
* Throws an [UnsupportedError] if this is a fixed-length list. In that case
* the list is not modified.
*/
E removeAt(int index);
/**
* Pops and returns the last object in this list.
*
* The list must not be empty.
*
* Throws an [UnsupportedError] if this is a fixed-length list.
*/
E removeLast();
/**
* Removes all objects from this list that satisfy [test].
*
* An object [:o:] satisfies [test] if [:test(o):] is true.
*
* List<String> numbers = ['one', 'two', 'three', 'four'];
* numbers.removeWhere((item) => item.length == 3);
* numbers.join(', '); // 'three, four'
*
* Throws an [UnsupportedError] if this is a fixed-length list.
*/
void removeWhere(bool test(E element));
/**
* Removes all objects from this list that fail to satisfy [test].
*
* An object [:o:] satisfies [test] if [:test(o):] is true.
*
* List<String> numbers = ['one', 'two', 'three', 'four'];
* numbers.retainWhere((item) => item.length == 3);
* numbers.join(', '); // 'one, two'
*
* Throws an [UnsupportedError] if this is a fixed-length list.
*/
void retainWhere(bool test(E element));
/**
* Returns the concatenation of this list and [other].
*
* Returns a new list containing the elements of this list followed by
* the elements of [other].
*
* The default behavior is to return a normal growable list.
* Some list types may choose to return a list of the same type as themselves
* (see [Uint8List.+]);
*/
List<E> operator +(List<E> other);
/**
* Returns a new list containing the elements between [start] and [end].
*
* The new list is a `List<E>` containing the elements of this list at
* positions greater than or equal to [start] and less than [end] in the same
* order as they occur in this list.
*
* ```dart
* var colors = ["red", "green", "blue", "orange", "pink"];
* print(colors.sublist(1, 3)); // [green, blue]
* ```
*
* If [end] is omitted, it defaults to the [length] of this list.
*
* ```dart
* print(colors.sublist(1)); // [green, blue, orange, pink]
* ```
*
* The `start` and `end` positions must satisfy the relations
* 0 ≤ `start` ≤ `end` ≤ `this.length`
* If `end` is equal to `start`, then the returned list is empty.
*/
List<E> sublist(int start, [int end]);
/**
* Returns an [Iterable] that iterates over the objects in the range
* [start] inclusive to [end] exclusive.
*
* The provided range, given by [start] and [end], must be valid at the time
* of the call.
*
* A range from [start] to [end] is valid if `0 <= start <= end <= len`, where
* `len` is this list's `length`. The range starts at `start` and has length
* `end - start`. An empty range (with `end == start`) is valid.
*
* The returned [Iterable] behaves like `skip(start).take(end - start)`.
* That is, it does *not* throw if this list changes size.
*
* List<String> colors = ['red', 'green', 'blue', 'orange', 'pink'];
* Iterable<String> range = colors.getRange(1, 4);
* range.join(', '); // 'green, blue, orange'
* colors.length = 3;
* range.join(', '); // 'green, blue'
*/
Iterable<E> getRange(int start, int end);
/**
* Copies the objects of [iterable], skipping [skipCount] objects first,
* into the range [start], inclusive, to [end], exclusive, of the list.
*
* List<int> list1 = [1, 2, 3, 4];
* List<int> list2 = [5, 6, 7, 8, 9];
* // Copies the 4th and 5th items in list2 as the 2nd and 3rd items
* // of list1.
* list1.setRange(1, 3, list2, 3);
* list1.join(', '); // '1, 8, 9, 4'
*
* The provided range, given by [start] and [end], must be valid.
* A range from [start] to [end] is valid if `0 <= start <= end <= len`, where
* `len` is this list's `length`. The range starts at `start` and has length
* `end - start`. An empty range (with `end == start`) is valid.
*
* The [iterable] must have enough objects to fill the range from `start`
* to `end` after skipping [skipCount] objects.
*
* If `iterable` is this list, the operation copies the elements
* originally in the range from `skipCount` to `skipCount + (end - start)` to
* the range `start` to `end`, even if the two ranges overlap.
*
* If `iterable` depends on this list in some other way, no guarantees are
* made.
*/
void setRange(int start, int end, Iterable<E> iterable, [int skipCount = 0]);
/**
* Removes the objects in the range [start] inclusive to [end] exclusive.
*
* The provided range, given by [start] and [end], must be valid.
* A range from [start] to [end] is valid if `0 <= start <= end <= len`, where
* `len` is this list's `length`. The range starts at `start` and has length
* `end - start`. An empty range (with `end == start`) is valid.
*
* Throws an [UnsupportedError] if this is a fixed-length list. In that case
* the list is not modified.
*/
void removeRange(int start, int end);
/**
* Sets the objects in the range [start] inclusive to [end] exclusive
* to the given [fillValue].
*
* The provided range, given by [start] and [end], must be valid.
* A range from [start] to [end] is valid if `0 <= start <= end <= len`, where
* `len` is this list's `length`. The range starts at `start` and has length
* `end - start`. An empty range (with `end == start`) is valid.
*
* Example:
* ```dart
* List<int> list = new List(3);
* list.fillRange(0, 2, 1);
* print(list); // [1, 1, null]
* ```
*
*/
void fillRange(int start, int end, [E fillValue]);
/**
* Removes the objects in the range [start] inclusive to [end] exclusive
* and inserts the contents of [replacement] in its place.
*
* List<int> list = [1, 2, 3, 4, 5];
* list.replaceRange(1, 4, [6, 7]);
* list.join(', '); // '1, 6, 7, 5'
*
* The provided range, given by [start] and [end], must be valid.
* A range from [start] to [end] is valid if `0 <= start <= end <= len`, where
* `len` is this list's `length`. The range starts at `start` and has length
* `end - start`. An empty range (with `end == start`) is valid.
*
* This method does not work on fixed-length lists, even when [replacement]
* has the same number of elements as the replaced range. In that case use
* [setRange] instead.
*/
void replaceRange(int start, int end, Iterable<E> replacement);
/**
* Returns an unmodifiable [Map] view of `this`.
*
* The map uses the indices of this list as keys and the corresponding objects
* as values. The `Map.keys` [Iterable] iterates the indices of this list
* in numerical order.
*
* List<String> words = ['fee', 'fi', 'fo', 'fum'];
* Map<int, String> map = words.asMap();
* map[0] + map[1]; // 'feefi';
* map.keys.toList(); // [0, 1, 2, 3]
*/
Map<int, E> asMap();
}