Создание протокола ValidIndexCollection в Swift 3

Некоторое время назад я создал тип Binary Search Tree в Swift, который хотел соответствовать протоколу Collection. Однако требование endIndex — это индекс «за концом», который на самом деле не подходит для дерева, потому что каждый индекс должен содержать ссылку на соответствующий узел для доступа 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($0) } ?? .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. Сообщения об ошибках очень бесполезны, в основном это такие сообщения, как:

Для протокола требуется вложенный тип SubSequence; Вы хотите добавить это?

or

Тип по умолчанию DefaultIndices<CollectionOfTwo<Element>> для ассоциированного типа Indices (из протокола Collection) не соответствует IndexableBase

Есть ли способ заставить это работать? Насколько я могу судить, ValidIndexCollection прекрасно удовлетворяет требованиям Collection.

Некоторые вещи, которые следует отметить:

• Я назвал метод протокола ValidIndexCollection validIndex(after:) таким образом, потому что его вызов index(after:) привел к ошибке сегментации при попытке реализовать этот протокол. Вероятно, это как-то связано с методом index(after:) из протокола Collection.

• По той же причине я использовал element(at:) вместо нижнего индекса.

• Я использовал typealias _Index вместо typealias Index, потому что последнее привело к сообщению об ошибке, в котором говорилось, что «Index неоднозначен для поиска типа в этом контексте». Опять же, это, вероятно, как-то связано с типом, связанным с Collection Index.