Overloading with conditional conformance

(Note: Full code is here, the Swift 4.2 toolchain wasn't liking my collection conditional conformance for some reason so you'll have to use a Swift 5 one)

I'm trying to make a struct that exposes a sequence/collection of adjacent pairs of elements in a base sequence/collection (so it would turn [1, 2, 3, 4] into [(1, 2), (2, 3), (3, 4)]). To do it, I'm following the (I think) standard practice of making the base struct that conforms to Sequence and then conditional conformances to Collection, BidirectionalCollection, etc.

I'm modeling my Index as a pair of Base.Index representing the two indices from the base collection. Its comparable conformance only compares the second index, since the other index should always be the one directly before it.

Based on that, for my conformance to Collection, since I can't get the index before the base's endIndex (since Base is only a collection) I just do this for my endIndex:

extension AdjacentPairsSequence: Collection where Base: Collection {
	// Other collection conformance stuff
	public var endIndex: Index {
		return Index(first: base.endIndex, second: base.endIndex)
	}
}

Since the endIndex of a Collection can only be used as a comparison point (and my comparison only checks the second element) this should be fine.

On the other hand, in the BidirectionalCollection interface, that's no longer enough, since you can use the endIndex to get indices before the endIndex and those have to be valid. Because of that, I added a second endIndex definition to the BidirectionalCollection extension:

extension AdjacentPairsSequence: BidirectionalCollection where Base: BidirectionalCollection {
	public var endIndex: Index {
		let end = base.endIndex
		guard end != base.startIndex else { return Index(first: end, second: end) }
		return Index(first: base.index(before: end), second: end)
	}
	// index(before:) method
}

I was hoping that in use, BidirectionalCollections would get the second method and other Collections would get the first, which... sort of happens:

func printEndIndex<C: BidirectionalCollection>(_ c: C) {
	print("End index as viewed from a generic function: \(c.endIndex)")
}
let col = [1, 2, 3].adjacentPairs
print("End index from a non-generic context: \(col.endIndex)") // Uses the BidirectionalCollection extension's method
printEndIndex(col) // Uses the Collection extension's method

Is this the intended behavior? Should I be able to define both of those methods at all?

Unrelated to your specific generics issue, I would suggest only storing one index from the base collection in your index so you can avoid the possibility of them becoming inconsistent. Though I guess it's theoretically possible that finding the next index for some collection is very expensive, and your current implementation would avoid having to do that when subscripting. One trick that might be helpful here is that you can make a custom end index that is unrelated to the underlying collection, e.g. a separate enum case.

Advancing indices in subscripts can cause O(n) subscripting (for example on lazy filter collections) which breaks the requirement that collection subscripting must be O(1) and could mess up time complexities of algorithms

I considered having the enum but doing that would have made things much more complicated so I'd rather not

2 Likes
Terms of Service

Privacy Policy

Cookie Policy