swift - 改为使用协议(protocol)实现 `Array` 和 `ArraySlice` 扩展

Question

我有以下 Swift 代码:

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.
  }
}

不是用相同的代码扩展 Array 和 ArraySlice，有没有我可以扩展的协议(protocol)来实现相同的结果？

本质上，我想扩展关联类型 Indices 是 CountableRange 的任何集合。

尝试通用实现

我已经尝试过以多种方式表达这一点，但我还没有找到使其编译的方法。

尝试 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])})
  }
}

这次尝试给出了 2 个错误:

Value of type 'Self.Indices' has no member 'groupSplitIndices'

Closure use of non-escaping parameter 'equal' may allow it to escape

(我认为第二个错误是 Swift 感到困惑。)

尝试 2

extension RandomAccessCollection where Indices: CountableRange {
  // Implementation omitted.
}

给出错误:

Reference to generic type 'CountableRange' requires arguments in <...>

尝试 3

extension RandomAccessCollection where Indices: CountableRange<Int> {
  // Implementation omitted.
}

给出错误:

Type 'Indices' constrained to non-protocol type 'CountableRange'

---

背景

这是 CountableRange 的扩展，实现了上面省略的 groupRanges(withEqualTest:)。讨论了该算法、它的作用以及它的 Big O 成本 in this question .

我曾尝试实现类似于 RandomAccessCollection 的扩展，但运气不佳。

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
  }
}

Answer 1

为了调用indices.groupSplitIndices()你需要约束
Indices == CountableRange<Index>在集合扩展上，这需要 Index成为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 []
    }
}

这实际上是用 Swift 4(Xcode 9 beta 或 Xcode 8.3.3 和 Swift 4 工具链)编译的。

但有一个问题:Xcode 8.3.3 中的 Swift 3 编译器在编译上面的代码带有“调试”配置。好像是编译器错误，因为它在“发布”配置中编译没有问题，以及 Xcode 9 或 Xcode 8.3.2 和 Swift 4 工具链。

---

这是我如何想出上述解决方案的粗略描述。让我们从您的“尝试 3”开始:

extension RandomAccessCollection where Indices: CountableRange<Int>

// error: type 'Indices' constrained to non-protocol type 'CountableRange<Int>

Indices不能是 CountableRange<Int> 的子类或类型，这意味着我们需要一个相同类型的要求:

extension RandomAccessCollection where Indices == CountableRange<Int>

这导致

// error: cannot subscript a value of type 'Self' with an index of type 'Int'

在 self[$0]和 self[$1] . subscript Collection的方法|需要 Self.Index参数，所以我们把它改成

extension RandomAccessCollection where Indices == CountableRange<Index>

// error: type 'Self.Index' does not conform to protocol '_Strideable'

所以 Index必须是 Strideable :

extension RandomAccessCollection where Index: Strideable, Indices == CountableRange<Index>

就是这样!