2
我做了一个（非常基本的）BinaryTree协议序列：符合新协议与默认makeIterator（）实现
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无法推断。如果我手动指定与
extension BinaryHeap: BinaryTree {
typealias Iterator = BinaryTreeIterator<BinaryHeap>
...
}
的Iterator类型，然后编译器显示的错误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
苹果自己的IndexingIterator似乎以类似的方式来工作，我BinaryTreeIterator：
public struct IndexingIterator<
Elements : IndexableBase
// FIXME(compiler limitation):
// Elements : Collection
> : IteratorProtocol, Sequence {
...
}
从source code 。也许我面临的问题也可能是因为那里提到的编译器限制，但我不确定。
有没有办法符合BinaryTree到Sequence而不使用AnyIterator？
这是一个令人难以置信的令人烦恼的问题。到目前为止，我已经投入了数小时的研究，并没有发现任何真正有用的东西。 – KFDoom
如何不使用'AnyIterator'考虑使用BinaryTreeIterator类型转换，并添加'序列'作为一个协议，以符合'BinaryTreeIterator'结构？ – KFDoom
@KFDoom我不确定我会跟着，你想打什么？ –