| 1 |
/* |
| 2 |
* Fuzzy |
| 3 |
* https://github.com/myork/fuzzy |
| 4 |
* |
| 5 |
* Copyright (c) 2012 Matt York |
| 6 |
* |
| 7 |
* Permission is hereby granted, free of charge, to any person |
| 8 |
* obtaining a copy of this software and associated documentation |
| 9 |
* files (the "Software"), to deal in the Software without |
| 10 |
* restriction, including without limitation the rights to use, |
| 11 |
* copy, modify, merge, publish, distribute, sublicense, and/or sell |
| 12 |
* copies of the Software, and to permit persons to whom the |
| 13 |
* Software is furnished to do so, subject to the following |
| 14 |
* conditions: |
| 15 |
* |
| 16 |
* The above copyright notice and this permission notice shall be |
| 17 |
* included in all copies or substantial portions of the Software. |
| 18 |
* |
| 19 |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| 20 |
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
| 21 |
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| 22 |
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
| 23 |
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
| 24 |
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| 25 |
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
| 26 |
* OTHER DEALINGS IN THE SOFTWARE. |
| 27 |
* |
| 28 |
* A slightly modified version of https://github.com/mattyork/fuzzy/blob/3613086aa40c180ca722aeaf48cef575dc57eb5d/lib/fuzzy.js |
| 29 |
*/ |
| 30 |
|
| 31 |
(function() { |
| 32 |
|
| 33 |
var root = this; |
| 34 |
|
| 35 |
var fuzzy = {}; |
| 36 |
|
| 37 |
// Use in node or in browser |
| 38 |
if (typeof exports !== 'undefined') { |
| 39 |
module.exports = fuzzy; |
| 40 |
} else { |
| 41 |
root.fuzzy = fuzzy; |
| 42 |
} |
| 43 |
|
| 44 |
// Return all elements of `array` that have a fuzzy |
| 45 |
// match against `pattern`. |
| 46 |
fuzzy.simpleFilter = function(pattern, array) { |
| 47 |
return array.filter(function(str) { |
| 48 |
return fuzzy.test(pattern, str); |
| 49 |
}); |
| 50 |
}; |
| 51 |
|
| 52 |
// Does `pattern` fuzzy match `str`? |
| 53 |
fuzzy.test = function(pattern, str) { |
| 54 |
return fuzzy.match(pattern, str) !== null; |
| 55 |
}; |
| 56 |
|
| 57 |
// If `pattern` matches `str`, wrap each matching character |
| 58 |
// in `opts.pre` and `opts.post`. If no match, return null |
| 59 |
fuzzy.match = function(pattern, str, opts, _fromIndex) { |
| 60 |
opts = opts || {}; |
| 61 |
var patternIdx = 0 |
| 62 |
, result = [] |
| 63 |
, len = str.length |
| 64 |
, fromIndex = _fromIndex || 0 |
| 65 |
, totalScore = 0 |
| 66 |
, currScore = 0 |
| 67 |
// prefix |
| 68 |
, pre = opts.pre || '' |
| 69 |
// suffix |
| 70 |
, post = opts.post || '' |
| 71 |
// String to compare against. This might be a lowercase version of the |
| 72 |
// raw string |
| 73 |
, compareString = opts.caseSensitive && str || str.toLowerCase() |
| 74 |
, ch; |
| 75 |
|
| 76 |
pattern = opts.caseSensitive && pattern || pattern.toLowerCase(); |
| 77 |
|
| 78 |
// If there's an exact match, add pre/post, max out score and skip the lookup |
| 79 |
if (compareString === pattern) { |
| 80 |
return { |
| 81 |
rendered: pre + compareString.split('').join(post+pre) + post, |
| 82 |
score: Infinity |
| 83 |
}; |
| 84 |
} |
| 85 |
|
| 86 |
// For each character in the string, either add it to the result |
| 87 |
// or wrap in template if it's the next string in the pattern |
| 88 |
for(var idx = 0; idx < len; idx++) { |
| 89 |
ch = str[idx]; |
| 90 |
if(idx >= fromIndex && compareString[idx] === pattern[patternIdx]) { |
| 91 |
ch = pre + ch + post; |
| 92 |
patternIdx += 1; |
| 93 |
|
| 94 |
// consecutive characters should increase the score more than linearly |
| 95 |
currScore += 1 + currScore; |
| 96 |
} else { |
| 97 |
currScore = 0; |
| 98 |
} |
| 99 |
totalScore += currScore; |
| 100 |
result[result.length] = ch; |
| 101 |
} |
| 102 |
|
| 103 |
// return rendered string if we have a match for every char |
| 104 |
if(patternIdx === pattern.length) { |
| 105 |
var nextPossible = str.indexOf(pattern[0], str.indexOf(pattern[0], fromIndex) + 1) |
| 106 |
, candidate; |
| 107 |
|
| 108 |
// If possible, try to find a better match at the rest of the string |
| 109 |
if (nextPossible > -1 && str.length - nextPossible >= pattern.length) { |
| 110 |
var candidate = fuzzy.match(pattern, str, opts, nextPossible); |
| 111 |
} |
| 112 |
|
| 113 |
return candidate && candidate.score > totalScore ? candidate : { |
| 114 |
rendered: result.join(''), score: totalScore |
| 115 |
}; |
| 116 |
} |
| 117 |
|
| 118 |
return null; |
| 119 |
}; |
| 120 |
|
| 121 |
// The normal entry point. Filters `arr` for matches against `pattern`. |
| 122 |
// It returns an array with matching values of the type: |
| 123 |
// |
| 124 |
// [{ |
| 125 |
// string: '<b>lah' // The rendered string |
| 126 |
// , index: 2 // The index of the element in `arr` |
| 127 |
// , original: 'blah' // The original element in `arr` |
| 128 |
// }] |
| 129 |
// |
| 130 |
// `opts` is an optional argument bag. Details: |
| 131 |
// |
| 132 |
// opts = { |
| 133 |
// // string to put before a matching character |
| 134 |
// pre: '<b>' |
| 135 |
// |
| 136 |
// // string to put after matching character |
| 137 |
// , post: '</b>' |
| 138 |
// |
| 139 |
// // Optional function. Input is an entry in the given arr`, |
| 140 |
// // output should be the string to test `pattern` against. |
| 141 |
// // In this example, if `arr = [{crying: 'koala'}]` we would return |
| 142 |
// // 'koala'. |
| 143 |
// , extract: function(arg) { return arg.crying; } |
| 144 |
// } |
| 145 |
fuzzy.filter = function(pattern, arr, opts) { |
| 146 |
if(!arr || arr.length === 0) { |
| 147 |
return []; |
| 148 |
} |
| 149 |
if (typeof pattern !== 'string' || pattern === '') { |
| 150 |
return arr; |
| 151 |
} |
| 152 |
opts = opts || {}; |
| 153 |
return arr |
| 154 |
.reduce(function(prev, element, idx, arr) { |
| 155 |
var str = element; |
| 156 |
if(opts.extract) { |
| 157 |
str = opts.extract(element); |
| 158 |
} |
| 159 |
var rendered = fuzzy.match(pattern, str, opts); |
| 160 |
if(rendered != null) { |
| 161 |
prev[prev.length] = { |
| 162 |
string: rendered.rendered |
| 163 |
, score: rendered.score |
| 164 |
, index: idx |
| 165 |
, original: element |
| 166 |
}; |
| 167 |
} |
| 168 |
return prev; |
| 169 |
}, []) |
| 170 |
|
| 171 |
// Sort by score. Browsers are inconsistent wrt stable/unstable |
| 172 |
// sorting, so force stable by using the index in the case of tie. |
| 173 |
// See http://ofb.net/~sethml/is-sort-stable.html |
| 174 |
.sort(function(a,b) { |
| 175 |
var compare = b.score - a.score; |
| 176 |
if(compare) return compare; |
| 177 |
return a.index - b.index; |
| 178 |
}); |
| 179 |
}; |
| 180 |
|
| 181 |
|
| 182 |
}()); |