/// A default index type for a type that only supplies
/// `IteratorProtocol` conformance and value semantics
enum SequenceIndex<Base: Sequence> : Comparable {

  init() { self = .end }

  init(_ s: Base) {
    self = .normal(0, s.makeIterator())
  }


  /// An index of an element in the collection.
  ///
  /// The associated values are:
  /// - The zero-based position in the collection, for `Comparable` purposes.
  /// - The element itself, so that it only needs to be computed once.
  /// - The state, immediately after generating the element at this index.
  case normal(Int, Base.Iterator)

  /// An index representing the end of the collection.
  case end

  var isEnd: Bool {
    if case .normal(_, var i) = self { return i.next() == nil }
    return true
  }

  static func ==(lhs: SequenceIndex, rhs: SequenceIndex) -> Bool {
    if case .normal(let l,  _) = lhs, case .normal(let r, _) = rhs {
      return l == r
    }
    return lhs.isEnd == rhs.isEnd
  }

  static func < (lhs: SequenceIndex, rhs: SequenceIndex) -> Bool {
    if case .normal(let l,  _) = lhs, case .normal(let r, _) = rhs {
      return l < r
    }
    return !lhs.isEnd && rhs.isEnd
  }

  mutating func stepForward() {
    guard case .normal(let pos, var i) = self else {
      fatalError("Can't advance past end")
    }
    _ = i.next()
    self = .normal(pos + 1, i)
  }

  func distance(to other: SequenceIndex) -> Int {
    switch (self, other) {
    case (.end, .end): return 0
    case (.normal(let l, _), .normal(let r, _)): return r - l
    default: break
    }
    var i = self
    var n = 0
    while i != .end { i.stepForward(); n += 1 }
    return n
  }

  var element: Base.Element {
    guard case .normal(_, var i) = self else {
      fatalError("Can't subscript at end")
    }
    return i.next()!
  }
}

protocol MultipassSequence : Collection {}

extension MultipassSequence {
  var startIndex: SequenceIndex<Self> {
    return SequenceIndex(self)
  }

  var endIndex: SequenceIndex<Self> {
    return SequenceIndex()
  }

  subscript(i: SequenceIndex<Self>) -> Iterator.Element {
    return i.element
  }

  func index(after i: SequenceIndex<Self>) -> SequenceIndex<Self> {
    var j = i
    j.stepForward()
    return j
  }

  func formIndex(after i: inout SequenceIndex<Self>) {
    i.stepForward()
  }

  typealias SubSequence = MultipassSubSequence<Self>
  subscript(r: Range<SequenceIndex<Self>>) -> MultipassSubSequence<Self> {
    return MultipassSubSequence(
      startIndex: r.lowerBound,
      endIndex: r.upperBound
    )
  }
}

struct MultipassSubSequence<Base: MultipassSequence> : Collection {
  typealias Element = Base.Element
  typealias Index = SequenceIndex<Base>
  typealias SubSequence = MultipassSubSequence

  let startIndex, endIndex: Index

  subscript(i: Index) -> Iterator.Element {
    return i.element
  }

  func index(after i: Index) -> Index {
    var j = i
    j.stepForward()
    return j
  }

  func formIndex(after i: inout Index) {
    i.stepForward()
  }

  subscript(r: Range<SequenceIndex<Base>>) -> MultipassSubSequence {
    return MultipassSubSequence(
      startIndex: r.lowerBound,
      endIndex: r.upperBound
    )
  }
}

extension Collection {
  /// Returns the index of the first element in the collection
  /// that matches the predicate.
  ///
  /// The collection must already be partitioned according to the
  /// predicate, as if `self.partition(by: predicate)` had already
  /// been called.
  func partitionPoint(
    where predicate: (Element) throws -> Bool
  ) rethrows -> Index {
    var n = count
    var l = startIndex

    while n > 0 {
      let half = n / 2
      let mid = index(l, offsetBy: half)
      if try predicate(self[mid]) {
        n = half
      } else {
        l = index(after: mid)
        n -= half + 1
      }
    }
    return l
  }
}

/// A minimal sequence that gets its `Collection` conformance by declaring its
/// `Index == SequenceIndex`.
struct S: MultipassSequence, IteratorProtocol {
  typealias Iterator = S
  typealias Index = SequenceIndex<S>

  var n = 0
  var m = 1
  mutating func next() -> Int? {
    let r = n
    (n, m) = (m, n + m)
    return r
  }
}

let s = S()
print(Array(s.prefix(5)))                    // [0, 1, 1, 2, 3]
let i = s.index(where: { $0 > 6 })!
print(Array(s[i...].prefix(5)))              // [8, 13, 21, 34, 55]

let s2 = S().prefix(90)
print(
  s2.distance(
    from: s2.startIndex, to: s2.partitionPoint { $0 >= 1000 }))