-
Notifications
You must be signed in to change notification settings - Fork 10.3k
/
Sequence.swift
1465 lines (1380 loc) · 52.3 KB
/
Sequence.swift
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
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
/// A type that supplies the values of a sequence one at a time.
///
/// The `IteratorProtocol` protocol is tightly linked with the `Sequence`
/// protocol. Sequences provide access to their elements by creating an
/// iterator, which keeps track of its iteration process and returns one
/// element at a time as it advances through the sequence.
///
/// Whenever you use a `for`-`in` loop with an array, set, or any other
/// collection or sequence, you're using that type's iterator. Swift uses a
/// sequence's or collection's iterator internally to enable the `for`-`in`
/// loop language construct.
///
/// Using a sequence's iterator directly gives you access to the same elements
/// in the same order as iterating over that sequence using a `for`-`in` loop.
/// For example, you might typically use a `for`-`in` loop to print each of
/// the elements in an array.
///
/// let animals = ["Antelope", "Butterfly", "Camel", "Dolphin"]
/// for animal in animals {
/// print(animal)
/// }
/// // Prints "Antelope"
/// // Prints "Butterfly"
/// // Prints "Camel"
/// // Prints "Dolphin"
///
/// Behind the scenes, Swift uses the `animals` array's iterator to loop over
/// the contents of the array.
///
/// var animalIterator = animals.makeIterator()
/// while let animal = animalIterator.next() {
/// print(animal)
/// }
/// // Prints "Antelope"
/// // Prints "Butterfly"
/// // Prints "Camel"
/// // Prints "Dolphin"
///
/// The call to `animals.makeIterator()` returns an instance of the array's
/// iterator. Next, the `while` loop calls the iterator's `next()` method
/// repeatedly, binding each element that is returned to `animal` and exiting
/// when the `next()` method returns `nil`.
///
/// Using Iterators Directly
/// ========================
///
/// You rarely need to use iterators directly, because a `for`-`in` loop is the
/// more idiomatic approach to traversing a sequence in Swift. Some
/// algorithms, however, may call for direct iterator use.
///
/// One example is the `reduce1(_:)` method. Similar to the `reduce(_:_:)`
/// method defined in the standard library, which takes an initial value and a
/// combining closure, `reduce1(_:)` uses the first element of the sequence as
/// the initial value.
///
/// Here's an implementation of the `reduce1(_:)` method. The sequence's
/// iterator is used directly to retrieve the initial value before looping
/// over the rest of the sequence.
///
/// extension Sequence {
/// func reduce1(
/// _ nextPartialResult: (Element, Element) -> Element
/// ) -> Element?
/// {
/// var i = makeIterator()
/// guard var accumulated = i.next() else {
/// return nil
/// }
///
/// while let element = i.next() {
/// accumulated = nextPartialResult(accumulated, element)
/// }
/// return accumulated
/// }
/// }
///
/// The `reduce1(_:)` method makes certain kinds of sequence operations
/// simpler. Here's how to find the longest string in a sequence, using the
/// `animals` array introduced earlier as an example:
///
/// let longestAnimal = animals.reduce1 { current, element in
/// if current.count > element.count {
/// return current
/// } else {
/// return element
/// }
/// }
/// print(longestAnimal)
/// // Prints "Butterfly"
///
/// Using Multiple Iterators
/// ========================
///
/// Whenever you use multiple iterators (or `for`-`in` loops) over a single
/// sequence, be sure you know that the specific sequence supports repeated
/// iteration, either because you know its concrete type or because the
/// sequence is also constrained to the `Collection` protocol.
///
/// Obtain each separate iterator from separate calls to the sequence's
/// `makeIterator()` method rather than by copying. Copying an iterator is
/// safe, but advancing one copy of an iterator by calling its `next()` method
/// may invalidate other copies of that iterator. `for`-`in` loops are safe in
/// this regard.
///
/// Adding IteratorProtocol Conformance to Your Type
/// ================================================
///
/// Implementing an iterator that conforms to `IteratorProtocol` is simple.
/// Declare a `next()` method that advances one step in the related sequence
/// and returns the current element. When the sequence has been exhausted, the
/// `next()` method returns `nil`.
///
/// For example, consider a custom `Countdown` sequence. You can initialize the
/// `Countdown` sequence with a starting integer and then iterate over the
/// count down to zero. The `Countdown` structure's definition is short: It
/// contains only the starting count and the `makeIterator()` method required
/// by the `Sequence` protocol.
///
/// struct Countdown: Sequence {
/// let start: Int
///
/// func makeIterator() -> CountdownIterator {
/// return CountdownIterator(self)
/// }
/// }
///
/// The `makeIterator()` method returns another custom type, an iterator named
/// `CountdownIterator`. The `CountdownIterator` type keeps track of both the
/// `Countdown` sequence that it's iterating and the number of times it has
/// returned a value.
///
/// struct CountdownIterator: IteratorProtocol {
/// let countdown: Countdown
/// var times = 0
///
/// init(_ countdown: Countdown) {
/// self.countdown = countdown
/// }
///
/// mutating func next() -> Int? {
/// let nextNumber = countdown.start - times
/// guard nextNumber > 0
/// else { return nil }
///
/// times += 1
/// return nextNumber
/// }
/// }
///
/// Each time the `next()` method is called on a `CountdownIterator` instance,
/// it calculates the new next value, checks to see whether it has reached
/// zero, and then returns either the number, or `nil` if the iterator is
/// finished returning elements of the sequence.
///
/// Creating and iterating over a `Countdown` sequence uses a
/// `CountdownIterator` to handle the iteration.
///
/// let threeTwoOne = Countdown(start: 3)
/// for count in threeTwoOne {
/// print("\(count)...")
/// }
/// // Prints "3..."
/// // Prints "2..."
/// // Prints "1..."
public protocol IteratorProtocol {
/// The type of element traversed by the iterator.
associatedtype Element
/// Advances to the next element and returns it, or `nil` if no next element
/// exists.
///
/// Repeatedly calling this method returns, in order, all the elements of the
/// underlying sequence. As soon as the sequence has run out of elements, all
/// subsequent calls return `nil`.
///
/// You must not call this method if any other copy of this iterator has been
/// advanced with a call to its `next()` method.
///
/// The following example shows how an iterator can be used explicitly to
/// emulate a `for`-`in` loop. First, retrieve a sequence's iterator, and
/// then call the iterator's `next()` method until it returns `nil`.
///
/// let numbers = [2, 3, 5, 7]
/// var numbersIterator = numbers.makeIterator()
///
/// while let num = numbersIterator.next() {
/// print(num)
/// }
/// // Prints "2"
/// // Prints "3"
/// // Prints "5"
/// // Prints "7"
///
/// - Returns: The next element in the underlying sequence, if a next element
/// exists; otherwise, `nil`.
mutating func next() -> Element?
}
/// A type that provides sequential, iterated access to its elements.
///
/// A sequence is a list of values that you can step through one at a time. The
/// most common way to iterate over the elements of a sequence is to use a
/// `for`-`in` loop:
///
/// let oneTwoThree = 1...3
/// for number in oneTwoThree {
/// print(number)
/// }
/// // Prints "1"
/// // Prints "2"
/// // Prints "3"
///
/// While seemingly simple, this capability gives you access to a large number
/// of operations that you can perform on any sequence. As an example, to
/// check whether a sequence includes a particular value, you can test each
/// value sequentially until you've found a match or reached the end of the
/// sequence. This example checks to see whether a particular insect is in an
/// array.
///
/// let bugs = ["Aphid", "Bumblebee", "Cicada", "Damselfly", "Earwig"]
/// var hasMosquito = false
/// for bug in bugs {
/// if bug == "Mosquito" {
/// hasMosquito = true
/// break
/// }
/// }
/// print("'bugs' has a mosquito: \(hasMosquito)")
/// // Prints "'bugs' has a mosquito: false"
///
/// The `Sequence` protocol provides default implementations for many common
/// operations that depend on sequential access to a sequence's values. For
/// clearer, more concise code, the example above could use the array's
/// `contains(_:)` method, which every sequence inherits from `Sequence`,
/// instead of iterating manually:
///
/// if bugs.contains("Mosquito") {
/// print("Break out the bug spray.")
/// } else {
/// print("Whew, no mosquitos!")
/// }
/// // Prints "Whew, no mosquitos!"
///
/// Repeated Access
/// ===============
///
/// The `Sequence` protocol makes no requirement on conforming types regarding
/// whether they will be destructively consumed by iteration. As a
/// consequence, don't assume that multiple `for`-`in` loops on a sequence
/// will either resume iteration or restart from the beginning:
///
/// for element in sequence {
/// if ... some condition { break }
/// }
///
/// for element in sequence {
/// // No defined behavior
/// }
///
/// In this case, you cannot assume either that a sequence will be consumable
/// and will resume iteration, or that a sequence is a collection and will
/// restart iteration from the first element. A conforming sequence that is
/// not a collection is allowed to produce an arbitrary sequence of elements
/// in the second `for`-`in` loop.
///
/// To establish that a type you've created supports nondestructive iteration,
/// add conformance to the `Collection` protocol.
///
/// Conforming to the Sequence Protocol
/// ===================================
///
/// Making your own custom types conform to `Sequence` enables many useful
/// operations, like `for`-`in` looping and the `contains` method, without
/// much effort. To add `Sequence` conformance to your own custom type, add a
/// `makeIterator()` method that returns an iterator.
///
/// Alternatively, if your type can act as its own iterator, implementing the
/// requirements of the `IteratorProtocol` protocol and declaring conformance
/// to both `Sequence` and `IteratorProtocol` are sufficient.
///
/// Here's a definition of a `Countdown` sequence that serves as its own
/// iterator. The `makeIterator()` method is provided as a default
/// implementation.
///
/// struct Countdown: Sequence, IteratorProtocol {
/// var count: Int
///
/// mutating func next() -> Int? {
/// if count == 0 {
/// return nil
/// } else {
/// defer { count -= 1 }
/// return count
/// }
/// }
/// }
///
/// let threeToGo = Countdown(count: 3)
/// for i in threeToGo {
/// print(i)
/// }
/// // Prints "3"
/// // Prints "2"
/// // Prints "1"
///
/// Expected Performance
/// ====================
///
/// A sequence should provide its iterator in O(1). The `Sequence` protocol
/// makes no other requirements about element access, so routines that
/// traverse a sequence should be considered O(*n*) unless documented
/// otherwise.
public protocol Sequence {
/// A type representing the sequence's elements.
associatedtype Element
/// A type that provides the sequence's iteration interface and
/// encapsulates its iteration state.
associatedtype Iterator : IteratorProtocol where Iterator.Element == Element
/// A type that represents a subsequence of some of the sequence's elements.
associatedtype SubSequence : Sequence = AnySequence<Element>
where Element == SubSequence.Element,
SubSequence.SubSequence == SubSequence
/// Returns an iterator over the elements of this sequence.
func makeIterator() -> Iterator
/// A value less than or equal to the number of elements in
/// the sequence, calculated nondestructively.
///
/// - Complexity: O(1)
var underestimatedCount: Int { get }
/// Returns an array containing the results of mapping the given closure
/// over the sequence's elements.
///
/// In this example, `map` is used first to convert the names in the array
/// to lowercase strings and then to count their characters.
///
/// let cast = ["Vivien", "Marlon", "Kim", "Karl"]
/// let lowercaseNames = cast.map { $0.lowercased() }
/// // 'lowercaseNames' == ["vivien", "marlon", "kim", "karl"]
/// let letterCounts = cast.map { $0.count }
/// // 'letterCounts' == [6, 6, 3, 4]
///
/// - Parameter transform: A mapping closure. `transform` accepts an
/// element of this sequence as its parameter and returns a transformed
/// value of the same or of a different type.
/// - Returns: An array containing the transformed elements of this
/// sequence.
func map<T>(
_ transform: (Element) throws -> T
) rethrows -> [T]
/// Returns an array containing, in order, the elements of the sequence
/// that satisfy the given predicate.
///
/// In this example, `filter(_:)` is used to include only names shorter than
/// five characters.
///
/// let cast = ["Vivien", "Marlon", "Kim", "Karl"]
/// let shortNames = cast.filter { $0.count < 5 }
/// print(shortNames)
/// // Prints "["Kim", "Karl"]"
///
/// - Parameter isIncluded: A closure that takes an element of the
/// sequence as its argument and returns a Boolean value indicating
/// whether the element should be included in the returned array.
/// - Returns: An array of the elements that `isIncluded` allowed.
func filter(
_ isIncluded: (Element) throws -> Bool
) rethrows -> [Element]
/// Calls the given closure on each element in the sequence in the same order
/// as a `for`-`in` loop.
///
/// The two loops in the following example produce the same output:
///
/// let numberWords = ["one", "two", "three"]
/// for word in numberWords {
/// print(word)
/// }
/// // Prints "one"
/// // Prints "two"
/// // Prints "three"
///
/// numberWords.forEach { word in
/// print(word)
/// }
/// // Same as above
///
/// Using the `forEach` method is distinct from a `for`-`in` loop in two
/// important ways:
///
/// 1. You cannot use a `break` or `continue` statement to exit the current
/// call of the `body` closure or skip subsequent calls.
/// 2. Using the `return` statement in the `body` closure will exit only from
/// the current call to `body`, not from any outer scope, and won't skip
/// subsequent calls.
///
/// - Parameter body: A closure that takes an element of the sequence as a
/// parameter.
func forEach(_ body: (Element) throws -> Void) rethrows
// Note: The complexity of Sequence.dropFirst(_:) requirement
// is documented as O(n) because Collection.dropFirst(_:) is
// implemented in O(n), even though the default
// implementation for Sequence.dropFirst(_:) is O(1).
/// Returns a subsequence containing all but the given number of initial
/// elements.
///
/// If the number of elements to drop exceeds the number of elements in
/// the sequence, the result is an empty subsequence.
///
/// let numbers = [1, 2, 3, 4, 5]
/// print(numbers.dropFirst(2))
/// // Prints "[3, 4, 5]"
/// print(numbers.dropFirst(10))
/// // Prints "[]"
///
/// - Parameter n: The number of elements to drop from the beginning of
/// the sequence. `n` must be greater than or equal to zero.
/// - Returns: A subsequence starting after the specified number of
/// elements.
///
/// - Complexity: O(*n*), where *n* is the number of elements to drop from
/// the beginning of the sequence.
func dropFirst(_ n: Int) -> SubSequence
/// Returns a subsequence containing all but the specified number of final
/// elements.
///
/// The sequence must be finite. If the number of elements to drop exceeds
/// the number of elements in the sequence, the result is an empty
/// subsequence.
///
/// let numbers = [1, 2, 3, 4, 5]
/// print(numbers.dropLast(2))
/// // Prints "[1, 2, 3]"
/// print(numbers.dropLast(10))
/// // Prints "[]"
///
/// - Parameter n: The number of elements to drop off the end of the
/// sequence. `n` must be greater than or equal to zero.
/// - Returns: A subsequence leaving off the specified number of elements.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
func dropLast(_ n: Int) -> SubSequence
/// Returns a subsequence by skipping elements while `predicate` returns
/// `true` and returning the remaining elements.
///
/// - Parameter predicate: A closure that takes an element of the
/// sequence as its argument and returns a Boolean value indicating
/// whether the element is a match.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
func drop(
while predicate: (Element) throws -> Bool
) rethrows -> SubSequence
/// Returns a subsequence, up to the specified maximum length, containing
/// the initial elements of the sequence.
///
/// If the maximum length exceeds the number of elements in the sequence,
/// the result contains all the elements in the sequence.
///
/// let numbers = [1, 2, 3, 4, 5]
/// print(numbers.prefix(2))
/// // Prints "[1, 2]"
/// print(numbers.prefix(10))
/// // Prints "[1, 2, 3, 4, 5]"
///
/// - Parameter maxLength: The maximum number of elements to return.
/// `maxLength` must be greater than or equal to zero.
/// - Returns: A subsequence starting at the beginning of this sequence
/// with at most `maxLength` elements.
func prefix(_ maxLength: Int) -> SubSequence
/// Returns a subsequence containing the initial, consecutive elements that
/// satisfy the given predicate.
///
/// The following example uses the `prefix(while:)` method to find the
/// positive numbers at the beginning of the `numbers` array. Every element
/// of `numbers` up to, but not including, the first negative value is
/// included in the result.
///
/// let numbers = [3, 7, 4, -2, 9, -6, 10, 1]
/// let positivePrefix = numbers.prefix(while: { $0 > 0 })
/// // positivePrefix == [3, 7, 4]
///
/// If `predicate` matches every element in the sequence, the resulting
/// sequence contains every element of the sequence.
///
/// - Parameter predicate: A closure that takes an element of the sequence as
/// its argument and returns a Boolean value indicating whether the
/// element should be included in the result.
/// - Returns: A subsequence of the initial, consecutive elements that
/// satisfy `predicate`.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
func prefix(
while predicate: (Element) throws -> Bool
) rethrows -> SubSequence
/// Returns a subsequence, up to the given maximum length, containing the
/// final elements of the sequence.
///
/// The sequence must be finite. If the maximum length exceeds the number
/// of elements in the sequence, the result contains all the elements in
/// the sequence.
///
/// let numbers = [1, 2, 3, 4, 5]
/// print(numbers.suffix(2))
/// // Prints "[4, 5]"
/// print(numbers.suffix(10))
/// // Prints "[1, 2, 3, 4, 5]"
///
/// - Parameter maxLength: The maximum number of elements to return. The
/// value of `maxLength` must be greater than or equal to zero.
/// - Returns: A subsequence terminating at the end of this sequence with
/// at most `maxLength` elements.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
func suffix(_ maxLength: Int) -> SubSequence
/// Returns the longest possible subsequences of the sequence, in order, that
/// don't contain elements satisfying the given predicate.
///
/// The resulting array consists of at most `maxSplits + 1` subsequences.
/// Elements that are used to split the sequence are not returned as part of
/// any subsequence.
///
/// The following examples show the effects of the `maxSplits` and
/// `omittingEmptySubsequences` parameters when splitting a string using a
/// closure that matches spaces. The first use of `split` returns each word
/// that was originally separated by one or more spaces.
///
/// let line = "BLANCHE: I don't want realism. I want magic!"
/// print(line.split(whereSeparator: { $0 == " " })
/// .map(String.init))
/// // Prints "["BLANCHE:", "I", "don\'t", "want", "realism.", "I", "want", "magic!"]"
///
/// The second example passes `1` for the `maxSplits` parameter, so the
/// original string is split just once, into two new strings.
///
/// print(
/// line.split(maxSplits: 1, whereSeparator: { $0 == " " })
/// .map(String.init))
/// // Prints "["BLANCHE:", " I don\'t want realism. I want magic!"]"
///
/// The final example passes `false` for the `omittingEmptySubsequences`
/// parameter, so the returned array contains empty strings where spaces
/// were repeated.
///
/// print(line.split(omittingEmptySubsequences: false,
/// whereSeparator: { $0 == " " })
/// ).map(String.init))
/// // Prints "["BLANCHE:", "", "", "I", "don\'t", "want", "realism.", "I", "want", "magic!"]"
///
/// - Parameters:
/// - maxSplits: The maximum number of times to split the sequence, or one
/// less than the number of subsequences to return. If `maxSplits + 1`
/// subsequences are returned, the last one is a suffix of the original
/// sequence containing the remaining elements. `maxSplits` must be
/// greater than or equal to zero. The default value is `Int.max`.
/// - omittingEmptySubsequences: If `false`, an empty subsequence is
/// returned in the result for each pair of consecutive elements
/// satisfying the `isSeparator` predicate and for each element at the
/// start or end of the sequence satisfying the `isSeparator` predicate.
/// If `true`, only nonempty subsequences are returned. The default
/// value is `true`.
/// - isSeparator: A closure that returns `true` if its argument should be
/// used to split the sequence; otherwise, `false`.
/// - Returns: An array of subsequences, split from this sequence's elements.
func split(
maxSplits: Int, omittingEmptySubsequences: Bool,
whereSeparator isSeparator: (Element) throws -> Bool
) rethrows -> [SubSequence]
func _customContainsEquatableElement(
_ element: Element
) -> Bool?
/// If `self` is multi-pass (i.e., a `Collection`), invoke `preprocess` and
/// return its result. Otherwise, return `nil`.
func _preprocessingPass<R>(
_ preprocess: () throws -> R
) rethrows -> R?
/// Create a native array buffer containing the elements of `self`,
/// in the same order.
func _copyToContiguousArray() -> ContiguousArray<Element>
/// Copy `self` into an unsafe buffer, returning a partially-consumed
/// iterator with any elements that didn't fit remaining.
func _copyContents(
initializing ptr: UnsafeMutableBufferPointer<Element>
) -> (Iterator,UnsafeMutableBufferPointer<Element>.Index)
}
// Provides a default associated type witness for Iterator when the
// Self type is both a Sequence and an Iterator.
extension Sequence where Self: IteratorProtocol {
// @_implements(Sequence, Iterator)
public typealias _Default_Iterator = Self
}
/// A default makeIterator() function for `IteratorProtocol` instances that
/// are declared to conform to `Sequence`
extension Sequence where Self.Iterator == Self {
/// Returns an iterator over the elements of this sequence.
@_inlineable
public func makeIterator() -> Self {
return self
}
}
/// A sequence that lazily consumes and drops `n` elements from an underlying
/// `Base` iterator before possibly returning the first available element.
///
/// The underlying iterator's sequence may be infinite.
@_versioned
@_fixed_layout
internal struct _DropFirstSequence<Base : IteratorProtocol>
: Sequence, IteratorProtocol {
@_versioned
internal var _iterator: Base
@_versioned
internal let _limit: Int
@_versioned
internal var _dropped: Int
@_versioned
@_inlineable
internal init(_iterator: Base, limit: Int, dropped: Int = 0) {
self._iterator = _iterator
self._limit = limit
self._dropped = dropped
}
@_versioned
@_inlineable
internal func makeIterator() -> _DropFirstSequence<Base> {
return self
}
@_versioned
@_inlineable
internal mutating func next() -> Base.Element? {
while _dropped < _limit {
if _iterator.next() == nil {
_dropped = _limit
return nil
}
_dropped += 1
}
return _iterator.next()
}
@_versioned
@_inlineable
internal func dropFirst(_ n: Int) -> AnySequence<Base.Element> {
// If this is already a _DropFirstSequence, we need to fold in
// the current drop count and drop limit so no data is lost.
//
// i.e. [1,2,3,4].dropFirst(1).dropFirst(1) should be equivalent to
// [1,2,3,4].dropFirst(2).
return AnySequence(
_DropFirstSequence(
_iterator: _iterator, limit: _limit + n, dropped: _dropped))
}
}
/// A sequence that only consumes up to `n` elements from an underlying
/// `Base` iterator.
///
/// The underlying iterator's sequence may be infinite.
@_fixed_layout
@_versioned
internal struct _PrefixSequence<Base : IteratorProtocol>
: Sequence, IteratorProtocol {
@_versioned
internal let _maxLength: Int
@_versioned
internal var _iterator: Base
@_versioned
internal var _taken: Int
@_versioned
@_inlineable
internal init(_iterator: Base, maxLength: Int, taken: Int = 0) {
self._iterator = _iterator
self._maxLength = maxLength
self._taken = taken
}
@_versioned
@_inlineable
internal func makeIterator() -> _PrefixSequence<Base> {
return self
}
@_versioned
@_inlineable
internal mutating func next() -> Base.Element? {
if _taken >= _maxLength { return nil }
_taken += 1
if let next = _iterator.next() {
return next
}
_taken = _maxLength
return nil
}
@_versioned
@_inlineable
internal func prefix(_ maxLength: Int) -> AnySequence<Base.Element> {
return AnySequence(
_PrefixSequence(
_iterator: _iterator,
maxLength: Swift.min(maxLength, self._maxLength),
taken: _taken))
}
}
/// A sequence that lazily consumes and drops `n` elements from an underlying
/// `Base` iterator before possibly returning the first available element.
///
/// The underlying iterator's sequence may be infinite.
@_fixed_layout
@_versioned
internal struct _DropWhileSequence<Base : IteratorProtocol>
: Sequence, IteratorProtocol {
typealias Element = Base.Element
@_versioned
internal var _iterator: Base
@_versioned
internal var _nextElement: Base.Element?
@_versioned
@_inlineable
internal init(
iterator: Base,
nextElement: Base.Element?,
predicate: (Base.Element) throws -> Bool
) rethrows {
self._iterator = iterator
self._nextElement = nextElement ?? _iterator.next()
while try _nextElement.flatMap(predicate) == true {
_nextElement = _iterator.next()
}
}
@_versioned
@_inlineable
internal func makeIterator() -> _DropWhileSequence<Base> {
return self
}
@_versioned
@_inlineable
internal mutating func next() -> Element? {
guard _nextElement != nil else {
return _iterator.next()
}
let next = _nextElement
_nextElement = nil
return next
}
@_versioned
@_inlineable
internal func drop(
while predicate: (Element) throws -> Bool
) rethrows -> AnySequence<Element> {
// If this is already a _DropWhileSequence, avoid multiple
// layers of wrapping and keep the same iterator.
return try AnySequence(
_DropWhileSequence(
iterator: _iterator, nextElement: _nextElement, predicate: predicate))
}
}
//===----------------------------------------------------------------------===//
// Default implementations for Sequence
//===----------------------------------------------------------------------===//
extension Sequence {
/// Returns an array containing the results of mapping the given closure
/// over the sequence's elements.
///
/// In this example, `map` is used first to convert the names in the array
/// to lowercase strings and then to count their characters.
///
/// let cast = ["Vivien", "Marlon", "Kim", "Karl"]
/// let lowercaseNames = cast.map { $0.lowercased() }
/// // 'lowercaseNames' == ["vivien", "marlon", "kim", "karl"]
/// let letterCounts = cast.map { $0.count }
/// // 'letterCounts' == [6, 6, 3, 4]
///
/// - Parameter transform: A mapping closure. `transform` accepts an
/// element of this sequence as its parameter and returns a transformed
/// value of the same or of a different type.
/// - Returns: An array containing the transformed elements of this
/// sequence.
@_inlineable
public func map<T>(
_ transform: (Element) throws -> T
) rethrows -> [T] {
let initialCapacity = underestimatedCount
var result = ContiguousArray<T>()
result.reserveCapacity(initialCapacity)
var iterator = self.makeIterator()
// Add elements up to the initial capacity without checking for regrowth.
for _ in 0..<initialCapacity {
result.append(try transform(iterator.next()!))
}
// Add remaining elements, if any.
while let element = iterator.next() {
result.append(try transform(element))
}
return Array(result)
}
/// Returns an array containing, in order, the elements of the sequence
/// that satisfy the given predicate.
///
/// In this example, `filter(_:)` is used to include only names shorter than
/// five characters.
///
/// let cast = ["Vivien", "Marlon", "Kim", "Karl"]
/// let shortNames = cast.filter { $0.count < 5 }
/// print(shortNames)
/// // Prints "["Kim", "Karl"]"
///
/// - Parameter isIncluded: A closure that takes an element of the
/// sequence as its argument and returns a Boolean value indicating
/// whether the element should be included in the returned array.
/// - Returns: An array of the elements that `isIncluded` allowed.
@_inlineable
public func filter(
_ isIncluded: (Element) throws -> Bool
) rethrows -> [Element] {
return try _filter(isIncluded)
}
@_transparent
public func _filter(
_ isIncluded: (Element) throws -> Bool
) rethrows -> [Element] {
var result = ContiguousArray<Element>()
var iterator = self.makeIterator()
while let element = iterator.next() {
if try isIncluded(element) {
result.append(element)
}
}
return Array(result)
}
/// Returns a value less than or equal to the number of elements in
/// the sequence, nondestructively.
///
/// - Complexity: O(*n*)
@_inlineable
public var underestimatedCount: Int {
return 0
}
@_inlineable
public func _preprocessingPass<R>(
_ preprocess: () throws -> R
) rethrows -> R? {
return nil
}
@_inlineable
public func _customContainsEquatableElement(
_ element: Iterator.Element
) -> Bool? {
return nil
}
/// Calls the given closure on each element in the sequence in the same order
/// as a `for`-`in` loop.
///
/// The two loops in the following example produce the same output:
///
/// let numberWords = ["one", "two", "three"]
/// for word in numberWords {
/// print(word)
/// }
/// // Prints "one"
/// // Prints "two"
/// // Prints "three"
///
/// numberWords.forEach { word in
/// print(word)
/// }
/// // Same as above
///
/// Using the `forEach` method is distinct from a `for`-`in` loop in two
/// important ways:
///
/// 1. You cannot use a `break` or `continue` statement to exit the current
/// call of the `body` closure or skip subsequent calls.
/// 2. Using the `return` statement in the `body` closure will exit only from
/// the current call to `body`, not from any outer scope, and won't skip
/// subsequent calls.
///
/// - Parameter body: A closure that takes an element of the sequence as a
/// parameter.
@_inlineable
public func forEach(
_ body: (Element) throws -> Void
) rethrows {
for element in self {
try body(element)
}
}
}
@_versioned
@_fixed_layout
internal enum _StopIteration : Error {
case stop
}
extension Sequence {
/// Returns the first element of the sequence that satisfies the given
/// predicate.
///
/// The following example uses the `first(where:)` method to find the first
/// negative number in an array of integers:
///
/// let numbers = [3, 7, 4, -2, 9, -6, 10, 1]
/// if let firstNegative = numbers.first(where: { $0 < 0 }) {
/// print("The first negative number is \(firstNegative).")
/// }
/// // Prints "The first negative number is -2."
///
/// - Parameter predicate: A closure that takes an element of the sequence as
/// its argument and returns a Boolean value indicating whether the
/// element is a match.
/// - Returns: The first element of the sequence that satisfies `predicate`,
/// or `nil` if there is no element that satisfies `predicate`.
@_inlineable
public func first(
where predicate: (Element) throws -> Bool
) rethrows -> Element? {
var foundElement: Element?
do {
try self.forEach {
if try predicate($0) {
foundElement = $0
throw _StopIteration.stop
}
}
} catch is _StopIteration { }
return foundElement
}
}
extension Sequence where Element : Equatable {
/// Returns the longest possible subsequences of the sequence, in order,
/// around elements equal to the given element.
///
/// The resulting array consists of at most `maxSplits + 1` subsequences.
/// Elements that are used to split the sequence are not returned as part of
/// any subsequence.
///
/// The following examples show the effects of the `maxSplits` and
/// `omittingEmptySubsequences` parameters when splitting a string at each