Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
////===--- 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")
@natecook1000

This comment has been minimized.

Copy link

@natecook1000 natecook1000 commented May 25, 2020

Crashed the compiler with this version:

typealias EitherIterator<L: IteratorProtocol, R: IteratorProtocol> =
  Either<L, R> where L.Element == R.Element

extension EitherIterator: IteratorProtocol {
  mutating func next() -> Left.Element? {
    switch self {
    case .left(var l):
      return l.next()
    case .right(var r):
      return r.next()
    }
  }
}
  
extension EitherSequence: Sequence {
  internal typealias Iterator = Either<Left.Iterator, Right.Iterator>
  internal typealias Element = Left.Element

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

This comment has been minimized.

Copy link

@benjcohen benjcohen commented May 25, 2020

You need to mutate the iterator inside the case (rather than mutating a copy) so you’d need to assign back too, which makes it way less appealing. I don’t think we have a generalized enum equivalent of ?.mutation().

@natecook1000

This comment has been minimized.

Copy link

@natecook1000 natecook1000 commented May 25, 2020

Oh, good point 🤦

Maybe something like:

switch self {
case .left(inout l):
    return l.next()
case .right(inout r:):
    return r.next()
}

The inout is on the wrong side, though 🤔

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment