stdlib/public/core/Sequence.swift - third_party/swift - Git at Google

 //===----------------------------------------------------------------------===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See http://swift.org/LICENSE.txt for license information
 // See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //
 //===----------------------------------------------------------------------===//

 /// Encapsulates iteration state and interface for iteration over a
 /// *sequence*.
 ///
 /// - Note: While it is safe to copy a *generator*, advancing one
 ///   copy may invalidate the others.
 ///
 /// Any code that uses multiple generators (or `for`...`in` loops)
 /// over a single *sequence* should have static knowledge that the
 /// specific *sequence* is multi-pass, either because its concrete
 /// type is known or because it is constrained to `CollectionType`.
 /// Also, the generators must be obtained by distinct calls to the
 /// *sequence's* `generate()` method, rather than by copying.
 public protocol GeneratorType {
   /// The type of element generated by `self`.
   typealias Element

   /// Advance to the next element and return it, or `nil` if no next
   /// element exists.
   ///
   /// - Requires: `next()` has not been applied to a copy of `self`
   ///   since the copy was made, and no preceding call to `self.next()`
   ///   has returned `nil`.  Specific implementations of this protocol
   ///   are encouraged to respond to violations of this requirement by
   ///   calling `preconditionFailure("...")`.
   @warn_unused_result
   mutating func next() -> Element?
 }

 /// A type that can be iterated with a `for`...`in` loop.
 ///
 /// `SequenceType` makes no requirement on conforming types regarding
 /// whether they will be destructively "consumed" by iteration.  To
 /// ensure non-destructive iteration, constrain your *sequence* to
 /// `CollectionType`.
 ///
 /// As a consequence, it is not possible to run multiple `for` loops
 /// on a sequence to "resume" iteration:
 ///
 ///     for element in sequence {
 ///       if ... some condition { break }
 ///     }
 ///
 ///     for element in sequence {
 ///       // Not guaranteed to continue from the next element.
 ///     }
 ///
 /// `SequenceType` makes no requirement about the behavior in that
 /// case.  It is not correct to assume that a sequence will either 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 from the second generator.
 public protocol SequenceType {
   /// A type that provides the *sequence*'s iteration interface and
   /// encapsulates its iteration state.
   typealias Generator : GeneratorType

   // FIXME: should be constrained to SequenceType
   // (<rdar://problem/20715009> Implement recursive protocol
   // constraints)

   /// A type that represents a subsequence of some of the elements.
   typealias SubSequence

   /// Return a *generator* over the elements of this *sequence*.
   ///
   /// - Complexity: O(1).
   @warn_unused_result
   func generate() -> Generator

   /// Return a value less than or equal to the number of elements in
   /// `self`, **nondestructively**.
   ///
   /// - Complexity: O(N).
   @warn_unused_result
   func underestimateCount() -> Int

   /// Return an `Array` containing the results of mapping `transform`
   /// over `self`.
   ///
   /// - Complexity: O(N).
   @warn_unused_result
   func map<T>(
     @noescape transform: (Generator.Element) throws -> T
   ) rethrows -> [T]

   /// Return an `Array` containing the elements of `self`,
   /// in order, that satisfy the predicate `includeElement`.
   @warn_unused_result
   func filter(
     @noescape includeElement: (Generator.Element) throws -> Bool
   ) rethrows -> [Generator.Element]

   /// Call `body` on each element in `self` in the same order as a
   /// *for-in loop.*
   ///
   ///     sequence.forEach {
   ///       // body code
   ///     }
   ///
   /// is similar to:
   ///
   ///     for element in sequence {
   ///       // body code
   ///     }
   ///
   /// - Note: You cannot use the `break` or `continue` statement to exit the
   ///   current call of the `body` closure or skip subsequent calls.
   /// - Note: Using the `return` statement in the `body` closure will only
   ///   exit from the current call to `body`, not any outer scope, and won't
   ///   skip subsequent calls.
   ///
   /// - Complexity: O(`self.count`)
   func forEach(@noescape body: (Generator.Element) throws -> Void) rethrows

   /// Returns a subsequence containing all but the first `n` elements.
   ///
   /// - Requires: `n >= 0`
   /// - Complexity: O(`n`)
   @warn_unused_result
   func dropFirst(n: Int) -> SubSequence

   /// Returns a subsequence containing all but the last `n` elements.
   ///
   /// - Requires: `self` is a finite sequence.
   /// - Requires: `n >= 0`
   /// - Complexity: O(`self.count`)
   @warn_unused_result
   func dropLast(n: Int) -> SubSequence

   /// Returns a subsequence, up to `maxLength` in length, containing the
   /// initial elements.
   ///
   /// If `maxLength` exceeds `self.count`, the result contains all
   /// the elements of `self`.
   ///
   /// - Requires: `maxLength >= 0`
   @warn_unused_result
   func prefix(maxLength: Int) -> SubSequence

   /// Returns a slice, up to `maxLength` in length, containing the
   /// final elements of `s`.
   ///
   /// If `maxLength` exceeds `s.count`, the result contains all
   /// the elements of `s`.
   ///
   /// - Requires: `self` is a finite sequence.
   /// - Requires: `maxLength >= 0`
   @warn_unused_result
   func suffix(maxLength: Int) -> SubSequence

   /// Returns the maximal `SubSequence`s of `self`, in order, that
   /// don't contain elements satisfying the predicate `isSeparator`.
   ///
   /// - Parameter maxSplit: The maximum number of `SubSequence`s to
   ///   return, minus 1.
   ///   If `maxSplit + 1` `SubSequence`s are returned, the last one is
   ///   a suffix of `self` containing the remaining elements.
   ///   The default value is `Int.max`.
   ///
   /// - Parameter allowEmptySubsequences: If `true`, an empty `SubSequence`
   ///   is produced in the result for each pair of consecutive elements
   ///   satisfying `isSeparator`.
   ///   The default value is `false`.
   ///
   /// - Requires: `maxSplit >= 0`
   @warn_unused_result
   func split(maxSplit: Int, allowEmptySlices: Bool,
     @noescape isSeparator: (Generator.Element) throws -> Bool
   ) rethrows -> [SubSequence]

   @warn_unused_result
   func _customContainsEquatableElement(
     element: Generator.Element
   ) -> Bool?

   /// If `self` is multi-pass (i.e., a `CollectionType`), invoke
   /// `preprocess` on `self` and return its result.  Otherwise, return
   /// `nil`.
   func _preprocessingPass<R>(@noescape preprocess: (Self) -> R) -> R?

   /// Create a native array buffer containing the elements of `self`,
   /// in the same order.
   func _copyToNativeArrayBuffer() -> _ContiguousArrayBuffer<Generator.Element>

   /// Copy a Sequence into an array, returning one past the last
   /// element initialized.
   func _initializeTo(ptr: UnsafeMutablePointer<Generator.Element>)
     -> UnsafeMutablePointer<Generator.Element>
 }

 /// A default generate() function for `GeneratorType` instances that
 /// are declared to conform to `SequenceType`
 extension SequenceType
   where Self.Generator == Self, Self : GeneratorType {
   public func generate() -> Self {
     return self
   }
 }

 /// A sequence that lazily consumes and drops `n` elements from an underlying
 /// `Base` generator before possibly returning the first available element.
 ///
 /// The underlying generator's sequence may be infinite.
 ///
 /// This is a class - we require reference semantics to keep track
 /// of how many elements we've already dropped from the underlying sequence.
 internal class _DropFirstSequence<Base : GeneratorType>
     : SequenceType, GeneratorType {

   internal var generator: Base
   internal let limit: Int
   internal var dropped: Int

   internal init(_ generator: Base, limit: Int, dropped: Int = 0) {
     self.generator = generator
     self.limit = limit
     self.dropped = dropped
   }

   internal func generate() -> _DropFirstSequence<Base> {
     return self
   }

   internal func next() -> Base.Element? {
     while dropped < limit {
       if generator.next() == nil {
         dropped = limit
         return nil
       }
       dropped += 1
     }
     return generator.next()
   }
 }

 /// A sequence that only consumes up to `n` elements from an underlying
 /// `Base` generator.
 ///
 /// The underlying generator's sequence may be infinite.
 ///
 /// This is a class - we require reference semantics to keep track
 /// of how many elements we've already taken from the underlying sequence.
 internal class _PrefixSequence<Base : GeneratorType> : SequenceType, GeneratorType {
   internal let maxLength: Int
   internal var generator: Base
   internal var taken: Int

   internal init(_ generator: Base, maxLength: Int, taken: Int = 0) {
     self.generator = generator
     self.maxLength = maxLength
     self.taken = taken
   }

   internal func generate() -> _PrefixSequence<Base> {
     return self
   }

   internal func next() -> Base.Element? {
     if taken >= maxLength { return nil }
     taken += 1

     if let next = generator.next() {
       return next
     }

     taken = maxLength
     return nil
   }
 }

 //===----------------------------------------------------------------------===//
 // Default implementations for SequenceType
 //===----------------------------------------------------------------------===//

 extension SequenceType {
   /// Return an `Array` containing the results of mapping `transform`
   /// over `self`.
   ///
   /// - Complexity: O(N).
   @warn_unused_result
   public func map<T>(
     @noescape transform: (Generator.Element) throws -> T
   ) rethrows -> [T] {
     let initialCapacity = underestimateCount()
     var result = ContiguousArray<T>()
     result.reserveCapacity(initialCapacity)

     var generator = generate()

     // Add elements up to the initial capacity without checking for regrowth.
     for _ in 0..<initialCapacity {
       result.append(try transform(generator.next()!))
     }
     // Add remaining elements, if any.
     while let element = generator.next() {
       result.append(try transform(element))
     }
     return Array(result)
   }

   /// Return an `Array` containing the elements of `self`,
   /// in order, that satisfy the predicate `includeElement`.
   @warn_unused_result
   public func filter(
     @noescape includeElement: (Generator.Element) throws -> Bool
   ) rethrows -> [Generator.Element] {

     var result = ContiguousArray<Generator.Element>()

     var generator = generate()

     while let element = generator.next() {
       if try includeElement(element) {
         result.append(element)
       }
     }

     return Array(result)
   }

   /// Returns a subsequence containing all but the first `n` elements.
   ///
   /// - Requires: `n >= 0`
   /// - Complexity: O(`n`)
   @warn_unused_result
   public func dropFirst(n: Int) -> AnySequence<Generator.Element> {
     _precondition(n >= 0, "Can't drop a negative number of elements from a sequence")
     if n == 0 { return AnySequence(self) }
     // 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).
     // FIXME: <rdar://problem/21885675> Use method dispatch to fold
     // _PrefixSequence and _DropFirstSequence counts
     if let any = self as? AnySequence<Generator.Element>,
        let box = any._box as? _SequenceBox<_DropFirstSequence<Generator>> {
       let base = box._base
       let folded = _DropFirstSequence(base.generator, limit: base.limit + n,
           dropped: base.dropped)
       return AnySequence(folded)
     }

     return AnySequence(_DropFirstSequence(generate(), limit: n))
   }

   /// Returns a subsequence containing all but the last `n` elements.
   ///
   /// - Requires: `self` is a finite collection.
   /// - Requires: `n >= 0`
   /// - Complexity: O(`self.count`)
   @warn_unused_result
   public func dropLast(n: Int) -> AnySequence<Generator.Element> {
     _precondition(n >= 0, "Can't drop a negative number of elements from a sequence")
     if n == 0 { return AnySequence(self) }
     // FIXME: <rdar://problem/21885650> Create reusable RingBuffer<T>
     // Put incoming elements from this sequence in a holding tank, a ring buffer
     // of size <= n. If more elements keep coming in, pull them out of the
     // holding tank into the result, an `Array`. This saves
     // `n` * sizeof(Generator.Element) of memory, because slices keep the entire
     // memory of an `Array` alive.
     var result: [Generator.Element] = []
     var ringBuffer: [Generator.Element] = []
     var i = ringBuffer.startIndex

     for element in self {
       if ringBuffer.count < n {
         ringBuffer.append(element)
       } else {
         result.append(ringBuffer[i])
         ringBuffer[i] = element
         i = i.successor() % n
       }
     }
     return AnySequence(result)
   }

   @warn_unused_result
   public func prefix(maxLength: Int) -> AnySequence<Generator.Element> {
     _precondition(maxLength >= 0, "Can't take a prefix of negative length from a sequence")
     if maxLength == 0 {
       return AnySequence(EmptyCollection<Generator.Element>())
     }
     // FIXME: <rdar://problem/21885675> Use method dispatch to fold
     // _PrefixSequence and _DropFirstSequence counts
     if let any = self as? AnySequence<Generator.Element>,
        let box = any._box as? _SequenceBox<_PrefixSequence<Generator>> {
       let base = box._base
       let folded = _PrefixSequence(
         base.generator,
         maxLength: min(base.maxLength, maxLength),
         taken: base.taken)
       return AnySequence(folded)
     }
     return AnySequence(_PrefixSequence(generate(), maxLength: maxLength))
   }

   @warn_unused_result
   public func suffix(maxLength: Int) -> AnySequence<Generator.Element> {
     _precondition(maxLength >= 0, "Can't take a suffix of negative length from a sequence")
     if maxLength == 0 { return AnySequence([]) }
     // FIXME: <rdar://problem/21885650> Create reusable RingBuffer<T>
     // Put incoming elements into a ring buffer to save space. Once all
     // elements are consumed, reorder the ring buffer into an `Array`
     // and return it. This saves memory for sequences particularly longer
     // than `maxLength`.
     var ringBuffer: [Generator.Element] = []
     ringBuffer.reserveCapacity(min(maxLength, underestimateCount()))

     var i = ringBuffer.startIndex

     for element in self {
       if ringBuffer.count < maxLength {
         ringBuffer.append(element)
       } else {
         ringBuffer[i] = element
         i = i.successor() % maxLength
       }
     }

     if i != ringBuffer.startIndex {
       return AnySequence(
         [ringBuffer[i..<ringBuffer.endIndex], ringBuffer[0..<i]].flatten())
     }
     return AnySequence(ringBuffer)
   }

   /// Returns the maximal `SubSequence`s of `self`, in order, that
   /// don't contain elements satisfying the predicate `isSeparator`.
   ///
   /// - Parameter maxSplit: The maximum number of `SubSequence`s to
   ///   return, minus 1.
   ///   If `maxSplit + 1` `SubSequence`s are returned, the last one is
   ///   a suffix of `self` containing the remaining elements.
   ///   The default value is `Int.max`.
   ///
   /// - Parameter allowEmptySubsequences: If `true`, an empty `SubSequence`
   ///   is produced in the result for each pair of consecutive elements
   ///   satisfying `isSeparator`.
   ///   The default value is `false`.
   ///
   /// - Requires: `maxSplit >= 0`
   @warn_unused_result
   public func split(
     maxSplit: Int = Int.max,
     allowEmptySlices: Bool = false,
     @noescape isSeparator: (Generator.Element) throws -> Bool
   ) rethrows -> [AnySequence<Generator.Element>] {
     _precondition(maxSplit >= 0, "Must take zero or more splits")
     var result: [AnySequence<Generator.Element>] = []
     var subSequence: [Generator.Element] = []

     func appendSubsequence() -> Bool {
       if subSequence.isEmpty && !allowEmptySlices {
         return false
       }
       result.append(AnySequence(subSequence))
       subSequence = []
       return true
     }

     if maxSplit == 0 {
       // We aren't really splitting the sequence.  Convert `self` into an
       // `Array` using a fast entry point.
       subSequence = Array(self)
       appendSubsequence()
       return result
     }

     var hitEnd = false
     var generator = self.generate()
     while true {
       guard let element = generator.next() else {
         hitEnd = true
         break
       }
       if try isSeparator(element) {
         if !appendSubsequence() {
           continue
         }
         if result.count == maxSplit {
           break
         }
       } else {
         subSequence.append(element)
       }
     }
     if !hitEnd {
       while let element = generator.next() {
         subSequence.append(element)
       }
     }
     appendSubsequence()
     return result
   }

   /// Return a value less than or equal to the number of elements in
   /// `self`, **nondestructively**.
   ///
   /// - Complexity: O(N).
   @warn_unused_result
   public func underestimateCount() -> Int {
     return 0
   }

   public func _preprocessingPass<R>(@noescape preprocess: (Self) -> R) -> R? {
     return nil
   }

   @warn_unused_result
   public func _customContainsEquatableElement(
     element: Generator.Element
   ) -> Bool? {
     return nil
   }
 }

 extension SequenceType {
   /// Call `body` on each element in `self` in the same order as a
   /// *for-in loop.*
   ///
   ///     sequence.forEach {
   ///       // body code
   ///     }
   ///
   /// is similar to:
   ///
   ///     for element in sequence {
   ///       // body code
   ///     }
   ///
   /// - Note: You cannot use the `break` or `continue` statement to exit the
   ///   current call of the `body` closure or skip subsequent calls.
   /// - Note: Using the `return` statement in the `body` closure will only
   ///   exit from the current call to `body`, not any outer scope, and won't
   ///   skip subsequent calls.
   ///
   /// - Complexity: O(`self.count`)
   public func forEach(
     @noescape body: (Generator.Element) throws -> Void
   ) rethrows {
     for element in self {
       try body(element)
     }
   }
 }

 extension SequenceType where Generator.Element : Equatable {
   /// Returns the maximal `SubSequence`s of `self`, in order, around elements
   /// equatable to `separator`.
   ///
   /// - Parameter maxSplit: The maximum number of `SubSequence`s to
   ///   return, minus 1.
   ///   If `maxSplit + 1` `SubSequence`s are returned, the last one is
   ///   a suffix of `self` containing the remaining elements.
   ///   The default value is `Int.max`.
   ///
   /// - Parameter allowEmptySubsequences: If `true`, an empty `SubSequence`
   ///   is produced in the result for each pair of consecutive elements
   ///   satisfying `isSeparator`.
   ///   The default value is `false`.
   ///
   /// - Requires: `maxSplit >= 0`
   @warn_unused_result
   public func split(
     separator: Generator.Element,
     maxSplit: Int = Int.max,
     allowEmptySlices: Bool = false
   ) -> [AnySequence<Generator.Element>] {
     return split(maxSplit, allowEmptySlices: allowEmptySlices,
       isSeparator: { $0 == separator })
   }
 }

 extension SequenceType {
   /// Returns a subsequence containing all but the first element.
   ///
   /// - Complexity: O(1)
   @warn_unused_result
   public func dropFirst() -> SubSequence { return dropFirst(1) }

   /// Returns a subsequence containing all but the last element.
   ///
   /// - Requires: `self` is a finite sequence.
   /// - Complexity: O(`self.count`)
   @warn_unused_result
   public func dropLast() -> SubSequence  { return dropLast(1) }
 }

 /// Return an underestimate of the number of elements in the given
 /// sequence, without consuming the sequence.  For Sequences that are
 /// actually Collections, this will return `x.count`.
 @available(*, unavailable, message="call the 'underestimateCount()' method on the sequence")
 public func underestimateCount<T : SequenceType>(x: T) -> Int {
   fatalError("unavailable function can't be called")
 }

 extension SequenceType {
   public func _initializeTo(ptr: UnsafeMutablePointer<Generator.Element>)
     -> UnsafeMutablePointer<Generator.Element> {
     var p = UnsafeMutablePointer<Generator.Element>(ptr)
     for x in GeneratorSequence(self.generate()) {
       p.initialize(x)
       p += 1
     }
     return p
   }
 }

 // Pending <rdar://problem/14011860> and <rdar://problem/14396120>,
 // pass a GeneratorType through GeneratorSequence to give it "SequenceType-ness"
 /// A sequence built around a generator of type `G`.
 ///
 /// Useful mostly to recover the ability to use `for`...`in`,
 /// given just a generator `g`:
 ///
 ///     for x in GeneratorSequence(g) { ... }
 public struct GeneratorSequence<
   Base : GeneratorType
 > : GeneratorType, SequenceType {

   @available(*, unavailable, renamed="Base")
   public typealias G = Base

   /// Construct an instance whose generator is a copy of `base`.
   public init(_ base: Base) {
     _base = base
   }

   /// Advance to the next element and return it, or `nil` if no next
   /// element exists.
   ///
   /// - Requires: `next()` has not been applied to a copy of `self`
   ///   since the copy was made, and no preceding call to `self.next()`
   ///   has returned `nil`.
   public mutating func next() -> Base.Element? {
     return _base.next()
   }

   internal var _base: Base
 }
	//===----------------------------------------------------------------------===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See http://swift.org/LICENSE.txt for license information
	// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//

	/// Encapsulates iteration state and interface for iteration over a
	/// sequence.
	///
	/// - Note: While it is safe to copy a generator, advancing one
	/// copy may invalidate the others.
	///
	/// Any code that uses multiple generators (or `for`...`in` loops)
	/// over a single sequence should have static knowledge that the
	/// specific sequence is multi-pass, either because its concrete
	/// type is known or because it is constrained to `CollectionType`.
	/// Also, the generators must be obtained by distinct calls to the
	/// sequence's `generate()` method, rather than by copying.
	public protocol GeneratorType {
	/// The type of element generated by `self`.
	typealias Element

	/// Advance to the next element and return it, or `nil` if no next
	/// element exists.
	///
	/// - Requires: `next()` has not been applied to a copy of `self`
	/// since the copy was made, and no preceding call to `self.next()`
	/// has returned `nil`. Specific implementations of this protocol
	/// are encouraged to respond to violations of this requirement by
	/// calling `preconditionFailure("...")`.
	@warn_unused_result
	mutating func next() -> Element?
	}

	/// A type that can be iterated with a `for`...`in` loop.
	///
	/// `SequenceType` makes no requirement on conforming types regarding
	/// whether they will be destructively "consumed" by iteration. To
	/// ensure non-destructive iteration, constrain your sequence to
	/// `CollectionType`.
	///
	/// As a consequence, it is not possible to run multiple `for` loops
	/// on a sequence to "resume" iteration:
	///
	/// for element in sequence {
	/// if ... some condition { break }
	/// }
	///
	/// for element in sequence {
	/// // Not guaranteed to continue from the next element.
	/// }
	///
	/// `SequenceType` makes no requirement about the behavior in that
	/// case. It is not correct to assume that a sequence will either 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 from the second generator.
	public protocol SequenceType {
	/// A type that provides the sequence's iteration interface and
	/// encapsulates its iteration state.
	typealias Generator : GeneratorType

	// FIXME: should be constrained to SequenceType
	// (<rdar://problem/20715009> Implement recursive protocol
	// constraints)

	/// A type that represents a subsequence of some of the elements.
	typealias SubSequence

	/// Return a generator over the elements of this sequence.
	///
	/// - Complexity: O(1).
	@warn_unused_result
	func generate() -> Generator

	/// Return a value less than or equal to the number of elements in
	/// `self`, nondestructively.
	///
	/// - Complexity: O(N).
	@warn_unused_result
	func underestimateCount() -> Int

	/// Return an `Array` containing the results of mapping `transform`
	/// over `self`.
	///
	/// - Complexity: O(N).
	@warn_unused_result
	func map<T>(
	@noescape transform: (Generator.Element) throws -> T
	) rethrows -> [T]

	/// Return an `Array` containing the elements of `self`,
	/// in order, that satisfy the predicate `includeElement`.
	@warn_unused_result
	func filter(
	@noescape includeElement: (Generator.Element) throws -> Bool
	) rethrows -> [Generator.Element]

	/// Call `body` on each element in `self` in the same order as a
	/// for-in loop.
	///
	/// sequence.forEach {
	/// // body code
	/// }
	///
	/// is similar to:
	///
	/// for element in sequence {
	/// // body code
	/// }
	///
	/// - Note: You cannot use the `break` or `continue` statement to exit the
	/// current call of the `body` closure or skip subsequent calls.
	/// - Note: Using the `return` statement in the `body` closure will only
	/// exit from the current call to `body`, not any outer scope, and won't
	/// skip subsequent calls.
	///
	/// - Complexity: O(`self.count`)
	func forEach(@noescape body: (Generator.Element) throws -> Void) rethrows

	/// Returns a subsequence containing all but the first `n` elements.
	///
	/// - Requires: `n >= 0`
	/// - Complexity: O(`n`)
	@warn_unused_result
	func dropFirst(n: Int) -> SubSequence

	/// Returns a subsequence containing all but the last `n` elements.
	///
	/// - Requires: `self` is a finite sequence.
	/// - Requires: `n >= 0`
	/// - Complexity: O(`self.count`)
	@warn_unused_result
	func dropLast(n: Int) -> SubSequence

	/// Returns a subsequence, up to `maxLength` in length, containing the
	/// initial elements.
	///
	/// If `maxLength` exceeds `self.count`, the result contains all
	/// the elements of `self`.
	///
	/// - Requires: `maxLength >= 0`
	@warn_unused_result
	func prefix(maxLength: Int) -> SubSequence

	/// Returns a slice, up to `maxLength` in length, containing the
	/// final elements of `s`.
	///
	/// If `maxLength` exceeds `s.count`, the result contains all
	/// the elements of `s`.
	///
	/// - Requires: `self` is a finite sequence.
	/// - Requires: `maxLength >= 0`
	@warn_unused_result
	func suffix(maxLength: Int) -> SubSequence

	/// Returns the maximal `SubSequence`s of `self`, in order, that
	/// don't contain elements satisfying the predicate `isSeparator`.
	///
	/// - Parameter maxSplit: The maximum number of `SubSequence`s to
	/// return, minus 1.
	/// If `maxSplit + 1` `SubSequence`s are returned, the last one is
	/// a suffix of `self` containing the remaining elements.
	/// The default value is `Int.max`.
	///
	/// - Parameter allowEmptySubsequences: If `true`, an empty `SubSequence`
	/// is produced in the result for each pair of consecutive elements
	/// satisfying `isSeparator`.
	/// The default value is `false`.
	///
	/// - Requires: `maxSplit >= 0`
	@warn_unused_result
	func split(maxSplit: Int, allowEmptySlices: Bool,
	@noescape isSeparator: (Generator.Element) throws -> Bool
	) rethrows -> [SubSequence]

	@warn_unused_result
	func _customContainsEquatableElement(
	element: Generator.Element
	) -> Bool?

	/// If `self` is multi-pass (i.e., a `CollectionType`), invoke
	/// `preprocess` on `self` and return its result. Otherwise, return
	/// `nil`.
	func _preprocessingPass<R>(@noescape preprocess: (Self) -> R) -> R?

	/// Create a native array buffer containing the elements of `self`,
	/// in the same order.
	func _copyToNativeArrayBuffer() -> _ContiguousArrayBuffer<Generator.Element>

	/// Copy a Sequence into an array, returning one past the last
	/// element initialized.
	func _initializeTo(ptr: UnsafeMutablePointer<Generator.Element>)
	-> UnsafeMutablePointer<Generator.Element>
	}

	/// A default generate() function for `GeneratorType` instances that
	/// are declared to conform to `SequenceType`
	extension SequenceType
	where Self.Generator == Self, Self : GeneratorType {
	public func generate() -> Self {
	return self
	}
	}

	/// A sequence that lazily consumes and drops `n` elements from an underlying
	/// `Base` generator before possibly returning the first available element.
	///
	/// The underlying generator's sequence may be infinite.
	///
	/// This is a class - we require reference semantics to keep track
	/// of how many elements we've already dropped from the underlying sequence.
	internal class _DropFirstSequence<Base : GeneratorType>
	: SequenceType, GeneratorType {

	internal var generator: Base
	internal let limit: Int
	internal var dropped: Int

	internal init(_ generator: Base, limit: Int, dropped: Int = 0) {
	self.generator = generator
	self.limit = limit
	self.dropped = dropped
	}

	internal func generate() -> _DropFirstSequence<Base> {
	return self
	}

	internal func next() -> Base.Element? {
	while dropped < limit {
	if generator.next() == nil {
	dropped = limit
	return nil
	}
	dropped += 1
	}
	return generator.next()
	}
	}

	/// A sequence that only consumes up to `n` elements from an underlying
	/// `Base` generator.
	///
	/// The underlying generator's sequence may be infinite.
	///
	/// This is a class - we require reference semantics to keep track
	/// of how many elements we've already taken from the underlying sequence.
	internal class _PrefixSequence<Base : GeneratorType> : SequenceType, GeneratorType {
	internal let maxLength: Int
	internal var generator: Base
	internal var taken: Int

	internal init(_ generator: Base, maxLength: Int, taken: Int = 0) {
	self.generator = generator
	self.maxLength = maxLength
	self.taken = taken
	}

	internal func generate() -> _PrefixSequence<Base> {
	return self
	}

	internal func next() -> Base.Element? {
	if taken >= maxLength { return nil }
	taken += 1

	if let next = generator.next() {
	return next
	}

	taken = maxLength
	return nil
	}
	}

	//===----------------------------------------------------------------------===//
	// Default implementations for SequenceType
	//===----------------------------------------------------------------------===//

	extension SequenceType {
	/// Return an `Array` containing the results of mapping `transform`
	/// over `self`.
	///
	/// - Complexity: O(N).
	@warn_unused_result
	public func map<T>(
	@noescape transform: (Generator.Element) throws -> T
	) rethrows -> [T] {
	let initialCapacity = underestimateCount()
	var result = ContiguousArray<T>()
	result.reserveCapacity(initialCapacity)

	var generator = generate()

	// Add elements up to the initial capacity without checking for regrowth.
	for _ in 0..<initialCapacity {
	result.append(try transform(generator.next()!))
	}
	// Add remaining elements, if any.
	while let element = generator.next() {
	result.append(try transform(element))
	}
	return Array(result)
	}

	/// Return an `Array` containing the elements of `self`,
	/// in order, that satisfy the predicate `includeElement`.
	@warn_unused_result
	public func filter(
	@noescape includeElement: (Generator.Element) throws -> Bool
	) rethrows -> [Generator.Element] {

	var result = ContiguousArray<Generator.Element>()

	var generator = generate()

	while let element = generator.next() {
	if try includeElement(element) {
	result.append(element)
	}
	}

	return Array(result)
	}

	/// Returns a subsequence containing all but the first `n` elements.
	///
	/// - Requires: `n >= 0`
	/// - Complexity: O(`n`)
	@warn_unused_result
	public func dropFirst(n: Int) -> AnySequence<Generator.Element> {
	_precondition(n >= 0, "Can't drop a negative number of elements from a sequence")
	if n == 0 { return AnySequence(self) }
	// 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).
	// FIXME: <rdar://problem/21885675> Use method dispatch to fold
	// _PrefixSequence and _DropFirstSequence counts
	if let any = self as? AnySequence<Generator.Element>,
	let box = any._box as? _SequenceBox<_DropFirstSequence<Generator>> {
	let base = box._base
	let folded = _DropFirstSequence(base.generator, limit: base.limit + n,
	dropped: base.dropped)
	return AnySequence(folded)
	}

	return AnySequence(_DropFirstSequence(generate(), limit: n))
	}

	/// Returns a subsequence containing all but the last `n` elements.
	///
	/// - Requires: `self` is a finite collection.
	/// - Requires: `n >= 0`
	/// - Complexity: O(`self.count`)
	@warn_unused_result
	public func dropLast(n: Int) -> AnySequence<Generator.Element> {
	_precondition(n >= 0, "Can't drop a negative number of elements from a sequence")
	if n == 0 { return AnySequence(self) }
	// FIXME: <rdar://problem/21885650> Create reusable RingBuffer<T>
	// Put incoming elements from this sequence in a holding tank, a ring buffer
	// of size <= n. If more elements keep coming in, pull them out of the
	// holding tank into the result, an `Array`. This saves
	// `n` * sizeof(Generator.Element) of memory, because slices keep the entire
	// memory of an `Array` alive.
	var result: [Generator.Element] = []
	var ringBuffer: [Generator.Element] = []
	var i = ringBuffer.startIndex

	for element in self {
	if ringBuffer.count < n {
	ringBuffer.append(element)
	} else {
	result.append(ringBuffer[i])
	ringBuffer[i] = element
	i = i.successor() % n
	}
	}
	return AnySequence(result)
	}

	@warn_unused_result
	public func prefix(maxLength: Int) -> AnySequence<Generator.Element> {
	_precondition(maxLength >= 0, "Can't take a prefix of negative length from a sequence")
	if maxLength == 0 {
	return AnySequence(EmptyCollection<Generator.Element>())
	}
	// FIXME: <rdar://problem/21885675> Use method dispatch to fold
	// _PrefixSequence and _DropFirstSequence counts
	if let any = self as? AnySequence<Generator.Element>,
	let box = any._box as? _SequenceBox<_PrefixSequence<Generator>> {
	let base = box._base
	let folded = _PrefixSequence(
	base.generator,
	maxLength: min(base.maxLength, maxLength),
	taken: base.taken)
	return AnySequence(folded)
	}
	return AnySequence(_PrefixSequence(generate(), maxLength: maxLength))
	}

	@warn_unused_result
	public func suffix(maxLength: Int) -> AnySequence<Generator.Element> {
	_precondition(maxLength >= 0, "Can't take a suffix of negative length from a sequence")
	if maxLength == 0 { return AnySequence([]) }
	// FIXME: <rdar://problem/21885650> Create reusable RingBuffer<T>
	// Put incoming elements into a ring buffer to save space. Once all
	// elements are consumed, reorder the ring buffer into an `Array`
	// and return it. This saves memory for sequences particularly longer
	// than `maxLength`.
	var ringBuffer: [Generator.Element] = []
	ringBuffer.reserveCapacity(min(maxLength, underestimateCount()))

	var i = ringBuffer.startIndex

	for element in self {
	if ringBuffer.count < maxLength {
	ringBuffer.append(element)
	} else {
	ringBuffer[i] = element
	i = i.successor() % maxLength
	}
	}

	if i != ringBuffer.startIndex {
	return AnySequence(
	[ringBuffer[i..<ringBuffer.endIndex], ringBuffer[0..<i]].flatten())
	}
	return AnySequence(ringBuffer)
	}

	/// Returns the maximal `SubSequence`s of `self`, in order, that
	/// don't contain elements satisfying the predicate `isSeparator`.
	///
	/// - Parameter maxSplit: The maximum number of `SubSequence`s to
	/// return, minus 1.
	/// If `maxSplit + 1` `SubSequence`s are returned, the last one is
	/// a suffix of `self` containing the remaining elements.
	/// The default value is `Int.max`.
	///
	/// - Parameter allowEmptySubsequences: If `true`, an empty `SubSequence`
	/// is produced in the result for each pair of consecutive elements
	/// satisfying `isSeparator`.
	/// The default value is `false`.
	///
	/// - Requires: `maxSplit >= 0`
	@warn_unused_result
	public func split(
	maxSplit: Int = Int.max,
	allowEmptySlices: Bool = false,
	@noescape isSeparator: (Generator.Element) throws -> Bool
	) rethrows -> [AnySequence<Generator.Element>] {
	_precondition(maxSplit >= 0, "Must take zero or more splits")
	var result: [AnySequence<Generator.Element>] = []
	var subSequence: [Generator.Element] = []

	func appendSubsequence() -> Bool {
	if subSequence.isEmpty && !allowEmptySlices {
	return false
	}
	result.append(AnySequence(subSequence))
	subSequence = []
	return true
	}

	if maxSplit == 0 {
	// We aren't really splitting the sequence. Convert `self` into an
	// `Array` using a fast entry point.
	subSequence = Array(self)
	appendSubsequence()
	return result
	}

	var hitEnd = false
	var generator = self.generate()
	while true {
	guard let element = generator.next() else {
	hitEnd = true
	break
	}
	if try isSeparator(element) {
	if !appendSubsequence() {
	continue
	}
	if result.count == maxSplit {
	break
	}
	} else {
	subSequence.append(element)
	}
	}
	if !hitEnd {
	while let element = generator.next() {
	subSequence.append(element)
	}
	}
	appendSubsequence()
	return result
	}

	/// Return a value less than or equal to the number of elements in
	/// `self`, nondestructively.
	///
	/// - Complexity: O(N).
	@warn_unused_result
	public func underestimateCount() -> Int {
	return 0
	}

	public func _preprocessingPass<R>(@noescape preprocess: (Self) -> R) -> R? {
	return nil
	}

	@warn_unused_result
	public func _customContainsEquatableElement(
	element: Generator.Element
	) -> Bool? {
	return nil
	}
	}

	extension SequenceType {
	/// Call `body` on each element in `self` in the same order as a
	/// for-in loop.
	///
	/// sequence.forEach {
	/// // body code
	/// }
	///
	/// is similar to:
	///
	/// for element in sequence {
	/// // body code
	/// }
	///
	/// - Note: You cannot use the `break` or `continue` statement to exit the
	/// current call of the `body` closure or skip subsequent calls.
	/// - Note: Using the `return` statement in the `body` closure will only
	/// exit from the current call to `body`, not any outer scope, and won't
	/// skip subsequent calls.
	///
	/// - Complexity: O(`self.count`)
	public func forEach(
	@noescape body: (Generator.Element) throws -> Void
	) rethrows {
	for element in self {
	try body(element)
	}
	}
	}

	extension SequenceType where Generator.Element : Equatable {
	/// Returns the maximal `SubSequence`s of `self`, in order, around elements
	/// equatable to `separator`.
	///
	/// - Parameter maxSplit: The maximum number of `SubSequence`s to
	/// return, minus 1.
	/// If `maxSplit + 1` `SubSequence`s are returned, the last one is
	/// a suffix of `self` containing the remaining elements.
	/// The default value is `Int.max`.
	///
	/// - Parameter allowEmptySubsequences: If `true`, an empty `SubSequence`
	/// is produced in the result for each pair of consecutive elements
	/// satisfying `isSeparator`.
	/// The default value is `false`.
	///
	/// - Requires: `maxSplit >= 0`
	@warn_unused_result
	public func split(
	separator: Generator.Element,
	maxSplit: Int = Int.max,
	allowEmptySlices: Bool = false
	) -> [AnySequence<Generator.Element>] {
	return split(maxSplit, allowEmptySlices: allowEmptySlices,
	isSeparator: { $0 == separator })
	}
	}

	extension SequenceType {
	/// Returns a subsequence containing all but the first element.
	///
	/// - Complexity: O(1)
	@warn_unused_result
	public func dropFirst() -> SubSequence { return dropFirst(1) }

	/// Returns a subsequence containing all but the last element.
	///
	/// - Requires: `self` is a finite sequence.
	/// - Complexity: O(`self.count`)
	@warn_unused_result
	public func dropLast() -> SubSequence { return dropLast(1) }
	}

	/// Return an underestimate of the number of elements in the given
	/// sequence, without consuming the sequence. For Sequences that are
	/// actually Collections, this will return `x.count`.
	@available(*, unavailable, message="call the 'underestimateCount()' method on the sequence")
	public func underestimateCount<T : SequenceType>(x: T) -> Int {
	fatalError("unavailable function can't be called")
	}

	extension SequenceType {
	public func _initializeTo(ptr: UnsafeMutablePointer<Generator.Element>)
	-> UnsafeMutablePointer<Generator.Element> {
	var p = UnsafeMutablePointer<Generator.Element>(ptr)
	for x in GeneratorSequence(self.generate()) {
	p.initialize(x)
	p += 1
	}
	return p
	}
	}

	// Pending <rdar://problem/14011860> and <rdar://problem/14396120>,
	// pass a GeneratorType through GeneratorSequence to give it "SequenceType-ness"
	/// A sequence built around a generator of type `G`.
	///
	/// Useful mostly to recover the ability to use `for`...`in`,
	/// given just a generator `g`:
	///
	/// for x in GeneratorSequence(g) { ... }
	public struct GeneratorSequence<
	Base : GeneratorType
	> : GeneratorType, SequenceType {

	@available(*, unavailable, renamed="Base")
	public typealias G = Base

	/// Construct an instance whose generator is a copy of `base`.
	public init(_ base: Base) {
	_base = base
	}

	/// Advance to the next element and return it, or `nil` if no next
	/// element exists.
	///
	/// - Requires: `next()` has not been applied to a copy of `self`
	/// since the copy was made, and no preceding call to `self.next()`
	/// has returned `nil`.
	public mutating func next() -> Base.Element? {
	return _base.next()
	}

	internal var _base: Base
	}