1 | "use strict";
|
2 |
|
3 | Object.defineProperty(exports, "__esModule", {
|
4 | value: true
|
5 | });
|
6 | exports.default = suggestionList;
|
7 |
|
8 | var _naturalCompare = _interopRequireDefault(require("./naturalCompare.js"));
|
9 |
|
10 | function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }
|
11 |
|
12 |
|
13 |
|
14 |
|
15 |
|
16 | function suggestionList(input, options) {
|
17 | var optionsByDistance = Object.create(null);
|
18 | var lexicalDistance = new LexicalDistance(input);
|
19 | var threshold = Math.floor(input.length * 0.4) + 1;
|
20 |
|
21 | for (var _i2 = 0; _i2 < options.length; _i2++) {
|
22 | var option = options[_i2];
|
23 | var distance = lexicalDistance.measure(option, threshold);
|
24 |
|
25 | if (distance !== undefined) {
|
26 | optionsByDistance[option] = distance;
|
27 | }
|
28 | }
|
29 |
|
30 | return Object.keys(optionsByDistance).sort(function (a, b) {
|
31 | var distanceDiff = optionsByDistance[a] - optionsByDistance[b];
|
32 | return distanceDiff !== 0 ? distanceDiff : (0, _naturalCompare.default)(a, b);
|
33 | });
|
34 | }
|
35 |
|
36 |
|
37 |
|
38 |
|
39 |
|
40 |
|
41 |
|
42 |
|
43 |
|
44 |
|
45 |
|
46 |
|
47 |
|
48 |
|
49 |
|
50 |
|
51 | var LexicalDistance = function () {
|
52 | function LexicalDistance(input) {
|
53 | this._input = input;
|
54 | this._inputLowerCase = input.toLowerCase();
|
55 | this._inputArray = stringToArray(this._inputLowerCase);
|
56 | this._rows = [new Array(input.length + 1).fill(0), new Array(input.length + 1).fill(0), new Array(input.length + 1).fill(0)];
|
57 | }
|
58 |
|
59 | var _proto = LexicalDistance.prototype;
|
60 |
|
61 | _proto.measure = function measure(option, threshold) {
|
62 | if (this._input === option) {
|
63 | return 0;
|
64 | }
|
65 |
|
66 | var optionLowerCase = option.toLowerCase();
|
67 |
|
68 | if (this._inputLowerCase === optionLowerCase) {
|
69 | return 1;
|
70 | }
|
71 |
|
72 | var a = stringToArray(optionLowerCase);
|
73 | var b = this._inputArray;
|
74 |
|
75 | if (a.length < b.length) {
|
76 | var tmp = a;
|
77 | a = b;
|
78 | b = tmp;
|
79 | }
|
80 |
|
81 | var aLength = a.length;
|
82 | var bLength = b.length;
|
83 |
|
84 | if (aLength - bLength > threshold) {
|
85 | return undefined;
|
86 | }
|
87 |
|
88 | var rows = this._rows;
|
89 |
|
90 | for (var j = 0; j <= bLength; j++) {
|
91 | rows[0][j] = j;
|
92 | }
|
93 |
|
94 | for (var i = 1; i <= aLength; i++) {
|
95 | var upRow = rows[(i - 1) % 3];
|
96 | var currentRow = rows[i % 3];
|
97 | var smallestCell = currentRow[0] = i;
|
98 |
|
99 | for (var _j = 1; _j <= bLength; _j++) {
|
100 | var cost = a[i - 1] === b[_j - 1] ? 0 : 1;
|
101 | var currentCell = Math.min(upRow[_j] + 1,
|
102 | currentRow[_j - 1] + 1,
|
103 | upRow[_j - 1] + cost
|
104 | );
|
105 |
|
106 | if (i > 1 && _j > 1 && a[i - 1] === b[_j - 2] && a[i - 2] === b[_j - 1]) {
|
107 |
|
108 | var doubleDiagonalCell = rows[(i - 2) % 3][_j - 2];
|
109 | currentCell = Math.min(currentCell, doubleDiagonalCell + 1);
|
110 | }
|
111 |
|
112 | if (currentCell < smallestCell) {
|
113 | smallestCell = currentCell;
|
114 | }
|
115 |
|
116 | currentRow[_j] = currentCell;
|
117 | }
|
118 |
|
119 |
|
120 | if (smallestCell > threshold) {
|
121 | return undefined;
|
122 | }
|
123 | }
|
124 |
|
125 | var distance = rows[aLength % 3][bLength];
|
126 | return distance <= threshold ? distance : undefined;
|
127 | };
|
128 |
|
129 | return LexicalDistance;
|
130 | }();
|
131 |
|
132 | function stringToArray(str) {
|
133 | var strLength = str.length;
|
134 | var array = new Array(strLength);
|
135 |
|
136 | for (var i = 0; i < strLength; ++i) {
|
137 | array[i] = str.charCodeAt(i);
|
138 | }
|
139 |
|
140 | return array;
|
141 | }
|