Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Demonstrate a multipass sequence index that doesn't store the Element
/// 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