starfuzz

//// A module providing fuzzy search collections matching capabilities.
//// Collections of custom candidates can be searched in-memory with custom selectors,
//// similarity scoring functions, score thresholds, and limits.

import gleam/option.{type Option, None, Some}
import gleam/list
import gleam/order.{type Order, Lt, Gt}
import starfuzz/normalize.{type Normalizer}
import starfuzz/similarity

/// A matched result from a fuzzy search query.
pub type Match(candidate) {
  Match(
    /// The original candidate item from the list.
    candidate: candidate,
    /// The similarity score calculated for this match (between 0.0 and 1.0).
    score: Float,
    /// The original index of this candidate in the input list (used for stable tie-breaking).
    index: Int,
  )
}

/// An immutable search configuration builder.
pub type SearchBuilder(candidate) {
  SearchBuilder(
    candidates: List(candidate),
    selector: fn(candidate) -> String,
    scorer: fn(String, String) -> Float,
    normalizer: Option(Normalizer),
    min_score: Float,
    limit: Option(Int),
  )
}

/// Creates a new SearchBuilder with the list of candidates and a string selector function.
/// Defaults to using Levenshtein similarity, no normalizer, minimum score of 0.0, and no limit.
pub fn new(candidates: List(candidate), selector: fn(candidate) -> String) -> SearchBuilder(candidate) {
  SearchBuilder(
    candidates: candidates,
    selector: selector,
    scorer: similarity.levenshtein,
    normalizer: None,
    min_score: 0.0,
    limit: None,
  )
}

/// Configures a custom selector function to retrieve the string value to match from candidates.
pub fn by(builder: SearchBuilder(candidate), selector: fn(candidate) -> String) -> SearchBuilder(candidate) {
  SearchBuilder(..builder, selector: selector)
}

/// Configures the similarity scoring function to use for comparison (e.g. `similarity.jaro_winkler`).
pub fn using(builder: SearchBuilder(candidate), scorer: fn(String, String) -> Float) -> SearchBuilder(candidate) {
  SearchBuilder(..builder, scorer: scorer)
}

/// Configures the normalizer to clean up both query and candidate strings before scoring.
pub fn with_normalizer(builder: SearchBuilder(candidate), normalizer: Normalizer) -> SearchBuilder(candidate) {
  SearchBuilder(..builder, normalizer: Some(normalizer))
}

/// Configures the minimum score threshold. Matches below this score are discarded.
pub fn with_minimum_score(builder: SearchBuilder(candidate), min_score: Float) -> SearchBuilder(candidate) {
  SearchBuilder(..builder, min_score: min_score)
}

/// Configures a limit on the number of matches returned.
pub fn with_limit(builder: SearchBuilder(candidate), limit: Int) -> SearchBuilder(candidate) {
  SearchBuilder(..builder, limit: Some(limit))
}

/// Runs the fuzzy search query against the candidates list.
/// Returns matched candidates sorted descending by score, with original index-based tie-breaking.
pub fn run(builder: SearchBuilder(candidate), query: String) -> List(Match(candidate)) {
  let norm_query = case builder.normalizer {
    Some(normalizer) -> normalize.apply(normalizer, query)
    None -> query
  }

  let candidates_indexed = list.index_map(builder.candidates, fn(c, i) { #(c, i) })

  let matches = list.fold(candidates_indexed, [], fn(acc, item) {
    let #(candidate, i) = item
    let raw_val = builder.selector(candidate)
    let val = case builder.normalizer {
      Some(normalizer) -> normalize.apply(normalizer, raw_val)
      None -> raw_val
    }

    let score = builder.scorer(norm_query, val)
    case score >=. builder.min_score {
      True -> [Match(candidate: candidate, score: score, index: i), ..acc]
      False -> acc
    }
  })

  let sorted = list.sort(matches, compare_matches)

  case builder.limit {
    Some(l) -> list.take(sorted, l)
    None -> sorted
  }
}

fn compare_matches(a: Match(c), b: Match(c)) -> Order {
  case a.score >. b.score {
    True -> Lt
    False -> {
      case a.score <. b.score {
        True -> Gt
        False -> {
          case a.index < b.index {
            True -> Lt
            False -> Gt
          }
        }
      }
    }
  }
}

/// Quick direct search over a list of strings using default Levenshtein similarity.
pub fn strings(query: String, candidates: List(String)) -> List(Match(String)) {
  new(candidates, fn(x) { x })
  |> run(query)
}