使用默认的makeIterator()实现将新协议与Sequence兼容 [英] Conforming a new protocol to Sequence with a default makeIterator() implementation

问题描述

我制定了(非常基本的)BinaryTree协议:

I made a (very basic) BinaryTree protocol:

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 }

}

对于基本的迭代有序遍历，我做了一个(请注意，我还没有实现Sequence):

For a basic iterative in-order traversal, I made a BinaryTreeIterator (note that I don't implement Sequence just yet):

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]
    }

}

为此协议添加二进制堆也很简单:

Implementing a binary heap to this protocol is also pretty straight-forward:

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]
    }

}

到目前为止，太好了.现在，我可以创建一个简单的堆并遍历其元素:

So far, so good. I can now make a simple heap and iterate through its elements:

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.但是，如果我更换

This works, but of course the goal of implementing makeIterator() is to conform to Sequence. however, if I replace

public protocol BinaryTree {

使用

public protocol BinaryTree: Sequence {

然后，编译器抱怨BinaryHeap没有实现Sequence，因为无法推断关联的类型Iterator.如果我手动指定Iterator类型

then the compiler complains that BinaryHeap doesn't implement Sequence because the associated type Iterator couldn't be inferred. If I manually specify the Iterator type with

extension BinaryHeap: BinaryTree {

    typealias Iterator = BinaryTreeIterator<BinaryHeap>

    ...

}

然后，编译器显示错误，Iterator循环引用其自身.因此，这可能就是为什么无法推断Iterator类型的原因.

then the compiler shows an error that Iterator circularly references itself. So that might be why the Iterator type couldn't be inferred.

有趣的是，如果我将自定义的BinaryTreeIterator包装在AnyIterator实例中，则可以使用:

Interestingly, it works if I wrap my custom BinaryTreeIterator in an AnyIterator instance:

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

苹果自己的IndexingIterator的工作方式与我的BinaryTreeIterator相似:

Apple's own IndexingIterator seems to work in a similar fashion to my BinaryTreeIterator:

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

来自源代码 .也许我面临的问题可能是由于那里提到的编译器限制，但我不确定.

From the source code. Maybe the problem I'm facing might also be because of the compiler limitation mentioned there, but I don't know for sure.

是否可以在不使用AnyIterator的情况下使BinaryTree符合Sequence?

Is there a way to conform BinaryTree to Sequence without using AnyIterator?

推荐答案

显然是Swift的错误:我的代码可以使用Swift 3.1很好地编译.

Apparently it was a Swift bug: my code compiles fine using Swift 3.1.

这篇关于使用默认的makeIterator()实现将新协议与Sequence兼容的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！