EitherCollection.swift

////===--- EitherCollection.swift - A collection of two different types -----===//
////
//// This source file is part of the Swift.org open source project
////
//// Copyright (c) 2014 - 2020 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
////
////===-----------------------------------------------------------------------------------===//

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

// A Collection that can hold an Either<Left,Right>
// When you don't need to iterate them fully in order, or you only
// want all of one of the types, you can iterate either the .left
// or .right property, which is a contiguous array of that type.
struct EitherCollection<Left,Right> {
  var left: [Left] = []
  var right: [Right] = []
  enum ElementType { case left, right }
  var types: [ElementType] = []
}

extension EitherCollection {
  mutating func append(_ element: Left) {
    left.append(element); types.append(.left)
  }
  mutating func append(_ element: Right) {
    right.append(element); types.append(.right)
  }
}

extension EitherCollection {
  struct Iterator {
    var left: Array<Left>.Iterator
    var right: Array<Right>.Iterator
    var types: Array<ElementType>.Iterator
  }
}

extension EitherCollection.Iterator: IteratorProtocol {
  typealias Element = Either<Left,Right>
  mutating func next() -> Element? {
    types.next().flatMap {
      switch $0 {
      case .left: return left.next().map(Either.init)
      case .right: return right.next().map(Either.init)
      }
    }
  }
}

extension EitherCollection: Sequence {
  func makeIterator() -> Iterator {
    Iterator(left: left.makeIterator(), right: right.makeIterator(), types: types.makeIterator())
  }
}

extension EitherCollection {
  struct Index {
    let left: Int
    let right: Int
    var sum: Int { left &+ right }
  }
}

extension EitherCollection.Index: Comparable {
  static func < (lhs: Self, rhs: Self) -> Bool { lhs.sum < rhs.sum }
}


extension EitherCollection: Collection {
  typealias Element = Either<Left,Right>
  
  var startIndex: Index { Index(left: 0, right: 0) }
  var endIndex: Index { Index(left: left.endIndex, right: right.endIndex) }
  subscript(i: Index) -> Element {
    switch types[i.sum] {
    case .left: return Element(left[i.left])
    case .right: return Element(right[i.right])
    }
  }
  func index(after i: Index) -> Index {
    guard i != endIndex else { return endIndex }
    switch types[i.sum] {
    case .left: return Index(left: i.left &+ 1, right: i.right)
    case .right: return Index(left: i.left, right: i.right &+ 1)
    }
  }
}


import QuartzCore

extension EitherCollection where Left == Int, Right == Double {
  func test() -> Int {
    left.reduce(0, &+) + right.reduce(0) { $0 &+ Int($1) }
  }
}

extension Collection where Element == Either<Int,Double> {
  func test() -> Int {
    reduce(0) { sum, e in
      switch e {
      case let .left(l): return sum &+ l
      case let .right(r): return sum &+ Int(r)
      }
    }
  }
}

extension Collection where Element == Any {
  func test() -> Int {
    reduce(0) { sum, a in
      switch a {
      case let i as Int: return sum &+ i
      case let d as Double: return sum &+ Int(d)
      default: fatalError()
      }
    }
  }
}

let n = 1000

@inline(never)
func fetchArrayOfEither() -> [Either<Int,Double>] {
  (0..<n).map { i in Bool.random() ? Either(i) : Either(Double(i)) }
}

@inline(never)
func fetchEitherArray() -> EitherCollection<Int,Double> {
  var result = EitherCollection<Int,Double>()
  for i in 0..<n {
    if Bool.random() {
      result.append(i)
    } else {
      result.append(Double(i))
    }
  }
  return result
}

@inline(never)
func fetchArrayOfAny() -> [Any] {
  (0..<n).map { i in Bool.random() ? i as Any : Double(i) as Any }
}

let either = fetchArrayOfEither()
let any = fetchArrayOfAny()
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()

let eitherArray = fetchEitherArray()
let start2 = CACurrentMediaTime()
var eitherArrayResult = 0
for _ in 0..<n { eitherArrayResult &+= eitherArray.test() }
let end2 = CACurrentMediaTime()


precondition(eitherResult == anyResult)

print("ArrayOfEither: ",(mid-start)*1_000)
print("AnyCollection: ",(end-mid)*1_000)
print("EitherCollection: ",(end2-start2)*1_000)
print("Speedup over Either: \(((mid-start)/(end2-start2)))x")
print("Speedup over Any: \(((end-mid)/(end2-start2)))x")

Wow, this is fast, this test is right?

swiftc EitherCollection.swift -O
./EitherCollection

ArrayOfEither:  1.2586839993673493
AnyCollection:  59.98129900035565
EitherCollection:  0.6025189995852998
Speedup over Either: 2.089036196756738x
Speedup over Any: 99.55088394165068x