I thought it's waiting to be added to the stdlib? ;-).
So let's say "the name that will possibly be proposed" (? - that's rather wordy... but I guess you understand what's meant)
Mh, I guess "term of art" itself is a term of art ;-)
If contains(_ :) isn't descriptive enough, and you prefer a longer name, that should not only be more descriptive -- it should also describe the right thing.
As @pyrtsa demonstrated, that is not the case for "subsequence", which might increase confusion instead of lessen it.
SubSequence is just an associated type, isn't it? So in general, the argument of a hypothetic hasSubsequence method won't be a SubSequence at all - because afaics, you only deal with that "type" when you extract a range from a collection.
Bottom line:
Imho contains is the right name -- plain and simple (it's harder to define the right types for the objects involved ;-)
I believe ignoring the existing contains(other:) by causing a redundancy is not the right way to go, although contains(subsequence:) for Collection is perfectly fine with me. Bikeshedding aside, we will see what the core team thinks.
I have already said this ā note it is Collection that defines its Subsequence to be contiguous. Not Sequence, which it inherits, or Swift. This can mislead people.
func read() {
I would appreciate if the readers try not to inflate the thread too much with the naming question. We can discuss it later in the review if the proposal gets accepted, but remember that the final decision is after the core team. I don't think arguing about names is beneficial at this state, especially considering how many of us here. We can simply propose a name instead, followed by the reason you think it's best.
}
@Tino, subsequence is fine as long as we vend for Collection, look up the definition (the docs, not Wikipedia). If you think the definition is wrong, well, I guess that's another Set Subsequence & Sequence thread :)
No, I can't see a any problems with the definition of SubSequence ;-):
It's something that is generated from a Sequence, and I'm perfectly happy if it stays that way.
How about renaming the contains(other:) in the proposal to isSupersequence(of:)?
It could be part of a family of functions Ć la Set's is(Strict)Sub/Superset(of:), ie:
extension Sequence where Element: Equatable {
...
func isSupersequence<S>(of other: S) -> Bool
where S: Sequence, S.Element == Element
{ ... }
func isSubsequence<S>(of other: S) -> Bool
where S: Sequence, S.Element == Element
{ ... }
func isStrictSupersequence<S>(of other: S) -> Bool
where S: Sequence, S.Element == Element
{ ... }
func isStrictSubsequence<S>(of other: S) -> Bool
where S: Sequence, S.Element == Element
{ ... }
...
}
This way, Sequence gains more useful functionality, and the possibility of misusing mySet.contains(otherSet) in place of mySet.isSuperset(of:otherSet) is reduced by spelling out their differences, and making sure they will be seen together in the list of code completions.
(IMO Sequence is the only sensible place for a method that checks whether one sequence contains another sequence.)
If there truly is no other way of doing it (for aSequence type that is destructively consumed by iteration) than copying to array, then I assume that it'd be enough to copy only the subsequence into an array. And I guess this could be done by incrementally caching the elements of subsequence, if/when they occur in sequence, so that it will only need to store the longest subsequence-prefix that occurs in sequence (which can of course at most be the whole subsequence).
I haven't researched or thought very much about this so I might be wrong.
extension Sequence where Element: Equatable {
/// Returns a Boolean value that indicates whether the sequence contains
/// the given sequence.
///
/// - Parameter other: The sequence to find within
/// this sequence. `other` must be finite.
/// - Returns: `true` if the sequence contains `other`;
/// otherwise, `false`.
public func isSupersequence<S>(of other: S) -> Bool
where S : Sequence, S.Element == Element
{
var selfIter = self.makeIterator()
var otherIter = RewindableIterator(other.makeIterator())
guard let otherFirst = otherIter.next() else { return false }
while let selfNext = selfIter.next() {
if selfNext == otherFirst {
while true {
let selfNext = selfIter.next()
let otherNext = otherIter.next()
if selfNext != otherNext {
if selfNext == nil { return false }
if otherNext == nil { return true }
break
} else {
if selfNext == nil { return true }
}
}
otherIter.rewind()
let _ = otherIter.next()
}
}
return false
}
}
// Helper type for the above implementation of `isSupersequence(of:)`.
struct RewindableIterator<Base: IteratorProtocol> : IteratorProtocol {
var base: Base
var cachedPrefix: [Base.Element] = []
var position = 0
init(_ base: Base) {
self.base = base
}
mutating func rewind() {
position = 0
}
mutating func next() -> Base.Element? {
if position < cachedPrefix.count {
defer { position += 1 }
return cachedPrefix[position]
} else if let next = base.next() {
defer { position += 1 }
cachedPrefix.append(next)
return next
} else {
return nil
}
}
}
// An example sequence type that is destructively consumed by iteration.
final class CountOnce: Sequence, IteratorProtocol {
var current: Int
let afterLast: Int
let step: Int
init(from: Int, to: Int) {
self.step = from <= to ? 1 : -1
self.current = from
self.afterLast = to + step
}
func makeIterator() -> CountOnce {
return self
}
func next() -> Int? {
if current != afterLast {
defer { current += step }
return current
} else {
return nil
}
}
}
let a = CountOnce(from: 1, to: 7)
let b = CountOnce(from: 4, to: 6)
let c = a.isSupersequence(of: b)
print(c) // true
let d = a.isSupersequence(of: b)
print(d) // false since they have been destructively consumed.
that demonstrates that it is possible to write one that will "only" need memory to store the longest subsequence-prefix that occurs within the sequence.
Try this one (I switched to array to allow for more general cases):
// An example sequence type that is destructively consumed by iteration.
final class CountOnce: Sequence, IteratorProtocol {
let array: [Int]
var current: Int
init(from array: [Int]) {
self.array = array
current = 0
}
func makeIterator() -> CountOnce {
return self
}
func next() -> Int? {
if current < array.count {
defer { current += 1 }
return array[current]
} else {
return nil
}
}
}
let a = CountOnce(from: [1, 2, 2, 2, 4, 2, 2])
let b = CountOnce(from: [2, 2, 4])
let c = a.isSupersequence(of: b)
print(c)
let d = a.isSupersequence(of: b)
print(d)
I haven't read the algorithm, but I roughly understand why it fails. The truth is that we need to be able to access the elements of both the sequence and subsequence multiple times, so there is no way we can use less memory than m + prefix(to: the last element of the sequence we need to inspect to make a conclusion) if we want to consider single-pass sequences.
And it might be even better to reserve m + n right away, because Array might allocate more than we need if it uses the exponential realloc, and allocating at each iteration isn't efficient at all.
I tried your example and it works as expected (just like my example before you switched to array). So I'm not sure what you mean.
Also I still don't understand why both sequences should have to be copied/cached (it's perfectly fine for the method to iterate them and destructively consume them, the containing sequence can be iterated once, element by element, but the subsequence need special care, that is caching, in my implementation that is done by RewindableIterator).
We have to be able to access an element of the sequence multiple times:
[1, 2, 2, 2, 4, 2, 2]
subsequence: [2, 2, 4]
(index, element)
Here's how we pass
(0, 1)
(1, 2)
(2, 2)
(3, 2)
(2, 2) second access
(3, 2) second access
(4, 4) -> found
I have accessed the subsequence's first element 3 times on (0, 1), (1, 2), (2, 2)
Ah! I didn't see the sequences, only the class, and I didn't try to scroll since I saw no scrollbars ...
OK, I stand corrected. (The mistake in my algorithm was that selfIter has to back up after inner while loop, ie max subseqLen-1 steps.)
When I was writing a method to do digit-wise natural-number addition, I first started with an actual method with a loop inside. It got a little complicated since I had to handle addend sequences of different lengths, and that an addend sequence may be single-pass. Then I thought that, since I was generating the sum digits one at a time, I could encapsulate addition as an iterator. The sum iterator would take two addend iterators as initializer arguments. This made my addition and iteration logic at lot easier.
The point is that we could do the same here. The count(of:) and contains(other:) have different results, but actually use the same algorithm. We can put that algorithm to find any match in an iterator:
/// Finds the starting offsets for all occurances a given pattern is in a given source.
public struct BruteForceMatchIterator<PatternIterator: IteratorProtocol, SourceIterator: IteratorProtocol> {
/// The type for equivalence closures.
public typealias EquivalenceClosure = (PatternIterator.Element, SourceIterator.Element) throws -> Bool
/// The source of the pattern sequence.
var patternIterator: PatternIterator
/// The source of the searched-for sequence.
var sourceIterator: SourceIterator
/// The cached prefix of the pattern.
var cachedPattern: [PatternIterator.Element]
/// Whether or not all of the pattern has been scanned.
var hasFullyReadPattern: Bool
/// The predicate to check equivalence between pattern and search-source elements.
var areEquivalent: EquivalenceClosure
/// The number of source elements read.
var sourceCount: Int
/// The number of matching elements per potential matching run.
var runningMatches: [Int]
/**
Creates an iterator that searches for a pattern within source elements and returns starting offsets for each match.
- Parameter patternIterator: The source of the pattern sequence's elements. Must be finite.
- Parameter sourceIterator: The source of the elements for the sequence to be searched.
- Parameter predicate: The closure to check pattern and source elements for equivalence.
*/
public init(patternIterator: PatternIterator, sourceIterator: SourceIterator, equateWith predicate: @escaping EquivalenceClosure) {
self.patternIterator = patternIterator
self.sourceIterator = sourceIterator
cachedPattern = []
hasFullyReadPattern = false
areEquivalent = predicate
sourceCount = 0
runningMatches = []
hasThrown = false
}
/// Whether or not iteration has ended because a predicate call threw.
public private(set) var hasThrown: Bool
}
// Convenience Initializers and Statuses
extension BruteForceMatchIterator {
/// Creates a searching iterator with a given pattern sequence and searched-for iterator.
public init<P: Sequence>(pattern: P, sourceIterator: SourceIterator, equateWith predicate: @escaping EquivalenceClosure) where P.Iterator == PatternIterator {
self.init(patternIterator: pattern.makeIterator(), sourceIterator: sourceIterator, equateWith: predicate)
}
/// Creates a searching iterator with a given pattern iterator and searched-for sequence.
public init<S: Sequence>(patternIterator: PatternIterator, source: S, equateWith predicate: @escaping EquivalenceClosure) where S.Iterator == SourceIterator {
self.init(patternIterator: patternIterator, sourceIterator: source.makeIterator(), equateWith: predicate)
}
/// Creates a searching iterator with the given pattern and searched-for sequences.
public init<P: Sequence, S: Sequence>(pattern: P, source: S, equateWith predicate: @escaping EquivalenceClosure) where P.Iterator == PatternIterator, S.Iterator == SourceIterator {
self.init(patternIterator: pattern.makeIterator(), sourceIterator: source.makeIterator(), equateWith: predicate)
}
/// The pattern to search for, but only if all of it has been read.
public var definitivePattern: [PatternIterator.Element]? { return hasFullyReadPattern ? cachedPattern : nil }
/// The equivalence test.
public var predicate: EquivalenceClosure { return areEquivalent }
}
// Iteration Logic
extension BruteForceMatchIterator: IteratorProtocol {
/// Returns the pattern element at the speciified index, reading more as needed, or `nil` if not found.
mutating func pattern(at i: Int) -> PatternIterator.Element? {
precondition(i >= 0)
if !hasFullyReadPattern {
while i >= cachedPattern.count {
guard let nextPatternElement = patternIterator.next() else {
hasFullyReadPattern = true
break
}
cachedPattern.append(nextPatternElement)
}
}
return i < cachedPattern.count ? cachedPattern[i] : nil
}
public mutating func next() -> Int? {
guard !hasThrown else { return nil }
while (runningMatches.first ?? Int.min) < (definitivePattern?.count ?? Int.max) {
if !hasFullyReadPattern {
// Read in the pattern along with the source. Prevents an occasional one-cycle delay in discovering a match otherwise.
_ = pattern(at: cachedPattern.count)
}
guard let nextSourceElement = sourceIterator.next() else {
if let oldestMatchRun = runningMatches.first, oldestMatchRun >= cachedPattern.count, pattern(at: oldestMatchRun) == nil {
runningMatches.removeFirst()
return oldestMatchRun - sourceCount
} else {
return nil
}
}
sourceCount += 1
// Make sure to compare the latest source element with the start of the pattern.
runningMatches.append(0)
// Remove any eventually-failed matches.
var runningMatchesToRemove = Set<Array<Int>.Index>()
defer {
var remainingRunningMatches = [Int]()
for ri in runningMatches.indices {
if !runningMatchesToRemove.contains(ri) {
remainingRunningMatches.append(runningMatches[ri])
}
}
runningMatches = remainingRunningMatches
}
do {
// If the latest source element matches a running matching pattern, keep that pattern going.
for ri in runningMatches.indices.dropFirst().reversed() {
if try areEquivalent(pattern(at: runningMatches[ri])!, nextSourceElement) {
runningMatches[ri] += 1
} else {
runningMatchesToRemove.insert(ri)
}
}
// But special-case the oldest running match, since that's where we would discover when the pattern sequence runs out.
if let latestPatternElement = pattern(at: runningMatches.first!) {
if try areEquivalent(latestPatternElement, nextSourceElement) {
runningMatches[runningMatches.startIndex] += 1
} else {
runningMatchesToRemove.insert(runningMatches.startIndex)
}
} else {
// Should have returned in the previous loop.
runningMatchesToRemove.insert(runningMatches.startIndex)
return (sourceCount - 1) - definitivePattern!.count
}
} catch {
// Can't really continue, since the state machine is now messed up.
hasThrown = true
return nil
}
}
runningMatches.removeFirst()
return sourceCount - definitivePattern!.count
}
}
I originally had the next code read from the pattern sequence only as needed, but I changed it to read one element per source element read. The original algorithm sometimes has an off-by-one round delay to find a match. It mostly works, but if a delay happens when the source iterator ends, then that last match is lost. If someone can find a way to make the if statement before the guard-nextSourceElement obsolete, that would be appreciated.
I wrote those tests in the order given, except the "##' was last. That gave me insight into the problem at "%%". In those two cases, the match is flagged one while-loop iteration late. That causes a problem in line "%%" because the source iteration ends right after. (Remove the if !hasFullyReadPattern statement before the guard let nextSourceElement statement to see the problem.)
Note that the code works for empty sources (no matches) and for empty patterns (match before every source element).
Now that the direct action is encapsulated in an algorithm object, we can define the user-level functions:
extension Sequence {
/// Returns whether or not the given sequence appears at least once in this sequence, using the given predicate for equivalence-testing.
func contains<S: Sequence>(otherSequence: S, comparingWith areEquivalent: @escaping (Element, S.Element) throws -> Bool) -> Bool {
var iterator = BruteForceMatchIterator(pattern: otherSequence, sourceIterator: makeIterator()) { try areEquivalent($1, $0) }
return iterator.next() != nil
}
/// Returns how many times a given sequence appears in this sequence, using the given predicate for equivalence-testing.
func countOf<S: Sequence>(otherSequence: S, permitOverlap: Bool, comparingWith areEquivalent: @escaping (Element, S.Element) throws -> Bool) -> Int {
let otherCollection = Array(otherSequence)
var finder = BruteForceMatchIterator(pattern: otherCollection, sourceIterator: makeIterator()) { try areEquivalent($1, $0) }
guard let firstFind = finder.next() else { return 0 }
var finds = [firstFind]
while let nextFind = finder.next() {
if !permitOverlap, nextFind - finds.last! < otherCollection.count {
continue
}
finds.append(nextFind)
}
return finds.count
}
}
extension Sequence where Element: Equatable {
/// Returns whether or not the given sequence appears at least once in this sequence.
func contains<S: Sequence>(otherSequence: S) -> Bool where S.Element == Element {
return contains(otherSequence: otherSequence, comparingWith: ==)
}
/// Returns how many times a given sequence appears in this sequence.
func countOf<S: Sequence>(otherSequence: S, permitOverlap: Bool) -> Int where S.Element == Element {
return countOf(otherSequence: otherSequence, permitOverlap: permitOverlap, comparingWith: ==)
}
}
extension Collection {
/// Returns the ranges for each time a given sequence appears in this collection, using the given predicate for equivalence-testing.
func matchesFor<S: Sequence>(_ otherSequence: S, permitOverlap: Bool, comparingWith areEquivalent: @escaping (Element, S.Element) throws -> Bool) -> [Range<Index>]? {
let otherCollection = Array(otherSequence)
var finder = BruteForceMatchIterator(pattern: otherCollection, sourceIterator: makeIterator()) { try areEquivalent($1, $0) }
guard let firstFind = finder.next() else { return finder.hasThrown ? nil : [] }
var finds = [firstFind]
while let nextFind = finder.next() {
if !permitOverlap, nextFind - finds.last! < otherCollection.count {
continue
}
finds.append(nextFind)
}
guard !finder.hasThrown else { return nil }
let runningOffsets = zip(finds.dropLast(), finds.dropFirst()).map { $0.1 - $0.0 }
var firstIndex = index(startIndex, offsetBy: firstFind)
var firstEndIndex = index(firstIndex, offsetBy: otherCollection.count)
var ranges = [firstIndex ..< firstEndIndex]
for o in runningOffsets {
formIndex(&firstIndex, offsetBy: o)
formIndex(&firstEndIndex, offsetBy: o)
ranges.append(firstIndex ..< firstEndIndex)
}
return ranges
}
}
extension Collection where Element: Equatable {
/// Returns the ranges for each time a given sequence appears in this collection.
func matchesFor<S: Sequence>(_ otherSequence: S, permitOverlap: Bool) -> [Range<Index>] where S.Element == Element {
return matchesFor(otherSequence, permitOverlap: permitOverlap, comparingWith: ==)!
}
}
Notice the third function that hasn't been noticed: the locations of the actual searches! Also:
contains is just comparing the result of countOf with zero.
countOf is just getting the length of the result of matchesFor.
but with optimized algorithms, and that matchesFor requires a Collection.
extension Sequence {
/// Returns whether or not the given sequence appears at least once in this sequence, using the given predicate for equivalence-testing.
func contains<S: Sequence>(otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) -> Bool? {
var iterator = BruteForceMatchIterator(pattern: otherSequence, sourceIterator: makeIterator()) { try areEquivalent($1, $0) }
return iterator.next() != nil ? true : iterator.hasThrown ? nil : false
}
/// Returns the offsets relative to this sequence for every match (even if consecutive matches overlap) to the given sequence, using the given predicate for equivalence-testing.
func offsetsForEveryMatch<S: Sequence>(of otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) -> [Int]? {
var finder = BruteForceMatchIterator(pattern: otherSequence, sourceIterator: makeIterator()) { try areEquivalent($1, $0) }
guard let firstFind = finder.next() else { return finder.hasThrown ? nil : [] }
var finds = [firstFind]
while let nextFind = finder.next() {
finds.append(nextFind)
}
guard !finder.hasThrown else { return nil }
return finds
}
/// Returns the offsets relative to this sequence for every non-overlapping match to the given sequence, using the given predicate for equivalence-testing.
func offsetsForDisjointMatches<S: Sequence>(on otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) -> [Int]? {
let otherCollection = Array(otherSequence)
guard let allMatches = offsetsForEveryMatch(of: otherCollection, comparingBy: areEquivalent) else { return nil }
guard let firstFind = allMatches.first else { return [] }
var finds = [firstFind]
for f in allMatches.dropFirst() {
guard f - finds.last! >= otherCollection.count else { continue }
finds.append(f)
}
return finds
}
/// Returns how many times a given sequence appears in this sequence (allowing overlaps), using the given predicate for equivalence-testing.
func countAllMatches<S: Sequence>(for otherSeequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) -> Int? {
return offsetsForEveryMatch(of: otherSeequence, comparingBy: areEquivalent)?.count
}
/// Returns how many times a given sequence appears in this sequence without overlaps, using the given predicate for equivalence-testing.
func countAllDisjointMatches<S: Sequence>(for otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) -> Int? {
return offsetsForDisjointMatches(on: otherSequence, comparingBy: areEquivalent)?.count
}
}
extension Sequence where Element: Equatable {
/// Returns whether or not the given sequence appears at least once in this sequence.
func contains<S: Sequence>(otherSequence: S) -> Bool where S.Element == Element {
return contains(otherSequence: otherSequence, comparingBy: ==)!
}
/// Returns the offsets relative to this sequence for every match (even if consecutive matches overlap) to the given sequence.
func offsetsForEveryMatch<S: Sequence>(of otherSequence: S) -> [Int] where S.Element == Element {
return offsetsForEveryMatch(of: otherSequence, comparingBy: ==)!
}
/// Returns the offsets relative to this sequence for every non-overlapping match to the given sequence.
func offsetsForDisjointMatches<S: Sequence>(on otherSequence: S) -> [Int] where S.Element == Element {
return offsetsForDisjointMatches(on: otherSequence, comparingBy: ==)!
}
/// Returns how many times a given sequence appears in this sequence (allowing overlaps).
func countAllMatches<S: Sequence>(for otherSeequence: S) -> Int where S.Element == Element {
return countAllMatches(for: otherSeequence, comparingBy: ==)!
}
/// Returns how many times a given sequence appears in this sequence without overlaps.
func countAllDisjointMatches<S: Sequence>(for otherSequence: S) -> Int where S.Element == Element {
return countAllDisjointMatches(for: otherSequence, comparingBy: ==)!
}
}
extension Collection {
/// Returns the ranges for each time a given sequence appears in this collection, using the given predicate for equivalence-testing.
func matchesFor<S: Sequence>(_ otherSequence: S, permitOverlap: Bool, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) -> [Range<Index>]? {
let otherCollection = Array(otherSequence)
guard let matchOffsets = permitOverlap ? offsetsForEveryMatch(of: otherCollection, comparingBy: areEquivalent) : offsetsForDisjointMatches(on: otherCollection, comparingBy: areEquivalent) else { return nil }
guard let firstMatchingOffset = matchOffsets.first else { return [] }
let runningOffsets = zip(matchOffsets.dropLast(), matchOffsets.dropFirst()).map { $0.1 - $0.0 }
var startingIndex = index(startIndex, offsetBy: firstMatchingOffset)
var endingIndex = index(startingIndex, offsetBy: otherCollection.count)
var ranges = [startingIndex ..< endingIndex]
for ro in runningOffsets {
formIndex(&startingIndex, offsetBy: ro)
formIndex(&endingIndex, offsetBy: ro)
ranges.append(startingIndex ..< endingIndex)
}
return ranges
}
}
extension Collection where Element: Equatable {
/// Returns the ranges for each time a given sequence appears in this collection.
func matchesFor<S: Sequence>(_ otherSequence: S, permitOverlap: Bool) -> [Range<Index>] where S.Element == Element {
return matchesFor(otherSequence, permitOverlap: permitOverlap, comparingBy: ==)!
}
}
Putting the include-overlap and exclude-overlap match-finding functionalities as cases of the same method only makes sense if they otherwise have the same performance characteristics, but they don't. The distinct-match versions do more work; they need to test close-by matches to see if they're too close, and the "too close" tests requires a Collection instead of a Sequence. I get around that last one by copying the pattern sequence first in order to get the count. So the two functions are now separate. I didn't do that to Collection.matchesFor; it just calls one of the two Sequence versions.
Note that since IteratorProtocol.next is non-throwing, a throwing predicate is handled by returning nil and setting a property on the instance. This is carried over to all the user-level functions by them returning Optionals. But since Equatable's == is non-throwing, the Equatable variants are non-Optional.
Before looking into all that code, I want to ask what the point of your example is. Are you proposing a more performant variant, or simply an alternative?
Both. Iām applying the technique I used for multi-precision arithmetic; instead of working in the Sequence realm, pull back and work in the IteratorProtocol realm. It sometimes makes things easier to reason out.
The two methods are proposed together because they are slightly different applications of the same functionality. But the original code couldnāt exploit that; each one wrote out the same algorithm twice. But pulling back to the IteratorProtocol level allows implementations that call the same base code.
Excuse me, I haven't yet tested your code so I don't know if it works as expected. But I appreciate the contribution.
The algorithms I provide indeed are similar, and I understand the point in wrapping them up for reuse in both methods. However, what is the point in this (or the way you designed it) if the result is the same, if not larger, amount of code? Besides, the functionality granulation you perform introduces a whole lot of new symbols (helper types, methods and properties), which make it less tidy and readable.
If so and your algorithm is somehow asymptotically faster, can you please provide some complexity information, accompanied with a explanation?
I meant the performance was better since contains and count would share code, not necessarily the algorithm used was better.
But, I threw that away. The exception policy was bothering me, and I couldn't find a way to fix it. I could change the iterator object to store the last exception thrown, instead of just recording that an exception occurred. But doing anything with that was difficult. Since any functions that used the matching iterator checked the exception status unconditionally, and combined with the fact the predicate wasn't directly used in those functions, I couldn't use rethrows in those functions, and trying to cascade whether or not the predicate was throwing came out to be a mess.
Right before that, I was looking into trying out Boyer-Moore searching. That involves suffix matching, which I have had encapsulated in posts on this forum as the Collection method converges(with:), which in turn is a call on my theoretical Collection.diverges(from:) method on reversed collections. When I started to rewrite diverges, I wondered it I could make the same generalization to Sequence that I asked you to do here with count and contains. So I did:
extension Sequence {
/**
Handles the elements of a prefix common with this sequence and a given sequence, using the given predicate as the equivalence test, by using the given closure.
The sequences are equivalent if the return value's elements are both `nil`.
- Parameter other: A sequence to compare to this sequence.
- Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.
- Parameter body: A closure that takes a pair of equivalent elements, one from each sequence, as arguments.
- Returns: A tuple with the first element of each sequence where they differ.
*/
public func handlePrefix<S: Sequence>(sharedWith other: S, equatingBy areEquivalent: (Element, S.Element) throws -> Bool, _ body: (Element, S.Element) throws -> Void) rethrows -> (nextElement: Element?, nextOtherElement: S.Element?) {
var iterator = makeIterator()
var otherIterator = other.makeIterator()
var nextElement = iterator.next()
var nextOtherElement = otherIterator.next()
while let ne = nextElement, let noe = nextOtherElement, try areEquivalent(ne, noe) {
defer { nextElement = iterator.next() ; nextOtherElement = otherIterator.next() }
try body(ne, noe)
}
return (nextElement, nextOtherElement)
}
}
extension Collection {
/**
Finds the common prefix between this collection and a given collection, using the given predicate as the equivalence test, by recording where they differ.
The predicate must be an equivalence relation over the elements. The collections are equivalent if the return value's `.prefixEndIndex` and `.otherPrefixEndIndex` elements are their respective collections' `endIndex`. (The `.prefixCount` element would then be their common element count.)
- Parameter other: A collection to compare to this collection.
- Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.
- Complexity: `min(count, other.count)` comparisons.
- Returns: A tuple describing where and how the mismatch between the sequences occur.
- `prefixCount` is how many initial elements the sequences have in common.
- `prefixEndIndex` is the index of the first element of `self` where the collections diverge, or `endIndex` if `self`'s sequence ended before an actual mismatch was found.
- `otherPrefixEndIndex` is the index of the first element of `other` where the collections diverge, or `other.endIndex` if `other`'s sequence ended before an actual mismatch was found.
- Throws: Whatever `areEquivalent` may throw.
*/
public func indicesEndingCommonPrefix<C: Collection>(sharedWith other: C, equatingBy areEquivalent: (Element, C.Element) throws -> Bool) rethrows -> (prefixCount: Int, prefixEndIndex: Index, otherPrefixEndIndex: C.Index) {
var selfIndex = startIndex, otherIndex = other.startIndex
var prefixCount = 0
_ = try handlePrefix(sharedWith: other, equatingBy: areEquivalent) { (_, _) in
formIndex(after: &selfIndex)
other.formIndex(after: &otherIndex)
prefixCount += 1
}
return (prefixCount, selfIndex, otherIndex)
}
/**
Finds where the leading elements between this collection and a given collection stop being equivalent, using the given predicate as the equivalence test.
The predicate must be an equivalence relation over the elements. The collections are equivalent if the return value's `.prefixEndIndex` and `.otherPrefixEndIndex` elements are their respective collections' `endIndex`.
- Parameter other: A collection to compare to this collection.
- Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.
- Complexity: `min(count, other.count)` comparisons.
- Returns: A tuple describing where and how the mismatch between the sequences occur.
- `prefixEndIndex` is the index of the first element of `self` where the collections diverge, or `endIndex` if `self`'s sequence ended before an actual mismatch was found.
- `otherPrefixEndIndex` is the index of the first element of `other` where the collections diverge, or `other.endIndex` if `other`'s sequence ended before an actual mismatch was found.
- Throws: Whatever `areEquivalent` may throw.
*/
public func diverges<C: Collection>(from other: C, by areEquivalent: (Element, C.Element) throws -> Bool) rethrows -> (prefixEndIndex: Index, otherPrefixEndIndex: C.Index) {
let rawResult = try indicesEndingCommonPrefix(sharedWith: other, equatingBy: areEquivalent)
return (rawResult.prefixEndIndex, rawResult.otherPrefixEndIndex)
}
}
extension BidirectionalCollection {
/**
Finds the common suffix between this collection and a given collection, using the given predicate as the equivalence test, by recording where they agree.
The predicate must be an equivalence relation over the elements. The collections are equivalent if the return value's `.suffixStartIndex` and `.otherSuffixStartIndex` elements are their respective collections' `startIndex`. (The `.suffixCount` element would then be their common element count.)
- Parameter other: A collection to compare to this collection.
- Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.
- Complexity: `min(count, other.count)` comparisons.
- Returns: A tuple describing where and how the match between the sequences occur.
- `suffixCount` is how many final elements the sequences have in common.
- `suffixStartIndex` is the index of the first element of `self` where the collections converge, or `startIndex` if `self`'s sequence begun without any mismatches.
- `otherSuffixStartIndex` is the index of the first element of `other` where the collections converge, or `other.startIndex` if `other`'s sequence begun without any mismatches.
- Throws: Whatever `areEquivalent` may throw.
*/
public func indicesStartingCommonSuffix<C: BidirectionalCollection>(sharedWith other: C, equatingBy areEquivalent: (Element, C.Element) throws -> Bool) rethrows -> (suffixCount: Int, suffixStartIndex: Index, otherSuffixStartIndex: C.Index) {
let rawResult = try reversed().indicesEndingCommonPrefix(sharedWith: other.reversed(), equatingBy: areEquivalent)
return (rawResult.prefixCount, rawResult.prefixEndIndex.base, rawResult.otherPrefixEndIndex.base)
}
/**
Finds where the trailing elements between this collection and a given collection start being equivalent, using the given predicate as the equivalence test.
The predicate must be an equivalence relation over the elements. The collections are equivalent if the return value's `.suffixStartIndex` and `.otherSuffixStartIndex` elements are their respective collections' `startIndex`.
- Parameter other: A collection to compare to this collection.
- Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.
- Complexity: `min(count, other.count)` comparisons.
- Returns: A tuple describing where and how the match between the sequences occur.
- `suffixStartIndex` is the index of the first element of `self` where the collections converge, or `startIndex` if `self`'s sequence begun without any mismatches.
- `otherSuffixStartIndex` is the index of the first element of `other` where the collections converge, or `other.startIndex` if `other`'s sequence begun without any mismatches.
- Throws: Whatever `areEquivalent` may throw.
*/
public func converges<C: BidirectionalCollection>(with other: C, by areEquivalent: (Element, C.Element) throws -> Bool) rethrows -> (suffixStartIndex: Index, otherSuffixStartIndex: C.Index) {
let rawResult = try indicesStartingCommonSuffix(sharedWith: other, equatingBy: areEquivalent)
return (rawResult.suffixStartIndex, rawResult.otherSuffixStartIndex)
}
}
So, I got rid of BruteForceMatchIterator, in favor of a master method like handlePrefix:
extension Sequence {
/**
Processes each occurrence of a given sequence within this sequence, using the given predicate as the equivalence test, by using the given closure.
- Precondition: Both this sequence and the given sequence must be finite.
- Parameter otherSequence: A sequence to search within this sequence.
- Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.
- Parameter body: A closure that takes the offset of the next match from the start of this sequence as its first argument. Its second argument can be set to `true` stop looking for subsequent matches.
- Complexity: O(n * m) comparisons, where `n` and `m` are the lengths of the sequences.
- Throws: Whatever either `areEquivalent` and/or `body` may throw.
*/
func forEachMatchOffset<S: Sequence>(for otherSequence: S, equatingBy areEquivalent: (Element, S.Element) throws -> Bool, _ body: (Int, inout Bool) throws -> Void) rethrows {
// Read in the pattern sequence.
var elementsRead = 0
var patternBuffer = BufferedIterator(base: otherSequence.makeIterator(), capacity: Int.max)
var buffer = BufferedIterator(base: makeIterator(), capacity: Int.max)
while case .some = patternBuffer.next() {
// If the guard fails, then this sequence is too short to ever match the pattern.
guard case .some = buffer.next() else { return }
elementsRead += 1
}
assert(patternBuffer.count == buffer.count)
patternBuffer.capacity = patternBuffer.count
buffer.capacity = buffer.count
// Check this sequence for matches.
var stopped = false
repeat {
if try patternBuffer.cache.elementsEqual(buffer.cache, by: { try areEquivalent($1, $0) }) {
try body(elementsRead - patternBuffer.count, &stopped)
}
elementsRead += 1
} while !stopped && buffer.next() != nil
}
}
I think it pretty much works like @Jens and your versions. Since it's no longer a one-at-a-time iterator, it can't work when the source sequence is infinite. (The pattern sequence always had to be finite.) A key to how my version works is the BufferedIterator type, which wraps another iterator and caches the most recent elements. (@Jens expresses the same need differently.)
Something I noticed in this version over my iterator version is when nothing happens. In the iterator version, when using an empty pattern, I got a match before every source element. Now the loop in this method does that match after each element. But the fact I'm using a repeat-while loop means I also match nothing before the first source element too. So having a empty pattern went from "length(source)" matches to "length(source) + 1" matches. This also means that when the source is empty, matching empty against empty works once (instead of none). I don't know if that's a big deal or not.
Since the action closure passed to forEachMatchOffset has an inout stop flag, it can work just once to implement contains, and without stoppage to implement count. Error throwing, from either the predicate and/or the action closures, cascades properly and rethrows works.
All the methods for a regular user now have non-Optional returns and use rethrows:
extension Sequence {
/// Returns whether or not the given sequence appears at least once in this sequence, using the given predicate for equivalence-testing.
func contains<S: Sequence>(otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> Bool {
var foundMatch = false
try forEachMatchOffset(for: otherSequence, equatingBy: areEquivalent) { (_, stop) in
foundMatch = true
stop = true
}
return foundMatch
}
/// Returns the offsets relative to this sequence for every match (even if consecutive matches overlap) to the given sequence, using the given predicate for equivalence-testing.
func offsetsForEveryMatch<S: Sequence>(of otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> [Int] {
var result = [Int]()
try forEachMatchOffset(for: otherSequence, equatingBy: areEquivalent) { (offset, _) in
result.append(offset)
}
return result
}
/// Returns the offsets relative to this sequence for every non-overlapping match to the given sequence, using the given predicate for equivalence-testing.
func offsetsForDisjointMatches<S: Sequence>(on otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> [Int] {
let otherCollection = Array(otherSequence)
var result = [Int]()
try forEachMatchOffset(for: otherCollection, equatingBy: areEquivalent) { (offset, _) in
guard let lastOffset = result.last else { result.append(offset) ; return }
if offset - lastOffset >= otherCollection.count {
result.append(offset)
}
}
return result
}
/// Returns the offsets relative to this sequence for matches, up to a given limit, to the given sequence, using the given predicate for equivalence-testing.
func offsetsForInitialMatches<S: Sequence>(to otherSequence: S, maxMatches: Int, permitOverlap: Bool, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> [Int] {
precondition(maxMatches >= 0)
let otherCollection = Array(otherSequence)
var result = [Int]()
result.reserveCapacity(maxMatches)
try forEachMatchOffset(for: otherCollection, equatingBy: areEquivalent) { (offset, stop) in
guard result.count <= maxMatches else { stop = true ; return }
guard let lastOffset = result.last else { result.append(offset) ; return }
if permitOverlap || offset - lastOffset >= otherCollection.count {
result.append(offset)
}
}
return result
}
/// Returns how many times a given sequence appears in this sequence (allowing overlaps), using the given predicate for equivalence-testing.
func countAllMatches<S: Sequence>(for otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> Int {
var result = 0
try forEachMatchOffset(for: otherSequence, equatingBy: areEquivalent) { (_, _) in
result += 1
}
return result
}
/// Returns how many times a given sequence appears in this sequence without overlaps, using the given predicate for equivalence-testing.
func countAllDisjointMatches<S: Sequence>(for otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> Int {
// Yes, this does unnecessarily waste memory.
return try offsetsForDisjointMatches(on: otherSequence, comparingBy: areEquivalent).count
}
/// Returns whether the number of times a given sequence appears in this sequence is over a limit, using the given predicate for equivalence-testing.
func matchCountExceeds<S: Sequence>(limit: Int, onMatching otherSequence: S, permitOverlap: Bool, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> Bool {
precondition(0..<Int.max ~= limit)
// Yes, this does unnecessarily waste memory.
return try offsetsForInitialMatches(to: otherSequence, maxMatches: limit + 1, permitOverlap: permitOverlap, comparingBy: areEquivalent).count > limit
}
}
extension Collection {
/// Returns the ranges for each time a given sequence appears in this collection, using the given predicate for equivalence-testing.
func matchesFor<S: Sequence>(_ otherSequence: S, permitOverlap: Bool, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> [Range<Index>] {
let otherCollection = Array(otherSequence)
let matchOffsets: [Int]
if permitOverlap {
matchOffsets = try offsetsForEveryMatch(of: otherCollection, comparingBy: areEquivalent)
} else {
matchOffsets = try offsetsForDisjointMatches(on: otherCollection, comparingBy: areEquivalent)
}
guard let firstMatchingOffset = matchOffsets.first else { return [] }
let runningOffsets = zip(matchOffsets.dropLast(), matchOffsets.dropFirst()).map { $0.1 - $0.0 }
var startingIndex = index(startIndex, offsetBy: firstMatchingOffset)
var endingIndex = index(startingIndex, offsetBy: otherCollection.count)
var ranges = [startingIndex ..< endingIndex]
for ro in runningOffsets {
formIndex(&startingIndex, offsetBy: ro)
formIndex(&endingIndex, offsetBy: ro)
ranges.append(startingIndex ..< endingIndex)
}
return ranges
}
}
The original methods I had would exploit forEachMatchOffset stop flag exactly once or never, so I added the offsetsForInitialMatches method for something in-between. Since a count-based alternative to offsetsForInitialMatches wouldn't be useful (It's always at most your limit.), I added the matchCountExceeds method instead.
offsetsForInitialMatches and matchCountExceeds use a permit-overlap flag instead of two different methods each because I got lazy. When I was not lazy, the main match offset/count methods have different methods for no-overlap versus allowing-overlap, so the allowing-overlap versions don't waste time with unnecessary tests.
I moved the code that distinguishes between overlapping and non-overlapping searches to its own method. Then I consolidated all the user-level methods to have parameter switches for overlapping vs. distinct and a maximum limit for searches.
extension Sequence {
/**
Processes each occurrence of a given sequence within this sequence, using the given predicate as the equivalence test, by using the given closure.
- Precondition: Both this sequence and the given sequence must be finite.
- Parameter otherSequence: A sequence to search within this sequence.
- Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.
- Parameter body: A closure that takes the offset of the next match from the start of this sequence as its first argument. Its second argument can be set to `true` stop looking for subsequent matches.
- Complexity: O(n * m) comparisons, where `n` and `m` are the lengths of the sequences.
- Throws: Whatever either `areEquivalent` and/or `body` may throw.
*/
func forEachMatchOffset<S: Sequence>(for otherSequence: S, equatingBy areEquivalent: (Element, S.Element) throws -> Bool, _ body: (Int, inout Bool) throws -> Void) rethrows {
// Read in the pattern sequence.
var elementsRead = 0
var patternBuffer = BufferedIterator(base: otherSequence.makeIterator(), capacity: Int.max)
var buffer = BufferedIterator(base: makeIterator(), capacity: Int.max)
while case .some = patternBuffer.next() {
// If the guard fails, then this sequence is too short to ever match the pattern.
guard case .some = buffer.next() else { return }
elementsRead += 1
}
assert(patternBuffer.count == buffer.count)
patternBuffer.capacity = patternBuffer.count
buffer.capacity = buffer.count
// Check this sequence for matches.
var stopped = false
repeat {
if try patternBuffer.cache.elementsEqual(buffer.cache, by: { try areEquivalent($1, $0) }) {
try body(elementsRead - patternBuffer.count, &stopped)
}
elementsRead += 1
} while !stopped && buffer.next() != nil
}
/**
Processes each non-overlapping occurrence of a given sequence within this sequence, using the given predicate as the equivalence test, by using the given closure.
When occurrences overlap, the one with the earliest starting offset that isn't already excluded is included and all other occurrences that overlap with that one are excluded, with the earliest occurrence in the entire sequence is always included. For instance, if the first three occurrences overlap, where the first and third occurrences do not overlap each other (but only through the second occurrence), then the first and third occurrence will be included while the second one wouldn't.
- Precondition: Both this sequence and the given sequence must be finite.
- Parameter otherSequence: A sequence to search within this sequence.
- Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.
- Parameter body: A closure that takes the offset of the next match from the start of this sequence as its first argument. Its second argument can be set to `true` stop looking for subsequent matches.
- Complexity: O(n * m) comparisons, where `n` and `m` are the lengths of the sequences.
- Throws: Whatever either `areEquivalent` and/or `body` may throw.
*/
func forEachDistinctMatchOffset<S: Sequence>(for otherSequence: S, equatingBy areEquivalent: (Element, S.Element) throws -> Bool, _ body: (Int, inout Bool) throws -> Void) rethrows {
let otherCollection = Array(otherSequence)
let otherCount = otherCollection.count
var lastOffset = -otherCount
try forEachMatchOffset(for: otherCollection, equatingBy: areEquivalent) { (offset, stop) in
guard offset - lastOffset >= otherCount else { return }
lastOffset = offset
try body(offset, &stop)
}
}
}
extension Sequence where Element: Equatable {
/**
Processes each occurrence of a given sequence within this sequence by using the given closure.
- Precondition: Both this sequence and the given sequence must be finite.
- Parameter otherSequence: A sequence to search within this sequence.
- Parameter body: A closure that takes the offset of the next match from the start of this sequence as its first argument. Its second argument can be set to `true` stop looking for subsequent matches.
- Complexity: O(n * m) comparisons, where `n` and `m` are the lengths of the sequences.
- Throws: Whatever `body` may throw.
*/
func forEachMatchOffset<S: Sequence>(for otherSequence: S, _ body: (Int, inout Bool) throws -> Void) rethrows where S.Element == Element {
return try forEachMatchOffset(for: otherSequence, equatingBy: ==, body)
}
/**
Processes each non-overlapping occurrence of a given sequence within this sequence by using the given closure.
When occurrences overlap, the one with the earliest starting offset that isn't already excluded is included and all other occurrences that overlap with that one are excluded, with the earliest occurrence in the entire sequence is always included. For instance, if the fist three occurrences overlap, where the first and third occurrences do not overlap each other (but only through the second occurrence), then the first and third occurrence will be included while the second one wouldn't.
- Precondition: Both this sequence and the given sequence must be finite.
- Parameter otherSequence: A sequence to search within this sequence.
- Parameter body: A closure that takes the offset of the next match from the start of this sequence as its first argument. Its second argument can be set to `true` stop looking for subsequent matches.
- Complexity: O(n * m) comparisons, where `n` and `m` are the lengths of the sequences.
- Throws: Whatever `body` may throw.
*/
func forEachDistinctMatchOffset<S: Sequence>(for otherSequence: S, _ body: (Int, inout Bool) throws -> Void) rethrows where S.Element == Element {
return try forEachMatchOffset(for: otherSequence, equatingBy: ==, body)
}
}
extension Sequence {
/// Returns how many occurrences the given sequence appears in this one, possibly up to a given limit, using the given predicate for equivalence-testing.
public func countMatches<S: Sequence>(to otherSequence: S, permitOverlap: Bool, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool, upTo limit: Int = Int.max) rethrows -> Int {
precondition(limit >= 0)
var count = 0
let action: (Int, inout Bool) -> Void = { (_, stop) in
guard count < limit else { stop = true ; return }
count += 1
}
if permitOverlap {
try forEachMatchOffset(for: otherSequence, equatingBy: areEquivalent, action)
} else {
try forEachDistinctMatchOffset(for: otherSequence, equatingBy: areEquivalent, action)
}
return count
}
/// Returns whether the number of times a given sequence appears in this sequence is over a limit, using the given predicate for equivalence-testing.
public func matchCountExceeds<S: Sequence>(limit: Int, onMatching otherSequence: S, permitOverlap: Bool, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> Bool {
precondition(0..<Int.max ~= limit)
return try countMatches(to: otherSequence, permitOverlap: permitOverlap, comparingBy: areEquivalent, upTo: limit + 1) > limit
}
/// Returns whether or not the given sequence appears at least once in this sequence, using the given predicate for equivalence-testing.
public func contains<S: Sequence>(otherSequence: S, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool) rethrows -> Bool {
return try matchCountExceeds(limit: 0, onMatching: otherSequence, permitOverlap: true, comparingBy: areEquivalent)
}
/// Returns the offsets relative to this sequence for every match to the given sequence, possibly up to a given limit, using the given predicate for equivalence-testing.
public func offsetsForMatches<S: Sequence>(to otherSequence: S, permitOverlap: Bool, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool, upTo limit: Int = Int.max) rethrows -> [Int] {
precondition(limit >= 0)
var offsets = [Int]()
offsets.reserveCapacity(Swift.max(0, underestimatedCount - otherSequence.underestimatedCount + 1))
let action: (Int, inout Bool) -> Void = { (offset, stop) in
guard offsets.count < limit else { stop = true ; return }
offsets.append(offset)
}
if permitOverlap {
try forEachMatchOffset(for: otherSequence, equatingBy: areEquivalent, action)
} else {
try forEachDistinctMatchOffset(for: otherSequence, equatingBy: areEquivalent, action)
}
return offsets
}
}
extension Sequence where Element: Equatable {
/// Returns how many occurrences the given sequence appears in this one, possibly up to a given limit.
public func countMatches<S: Sequence>(to otherSequence: S, permitOverlap: Bool, upTo limit: Int = Int.max) -> Int where S.Element == Element {
return countMatches(to: otherSequence, permitOverlap: permitOverlap, comparingBy: ==, upTo: limit)
}
/// Returns whether the number of times a given sequence appears in this sequence is over a limit.
public func matchCountExceeds<S: Sequence>(limit: Int, onMatching otherSequence: S, permitOverlap: Bool) -> Bool where S.Element == Element {
return matchCountExceeds(limit: limit, onMatching: otherSequence, permitOverlap: permitOverlap, comparingBy: ==)
}
/// Returns whether or not the given sequence appears at least once in this sequence.
public func contains<S: Sequence>(otherSequence: S) -> Bool where S.Element == Element {
return contains(otherSequence: otherSequence, comparingBy: ==)
}
/// Returns the offsets relative to this sequence for every match to the given sequence, possibly up to a given limit.
public func offsetsForMatches<S: Sequence>(to otherSequence: S, permitOverlap: Bool, upTo limit: Int = Int.max) -> [Int] where S.Element == Element {
return offsetsForMatches(to: otherSequence, permitOverlap: permitOverlap, comparingBy: ==, upTo: limit)
}
}
extension Collection {
/// Returns the ranges for each time a given sequence appears in this collection, possibly up to a given limit, using the given predicate for equivalence-testing.
public func matchesFor<S: Sequence>(_ otherSequence: S, permitOverlap: Bool, comparingBy areEquivalent: @escaping (Element, S.Element) throws -> Bool, upTo limit: Int = Int.max) rethrows -> [Range<Index>] {
let otherCollection = Array(otherSequence)
let matchOffsets = try offsetsForMatches(to: otherCollection, permitOverlap: permitOverlap, comparingBy: areEquivalent, upTo: limit)
guard let firstMatchingOffset = matchOffsets.first else { return [] }
let runningOffsets = zip(matchOffsets.dropLast(), matchOffsets.dropFirst()).map { $0.1 - $0.0 }
var startingIndex = index(startIndex, offsetBy: firstMatchingOffset)
var endingIndex = index(startingIndex, offsetBy: otherCollection.count)
var ranges = [startingIndex ..< endingIndex]
for ro in runningOffsets {
formIndex(&startingIndex, offsetBy: ro)
formIndex(&endingIndex, offsetBy: ro)
ranges.append(startingIndex ..< endingIndex)
}
return ranges
}
}
extension Collection where Element: Equatable {
/// Returns the ranges for each time a given sequence appears in this collection, possibly up to a given limit.
public func matchesFor<S: Sequence>(_ otherSequence: S, permitOverlap: Bool, upTo limit: Int = Int.max) -> [Range<Index>] where S.Element == Element {
return matchesFor(otherSequence, permitOverlap: permitOverlap, comparingBy: ==, upTo: limit)
}
}