/**
 * Fuzzy search for list of objects.
 * - Each object in `items` must have a `value`. Or set the search key in options.
 * - Returns an array of original objects ordered by their relevance.
 * - Implements a cutoff for non-matching strings based on minimum relevance. Can be set in the options.
 *
 * @param {string} query - The search string.
 * @param {Object[]} items - The array of objects to search. Each must have a 'value' property (string).
 * @param {object} [options] - Optional settings.
 * @param {number} [options.cutoff=0.2] - Minimum relevance threshold (0 to 1).
 * @param {string} [options.key='value'] - The property name to match against (default: 'value').
 * @param {boolean} [options.allOnEmpty=true] - Return all items on empty query.
 * @param {Object} [options.boostMap] - An object mapping item keys (by 'value') to normalized boost values (0 to 1).
 * @param {number} [options.boostWeight=0.1] - The maximum boost to apply for boostMap value 1.0.
 * @returns {Object[]} - Array of matching objects sorted by relevance.
 */
function fuzzySearch(query, items, options = {}) {
  const cutoff = options.cutoff ?? 0.2;
  const key = options.key ?? 'name';
  const boostMap = options.boostMap || {};
  const boostWeight = options.boostWeight ?? 0.1;
  const allOnEmpty = options.allOnEmpty == undefined || options.allOnEmpty == true;

  if (!query) return allOnEmpty ? items : []

  const q = query.toLowerCase();

  return items
    .map(item => {
      const text = (item[key] || '').toLowerCase();
      let score = 0;

      // Perfect match
      if (text === q) score = 1.0;
      // Starts with
      else if (text.startsWith(q)) score = 0.9 + 0.01 * (1 - q.length / (text.length || 1));
      // Substring match
      else {
        const idx = text.indexOf(q);
        if (idx !== -1) {
          const startScore = 0.7 - 0.1 * (idx / (text.length || 1));
          const lengthScore = 0.2 * (q.length / (text.length || 1));
          score = startScore + lengthScore;
        } else {
          // Fuzzy: all query chars in order
          let lastIdx = -1;
          let found = true;
          for (let c of q) {
            lastIdx = text.indexOf(c, lastIdx + 1);
            if (lastIdx === -1) {
              found = false;
              break;
            }
          }
          if (found) {
            score = 0.5 * (q.length / (text.length || 1));
          }
        }
      }

      // Boost: expects normalized boostMap (values from 0 to 1)
      const boost = Math.max(0, Math.min(1, boostMap[item[key]] || 0)) * boostWeight;

      return { item, score: score + boost };
    })
    .filter(result => result.score >= cutoff)
    .sort((a, b) => b.score - a.score)
    .map(result => result.item);
}