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))

A compiled searcher that can be reused many times on different data.

pub opaque type Searcher(container)

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.

Search Document