Fast SublimeText-like fuzzy search for JavaScript.

/*
WHAT: SublimeText-like Fuzzy Search

https://github.com/farzher/fuzzysort

USAGE:
  fuzzysort.single('fs', 'Fuzzy Search') // {score: -16}
  fuzzysort.single('test', 'test') // {score: 0}
  fuzzysort.single('doesnt exist', 'target') // null

  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) 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]);
                // var threshold = options && options.threshold || instanceOptions && instanceOptions.threshold || -9007199254740991
                // var result = algorithm(search, target, search[0])
                // if(result === null) return null
                // if(result.score < threshold) return null
                // return result
            },

            go: function(search, targets, options) {
                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) 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) {
                                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);
                                }

                                if (iCurrent % 1000 /*itemsPerCheck*/ === 0) {
                                    if (
                                        Date.now() - startMs >=
                                        10 /*asyncInterval*/
                                    ) {
                                        isNode
                                            ? setImmediate(step)
                                            : setTimeout(step);
                                        return;
                                    }
                                }
                            }

                            // options.key
                        } else if (options && options.key) {
                            var key = options.key;
                            for (; iCurrent >= 0; --iCurrent) {
                                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);
                                }

                                if (iCurrent % 1000 /*itemsPerCheck*/ === 0) {
                                    if (
                                        Date.now() - startMs >=
                                        10 /*asyncInterval*/
                                    ) {
                                        isNode
                                            ? setImmediate(step)
                                            : setTimeout(step);
                                        return;
                                    }
                                }
                            }

                            // no keys
                        } else {
                            for (; iCurrent >= 0; --iCurrent) {
                                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 (iCurrent % 1000 /*itemsPerCheck*/ === 0) {
                                    if (
                                        Date.now() - startMs >=
                                        10 /*asyncInterval*/
                                    ) {
                                        isNode
                                            ? setImmediate(step)
                                            : setTimeout(step);
                                        return;
                                    }
                                }
                            }
                        }

                        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();
                });
                p.cancel = function() {
                    canceled = true;
                };
                return p;
            },

            highlight: function(result, hOpen, hClose) {
                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;
            },

            prepare: function(target) {
                if (!target) return;
                return {
                    target: target,
                    _targetLowerCodes: fuzzysort.prepareLowerCodes(target),
                    _nextBeginningIndexes: null,
                    score: null,
                    indexes: null,
                    obj: null
                }; // hidden
            },
            prepareSlow: function(target) {
                if (!target) return;
                return {
                    target: target,
                    _targetLowerCodes: fuzzysort.prepareLowerCodes(target),
                    _nextBeginningIndexes: fuzzysort.prepareNextBeginningIndexes(
                        target
                    ),
                    score: null,
                    indexes: null,
                    obj: null
                }; // hidden
            },
            prepareSearch: function(search) {
                if (!search) return;
                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 MAX_INT = Number.MAX_SAFE_INTEGER
    // var MIN_INT = Number.MIN_VALUE
    var preparedCache = new Map();
    var preparedSearchCache = new Map();
    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) layout memory in an optimal way to go fast by avoiding cache misses
// TODO: (performance) preparedCache is a memory leak
// TODO: (like sublime) backslash === forwardslash
// TODO: (performance) i have no idea how well optizmied the allowing typos algorithm is