Implement the `Array` &` ArraySlice` extension instead of the protocol
I have the following Swift code:
extension Array {
typealias EqualTest = (Iterator.Element, Iterator.Element) -> Bool
func groupSplitIndices(withEqualTest equal: EqualTest) -> [Index] {
return indices.groupSplitIndices(withEqualTest: {equal(self[$0], self[$1])})
}
}
extension ArraySlice {
typealias EqualTest = (Iterator.Element, Iterator.Element) -> Bool
func groupSplitIndices(withEqualTest equal: EqualTest) -> [Index] {
return indices.groupSplitIndices(withEqualTest: {equal(self[$0], self[$1])})
}
}
extension CountableRange {
typealias EqualTest = (Element, Element) -> Bool
func groupSplitIndices(withEqualTest equal: EqualTest) -> [Element] {
// Implementation omitted here.
// For details see "Background" at the end of the question.
}
}
Instead of extending Array
and ArraySlice
using identical code, is there a protocol that I can extend that will achieve the same result?
Essentially, I would like to extend any collection where the associated type Indices
is CountableRange
.
General implementation attempts
I've tried to express this in different ways, but I haven't found a way to compile it.
Attempt 1
extension RandomAccessCollection {
typealias EqualTest = (Iterator.Element, Iterator.Element) -> Bool
func groupSplitIndices(withEqualTest equal: EqualTest) -> [Index] {
// Error on next line…
return indices.groupSplitIndices(withEqualTest: {equal(self[$0], self[$1])})
}
}
This attempt gives 2 errors:
The value of type "Self.Indices" has no member groupSplitIndices'
Closing a parameter use without aligning "equals" may let it exit
(I think the second error is: Swift is confusing.)
Attempt 2
extension RandomAccessCollection where Indices: CountableRange {
// Implementation omitted.
}
Gives an error:
A reference to the generic type "CountableRange" requires arguments in <...>
Attempt 3
extension RandomAccessCollection where Indices: CountableRange<Int> {
// Implementation omitted.
}
Gives an error:
Type "Indexes" bound to the non-protocol type "CountableRange"
Background
Here's an extension to CountableRange
, implementing groupRanges(withEqualTest:)
, which is omitted above. The algorithm, what it does, and the cost of Big O are discussed in this question.
I tried to implement something similar to an extension RandomAccessCollection
but didn't have much luck.
extension CountableRange {
typealias EqualTest = (Element, Element) -> Bool
func groupRanges(withEqualTest equal:EqualTest) -> [CountableRange] {
let groupIndices = groupSplitIndices(withEqualTest: equal)
return groupIndices.indices.dropLast().map {groupIndices[$0]..<groupIndices[$0+1]}
}
func groupSplitIndices(withEqualTest equal: EqualTest) -> [Element] {
var allIndexes = [lowerBound]
allIndexes.append(contentsOf: interiorGroupSplitIndices(withEqualTest: equal))
allIndexes.append(upperBound)
return allIndexes
}
func interiorGroupSplitIndices(withEqualTest equal: EqualTest) -> [Element] {
var result = Array<Element>()
var toDo = [self]
while toDo.count > 0 {
let range = toDo.removeLast()
guard
let firstElement = range.first,
let lastElement = range.last,
firstElement != lastElement,
!equal(firstElement, lastElement) else {
continue;
}
switch range.count {
case 2:
result.append(lastElement)
default:
let midIndex = index(firstElement, offsetBy: range.count/2)
toDo.append(range.suffix(from: midIndex))
toDo.append(range.prefix(through: midIndex))
}
}
return result
}
}
source to share
To call indices.groupSplitIndices()
you will need a constraint
Indices == CountableRange<Index>
in the extension of the collection, and this requires Index
being Strideable
:
extension RandomAccessCollection where Index: Strideable, Indices == CountableRange<Index> {
typealias EqualTest = (Iterator.Element, Iterator.Element) -> Bool
func groupSplitIndices(withEqualTest equal: EqualTest) -> [Index] {
return indices.groupSplitIndices(withEqualTest: {
equal(self[$0], self[$1])
})
}
}
extension CountableRange {
typealias EqualTest = (Element, Element) -> Bool
func groupSplitIndices(withEqualTest equal: EqualTest) -> [Element] {
// Dummy implementation:
return []
}
}
and this actually compiles with Swift 4 (Xcode 9 beta or Xcode 8.3.3 with Swift 4 toolchain).
There is one problem: the Swift 3 compiler in Xcode 8.3.3 crashes when compiling the above code with the "Debug" configuration. This seems to be a compiler bug as it compiles without issue in the "Release" configuration, or with Xcode 9 or Xcode 8.3.2 and the Swift 4 toolchain.
Here is a rough description of how I figured out this solution. Start with Attempt 3:
extension RandomAccessCollection where Indices: CountableRange<Int>
// error: type 'Indices' constrained to non-protocol type 'CountableRange<Int>
Indices
cannot be a subclass or an accepting type, CountableRange<Int>
which means we need the same type of requirement:
extension RandomAccessCollection where Indices == CountableRange<Int>
The result is
// error: cannot subscript a value of type 'Self' with an index of type 'Int'
in self[$0]
and self[$1]
. The method subscript
Collection
takes a parameter Self.Index
, so we change it to
extension RandomAccessCollection where Indices == CountableRange<Index>
// error: type 'Self.Index' does not conform to protocol '_Strideable'
So it Index
should be Strideable
:
extension RandomAccessCollection where Index: Strideable, Indices == CountableRange<Index>
what is it!
source to share