Mutable Bidirectional RangeReplaceable Zip

MutableBidirectionalRangeReplaceableZip.swift

struct MutableBidirectionalRangeReplaceableZip2<
First : BidirectionalCollection
  & RangeReplaceableCollection
  & MutableCollection,
Second : BidirectionalCollection 
  & RangeReplaceableCollection 
  & MutableCollection
> {
  var first: First, second: Second
  init(first: First, second: Second) {
    precondition(first.count == second.count)
    self.first = first
    self.second = second
  }
}

extension MutableBidirectionalRangeReplaceableZip2 : Sequence {
  func makeIterator() -> Zip2Sequence<First,Second>.Iterator {
    return (zip(first, second) as Zip2Sequence).makeIterator()
  }
}

extension MutableBidirectionalRangeReplaceableZip2 : MutableCollection {
  struct Index : Comparable {
    var first: First.Index
    var second: Second.Index

    static func == (lhs: Index, rhs: Index) -> Bool {
      return lhs.first == rhs.first && lhs.second == rhs.second
    }
    static func < (lhs: Index, rhs: Index) -> Bool {
      return lhs.first < rhs.first ||
        lhs.first == rhs.first &&  lhs.second < rhs.second
    }
  }

  var startIndex: Index {
    return Index(first: first.startIndex, second: second.startIndex)
  }
  var endIndex: Index {
    return Index(first: first.endIndex, second: second.endIndex)
  }
  func index(after i: Index) -> Index {
    return Index(
      first: first.index(after: i.first),
      second: second.index(after: i.second))
  }
  subscript(i: Index) -> (First.Element, Second.Element) {
    get {
      return (first[i.first], second[i.second])
    }
    set {
      (first[i.first], second[i.second]) = newValue
    }
  }
}

extension MutableBidirectionalRangeReplaceableZip2
  : BidirectionalCollection {
  func index(before i: Index) -> Index {
    return Index(
      first: first.index(before: i.first),
      second: second.index(before: i.second))
  }
}

extension MutableBidirectionalRangeReplaceableZip2
: RangeReplaceableCollection {
  init() { (first, second) = (First(), Second()) }
  
  mutating func replaceSubrange<Replacement : Collection>(
    _ r: Range<Index>, with replacement: Replacement
  ) where Replacement.Element == Element {
    first.replaceSubrange(
      r.lowerBound.first..<r.upperBound.first,
      with: replacement.lazy.map { $0.0 })
    second.replaceSubrange(
      r.lowerBound.second..<r.upperBound.second,
      with: replacement.lazy.map { $0.1 })
  }
}

extension BidirectionalCollection where Self : MutableCollection {
  @discardableResult
  mutating func partition(
    by belongsInSecondPartition: (Element)->Bool
  ) -> Index {
    guard var pivot = index(where: belongsInSecondPartition)
    else { return endIndex }
    
    for i in indices[index(after: pivot)...] {
      if !belongsInSecondPartition(self[i]) {
        swapAt(pivot, i)
        formIndex(after: &pivot)
      }
    }
    return pivot
  }
}

extension BidirectionalCollection where Self : MutableCollection,
  SubSequence : MutableCollection & BidirectionalCollection  {
  mutating func quicksort(by comesBefore: (Element, Element)->Bool) {
    guard let p = first else { return }
    let start = index(after: startIndex)
    guard start != endIndex else { return }
    let mid = self[start...].partition { comesBefore(p, $0) }
    swapAt(startIndex, index(before: mid))
    self[..<mid].quicksort(by: comesBefore)
    self[mid...].quicksort(by: comesBefore)
  }
}

func printAddress<T>(_ p: UnsafePointer<T>) { print(p) }
func testme() {
  var a = Array((1...20).reversed())
  a.sort { $0 % 2 < $1 % 2 }
  print(a)
  printAddress(a)
  a.quicksort(by: <)
  printAddress(a)
  print(a)

  var b = MutableBidirectionalRangeReplaceableZip2(
    first: Array(0...10), second: (0...10).map(String.init)
  )
  print(Array(b))
  b.quicksort(by: { $0.1 < $1.1 })
  print(Array(b))
  let i = b.index { $0.0 == 10 }!
  b.replaceSubrange(i..<b.index(i, offsetBy: 2), with: [(55, "boo"), (65, "goo"), (95, "foo")])
  print(Array(b)) 
}

testme()