InterspersedSequence.swift

/// A sequence that presents the elements of the base sequence with the
/// separator inserted between each element.
public struct InterspersedSequence<Base: Sequence> {

  let base: Base
  let separator: Base.Element

  /// Creates a sequence that presents the elements of `base` sequence with the
  /// `separator` inserted between each element.
  ///
  /// - Parameters:
  ///   - base: The base sequence.
  ///   - separator: A separator to insert between each element of the base.
  /// - Complexity: O(1)
  init(base: Base, separator: Base.Element) {
    self.base = base
    self.separator = separator
  }
}

extension InterspersedSequence {
  /// An iterator that presents the elements of the base iterator with the
  /// separator inserted between each element.
  public struct Iterator {

    var base: Base.Iterator
    let separator: Base.Element
    var state: State

    enum State {
      case start
      case separator
      case base(Element)
    }

    init(base: Base.Iterator, separator: Base.Element) {
      self.base = base
      self.separator = separator
      self.state = .start
    }
  }
}

extension InterspersedSequence.Iterator: IteratorProtocol {

  public mutating func next() -> Base.Element? {

    switch state {

    case .start:
      state = .separator
      return base.next()

    case .separator:
      // If the next element is nil, there doesn't need to be a separator.
      guard let element = base.next() else { return nil }
      state = .base(element)
      return separator

    case .base(let element):
      state = .separator
      return element
    }
  }
}

extension InterspersedSequence: Sequence {

  public typealias Element = Base.Element

  /// Returns an iterator over the elements of this sequence.
  ///
  /// - Returns: An iterator over the elements.
  /// - Complexity: O(1)
  public func makeIterator() -> Iterator {
    let baseIterator = base.makeIterator()
    return Iterator(base: baseIterator, separator: separator)
  }
}

extension Sequence {

  /// Returns a sequence which which inserts the separator between each element.
  ///
  /// This example shows how an array of `String` instances can be interspersed,
  /// using an `String` instance as the separator.
  ///
  ///     let strings = ["A", "B", "C", "D", "E"]
  ///     let interspersed = strings.interspersed(separator: "-")
  ///     print(Array(interspersed))
  ///     // Prints "["A", "-", "B", "-", "C", "-", "D", "-", "E"]"
  ///
  /// - Parameter separator: An element to insert between each of this
  ///   sequence's elements.
  /// - Returns: The interspersed sequence of elements.
  public func interspersed(separator: Element) -> InterspersedSequence<Self> {
    return InterspersedSequence(base: self, separator: separator)
  }
}

let empty = EmptyCollection<Int>().interspersed(separator: 0)
Array(empty) // []

let one = CollectionOfOne("A").interspersed(separator: "-")
Array(one) // ["A"]

var array = [1,2,3,4,5,6,7,8,9].interspersed(separator: 0)
Array(array) // [1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9]

let string = "ABCDE".interspersed(separator: "-")
String(string) // "A-B-C-D-E"