Created
March 15, 2018 23:01
-
-
Save dabrahams/81fb2dd7d81d307ed7ca051f771a7752 to your computer and use it in GitHub Desktop.
Demonstrate a multipass sequence index that doesn't store the Element
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// 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 })) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment