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

Question

Некоторое время назад я создал двоичный тип дерева поиска в Swift, который я хотел бы согласовать с протоколом Collection. Однако требование endIndex является индексом «за конец», который не подходит для дерева, потому что каждый индекс должен содержать ссылку на соответствующий узел для доступа O (1). Я закончил с опциональной ссылкой (был nil в случае endIndex), но это связано с большим количеством кода шаблона, который я бы предпочел избежать.

я решил сделать 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; вы хотите добавить его?

или

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

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

Некоторые вещи, чтобы отметить:

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

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

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

Answer 1

Добавление associatedtype Element к ValidIndexCollection и заменив все вхождения Iterator.Element от Element установил ее.