How can I fix "Type 'MyType' does not conform to protocol 'Collection'"?

Using Swift
,
6

Ok, a few things:

  • It looks like debouncing rather than deduplication.

  • startIndex can take O(n) time. It should be documented, as it departs from Collection's contract.

  • index(after:) can take O(n) time. It should be documented for violation of Collection contract. It's for RandomAccessCollection, nvm.

  • The subscript(bounds:) implementation is incorrect. You shouldn't use upperBound.upperBound. It'd accidentally include value at upperBound if it has duplicated. Use upperBound.lowerBound instead.

    let a = LazyDeduplicationCollection([1, 2, 3, 3, 3], by: ==)
let start = a.startIndex, end = a.index(start, offsetBy: 2)
a[start] // 1
a[end] // 3
Array(a[start..<end]) // [1, 2, 3], but should exclude 3

The problem lies with the Index, try to move it outside. I don't know why either. It seems like a bug.

public struct LazyDeduplicationIndex<Base: Comparable>: Comparable {
    ...
}

extension LazyDeduplicationIndex: Hashable where Base: Hashable {}

extension LazyDeduplicationSequence: Collection where Base: Collection {
    public typealias SubSequence = LazyDeduplicationSequence<Base.SubSequence>
    public typealias Index = LazyDeduplicationIndex<Base.Index>

    ...
}

Though I'd suggest an easier implementation by using just Base.Index that points to first entry in the duplicated subsequence. This also fix the subscript(bounds:) bug mentioned above.

extension LazyDeduplicationSequence: Collection where Base: Collection {
    public typealias SubSequence = LazyDeduplicationSequence<Base.SubSequence>
    public typealias Index = Base.Index

    public var startIndex: Index { return base.startIndex }
    public var endIndex: Index { return base.endIndex }
    public var isEmpty: Bool { return base.isEmpty }
    public subscript(position: Index) -> Element { return base[position] }

    public func index(after i: Index) -> Index {
        let value = base[i]
        return base[i...].firstIndex { !areEquivalent($0, value) } ?? base.endIndex
    }

    public subscript(bounds: Range<Index>) -> SubSequence {
        return .init(base[bounds], by: areEquivalent)
    }
}

Which results in

let a = LazyDeduplicationCollection([1, 2, 3, 3, 3], by: ==)
let start = a.startIndex, end = a.index(start, offsetBy: 2)
a[start] // 1
a[end] // 3
Array(a[start..<end]) // [1, 2]
1 Like