Ich habe ein (sehr einfaches) @ gemacBinaryTree Protokoll

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 }

}

Für ein grundlegendesiterative in-order Traversal, Ich machte einenBinaryTreeIterator (beachte, dass ich @ nicht implementieSequence Jetzt)

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

}

Das Implementieren eines binären Heaps in dieses Protokoll ist ebenfalls recht einfach:

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 weit, ist es gut. Ich kann jetzt einen einfachen Haufen machen und durch seine Elemente iterieren:

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

Dies funktioniert, aber natürlich das Ziel der Implementierung vonmakeIterator() soll mit @ übereinstimmSequence. wenn ich jedoch @ erset

public protocol BinaryTree {

mi

public protocol BinaryTree: Sequence {

dann beschwert sich der Compiler, dassBinaryHeap implementiert @ nicSequence weil der zugehörige TypIterator konnte nicht gefolgert werden. Wenn ich das @ manuell eingeIterator tippe mit

extension BinaryHeap: BinaryTree {

    typealias Iterator = BinaryTreeIterator<BinaryHeap>

    ...

}

then der Compiler zeigt einen Fehler, dassIterator verweist sich kreisförmig auf sich selbst. Das könnte der Grund sein, warum dasIterator type konnte nicht abgeleitet werden.

Interessanterweise funktioniert es, wenn ich meine benutzerdefinierten @ WrBinaryTreeIterator in einem (nAnyIterator 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

Apples eigeneIndexingIterator scheint ähnlich wie mein @ zu funktionierBinaryTreeIterator:

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

Von demQuellcod. Vielleicht liegt das Problem auch an der dort genannten Compiler-Einschränkung, aber ich weiß es nicht genau.

Gibt es eine Möglichkeit, sich anzupassenBinaryTree zuSequence ohne zu benutzenAnyIterator?