Соответствие нового протокола Sequence с реализацией makeIterator () по умолчанию

Я сделал (очень простой)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 }

}

Для основногоитерационный обход по порядку, Я сделал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

Собственный AppleIndexingIterator кажется, работает так же, как мойBinaryTreeIterator:

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

Отисходный код, Может быть, проблема, с которой я сталкиваюсь, может быть также из-за упомянутых там ограничений компилятора, но я точно не знаю.

Есть ли способ соответствоватьBinaryTree вSequence без использованияAnyIterator?

 KFDoom03 июл. 2016 г., 08:27
Это невероятно неприятные проблемы. До сих пор я потратил часы на исследования и не нашел ничего действительно полезного.
 KFDoom04 июл. 2016 г., 12:52
Ты прав! Виноват. Хорошо, я думаю, я понял это сейчас. Не возражаете, если бы у нас был быстрый чат?
 Tim Vermeulen03 июл. 2016 г., 12:41
@KFDoom Я не уверен, что следую, что вы хотите набрать cast?
 Tim Vermeulen03 июл. 2016 г., 14:03
Мы можем соответствоватьBinaryTreeIterator вSequence, но компилятор все равно будет жаловатьсяBinaryHeap если мы попытаемся соответствоватьBinaryTree протокол кSequence, : /
 KFDoom03 июл. 2016 г., 12:51
Да, я полагаю, это ужасно неясно. Спасибо за ваше терпение. Я имею в виду следующее:gist.github.com/anonymous/80f162093f0b6f5354088b3823e503e2
 Tim Vermeulen04 июл. 2016 г., 12:15
Вы соответствуетеBinaryTreeIterator вSequence а такжеIteratorProtocol, но вы не соответствуетеBinaryTree ни к чему, верно?
 KFDoom04 июл. 2016 г., 11:21
Да, но в моем ответе я непросто соответствует Sequence, я также соответствую IteratorProtocol. Когда я размещаю код на игровой площадке, он возвращает результаты без каких-либо ошибок. Не могли бы вы протестировать это?
 KFDoom03 июл. 2016 г., 10:42
Как насчет того, чтобы вместо использованияAnyIterator рассмотрите возможность использования BinaryTreeIterator для набора типов и добавьтеSequence в качестве протокола, чтобы соответствовать вBinaryTreeIterator структура?
 KFDoom04 июл. 2016 г., 12:52

Ответы на вопрос(2)

Решение Вопроса

мой код прекрасно компилируется с помощью Swift 3.1.

что я мог взять. Теперь компилятор по-прежнему будет жаловаться на кучу, не содержащую какого-либо члена makeIterator (который, как я думал, был включен по умолчанию, когда кто-то соответствует последовательности - неправильно получается, что нужно соответствовать последовательностиа такжеIteratorProtocol для реализации по умолчанию) и имеет следующий - но как только вы добавите эти методы, его плавный переход.

Так что makeIterator + следующий способ сделать счастливым компилятор Mr / Mrs / Preferred Gender Pronoun.

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: " ")
}

Ваш ответ на вопрос