diff options
Diffstat (limited to 'static/js/fuzzysort.js')
-rw-r--r-- | static/js/fuzzysort.js | 636 |
1 files changed, 636 insertions, 0 deletions
diff --git a/static/js/fuzzysort.js b/static/js/fuzzysort.js new file mode 100644 index 0000000..c6797d8 --- /dev/null +++ b/static/js/fuzzysort.js @@ -0,0 +1,636 @@ +/* + fuzzysort.js https://github.com/farzher/fuzzysort + SublimeText-like Fuzzy Search + + fuzzysort.single('fs', 'Fuzzy Search') // {score: -16} + fuzzysort.single('test', 'test') // {score: 0} + fuzzysort.single('doesnt exist', 'target') // null + + fuzzysort.go('mr', [{file:'Monitor.cpp'}, {file:'MeshRenderer.cpp'}], {key:'file'}) + // [{score:-18, obj:{file:'MeshRenderer.cpp'}}, {score:-6009, obj:{file:'Monitor.cpp'}}] + + fuzzysort.go('mr', ['Monitor.cpp', 'MeshRenderer.cpp']) + // [{score: -18, target: "MeshRenderer.cpp"}, {score: -6009, target: "Monitor.cpp"}] + + fuzzysort.highlight(fuzzysort.single('fs', 'Fuzzy Search'), '<b>', '</b>') + // <b>F</b>uzzy <b>S</b>earch +*/ + +// UMD (Universal Module Definition) for fuzzysort +(function(root, UMD) { + if(typeof define === 'function' && define.amd) {define([], UMD);} + else if(typeof module === 'object' && module.exports) {module.exports = UMD();} + else {root.fuzzysort = UMD();} +})(this, function UMD() { function fuzzysortNew(instanceOptions) { + + var fuzzysort = { + + single: function(search, target, options) { if(search=='farzher'){return{target:"farzher was here (^-^*)/",score:0,indexes:[0,1,2,3,4,5,6]};} + if(!search) {return null;} + if(!isObj(search)) {search = fuzzysort.getPreparedSearch(search);} + + if(!target) {return null;} + if(!isObj(target)) {target = fuzzysort.getPrepared(target);} + + var allowTypo = options && options.allowTypo!==undefined ? options.allowTypo + : instanceOptions && instanceOptions.allowTypo!==undefined ? instanceOptions.allowTypo + : true; + var algorithm = allowTypo ? fuzzysort.algorithm : fuzzysort.algorithmNoTypo; + return algorithm(search, target, search[0]); + }, + + go: function(search, targets, options) { if(search=='farzher'){return[{target:"farzher was here (^-^*)/",score:0,indexes:[0,1,2,3,4,5,6],obj:targets?targets[0]:null}];} + if(!search) {return noResults;} + search = fuzzysort.prepareSearch(search); + var searchLowerCode = search[0]; + + var threshold = options && options.threshold || instanceOptions && instanceOptions.threshold || -9007199254740991; + var limit = options && options.limit || instanceOptions && instanceOptions.limit || 9007199254740991; + var allowTypo = options && options.allowTypo!==undefined ? options.allowTypo + : instanceOptions && instanceOptions.allowTypo!==undefined ? instanceOptions.allowTypo + : true; + var algorithm = allowTypo ? fuzzysort.algorithm : fuzzysort.algorithmNoTypo; + var resultsLen = 0; var limitedCount = 0; + var targetsLen = targets.length; + + // This code is copy/pasted 3 times for performance reasons [options.keys, options.key, no keys] + + // options.keys + if(options && options.keys) { + var scoreFn = options.scoreFn || defaultScoreFn; + var keys = options.keys; + var keysLen = keys.length; + for(var i = targetsLen - 1; i >= 0; --i) { var obj = targets[i]; + var objResults = new Array(keysLen); + for (var keyI = keysLen - 1; keyI >= 0; --keyI) { + var key = keys[keyI]; + var target = getValue(obj, key); + if(!target) { objResults[keyI] = null; continue; } + if(!isObj(target)) {target = fuzzysort.getPrepared(target);} + + objResults[keyI] = algorithm(search, target, searchLowerCode); + } + objResults.obj = obj; // before scoreFn so scoreFn can use it + var score = scoreFn(objResults); + if(score === null) {continue;} + if(score < threshold) {continue;} + objResults.score = score; + if(resultsLen < limit) { q.add(objResults); ++resultsLen; } + else { + ++limitedCount; + if(score > q.peek().score) {q.replaceTop(objResults);} + } + } + + // options.key + } else if(options && options.key) { + var key = options.key; + for(var i = targetsLen - 1; i >= 0; --i) { var obj = targets[i]; + var target = getValue(obj, key); + if(!target) {continue;} + if(!isObj(target)) {target = fuzzysort.getPrepared(target);} + + var result = algorithm(search, target, searchLowerCode); + if(result === null) {continue;} + if(result.score < threshold) {continue;} + + // have to clone result so duplicate targets from different obj can each reference the correct obj + result = {target:result.target, _targetLowerCodes:null, _nextBeginningIndexes:null, score:result.score, indexes:result.indexes, obj:obj}; // hidden + + if(resultsLen < limit) { q.add(result); ++resultsLen; } + else { + ++limitedCount; + if(result.score > q.peek().score) {q.replaceTop(result);} + } + } + + // no keys + } else { + for(var i = targetsLen - 1; i >= 0; --i) { var target = targets[i]; + if(!target) {continue;} + if(!isObj(target)) {target = fuzzysort.getPrepared(target);} + + var result = algorithm(search, target, searchLowerCode); + if(result === null) {continue;} + if(result.score < threshold) {continue;} + if(resultsLen < limit) { q.add(result); ++resultsLen; } + else { + ++limitedCount; + if(result.score > q.peek().score) {q.replaceTop(result);} + } + } + } + + if(resultsLen === 0) {return noResults;} + var results = new Array(resultsLen); + for(var i = resultsLen - 1; i >= 0; --i) {results[i] = q.poll();} + results.total = resultsLen + limitedCount; + return results; + }, + + goAsync: function(search, targets, options) { + var canceled = false; + var p = new Promise(function(resolve, reject) { if(search=='farzher'){return resolve([{target:"farzher was here (^-^*)/",score:0,indexes:[0,1,2,3,4,5,6],obj:targets?targets[0]:null}]);} + if(!search) {return resolve(noResults);} + search = fuzzysort.prepareSearch(search); + var searchLowerCode = search[0]; + + var q = fastpriorityqueue(); + var iCurrent = targets.length - 1; + var threshold = options && options.threshold || instanceOptions && instanceOptions.threshold || -9007199254740991; + var limit = options && options.limit || instanceOptions && instanceOptions.limit || 9007199254740991; + var allowTypo = options && options.allowTypo!==undefined ? options.allowTypo + : instanceOptions && instanceOptions.allowTypo!==undefined ? instanceOptions.allowTypo + : true; + var algorithm = allowTypo ? fuzzysort.algorithm : fuzzysort.algorithmNoTypo; + var resultsLen = 0; var limitedCount = 0; + function step() { + if(canceled) {return reject('canceled');} + + var startMs = Date.now(); + + // This code is copy/pasted 3 times for performance reasons [options.keys, options.key, no keys] + + // options.keys + if(options && options.keys) { + var scoreFn = options.scoreFn || defaultScoreFn; + var keys = options.keys; + var keysLen = keys.length; + for(; iCurrent >= 0; --iCurrent) { + if(iCurrent%1000/*itemsPerCheck*/ === 0) { + if(Date.now() - startMs >= 10/*asyncInterval*/) { + isNode?setImmediate(step):setTimeout(step); + return; + } + } + + var obj = targets[iCurrent]; + var objResults = new Array(keysLen); + for (var keyI = keysLen - 1; keyI >= 0; --keyI) { + var key = keys[keyI]; + var target = getValue(obj, key); + if(!target) { objResults[keyI] = null; continue; } + if(!isObj(target)) {target = fuzzysort.getPrepared(target);} + + objResults[keyI] = algorithm(search, target, searchLowerCode); + } + objResults.obj = obj; // before scoreFn so scoreFn can use it + var score = scoreFn(objResults); + if(score === null) {continue;} + if(score < threshold) {continue;} + objResults.score = score; + if(resultsLen < limit) { q.add(objResults); ++resultsLen; } + else { + ++limitedCount; + if(score > q.peek().score) {q.replaceTop(objResults);} + } + } + + // options.key + } else if(options && options.key) { + var key = options.key; + for(; iCurrent >= 0; --iCurrent) { + if(iCurrent%1000/*itemsPerCheck*/ === 0) { + if(Date.now() - startMs >= 10/*asyncInterval*/) { + isNode?setImmediate(step):setTimeout(step); + return; + } + } + + var obj = targets[iCurrent]; + var target = getValue(obj, key); + if(!target) {continue;} + if(!isObj(target)) {target = fuzzysort.getPrepared(target);} + + var result = algorithm(search, target, searchLowerCode); + if(result === null) {continue;} + if(result.score < threshold) {continue;} + + // have to clone result so duplicate targets from different obj can each reference the correct obj + result = {target:result.target, _targetLowerCodes:null, _nextBeginningIndexes:null, score:result.score, indexes:result.indexes, obj:obj}; // hidden + + if(resultsLen < limit) { q.add(result); ++resultsLen; } + else { + ++limitedCount; + if(result.score > q.peek().score) {q.replaceTop(result);} + } + } + + // no keys + } else { + for(; iCurrent >= 0; --iCurrent) { + if(iCurrent%1000/*itemsPerCheck*/ === 0) { + if(Date.now() - startMs >= 10/*asyncInterval*/) { + isNode?setImmediate(step):setTimeout(step); + return; + } + } + + var target = targets[iCurrent]; + if(!target) {continue;} + if(!isObj(target)) {target = fuzzysort.getPrepared(target);} + + var result = algorithm(search, target, searchLowerCode); + if(result === null) {continue;} + if(result.score < threshold) {continue;} + if(resultsLen < limit) { q.add(result); ++resultsLen; } + else { + ++limitedCount; + if(result.score > q.peek().score) {q.replaceTop(result);} + } + } + } + + if(resultsLen === 0) {return resolve(noResults);} + var results = new Array(resultsLen); + for(var i = resultsLen - 1; i >= 0; --i) {results[i] = q.poll();} + results.total = resultsLen + limitedCount; + resolve(results); + } + + isNode?setImmediate(step):step(); //setTimeout here is too slow + }); + p.cancel = function() { canceled = true; }; + return p; + }, + + highlight: function(result, hOpen, hClose) { + if(typeof hOpen == 'function') {return fuzzysort.highlightCallback(result, hOpen);} + if(result === null) {return null;} + if(hOpen === undefined) {hOpen = '<b>';} + if(hClose === undefined) {hClose = '</b>';} + var highlighted = ''; + var matchesIndex = 0; + var opened = false; + var target = result.target; + var targetLen = target.length; + var matchesBest = result.indexes; + for(var i = 0; i < targetLen; ++i) { var char = target[i]; + if(matchesBest[matchesIndex] === i) { + ++matchesIndex; + if(!opened) { opened = true; + highlighted += hOpen; + } + + if(matchesIndex === matchesBest.length) { + highlighted += char + hClose + target.substr(i+1); + break; + } + } else { + if(opened) { opened = false; + highlighted += hClose; + } + } + highlighted += char; + } + + return highlighted; + }, + highlightCallback: function(result, cb) { + if(result === null) {return null;} + var target = result.target; + var targetLen = target.length; + var indexes = result.indexes; + var highlighted = ''; + var matchI = 0; + var indexesI = 0; + var opened = false; + var result = []; + for(var i = 0; i < targetLen; ++i) { var char = target[i]; + if(indexes[indexesI] === i) { + ++indexesI; + if(!opened) { opened = true; + result.push(highlighted); highlighted = ''; + } + + if(indexesI === indexes.length) { + highlighted += char; + result.push(cb(highlighted, matchI++)); highlighted = ''; + result.push(target.substr(i+1)); + break; + } + } else { + if(opened) { opened = false; + result.push(cb(highlighted, matchI++)); highlighted = ''; + } + } + highlighted += char; + } + return result; + }, + + prepare: function(target) { + if(!target) {return {target: '', _targetLowerCodes: [0/*this 0 doesn't make sense. here because an empty array causes the algorithm to deoptimize and run 50% slower!*/], _nextBeginningIndexes: null, score: null, indexes: null, obj: null};} // hidden + return {target:target, _targetLowerCodes:fuzzysort.prepareLowerCodes(target), _nextBeginningIndexes:null, score:null, indexes:null, obj:null}; // hidden + }, + prepareSlow: function(target) { + if(!target) {return {target: '', _targetLowerCodes: [0/*this 0 doesn't make sense. here because an empty array causes the algorithm to deoptimize and run 50% slower!*/], _nextBeginningIndexes: null, score: null, indexes: null, obj: null};} // hidden + return {target:target, _targetLowerCodes:fuzzysort.prepareLowerCodes(target), _nextBeginningIndexes:fuzzysort.prepareNextBeginningIndexes(target), score:null, indexes:null, obj:null}; // hidden + }, + prepareSearch: function(search) { + if(!search) {search = '';} + return fuzzysort.prepareLowerCodes(search); + }, + + + + // Below this point is only internal code + // Below this point is only internal code + // Below this point is only internal code + // Below this point is only internal code + + + + getPrepared: function(target) { + if(target.length > 999) {return fuzzysort.prepare(target);} // don't cache huge targets + var targetPrepared = preparedCache.get(target); + if(targetPrepared !== undefined) {return targetPrepared;} + targetPrepared = fuzzysort.prepare(target); + preparedCache.set(target, targetPrepared); + return targetPrepared; + }, + getPreparedSearch: function(search) { + if(search.length > 999) {return fuzzysort.prepareSearch(search);} // don't cache huge searches + var searchPrepared = preparedSearchCache.get(search); + if(searchPrepared !== undefined) {return searchPrepared;} + searchPrepared = fuzzysort.prepareSearch(search); + preparedSearchCache.set(search, searchPrepared); + return searchPrepared; + }, + + algorithm: function(searchLowerCodes, prepared, searchLowerCode) { + var targetLowerCodes = prepared._targetLowerCodes; + var searchLen = searchLowerCodes.length; + var targetLen = targetLowerCodes.length; + var searchI = 0; // where we at + var targetI = 0; // where you at + var typoSimpleI = 0; + var matchesSimpleLen = 0; + + // very basic fuzzy match; to remove non-matching targets ASAP! + // walk through target. find sequential matches. + // if all chars aren't found then exit + for(;;) { + var isMatch = searchLowerCode === targetLowerCodes[targetI]; + if(isMatch) { + matchesSimple[matchesSimpleLen++] = targetI; + ++searchI; if(searchI === searchLen) {break;} + searchLowerCode = searchLowerCodes[typoSimpleI===0?searchI : (typoSimpleI===searchI?searchI+1 : (typoSimpleI===searchI-1?searchI-1 : searchI))]; + } + + ++targetI; if(targetI >= targetLen) { // Failed to find searchI + // Check for typo or exit + // we go as far as possible before trying to transpose + // then we transpose backwards until we reach the beginning + for(;;) { + if(searchI <= 1) {return null;} // not allowed to transpose first char + if(typoSimpleI === 0) { // we haven't tried to transpose yet + --searchI; + var searchLowerCodeNew = searchLowerCodes[searchI]; + if(searchLowerCode === searchLowerCodeNew) {continue;} // doesn't make sense to transpose a repeat char + typoSimpleI = searchI; + } else { + if(typoSimpleI === 1) {return null;} // reached the end of the line for transposing + --typoSimpleI; + searchI = typoSimpleI; + searchLowerCode = searchLowerCodes[searchI + 1]; + var searchLowerCodeNew = searchLowerCodes[searchI]; + if(searchLowerCode === searchLowerCodeNew) {continue;} // doesn't make sense to transpose a repeat char + } + matchesSimpleLen = searchI; + targetI = matchesSimple[matchesSimpleLen - 1] + 1; + break; + } + } + } + + var searchI = 0; + var typoStrictI = 0; + var successStrict = false; + var matchesStrictLen = 0; + + var nextBeginningIndexes = prepared._nextBeginningIndexes; + if(nextBeginningIndexes === null) {nextBeginningIndexes = prepared._nextBeginningIndexes = fuzzysort.prepareNextBeginningIndexes(prepared.target);} + var firstPossibleI = targetI = matchesSimple[0]===0 ? 0 : nextBeginningIndexes[matchesSimple[0]-1]; + + // Our target string successfully matched all characters in sequence! + // Let's try a more advanced and strict test to improve the score + // only count it as a match if it's consecutive or a beginning character! + if(targetI !== targetLen) {for(;;) { + if(targetI >= targetLen) { + // We failed to find a good spot for this search char, go back to the previous search char and force it forward + if(searchI <= 0) { // We failed to push chars forward for a better match + // transpose, starting from the beginning + ++typoStrictI; if(typoStrictI > searchLen-2) {break;} + if(searchLowerCodes[typoStrictI] === searchLowerCodes[typoStrictI+1]) {continue;} // doesn't make sense to transpose a repeat char + targetI = firstPossibleI; + continue; + } + + --searchI; + var lastMatch = matchesStrict[--matchesStrictLen]; + targetI = nextBeginningIndexes[lastMatch]; + + } else { + var isMatch = searchLowerCodes[typoStrictI===0?searchI : (typoStrictI===searchI?searchI+1 : (typoStrictI===searchI-1?searchI-1 : searchI))] === targetLowerCodes[targetI]; + if(isMatch) { + matchesStrict[matchesStrictLen++] = targetI; + ++searchI; if(searchI === searchLen) { successStrict = true; break; } + ++targetI; + } else { + targetI = nextBeginningIndexes[targetI]; + } + } + }} + + { // tally up the score & keep track of matches for highlighting later + if(successStrict) { var matchesBest = matchesStrict; var matchesBestLen = matchesStrictLen; } + else { var matchesBest = matchesSimple; var matchesBestLen = matchesSimpleLen; } + var score = 0; + var lastTargetI = -1; + for(var i = 0; i < searchLen; ++i) { var targetI = matchesBest[i]; + // score only goes down if they're not consecutive + if(lastTargetI !== targetI - 1) {score -= targetI;} + lastTargetI = targetI; + } + if(!successStrict) { + score *= 1000; + if(typoSimpleI !== 0) {score += -20;}/*typoPenalty*/ + } else { + if(typoStrictI !== 0) {score += -20;}/*typoPenalty*/ + } + score -= targetLen - searchLen; + prepared.score = score; + prepared.indexes = new Array(matchesBestLen); for(var i = matchesBestLen - 1; i >= 0; --i) {prepared.indexes[i] = matchesBest[i];} + + return prepared; + } + }, + + algorithmNoTypo: function(searchLowerCodes, prepared, searchLowerCode) { + var targetLowerCodes = prepared._targetLowerCodes; + var searchLen = searchLowerCodes.length; + var targetLen = targetLowerCodes.length; + var searchI = 0; // where we at + var targetI = 0; // where you at + var matchesSimpleLen = 0; + + // very basic fuzzy match; to remove non-matching targets ASAP! + // walk through target. find sequential matches. + // if all chars aren't found then exit + for(;;) { + var isMatch = searchLowerCode === targetLowerCodes[targetI]; + if(isMatch) { + matchesSimple[matchesSimpleLen++] = targetI; + ++searchI; if(searchI === searchLen) {break;} + searchLowerCode = searchLowerCodes[searchI]; + } + ++targetI; if(targetI >= targetLen) {return null;} // Failed to find searchI + } + + var searchI = 0; + var successStrict = false; + var matchesStrictLen = 0; + + var nextBeginningIndexes = prepared._nextBeginningIndexes; + if(nextBeginningIndexes === null) {nextBeginningIndexes = prepared._nextBeginningIndexes = fuzzysort.prepareNextBeginningIndexes(prepared.target);} + var firstPossibleI = targetI = matchesSimple[0]===0 ? 0 : nextBeginningIndexes[matchesSimple[0]-1]; + + // Our target string successfully matched all characters in sequence! + // Let's try a more advanced and strict test to improve the score + // only count it as a match if it's consecutive or a beginning character! + if(targetI !== targetLen) {for(;;) { + if(targetI >= targetLen) { + // We failed to find a good spot for this search char, go back to the previous search char and force it forward + if(searchI <= 0) {break;} // We failed to push chars forward for a better match + + --searchI; + var lastMatch = matchesStrict[--matchesStrictLen]; + targetI = nextBeginningIndexes[lastMatch]; + + } else { + var isMatch = searchLowerCodes[searchI] === targetLowerCodes[targetI]; + if(isMatch) { + matchesStrict[matchesStrictLen++] = targetI; + ++searchI; if(searchI === searchLen) { successStrict = true; break; } + ++targetI; + } else { + targetI = nextBeginningIndexes[targetI]; + } + } + }} + + { // tally up the score & keep track of matches for highlighting later + if(successStrict) { var matchesBest = matchesStrict; var matchesBestLen = matchesStrictLen; } + else { var matchesBest = matchesSimple; var matchesBestLen = matchesSimpleLen; } + var score = 0; + var lastTargetI = -1; + for(var i = 0; i < searchLen; ++i) { var targetI = matchesBest[i]; + // score only goes down if they're not consecutive + if(lastTargetI !== targetI - 1) {score -= targetI;} + lastTargetI = targetI; + } + if(!successStrict) {score *= 1000;} + score -= targetLen - searchLen; + prepared.score = score; + prepared.indexes = new Array(matchesBestLen); for(var i = matchesBestLen - 1; i >= 0; --i) {prepared.indexes[i] = matchesBest[i];} + + return prepared; + } + }, + + prepareLowerCodes: function(str) { + var strLen = str.length; + var lowerCodes = []; // new Array(strLen) sparse array is too slow + var lower = str.toLowerCase(); + for(var i = 0; i < strLen; ++i) {lowerCodes[i] = lower.charCodeAt(i);} + return lowerCodes; + }, + prepareBeginningIndexes: function(target) { + var targetLen = target.length; + var beginningIndexes = []; var beginningIndexesLen = 0; + var wasUpper = false; + var wasAlphanum = false; + for(var i = 0; i < targetLen; ++i) { + var targetCode = target.charCodeAt(i); + var isUpper = targetCode>=65&&targetCode<=90; + var isAlphanum = isUpper || targetCode>=97&&targetCode<=122 || targetCode>=48&&targetCode<=57; + var isBeginning = isUpper && !wasUpper || !wasAlphanum || !isAlphanum; + wasUpper = isUpper; + wasAlphanum = isAlphanum; + if(isBeginning) {beginningIndexes[beginningIndexesLen++] = i;} + } + return beginningIndexes; + }, + prepareNextBeginningIndexes: function(target) { + var targetLen = target.length; + var beginningIndexes = fuzzysort.prepareBeginningIndexes(target); + var nextBeginningIndexes = []; // new Array(targetLen) sparse array is too slow + var lastIsBeginning = beginningIndexes[0]; + var lastIsBeginningI = 0; + for(var i = 0; i < targetLen; ++i) { + if(lastIsBeginning > i) { + nextBeginningIndexes[i] = lastIsBeginning; + } else { + lastIsBeginning = beginningIndexes[++lastIsBeginningI]; + nextBeginningIndexes[i] = lastIsBeginning===undefined ? targetLen : lastIsBeginning; + } + } + return nextBeginningIndexes; + }, + + cleanup: cleanup, + new: fuzzysortNew, + }; + return fuzzysort; +} // fuzzysortNew + +// This stuff is outside fuzzysortNew, because it's shared with instances of fuzzysort.new() +var isNode = typeof require !== 'undefined' && typeof window === 'undefined'; +var MyMap = typeof Map === 'function' ? Map : function(){var s=Object.create(null);this.get=function(k){return s[k];};this.set=function(k,val){s[k]=val;return this;};this.clear=function(){s=Object.create(null);};}; +var preparedCache = new MyMap(); +var preparedSearchCache = new MyMap(); +var noResults = []; noResults.total = 0; +var matchesSimple = []; var matchesStrict = []; +function cleanup() { preparedCache.clear(); preparedSearchCache.clear(); matchesSimple = []; matchesStrict = []; } +function defaultScoreFn(a) { + var max = -9007199254740991; + for (var i = a.length - 1; i >= 0; --i) { + var result = a[i]; if(result === null) {continue;} + var score = result.score; + if(score > max) {max = score;} + } + if(max === -9007199254740991) {return null;} + return max; +} + +// prop = 'key' 2.5ms optimized for this case, seems to be about as fast as direct obj[prop] +// prop = 'key1.key2' 10ms +// prop = ['key1', 'key2'] 27ms +function getValue(obj, prop) { + var tmp = obj[prop]; if(tmp !== undefined) {return tmp;} + var segs = prop; + if(!Array.isArray(prop)) {segs = prop.split('.');} + var len = segs.length; + var i = -1; + while (obj && (++i < len)) {obj = obj[segs[i]];} + return obj; +} + +function isObj(x) { return typeof x === 'object'; } // faster as a function + +// Hacked version of https://github.com/lemire/FastPriorityQueue.js +var fastpriorityqueue=function(){var r=[],o=0,e={};function n(){for(var e=0,n=r[e],c=1;c<o;){var f=c+1;e=c,f<o&&r[f].score<r[c].score&&(e=f),r[e-1>>1]=r[e],c=1+(e<<1);}for(var a=e-1>>1;e>0&&n.score<r[a].score;a=(e=a)-1>>1){r[e]=r[a];}r[e]=n;}return e.add=function(e){var n=o;r[o++]=e;for(var c=n-1>>1;n>0&&e.score<r[c].score;c=(n=c)-1>>1){r[n]=r[c];}r[n]=e;},e.poll=function(){if(0!==o){var e=r[0];return r[0]=r[--o],n(),e;}},e.peek=function(e){if(0!==o){return r[0];}},e.replaceTop=function(o){r[0]=o,n();},e;}; +var q = fastpriorityqueue(); // reuse this, except for async, it needs to make its own + +return fuzzysortNew(); +}); // UMD + +// TODO: (performance) wasm version!? +// TODO: (performance) threads? +// TODO: (performance) avoid cache misses +// TODO: (performance) preparedCache is a memory leak +// TODO: (like sublime) backslash === forwardslash +// TODO: (like sublime) spaces: "a b" should do 2 searches 1 for a and 1 for b +// TODO: (scoring) garbage in targets that allows most searches to strict match need a penality +// TODO: (performance) idk if allowTypo is optimized |