This package contains a very general implementation of the Boyer-Moore algorithm.
It does so by extending the Collection protocol.
An extension for String is also included that allows for string searching.
Currently this package supports types that implement the Collection protocol where the Element is Hashable and the subscript Index is of type Int
Call search(_ pattern: T) on the collection and a Range gets returned for
the first occurrence of the pattern.
Call searchAll(_ pattern: T) on a collection and an Iterator gets returned that
can be used to find every occurrence of the pattern.
Call chunk(_ pattern: T, includeSeperator: Bool) on a collection and an Iterator gets
returned that can be used to split the collection by the pattern. By default it
will NOT include the delimiter in the output
let sourceText = "He felt all at once like an ineffectual moth,
fluttering at the windowpane of reality, dimly seeing it from outside."
let result = sourceText.search("moth") // #=> Range(40..<44)
let input: [UInt8] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,]
let result = input.search([7, 7, 7]) // #=> Range(30..<33)
let input: [UInt8] = [0, 0, 7, 0, 0, 0, 0, 0, 0, 0,
0, 0, 7, 0, 0, 0, 0, 0, 0, 0,
0, 0, 7, 0, 0, 0, 0, 0, 0, 0,
0, 0, 7, 0, 0, 0, 0, 0, 0, 0,
0, 0, 7, 0, 0, 0, 0, 0, 0, 0,
0, 0, 7, 0, 0, 0, 0, 0, 0, 0,
0, 0, 7, 0, 0, 0, 0, 0, 0, 0,]
for range in input.searchAll([0, 0, 7]) {
print(range)
}
// #=> 0..<3
// #=> 10..<13
// #=> 20..<23
// #=> 30..<33
// #=> 40..<43
// #=> 50..<53
// #=> 60..<63
/// Do NOT include delimiter
let input: [UInt8] = [0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1,]
for chunk in input.chunk(with: [0, 0]) {
print(chunk)
}
// #=> [1, 1, 1, 1, 1, 1, 1, 1]
// #=> [1, 1, 1, 1, 1, 1, 1, 1]
// #=> [1, 1, 1, 1, 1, 1, 1, 1]
// #=> [1, 1, 1, 1, 1, 1, 1, 1]
// #=> [1, 1, 1, 1, 1, 1, 1, 1]
// #=> [1, 1, 1, 1, 1, 1, 1, 1]
// #=> [1, 1, 1, 1, 1, 1, 1, 1]
// Include the delimter
for chunk in input.chunk(with: [0, 0], includeSeperator: true) {
print(chunk)
}
// #=> [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
// #=> [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
// #=> [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
// #=> [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
// #=> [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
// #=> [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
// #=> [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
The shift rules work using a skip table.
As necessity requires this package will be updated to support other search techniques.