EitherSequence.swift

////===--- EitherSequence.swift - A sequence type-erasing two sequences -----===//
////
//// 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
////
////===----------------------------------------------------------------------===//

internal enum Either<Left, Right> {
  case left(Left), right(Right)
}

extension Either {
  internal init(_ left: Left, or other: Right.Type) { self = .left(left) }
  internal init(_ left: Left) { self = .left(left) }
  internal init(_ right: Right) { self = .right(right) }
}

extension Either: Equatable where Left: Equatable, Right: Equatable {
  internal static func == (lhs: Self, rhs: Self) -> Bool {
    switch (lhs, rhs) {
    case let (.left(l), .left(r)): return l == r
    case let (.right(l), .right(r)): return l == r
    case (.left, .right), (.right, .left): return false
    }
  }
}

extension Either: Comparable where Left: Comparable, Right: Comparable {
  internal static func < (lhs: Self, rhs: Self) -> Bool {
    switch (lhs, rhs) {
    case let (.left(l), .left(r)): return l < r
    case let (.right(l), .right(r)): return l < r
    case (.left, .right): return true
    case (.right, .left): return false
    }
  }
}

/// A sequence that type erases two sequences. A lighter-weight alternative to
/// AnySequence when more can be statically known, and which is more easily specialized.
/// If you  only know about one of the types, the second one can be AnySequence,
/// giving you a fast path for the known one.
/// If you have 3+ types to erase, you can nest them.
typealias EitherSequence<L: Sequence, R: Sequence> =
  Either<L,R> where L.Element == R.Element

extension EitherSequence {
  internal struct Iterator {
    var left: Left.Iterator?
    var right: Right.Iterator?
  }
}

extension Either.Iterator: IteratorProtocol {
  internal typealias Element = Left.Element

  internal mutating func next() -> Element? {
    left?.next() ?? right?.next()
  }
}

extension EitherSequence: Sequence {
  internal typealias Element = Left.Element

  internal func makeIterator() -> Iterator {
    switch self {
    case let .left(l):
      return Iterator(left: l.makeIterator(), right: nil)
    case let .right(r):
      return Iterator(left: nil, right: r.makeIterator())
    }
  }
}

internal typealias EitherCollection<
  T: Collection, U: Collection
> = EitherSequence<T,U> where T.Element == U.Element

extension EitherCollection: Collection {
  internal typealias Index = Either<Left.Index, Right.Index>

  internal var startIndex: Index {
    switch self {
    case let .left(s): return .left(s.startIndex)
    case let .right(s): return .right(s.startIndex)
    }
  }

  internal var endIndex: Index {
    switch self {
    case let .left(s): return .left(s.endIndex)
    case let .right(s): return .right(s.endIndex)
    }
  }

  internal subscript(position: Index) -> Element {
    switch (self,position) {
    case let (.left(s),.left(i)): return s[i]
    case let (.right(s),.right(i)): return s[i]
    default: fatalError("EitherCollecton: Sequence used with other index type")
    }
  }

  internal func index(after i: Index) -> Index {
    switch (self,i) {
    case let (.left(s),.left(i)): return .left(s.index(after: i))
    case let (.right(s),.right(i)): return .right(s.index(after: i))
    default: fatalError("EitherCollecton: wrong type of index used")
    }
  }

  internal func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
    switch (self,i,limit) {
    case let (.left(s),.left(i),.left(limit)):
      return s.index(i, offsetBy: distance, limitedBy: limit).map { .left($0) }
    case let (.right(s),.right(i),.right(limit)):
      return s.index(i, offsetBy: distance, limitedBy: limit).map { .right($0) }
    default: fatalError("EitherCollecton: wrong type of index used")
    }
  }

  internal func index(_ i: Index, offsetBy distance: Int) -> Index {
    switch (self,i) {
    case let (.left(s),.left(i)): return .left(s.index(i, offsetBy: distance))
    case let (.right(s),.right(i)): return .right(s.index(i, offsetBy: distance))
    default: fatalError("EitherCollecton: wrong type of index used")
    }
  }

  internal func distance(from start: Index, to end: Index) -> Int {
    switch (self,start,end) {
    case let (.left(s),.left(i),.left(j)):
      return s.distance(from: i, to: j)
    case let (.right(s),.right(i),.right(j)):
      return s.distance(from: i, to: j)
    default: fatalError("EitherCollecton: wrong type of index used")
    }
  }
}

internal typealias EitherBidirectionalCollection<
  T: BidirectionalCollection, U: BidirectionalCollection
> = Either<T,U> where T.Element == U.Element

extension EitherBidirectionalCollection: BidirectionalCollection {
  internal func index(before i: Index) -> Index {
    switch (self,i) {
    case let (.left(s),.left(i)): return .left(s.index(before: i))
    case let (.right(s),.right(i)): return .right(s.index(before: i))
    default: fatalError("EitherCollecton: wrong type of index used")
    }
  }
}

internal typealias EitherRandomAccessCollection<
  L: RandomAccessCollection, R: RandomAccessCollection
> = Either<L,R> where L.Element == R.Element

extension EitherRandomAccessCollection: RandomAccessCollection { }



import QuartzCore

extension Collection where Element == Int {
  func test() -> Int {
    reduce(0, &+) &+ self.min()! + count
  }
}

let n = 1000
let a = Array(0..<100)
let b = 0..<100

@inline(never)
func fetchEither() -> Either<[Int],Range<Int>> {
  Bool.random() ? Either(a) : Either(b)
}

@inline(never)
func fetchAny() -> AnyRandomAccessCollection<Int> {
  Bool.random() ? AnyRandomAccessCollection(a) : AnyRandomAccessCollection(b)
}

let either = fetchEither()
let any = fetchAny()
let start = CACurrentMediaTime()
var eitherResult = 0
for _ in 0..<n { eitherResult &+= either.test()  }
let mid = CACurrentMediaTime()
var anyResult = 0
for _ in 0..<n { anyResult &+= any.test() }
let end = CACurrentMediaTime()

precondition(eitherResult == anyResult)

print("EitherCollection: ",(mid-start)*1_000)
print("AnyCollection: ",(end-mid)*1_000)
print("Speedup: \(Int((end-mid)/(mid-start)))x")