Add `firstRange(of:)`, `lastRange(of:)`, `contains(_:)`

[timvermeulen]

Find the location of a subsequence in a collection.

• firstRange(of:)
• lastRange(of:)
• contains(_:)

extension Collection {
  public func firstRange<Other: Collection>(
    of other: Other,
    by areEquivalent: (Element, Other.Element) throws -> Bool
  ) rethrows -> Range<Index>?
}

extension Collection where Element: Equatable {
  public func firstRange<Other: Collection>(of other: Other) -> Range<Index>?
}

extension BidirectionalCollection {
  public func lastRange<Other: BidirectionalCollection>(
    of other: Other,
    by areEquivalent: (Element, Other.Element) throws -> Bool
  ) rethrows -> Range<Index>?
}

extension BidirectionalCollection where Element: Equatable {
  public func lastRange<Other: BidirectionalCollection>(
    of other: Other
  ) -> Range<Index>? where Other.Element == Element
}

extension Collection {
  public func contains<Other: Collection>(
    _ other: Other,
    by areEquivalent: (Element, Other.Element) throws -> Bool
  ) rethrows -> Bool
}

extension Collection where Element: Equatable {
  public func contains<Other: Collection>(
    _ other: Other
  ) -> Bool where Other.Element == Element
}

Checklist

• [x] I've added at least one test that validates that my change is working, if appropriate
• [x] I've followed the code style of the rest of the project
• [x] I've read the Contribution Guidelines
• [x] I've updated the documentation if necessary

[mdznr]

There could probably be optimizations based on count.

For example, if other’s count is larger than self, then there’s no point in iterating through self since it could never contain a larger collection as a subsequence. That’s just a base case that could be checked up front. However, this can also happen in the middle of the algorithm. For example, if we had a self.count of 20, and an other.count of 5, if we ever get a starting index (matchStart) past the 15th element, we can then just return nil since we can’t fit a subsequence of 5 with only 4 elements remaining.

[glessard]

@mdznr Such an optimization would only work for a RandomAccessCollection, and these are not specialized for those indexing semantics (yet.)

[natecook1000]

This functionality is handled by the string-processing package.