使用默认的 makeIterator() 实现使新协议符合 Sequence

Question

我做了一个（非常基本的）BinaryTree 协议：

public enum BinaryTreeChildSide {
    case left, right
}

public protocol BinaryTree {

    associatedtype Element
    associatedtype Index

    func child(of index: Index, side: BinaryTreeChildSide) -> Index?
    var rootIndex: Index? { get }
    subscript(position: Index) -> Element { get }

}

对于基本的 iterative in-order traversal，我做了一个 BinaryTreeIterator（注意我还没有实现 Sequence）：

public extension BinaryTree {

    func makeIterator() -> BinaryTreeIterator<Self> {
        return BinaryTreeIterator(self)
    }

}

public struct BinaryTreeIterator<Tree: BinaryTree>: IteratorProtocol {

    private let tree: Tree
    private var stack: [Tree.Index]
    private var index: Tree.Index?

    private init(_ tree: Tree) {
        self.tree = tree
        stack = []
        index = tree.rootIndex
    }

    public mutating func next() -> Tree.Element? {
        while let theIndex = index {
            stack.append(theIndex)
            index = tree.child(of: theIndex, side: .left)
        }

        guard let currentIndex = stack.popLast() else { return nil }
        defer { index = tree.child(of: currentIndex, side: .right) }

        return tree[currentIndex]
    }

}

为此协议实现二进制堆也非常简单：

public struct BinaryHeap<Element> {

    private var elements: [Element]

    public init(_ elements: [Element]) {
        self.elements = elements
    }

}

extension BinaryHeap: BinaryTree {

    private func safeIndexOrNil(_ index: Int) -> Int? {
        return elements.indices.contains(index) ? index : nil
    }

    public func child(of index: Int, side: BinaryTreeChildSide) -> Int? {
        switch side {
        case .left: return safeIndexOrNil(index * 2 + 1)
        case .right: return safeIndexOrNil(index * 2 + 2)
        }
    }

    public var rootIndex: Int? { return safeIndexOrNil(0) }

    public subscript(position: Int) -> Element {
        return elements[position]
    }

}

到目前为止，还不错。我现在可以制作一个简单的堆并遍历其元素：

let heap = BinaryHeap([4, 2, 6, 1, 3, 5, 7])
var iterator = heap.makeIterator()

while let next = iterator.next() {
    print(next, terminator: " ")
}
// 1 2 3 4 5 6 7

这行得通，但是实现 makeIterator() 的目标当然是要符合 Sequence。但是，如果我替换

public protocol BinaryTree {

与

public protocol BinaryTree: Sequence {

然后编译器抱怨 BinaryHeap 没有实现 Sequence 因为无法推断关联类型 Iterator。如果我用

手动指定 Iterator 类型

extension BinaryHeap: BinaryTree {

    typealias Iterator = BinaryTreeIterator<BinaryHeap>

    ...

}

然后编译器显示 Iterator 循环引用自身的错误。所以这可能就是无法推断 Iterator 类型的原因。

有趣的是，如果我将自定义 BinaryTreeIterator 包装在 AnyIterator 实例中，它会起作用：

public extension BinaryTree {

    func makeIterator() -> AnyIterator<Element> {
        return AnyIterator(BinaryTreeIterator(self))
    }

}

let heap = BinaryHeap([4, 2, 6, 1, 3, 5, 7])

for number in heap {
    print(number, terminator: " ")
}
// 1 2 3 4 5 6 7

Apple 自己的 IndexingIterator 似乎与我的 BinaryTreeIterator:

的工作方式类似

public struct IndexingIterator<
    Elements : IndexableBase
    // FIXME(compiler limitation):
    // Elements : Collection
> : IteratorProtocol, Sequence {
    ...
}

来自source code。也许我面临的问题也可能是因为那里提到的编译器限制，但我不确定。

有没有办法在不使用 AnyIterator 的情况下使 BinaryTree 符合 Sequence？

Answer 1

这是我能走的最远的地方了。现在编译器仍然会抱怨堆不包含任何 makeIterator 成员（我认为一旦有人符合序列，它就会被默认包含——错误的结果是，默认实现必须符合序列和 IteratorProtocol）并有一个下一个——但是一旦你添加这些方法一帆风顺。

所以 makeIterator + next 方法让 Mr/Mrs/Preferred 性别代词编译器满意。

public enum BinaryTreeChildSide {
    case left, right
}

public struct BinaryTreeIterator<Tree: BinaryTree>: Sequence, IteratorProtocol {

    private let tree: Tree
    private var stack: [Tree.Index]
    private var index: Tree.Index?

    private init(_ tree: Tree) {
        self.tree = tree
        stack = []
        index = tree.rootIndex
    }

    public mutating func next() -> Tree.Element? {
        while let theIndex = index {
            stack.append(theIndex)
            index = tree.child(of: theIndex, side: .left)
        }

        guard let currentIndex = stack.popLast() else { return nil }
        defer { index = tree.child(of: currentIndex, side: .right) }

        return tree[currentIndex]
    }

}


public protocol BinaryTree: Sequence {

    associatedtype Element
    associatedtype Index

    func child(of index: Index, side: BinaryTreeChildSide) -> Index?
    var rootIndex: Index? { get }
    subscript(position: Index) -> Element { get }

}



extension BinaryTree {

    func makeIterator() -> BinaryTreeIterator<Self> {
        return BinaryTreeIterator(self)
    }

}

extension BinaryHeap {


    private func safeIndexOrNil(_ index: Int) -> Int? {
        return elements.indices.contains(index) ? index : nil
    }

    public func child(of index: Int, side: BinaryTreeChildSide) -> Int? {
        switch side {
        case .left: return safeIndexOrNil(index * 2 + 1)
        case .right: return safeIndexOrNil(index * 2 + 2)
        }
    }

    public var rootIndex: Int? { return safeIndexOrNil(0) }

    public subscript(position: Int) -> Element {
        return elements[position]
    }

}

public struct BinaryHeap<Element> {

    private var elements: [Element]


    public init(_ elements: [Element]) {
        self.elements = elements
    }

}

let heap = BinaryHeap([4, 2, 6, 1, 3, 5, 7])
var iterator = heap.makeIterator()

while let next = iterator.next() {
    print(next, terminator: " ")
}

Answer 2

显然这是一个 Swift 错误：我的代码使用 Swift 3.1.

编译得很好

使用默认的 makeIterator() 实现使新协议符合 Sequence

Conforming a new protocol to Sequence with a default makeIterator() implementation

swift

swift3

swift-protocols