boyer_moore

import gleam/bit_array
import gleam/bool
import gleam/dict
import gleam/int
import gleam/option
import gleam/result

// ===========
// Generic API
// ===========

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

/// A compiled searcher that can be reused many times on different data.
pub opaque type Searcher(container) {
  Searcher(fun: fn(container, Bounds) -> Result(Int, Nil))
}

/// An API to use for a generic search over a user defined container type.
pub type API(container, item) {
  API(
    /// Returns the amount of distinct items in the container.
    get_size: fn(container) -> Int,
    /// 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.
    are_equal: fn(item, item) -> Bool,
    /// 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.
    unsafe_access: fn(container, Int) -> item,
  )
}

/// 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 build_generic_searcher(
  pattern pattern: container,
  api api: API(container, item),
) -> Result(Searcher(container), Nil) {
  let size = api.get_size(pattern)
  use <- bool.guard(size == 0, Error(Nil))

  let bad_chars = dict.new()
  let bad_chars = build_bad_chars(api, pattern, bad_chars, size, 0)

  let fun = fn(data: container, bounds: Bounds) {
    let data_size = api.get_size(data)
    case data_size {
      0 -> Error(Nil)
      _ -> {
        let start =
          int.clamp(option.unwrap(bounds.start, 0), min: 0, max: data_size)
        let end =
          int.clamp(
            option.unwrap(bounds.end, data_size),
            min: start,
            max: data_size,
          )

        let last_index = end - size
        let last_pattern_index = size - 1

        case
          do_search_loop(
            api,
            data,
            pattern,
            bad_chars,
            start,
            last_index,
            last_pattern_index,
          )
        {
          -1 -> Error(Nil)
          i -> Ok(i)
        }
      }
    }
  }

  Ok(Searcher(fun))
}

/// 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(haystack data: container, needle searcher: Searcher(container)) {
  search_bounded(data, searcher, Bounds(option.None, option.None))
}

/// 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.
pub fn search_bounded(
  haystack data: container,
  needle searcher: Searcher(container),
  bounds bounds: Bounds,
) {
  case bounds {
    Bounds(start: option.Some(start), end: option.Some(end)) if start == end ->
      Error(Nil)
    _ -> searcher.fun(data, bounds)
  }
}

/// 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 default_equality(a: item, b: item) {
  a == b
}

fn build_bad_chars(
  api: API(container, item),
  pattern: container,
  positions: dict.Dict(item, Int),
  pattern_size: Int,
  i: Int,
) -> dict.Dict(item, Int) {
  case i < pattern_size {
    True -> {
      let piece = api.unsafe_access(pattern, i)
      let positions = dict.insert(positions, piece, i)
      build_bad_chars(api, pattern, positions, pattern_size, i + 1)
    }
    False -> positions
  }
}

fn do_search_loop(
  api: API(container, item),
  data: container,
  pattern: container,
  bad_chars: dict.Dict(item, Int),
  current: Int,
  last_index: Int,
  last_pattern_index: Int,
) {
  case current > last_index {
    True -> -1
    False ->
      case
        calculate_skip(
          api,
          data,
          pattern,
          bad_chars,
          current,
          last_pattern_index,
        )
      {
        0 -> current
        skip -> {
          let current = current + skip
          do_search_loop(
            api,
            data,
            pattern,
            bad_chars,
            current,
            last_index,
            last_pattern_index,
          )
        }
      }
  }
}

fn calculate_skip(
  api: API(container, item),
  data: container,
  pattern: container,
  bad_chars: dict.Dict(item, Int),
  current: Int,
  current_pattern_index: Int,
) {
  case current_pattern_index < 0 {
    True -> 0
    False -> {
      let char = api.unsafe_access(data, current + current_pattern_index)
      let pattern_char = api.unsafe_access(pattern, current_pattern_index)
      case api.are_equal(char, pattern_char) {
        True ->
          calculate_skip(
            api,
            data,
            pattern,
            bad_chars,
            current,
            current_pattern_index - 1,
          )
        False -> {
          let pos = result.unwrap(dict.get(bad_chars, char), -1)
          int.max(1, current_pattern_index - pos)
        }
      }
    }
  }
}

// ============
// BitArray API
// ============

/// 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.
@external(erlang, "boyer_moore_ffi", "build_pattern")
pub fn build_byte_searcher(pattern: BitArray) -> Result(Searcher(BitArray), Nil) {
  build_generic_searcher(
    pattern,
    API(
      get_size: bit_array.byte_size,
      are_equal: default_equality,
      unsafe_access: bit_array_at,
    ),
  )
}

fn bit_array_at(data: BitArray, i: Int) -> Int {
  let assert Ok(<<byte:size(8)>>) = bit_array.slice(data, i, 1)
  byte
}