Sequence.swift

//===----------------------------------------------------------------------===//
//
// 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()
  }

  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(generator, limit: limit + n, dropped: dropped))
  }
}

/// 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
  }

  internal func prefix(maxLength: Int) -> AnySequence<Base.Element> {
    return AnySequence(
      _PrefixSequence(generator,
        maxLength: min(maxLength, self.maxLength), taken: taken))
  }
}

//===----------------------------------------------------------------------===//
// 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)
  }

  @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
  }

  /// 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 where
  SubSequence : SequenceType,
  SubSequence.Generator.Element == Generator.Element,
  SubSequence.SubSequence == SubSequence {

  /// 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) }
    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>())
    }
    return AnySequence(_PrefixSequence(generate(), maxLength: maxLength))
  }
}

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
}