WIP: Collection Consumers and Searchers

collection_searchers.swift

///
/// Collection Consumers
///

protocol CollectionConsumer {
  associatedtype Element
  func consumeFront<C: Collection>(_ c: C) -> C.Index? where C.Element == Element
}

extension CollectionConsumer {
  func _clampedConsumeFront<C: Collection>(_ c: C) -> C.Index where C.Element == Element {
    return consumeFront(c) ?? c.startIndex
  }
}

protocol BidirectionalCollectionConsumer: CollectionConsumer {
  // Return value is 1-past-the-end
  func consumeBack<C: BidirectionalCollection>(_ c: C) -> C.Index? where C.Element == Element
}

extension BidirectionalCollectionConsumer {
  func _clampedConsumeBack<C: BidirectionalCollection>(
    _ c: C
  ) -> C.Index where C.Element == Element {
    return consumeBack(c) ?? c.endIndex
  }

  func _clampedConsumeBoth<C: BidirectionalCollection>(
    _ c: C
  ) -> Range<C.Index> where C.Element == Element {
    return _clampedConsumeFront(c) ..< _clampedConsumeBack(c)
  }
}

extension Collection {
  func trimFront<CC: CollectionConsumer>(_ cc: CC) -> SubSequence where CC.Element == Element {
    return self[(cc._clampedConsumeFront(self))...]
  }
}

extension BidirectionalCollection {
  func trimBack<CC: BidirectionalCollectionConsumer>(_ cc: CC) -> SubSequence where CC.Element == Element {
    return self[..<(cc._clampedConsumeBack(self))]
  }
  func trim<CC: BidirectionalCollectionConsumer>(_ cc: CC) -> SubSequence where CC.Element == Element {
    return self[cc._clampedConsumeBoth(self)]
  }
}

extension Collection where SubSequence == Self {
  @discardableResult
  mutating func eat(upTo idx: Index) -> SubSequence {
    defer { self = self[idx...] }
    return self[..<idx]
  }
  @discardableResult
  mutating func eat(from idx: Index) -> SubSequence {
    defer { self = self[..<idx] }
    return self[idx...]
  }
  @discardableResult
  mutating func eat(around range: Range<Index>) -> (prefix: SubSequence, suffix: SubSequence) {
    defer { self = self[range] }
    return (self[..<range.lowerBound], self[range.upperBound...])
  }

  @discardableResult
  mutating func eat<CC: CollectionConsumer>(_ cc: CC) -> SubSequence where CC.Element == Element {
    return self.eat(upTo: cc._clampedConsumeFront(self))
  }
}

extension RangeReplaceableCollection {
  mutating func stripFront<CC: CollectionConsumer>(_ cc: CC) where CC.Element == Element {
    self.removeSubrange(..<cc._clampedConsumeFront(self))
  }
}
extension RangeReplaceableCollection where Self: BidirectionalCollection {
  mutating func stripBack<CC: BidirectionalCollectionConsumer>(_ cc: CC) where CC.Element == Element {
    self.removeSubrange(cc._clampedConsumeBack(self)...)
  }

  mutating func strip<CC: BidirectionalCollectionConsumer>(_ cc: CC) where CC.Element == Element {
    self.stripFront(cc)
    self.stripBack(cc)
  }
}

///
/// Convenience overloads with types:
///
///   * Element
///   * Sequence<Element>
///   * Set<Element>
///   * (Element) -> Bool
///
/// for:
///
///   * trimFront, trimBack, trim
///   * stripFront, stripBack, strip
///   * eat
///
///
struct _ConsumerPredicate<Element>: BidirectionalCollectionConsumer {
  let predicate: (Element) -> Bool

  init(_ predicate: @escaping (Element) -> Bool) { self.predicate = predicate }

  func consumeFront<C: Collection>(_ c: C) -> C.Index? where C.Element == Element {
    return c.firstIndex { !predicate($0) }
  }
  func consumeBack<C: BidirectionalCollection>(_ c: C) -> C.Index? where C.Element == Element {
    return consumeFront(c.reversed())?.base
  }
}

struct _ConsumerSequence<S: Sequence>: BidirectionalCollectionConsumer where S.Element: Equatable {
  let seq: S
  init(_ s: S) { self.seq = s }
  typealias Element = S.Element

  func consumeFront<C: Collection>(_ c: C) -> C.Index? where C.Element == Element {
    var idx = c.startIndex
    for e in self.seq {
      guard e == c[idx] else { return nil }
      c.formIndex(after: &idx)
    }
    return idx
  }

  func consumeBack<C: BidirectionalCollection>(_ c: C) -> C.Index? where C.Element == Element {
    // TODO: If `S` is also Bidi, we have a more efficient reverse method available...
    let revSeq = seq.reversed()
    let revConsumer = _ConsumerSequence<Array<S.Element>>(revSeq)
    return revConsumer.consumeFront(c.reversed())?.base
  }
}

///
/// Trim
///
extension Collection {
  func trimFront(_ predicate: (Element) -> Bool) -> SubSequence {
    return withoutActuallyEscaping(predicate) {
      return self.trimFront(_ConsumerPredicate($0))
    }
  }
}
extension Collection where Element: Equatable {
  func trimFront(_ e: Element) -> SubSequence {
    return self.trimFront { (other: Element) in other == e }
  }
  func trimFront<S: Sequence>(_ s: S) -> SubSequence where S.Element == Element {
    return self.trimFront(_ConsumerSequence(s))
  }
}

extension Collection where Element: Hashable {
  func trimFront(_ s: Set<Element>) -> SubSequence {
    return self.trimFront { s.contains($0) }
  }
}

extension BidirectionalCollection {
  func trimBack(_ predicate: (Element) -> Bool) -> SubSequence {
    return withoutActuallyEscaping(predicate) {
      return self.trimBack(_ConsumerPredicate($0))
    }
  }
  func trim(_ predicate: (Element) -> Bool) -> SubSequence {
    return withoutActuallyEscaping(predicate) {
      return self.trim(_ConsumerPredicate($0))
    }
  }
}
extension BidirectionalCollection where Element: Equatable {
  func trimBack(_ e: Element) -> SubSequence {
    return self.trimBack { (other: Element) in other == e }
  }
  func trimBack<S: Sequence>(_ s: S) -> SubSequence where S.Element == Element {
    return self.trimBack(_ConsumerSequence(s))
  }
  func trim<S: Sequence>(_ s: S) -> SubSequence where S.Element == Element {
    return self.trim(_ConsumerSequence(s))
  }
}

extension BidirectionalCollection where Element: Hashable {
  func trimBack(_ s: Set<Element>) -> SubSequence {
    return self.trimBack { s.contains($0) }
  }
  func trim(_ s: Set<Element>) -> SubSequence {
    return self.trim { s.contains($0) }
  }
}

///
/// Strip
///
extension RangeReplaceableCollection {
  mutating func stripFront(_ predicate: (Element) -> Bool) {
    withoutActuallyEscaping(predicate) {
      self.stripFront(_ConsumerPredicate($0))
    }
  }
}
extension RangeReplaceableCollection where Element: Equatable {
  mutating func stripFront(_ e: Element) {
    self.stripFront { (other: Element) in other == e }
  }
  mutating func stripFront<S: Sequence>(_ s: S) where S.Element == Element {
    self.stripFront(_ConsumerSequence(s))
  }
}

extension RangeReplaceableCollection where Element: Hashable {
  mutating func stripFront(_ s: Set<Element>) {
    self.stripFront { s.contains($0) }
  }
}

extension RangeReplaceableCollection where Self: BidirectionalCollection {
  mutating func stripBack(_ predicate: (Element) -> Bool) {
    withoutActuallyEscaping(predicate) { self.stripBack(_ConsumerPredicate($0)) }
  }
  mutating func strip(_ predicate: (Element) -> Bool) {
    withoutActuallyEscaping(predicate) { self.strip(_ConsumerPredicate($0)) }
  }
}
extension RangeReplaceableCollection where Self: BidirectionalCollection, Element: Equatable {
  mutating func stripBack(_ e: Element) {
    self.stripBack { (other: Element) in other == e }
  }
  mutating func stripBack<S: Sequence>(_ s: S) where S.Element == Element {
    self.stripBack(_ConsumerSequence(s))
  }
  mutating func strip<S: Sequence>(_ s: S) where S.Element == Element {
    self.strip(_ConsumerSequence(s))
  }
}

extension RangeReplaceableCollection where Self: BidirectionalCollection, Element: Hashable {
  mutating func stripBack(_ s: Set<Element>) {
    self.stripBack { s.contains($0) }
  }
  mutating func strip(_ s: Set<Element>) {
    self.strip { s.contains($0) }
  }
}


///
/// Eat
///
extension Collection where SubSequence == Self {
  @discardableResult
  mutating func eat(_ predicate: (Element) -> Bool) -> SubSequence {
    return withoutActuallyEscaping(predicate) {
      return self.eat(_ConsumerPredicate($0))
    }
  }
}
extension Collection where SubSequence == Self, Element: Equatable {
  @discardableResult
  mutating func eat(_ e: Element) -> SubSequence {
    return self.eat { (other: Element) in other == e }
  }
  @discardableResult
  mutating func eat<S: Sequence>(_ s: S) -> SubSequence where S.Element == Element {
    return self.eat(_ConsumerSequence(s))
  }
}

extension Collection where SubSequence == Self, Element: Hashable {
  @discardableResult
  mutating func eat(_ s: Set<Element>) -> SubSequence {
    return self.eat { s.contains($0) }
  }
}

///
/// Collection Searchers
///

// TODO: Front and Bidi searcher. No local state, init is fine...


// protocol CollectionSearcher {
//   associatedtype C: Collection

//   init(_ c: C)

//   func search(startingFrom idx: C.Index) -> Range<C.Index>?
// }

// extension CollectionSearcher where C: BidirectionalCollection {
//   func searchBack(endingAt idx: C.Index) -> Range<C.Index>? {
//     ???
//   }
// }


///
/// TODO: Searchers, with find, replace, replaceAll, split, seek(to/through?)
///


///
/// TODO: Strawman destructuring pattern matching with a consumer via (consumedPrefix, rest)
/// TODO: Strawman destructuring pattern matching with a searcher via (prior, matched, rest)
/// TODO: Strawman destructuring pattern matching with a value-producing adapter
/// TODO: Conform PatternKit
/// TODO: Conform NSRegularExpression
///




//
// protocol CollectionSearcher {
//   associatedtype C: Collection
//
//   func search(_ c: C) -> Range<C.Index>?
// }
// extension CollectionSearcher where C: BidirectionalCollection {
//   func rsearch(_ c: C) -> Range<C.Index>? {
//     fatalError("unimplemented")
//   }
// }
//

// extension Collection {
//   func _split<RE: RangeExpression>(
//     around re: RE
//   ) -> (SubSequence, SubSequence, SubSequence) where RE.Bound == Index {
//     let range = re.relative(to: self)
//     return (self[..<range.lowerBound], self[range], self[range.upperBound...])
//   }
// }




///
/// Test Harness
///

var testsPassed = true
defer {
  if testsPassed {
    print("[OK] Tests Passed")
  } else {
    print("[FAIL] Tests Failed")
  }
}

func checkExpect(
  _ condition: @autoclosure () -> Bool,
  expected: @autoclosure () -> String, saw: @autoclosure () -> String,
  file: StaticString = #file, line: UInt = #line
) {
  if !condition() {
    print("""
      [FAIL] \(file):\(line)
        expected: \(expected())
        saw:      \(saw())
      """)
    testsPassed = false
  }
}
func expectEqual<C: Equatable>(
  _ lhs: C, _ rhs: C, file: StaticString = #file, line: UInt = #line
) {
  checkExpect(
    lhs == rhs, expected: "\(lhs)", saw: "\(rhs)", file: file, line: line)
}
func expectNotEqual<C: Equatable>(
  _ lhs: C, _ rhs: C, file: StaticString = #file, line: UInt = #line
) {
  checkExpect(
    lhs != rhs, expected: "not \(lhs)", saw: "\(rhs)", file: file, line: line)
}
func expectNil<T>(
  _ t: T?, file: StaticString = #file, line: UInt = #line
) {
  checkExpect(t == nil, expected: "nil", saw: "\(t!)", file: file, line: line)
}
func expectTrue(
  _ t: Bool, file: StaticString = #file, line: UInt = #line
) {
  checkExpect(t, expected: "true", saw: "\(t)", file: file, line: line)
}

func expectEqualSequence<S1: Sequence, S2: Sequence>(
  _ lhs: S1, _ rhs: S2, file: StaticString = #file, line: UInt = #line
) where S1.Element == S2.Element, S1.Element: Equatable {
  checkExpect(lhs.elementsEqual(rhs), expected: "\(lhs)", saw: "\(rhs)",
    file: file, line: line)
}

var allTests: [(name: String, run: () -> ())] = []
struct TestSuite {
  let name: String
  init(_ s: String) {
    self.name = s
  }

  func test(_ name: String, _ f: @escaping () -> ()) {
    allTests.append((name, f))
  }
}
func runAllTests() {
  for (test, run) in allTests {
    print("Running test \(test)")
    run()
  }
}
defer { runAllTests() }

///
/// Tests
///

var SearcherTests = TestSuite("SearcherTests")

// Need exhaustive tests for:
//
// Trim, strip, eat, ...
//

// SearcherTests.test("_split(around:)") {
//   let array = [1,2,3,4,5,6,7,8,9,10]
//   let split = array._split(around: 3..<5)
//   expectEqual([1,2,3], split.0)
//   expectEqual([4,5], split.1)
//   expectEqual([6,7,8,9,10], split.2)
// }


// SearcherTests.test("Trimmer") {
//   let array = [1,2,3,4,5,6,7,8,9,10]

//   expectEqual([4, 5, 6, 7, 8, 9, 10], array.trim(Trimmer({ $0 < 4 })))
//   expectEqual([4, 5, 6, 7], array.trim(Trimmer({ !(4..<8).contains($0) })))
// }