boyer_moore
Types
An API to use for a generic search over a user defined container type.
pub type API(container, item) {
API(
get_size: fn(container) -> Int,
are_equal: fn(item, item) -> Bool,
unsafe_access: fn(container, Int) -> item,
)
}
Constructors
-
API( get_size: fn(container) -> Int, are_equal: fn(item, item) -> Bool, unsafe_access: fn(container, Int) -> item, )
Arguments
-
get_size
Returns the amount of distinct items in the container.
-
are_equal
Returns True if two items are equal to each other. You should use
default_equality
– which calls Gleam’s equality operator – unless you know that it won’t work for your item data type. -
unsafe_access
Returns item with the given index in the container. The algorithm will make sure to only call this within the bounds of the container, so the function can return a value directly instead of a result (using
let assert
). This assumes that the container does not have holes in it.
-
Bounds for the search operation. If either value is None
or out of range,
they are set to the corresponding end index (i.e. start
will be 0 and
end
will be the size of the data). If end
is lower than start
, it will
be set to start
(and thus the range to search will be empty).
Negative indices are not supported.
pub type Bounds {
Bounds(start: option.Option(Int), end: option.Option(Int))
}
Constructors
-
Bounds(start: option.Option(Int), end: option.Option(Int))
Functions
pub fn build_byte_searcher(
pattern: BitArray,
) -> Result(Searcher(BitArray), Nil)
Build a BitArray searcher that works for byte-aligned BitArrays.
On Erlang, this delegates to binary:match
as it is faster.
Returns an error if the BitArray is empty, or – on Erlang – if the BitArray is not byte-aligned.
pub fn build_generic_searcher(
pattern pattern: a,
api api: API(a, b),
) -> Result(Searcher(a), Nil)
Build a generic searcher that can be used many times.
This function allows you to use the search algorithm with your own custom
data structures by implementing the functions in the API
type.
A suitable data structure is one that provides fast, preferably constant time access to random indices. For example, a Dict would work, a List would not.
Additionally, the provided data structure must be 0-indexed with a strictly increasing index with no empty spaces (holes). If this guarantee is broken, the algorithm may crash.
Returns an error if the pattern is empty.
pub fn default_equality(a: a, b: a) -> Bool
Default equality algorithm that uses Gleam’s equality operator (==
). This
will work for the majority of cases and should be used unless you know your
data structure will not work with it.
pub fn search(
haystack data: a,
needle searcher: Searcher(a),
) -> Result(Int, Nil)
Search for needle
in the haystack
. Returns the index to the start of the
first occurrence of the found pattern, or an error if nothing was found.
pub fn search_bounded(
haystack data: a,
needle searcher: Searcher(a),
bounds bounds: Bounds,
) -> Result(Int, Nil)
Search for needle
in the haystack
, using bounds
to limit the searched
area. Returns the index to the start of the first occurrence of the found
pattern, or an error if nothing was found.