在 Swift 3 中创建 ValidIndexCollection 协议

Question

不久前，我在 Swift 中创建了一个二进制搜索树类型，我希望它符合 Collection 协议。然而，endIndex 要求是一个 "past the end" 索引，它并不真正适合树，因为每个索引都应该保存对其对应节点的引用，以便 O(1) 访问。我最终得到了一个可选参考（在 endIndex 的情况下是 nil），但它涉及很多我宁愿避免的样板代码。

我决定制作一个如下所示的 ValidIndexCollection 协议：

/// A collection defined by valid indices only, rather than a
/// startIndex and a "past the end" endIndex.
protocol ValidIndexCollection: Collection {

    associatedtype ValidIndex: Comparable

    /// The first valid index if the collection is nonempty,
    /// nil otherwise.
    var firstValidIndex: ValidIndex? { get }

    /// The last valid index if the collection is nonempty,
    /// nil otherwise.
    var lastValidIndex: ValidIndex? { get }

    /// Returns the index right after the given index.
    func validIndex(after index: ValidIndex) -> ValidIndex

    /// Returns the element at the given index.
    func element(at index: ValidIndex) -> Iterator.Element

}

在扩展这个协议以满足Collection要求之前，我必须先引入一个合适的索引：

enum ValidIndexCollectionIndex<ValidIndex: Comparable> {
    case index(ValidIndex)
    case endIndex
}

extension ValidIndexCollectionIndex: Comparable {
    // ...
}

现在我可以扩展 ValidIndexCollection:

// Implementing the Collection protocol requirements.
extension ValidIndexCollection {

    typealias _Index = ValidIndexCollectionIndex<ValidIndex>

    var startIndex: _Index {
        return firstValidIndex.flatMap { .index([=13=]) } ?? .endIndex
    }

    var endIndex: _Index {
        return .endIndex
    }

    func index(after index: _Index) -> _Index {
        guard case .index(let validIndex) = index else { fatalError("cannot increment endIndex") }
        return .index(self.validIndex(after: validIndex))
    }

    subscript(index: _Index) -> Iterator.Element {
        guard case .index(let validIndex) = index else { fatalError("cannot subscript using endIndex") }
        return element(at: validIndex)
    }

}

一切似乎都很好，编译器没有抱怨！但是，我尝试为自定义类型实现此协议：

struct CollectionOfTwo<Element> {
    let first, second: Element
}

extension CollectionOfTwo: ValidIndexCollection {

    var firstValidIndex: Int? { return 0 }
    var lastValidIndex: Int? { return 1 }

    func validIndex(after index: Int) -> Int {
        return index + 1
    }

    subscript(index: Int) -> Element {
        return index == 0 ? first : second
    }

}

现在编译器抱怨 CollectionOfTwo 不符合 Collection、Sequence 和 IndexableBase。错误消息非常无用，主要是这样的消息：

Protocol requires nested type SubSequence; do you want to add it?

或

Default type DefaultIndices<CollectionOfTwo<Element>> for associated type Indices (from protocol Collection) does not conform to IndexableBase

有什么方法可以让它工作吗？据我所知，ValidIndexCollection 很好地满足了 Collection 的要求。

一些注意事项：

我调用了ValidIndexCollection协议方法 validIndex(after:) 那样是因为叫它 index(after:) 尝试实现此协议时导致分段错误。这可能与 index(after:) 来自 Collection 协议的方法。
出于同样的原因，我使用 element(at:) 而不是下标。
我使用了 typealias _Index 而不是 typealias Index，因为后者会导致出现错误消息“Index 在此上下文中的类型查找不明确”。同样，这可能与 Collection 的 Index 关联类型有关。

Answer 1

将 associatedtype Element 添加到 ValidIndexCollection 并将出现的所有 Iterator.Element 替换为 Element 修复了它。

在 Swift 3 中创建 ValidIndexCollection 协议

Creating a ValidIndexCollection protocol in Swift 3

protocols

swift

swift-protocols

swift3