Stern's Diatomic and the Calkin–Wilf Sequences in Swift

Stern-Calkin-Wilf-sequences.swift

// Copyright (c) 2018 Daryle Walker.
// Distributed under the MIT License.

// Based off <https://en.wikipedia.org/wiki/Calkin–Wilf_tree>.
// "fusc" from Edsger W. Dijkstra.
// To-Do: Add the iterative version of "fusc"

struct SternDiatomicSequenceIterator: IteratorProtocol {

    var cache = [0: 0, 1: 1]
    var index = 0

    mutating func next() -> Int? {
        cache[2 * index] = cache[index]
        cache[2 * index + 1] = cache[index]! + cache[index + 1]!
        defer { index += 1 }
        return cache.removeValue(forKey: index)
    }

}

struct CalkinWilfSequenceIterator: IteratorProtocol {

    var fusc: SternDiatomicSequenceIterator
    var current: (Int, Int)

    init() {
        fusc = SternDiatomicSequenceIterator()
        current.0 = fusc.next()!
        current.1 = fusc.next()!
    }

    mutating func next() -> (Int, Int)? {
        defer { current = (current.1, fusc.next()!) }
        return current
    }

}