levenshtein.dart

import 'dart:math';

typedef Stringify<T> = String Function(T item);

/// Utility class to apply Levenshtein score on each items
class SearchResult<T> implements Comparable<SearchResult<T>> {
  SearchResult(this.value, {required this.score});
  
  final double score;

  final T value;

  @override
  int compareTo(SearchResult other) => score.compareTo(other.score);
}

/// The Levenshtein distance, or edit distance, between two words is the
/// minimum number of single-character edits (insertions, deletions or
/// substitutions) required to change one word into the other.
class Levenshtein {
  static int _distance(String s1, String s2) {
    if (s1 == s2) {
      return 0;
    }

    if (s1.isEmpty) {
      return s2.length;
    }

    if (s2.isEmpty) {
      return s1.length;
    }

    var v0 = List<int>.generate(s2.length + 1, (i) => i, growable: false);
    var v1 = List<int>.filled(s2.length + 1, 0);
    List<int> vtemp;

    for (var i = 0; i < s1.length; i++) {
      v1[0] = i + 1;

      for (var j = 0; j < s2.length; j++) {
        var cost = 1;
        if (s1.codeUnitAt(i) == s2.codeUnitAt(j)) {
          cost = 0;
        }
        v1[j + 1] = min(v1[j] + 1, min(v0[j + 1] + 1, v0[j] + cost));
      }

      vtemp = v0;
      v0 = v1;
      v1 = vtemp;
    }

    return v0[s2.length];
  }

  static double distance(String s1, String s2) {
    final maxLength = max(s1.length, s2.length);
    if (maxLength == 0) {
      return 0;
    }
    return _distance(s1.toLowerCase(), s2.toLowerCase()) / maxLength;
  }
}

extension SearchResultExtension<T> on Iterable<T> {
  /// Apply Levenshtein score on each sport center
  List<SearchResult<T>> asSearchResults(
    String query,
    Stringify<T> stringnify,
  ) {
    return map(
      (it) => SearchResult(it, score: Levenshtein.distance(query, stringnify(it))),
    ).toList();
  }

  /// Sort results by Levenshtein scores
  List<SearchResult<T>> sortedBy(
    String query,
    Stringify<T> stringnify,
  ) {
    return asSearchResults(query, stringnify)..sort((curr, next) => curr.compareTo(next));
  }

  /// return centers ordered by Levenshtein score
  List<T> orderWithLevenshteinScore(
    String query,
    Stringify<T> stringnify,
  ) {
    if (query.isEmpty) {
      return toList();
    }

    return sortedBy(query, stringnify).map((x) => x.value).toList();
  }
}