1/**
2 * Copyright (c) 2015-present, Facebook, Inc.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 *
7 *  strict
8 */
9
10/**
11 * Given an invalid input string and a list of valid options, returns a filtered
12 * list of valid options sorted based on their similarity with the input.
13 */
14export default function suggestionList(input, options) {
15  var optionsByDistance = Object.create(null);
16  var oLength = options.length;
17  var inputThreshold = input.length / 2;
18  for (var i = 0; i < oLength; i++) {
19    var distance = lexicalDistance(input, options[i]);
20    var threshold = Math.max(inputThreshold, options[i].length / 2, 1);
21    if (distance <= threshold) {
22      optionsByDistance[options[i]] = distance;
23    }
24  }
25  return Object.keys(optionsByDistance).sort(function (a, b) {
26    return optionsByDistance[a] - optionsByDistance[b];
27  });
28}
29
30/**
31 * Computes the lexical distance between strings A and B.
32 *
33 * The "distance" between two strings is given by counting the minimum number
34 * of edits needed to transform string A into string B. An edit can be an
35 * insertion, deletion, or substitution of a single character, or a swap of two
36 * adjacent characters.
37 *
38 * Includes a custom alteration from Damerau-Levenshtein to treat case changes
39 * as a single edit which helps identify mis-cased values with an edit distance
40 * of 1.
41 *
42 * This distance can be useful for detecting typos in input or sorting
43 *
44 * @param {string} a
45 * @param {string} b
46 * @return {int} distance in number of edits
47 */
48function lexicalDistance(aStr, bStr) {
49  if (aStr === bStr) {
50    return 0;
51  }
52
53  var i = void 0;
54  var j = void 0;
55  var d = [];
56  var a = aStr.toLowerCase();
57  var b = bStr.toLowerCase();
58  var aLength = a.length;
59  var bLength = b.length;
60
61  // Any case change counts as a single edit
62  if (a === b) {
63    return 1;
64  }
65
66  for (i = 0; i <= aLength; i++) {
67    d[i] = [i];
68  }
69
70  for (j = 1; j <= bLength; j++) {
71    d[0][j] = j;
72  }
73
74  for (i = 1; i <= aLength; i++) {
75    for (j = 1; j <= bLength; j++) {
76      var cost = a[i - 1] === b[j - 1] ? 0 : 1;
77
78      d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
79
80      if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
81        d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
82      }
83    }
84  }
85
86  return d[aLength][bLength];
87}