path: root/utils/scripts/fuzzysort.js

.pragma library

/*
https://github.com/farzher/fuzzysort

MIT License

Copyright (c) 2018 Stephen Kamenar

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/

var single =  (search, target) => {
    if(!search || !target) return NULL

    var preparedSearch = getPreparedSearch(search)
    if(!isPrepared(target)) target = getPrepared(target)

    var searchBitflags = preparedSearch.bitflags
    if((searchBitflags & target._bitflags) !== searchBitflags) return NULL

    return algorithm(preparedSearch, target)
}

var go = (search, targets, options) => {
    if(!search) return options?.all ? all(targets, options) : noResults

    var preparedSearch = getPreparedSearch(search)
    var searchBitflags = preparedSearch.bitflags
    var containsSpace  = preparedSearch.containsSpace

    var threshold = denormalizeScore( options?.threshold || 0 )
    var limit     = options?.limit || INFINITY

    var resultsLen = 0; var limitedCount = 0
    var targetsLen = targets.length

    function push_result(result) {
    if(resultsLen < limit) { q.add(result); ++resultsLen }
    else {
        ++limitedCount
        if(result._score > q.peek()._score) q.replaceTop(result)
    }
    }

    // This code is copy/pasted 3 times for performance reasons [options.key, options.keys, no keys]

    // options.key
    if(options?.key) {
    var key = options.key
    for(var i = 0; i < targetsLen; ++i) { var obj = targets[i]
        var target = getValue(obj, key)
        if(!target) continue
        if(!isPrepared(target)) target = getPrepared(target)

        if((searchBitflags & target._bitflags) !== searchBitflags) continue
        var result = algorithm(preparedSearch, target)
        if(result === NULL) continue
        if(result._score < threshold) continue

        result.obj = obj
        push_result(result)
    }

    // options.keys
    } else if(options?.keys) {
    var keys = options.keys
    var keysLen = keys.length

    outer: for(var i = 0; i < targetsLen; ++i) { var obj = targets[i]

        { // early out based on bitflags
        var keysBitflags = 0
        for (var keyI = 0; keyI < keysLen; ++keyI) {
            var key = keys[keyI]
            var target = getValue(obj, key)
            if(!target) { tmpTargets[keyI] = noTarget; continue }
            if(!isPrepared(target)) target = getPrepared(target)
            tmpTargets[keyI] = target

            keysBitflags |= target._bitflags
        }

        if((searchBitflags & keysBitflags) !== searchBitflags) continue
        }

        if(containsSpace) for(let i=0; i<preparedSearch.spaceSearches.length; i++) keysSpacesBestScores[i] = NEGATIVE_INFINITY

        for (var keyI = 0; keyI < keysLen; ++keyI) {
        target = tmpTargets[keyI]
        if(target === noTarget) { tmpResults[keyI] = noTarget; continue }

        tmpResults[keyI] = algorithm(preparedSearch, target, /*allowSpaces=*/false, /*allowPartialMatch=*/containsSpace)
        if(tmpResults[keyI] === NULL) { tmpResults[keyI] = noTarget; continue }

        // todo: this seems weird and wrong. like what if our first match wasn't good. this should just replace it instead of averaging with it
        // if our second match isn't good we ignore it instead of averaging with it
        if(containsSpace) for(let i=0; i<preparedSearch.spaceSearches.length; i++) {
            if(allowPartialMatchScores[i] > -1000) {
            if(keysSpacesBestScores[i] > NEGATIVE_INFINITY) {
                var tmp = (keysSpacesBestScores[i] + allowPartialMatchScores[i]) / 4/*bonus score for having multiple matches*/
                if(tmp > keysSpacesBestScores[i]) keysSpacesBestScores[i] = tmp
            }
            }
            if(allowPartialMatchScores[i] > keysSpacesBestScores[i]) keysSpacesBestScores[i] = allowPartialMatchScores[i]
        }
        }

        if(containsSpace) {
        for(let i=0; i<preparedSearch.spaceSearches.length; i++) { if(keysSpacesBestScores[i] === NEGATIVE_INFINITY) continue outer }
        } else {
        var hasAtLeast1Match = false
        for(let i=0; i < keysLen; i++) { if(tmpResults[i]._score !== NEGATIVE_INFINITY) { hasAtLeast1Match = true; break } }
        if(!hasAtLeast1Match) continue
        }

        var objResults = new KeysResult(keysLen)
        for(let i=0; i < keysLen; i++) { objResults[i] = tmpResults[i] }

        if(containsSpace) {
        var score = 0
        for(let i=0; i<preparedSearch.spaceSearches.length; i++) score += keysSpacesBestScores[i]
        } else {
        // todo could rewrite this scoring to be more similar to when there's spaces
        // if we match multiple keys give us bonus points
        var score = NEGATIVE_INFINITY
        for(let i=0; i<keysLen; i++) {
            var result = objResults[i]
            if(result._score > -1000) {
            if(score > NEGATIVE_INFINITY) {
                var tmp = (score + result._score) / 4/*bonus score for having multiple matches*/
                if(tmp > score) score = tmp
            }
            }
            if(result._score > score) score = result._score
        }
        }

        objResults.obj = obj
        objResults._score = score
        if(options?.scoreFn) {
        score = options.scoreFn(objResults)
        if(!score) continue
        score = denormalizeScore(score)
        objResults._score = score
        }

        if(score < threshold) continue
        push_result(objResults)
    }

    // no keys
    } else {
    for(var i = 0; i < targetsLen; ++i) { var target = targets[i]
        if(!target) continue
        if(!isPrepared(target)) target = getPrepared(target)

        if((searchBitflags & target._bitflags) !== searchBitflags) continue
        var result = algorithm(preparedSearch, target)
        if(result === NULL) continue
        if(result._score < threshold) continue

        push_result(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
}


// this is written as 1 function instead of 2 for minification. perf seems fine ...
// except when minified. the perf is very slow
var highlight = (result, open='<b>', close='</b>') => {
    var callback = typeof open === 'function' ? open : undefined

    var target      = result.target
    var targetLen   = target.length
    var indexes     = result.indexes
    var highlighted = ''
    var matchI      = 0
    var indexesI    = 0
    var opened      = false
    var parts       = []

    for(var i = 0; i < targetLen; ++i) { var char = target[i]
    if(indexes[indexesI] === i) {
        ++indexesI
        if(!opened) { opened = true
        if(callback) {
            parts.push(highlighted); highlighted = ''
        } else {
            highlighted += open
        }
        }

        if(indexesI === indexes.length) {
        if(callback) {
            highlighted += char
            parts.push(callback(highlighted, matchI++)); highlighted = ''
            parts.push(target.substr(i+1))
        } else {
            highlighted += char + close + target.substr(i+1)
        }
        break
        }
    } else {
        if(opened) { opened = false
        if(callback) {
            parts.push(callback(highlighted, matchI++)); highlighted = ''
        } else {
            highlighted += close
        }
        }
    }
    highlighted += char
    }

    return callback ? parts : highlighted
}


var prepare = (target) => {
    if(typeof target === 'number') target = ''+target
    else if(typeof target !== 'string') target = ''
    var info = prepareLowerInfo(target)
    return new_result(target, {_targetLower:info._lower, _targetLowerCodes:info.lowerCodes, _bitflags:info.bitflags})
}

var cleanup = () => { preparedCache.clear(); preparedSearchCache.clear() }


// 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


class Result {
    get ['indexes']() { return this._indexes.slice(0, this._indexes.len).sort((a,b)=>a-b) }
    set ['indexes'](indexes) { return this._indexes = indexes }
    ['highlight'](open, close) { return highlight(this, open, close) }
    get ['score']() { return normalizeScore(this._score) }
    set ['score'](score) { this._score = denormalizeScore(score) }
}

class KeysResult extends Array {
    get ['score']() { return normalizeScore(this._score) }
    set ['score'](score) { this._score = denormalizeScore(score) }
}

var new_result = (target, options) => {
    const result = new Result()
    result['target']             = target
    result['obj']                = options.obj                   ?? NULL
    result._score                = options._score                ?? NEGATIVE_INFINITY
    result._indexes              = options._indexes              ?? []
    result._targetLower          = options._targetLower          ?? ''
    result._targetLowerCodes     = options._targetLowerCodes     ?? NULL
    result._nextBeginningIndexes = options._nextBeginningIndexes ?? NULL
    result._bitflags             = options._bitflags             ?? 0
    return result
}


var normalizeScore = score => {
    if(score === NEGATIVE_INFINITY) return 0
    if(score > 1) return score
    return Math.E ** ( ((-score + 1)**.04307 - 1) * -2)
}
var denormalizeScore = normalizedScore => {
    if(normalizedScore === 0) return NEGATIVE_INFINITY
    if(normalizedScore > 1) return normalizedScore
    return 1 - Math.pow((Math.log(normalizedScore) / -2 + 1), 1 / 0.04307)
}


var prepareSearch = (search) => {
    if(typeof search === 'number') search = ''+search
    else if(typeof search !== 'string') search = ''
    search = search.trim()
    var info = prepareLowerInfo(search)

    var spaceSearches = []
    if(info.containsSpace) {
    var searches = search.split(/\s+/)
    searches = [...new Set(searches)] // distinct
    for(var i=0; i<searches.length; i++) {
        if(searches[i] === '') continue
        var _info = prepareLowerInfo(searches[i])
        spaceSearches.push({lowerCodes:_info.lowerCodes, _lower:searches[i].toLowerCase(), containsSpace:false})
    }
    }

    return {lowerCodes: info.lowerCodes, _lower: info._lower, containsSpace: info.containsSpace, bitflags: info.bitflags, spaceSearches: spaceSearches}
}



var getPrepared = (target) => {
    if(target.length > 999) return prepare(target) // don't cache huge targets
    var targetPrepared = preparedCache.get(target)
    if(targetPrepared !== undefined) return targetPrepared
    targetPrepared = prepare(target)
    preparedCache.set(target, targetPrepared)
    return targetPrepared
}
var getPreparedSearch = (search) => {
    if(search.length > 999) return prepareSearch(search) // don't cache huge searches
    var searchPrepared = preparedSearchCache.get(search)
    if(searchPrepared !== undefined) return searchPrepared
    searchPrepared = prepareSearch(search)
    preparedSearchCache.set(search, searchPrepared)
    return searchPrepared
}


var all = (targets, options) => {
    var results = []; results.total = targets.length // this total can be wrong if some targets are skipped

    var limit = options?.limit || INFINITY

    if(options?.key) {
    for(var i=0;i<targets.length;i++) { var obj = targets[i]
        var target = getValue(obj, options.key)
        if(target == NULL) continue
        if(!isPrepared(target)) target = getPrepared(target)
        var result = new_result(target.target, {_score: target._score, obj: obj})
        results.push(result); if(results.length >= limit) return results
    }
    } else if(options?.keys) {
    for(var i=0;i<targets.length;i++) { var obj = targets[i]
        var objResults = new KeysResult(options.keys.length)
        for (var keyI = options.keys.length - 1; keyI >= 0; --keyI) {
        var target = getValue(obj, options.keys[keyI])
        if(!target) { objResults[keyI] = noTarget; continue }
        if(!isPrepared(target)) target = getPrepared(target)
        target._score = NEGATIVE_INFINITY
        target._indexes.len = 0
        objResults[keyI] = target
        }
        objResults.obj = obj
        objResults._score = NEGATIVE_INFINITY
        results.push(objResults); if(results.length >= limit) return results
    }
    } else {
    for(var i=0;i<targets.length;i++) { var target = targets[i]
        if(target == NULL) continue
        if(!isPrepared(target)) target = getPrepared(target)
        target._score = NEGATIVE_INFINITY
        target._indexes.len = 0
        results.push(target); if(results.length >= limit) return results
    }
    }

    return results
}


var algorithm = (preparedSearch, prepared, allowSpaces=false, allowPartialMatch=false) => {
    if(allowSpaces===false && preparedSearch.containsSpace) return algorithmSpaces(preparedSearch, prepared, allowPartialMatch)

    var searchLower      = preparedSearch._lower
    var searchLowerCodes = preparedSearch.lowerCodes
    var searchLowerCode  = searchLowerCodes[0]
    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 = prepareNextBeginningIndexes(prepared.target)
    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!
    var backtrackCount = 0
    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

        ++backtrackCount; if(backtrackCount > 200) break // exponential backtracking is taking too long, just give up and return a bad 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]
        }
    }
    }

    // check if it's a substring match
    var substringIndex = searchLen <= 1 ? -1 : prepared._targetLower.indexOf(searchLower, matchesSimple[0]) // perf: this is slow
    var isSubstring = !!~substringIndex
    var isSubstringBeginning = !isSubstring ? false : substringIndex===0 || prepared._nextBeginningIndexes[substringIndex-1] === substringIndex

    // if it's a substring match but not at a beginning index, let's try to find a substring starting at a beginning index for a better score
    if(isSubstring && !isSubstringBeginning) {
    for(var i=0; i<nextBeginningIndexes.length; i=nextBeginningIndexes[i]) {
        if(i <= substringIndex) continue

        for(var s=0; s<searchLen; s++) if(searchLowerCodes[s] !== prepared._targetLowerCodes[i+s]) break
        if(s === searchLen) { substringIndex = i; isSubstringBeginning = true; break }
    }
    }

    // tally up the score & keep track of matches for highlighting later
    // if it's a simple match, we'll switch to a substring match if a substring exists
    // if it's a strict match, we'll switch to a substring match only if that's a better score

    var calculateScore = matches => {
    var score = 0

    var extraMatchGroupCount = 0
    for(var i = 1; i < searchLen; ++i) {
        if(matches[i] - matches[i-1] !== 1) {score -= matches[i]; ++extraMatchGroupCount}
    }
    var unmatchedDistance = matches[searchLen-1] - matches[0] - (searchLen-1)

    score -= (12+unmatchedDistance) * extraMatchGroupCount // penality for more groups

    if(matches[0] !== 0) score -= matches[0]*matches[0]*.2 // penality for not starting near the beginning

    if(!successStrict) {
        score *= 1000
    } else {
        // successStrict on a target with too many beginning indexes loses points for being a bad target
        var uniqueBeginningIndexes = 1
        for(var i = nextBeginningIndexes[0]; i < targetLen; i=nextBeginningIndexes[i]) ++uniqueBeginningIndexes

        if(uniqueBeginningIndexes > 24) score *= (uniqueBeginningIndexes-24)*10 // quite arbitrary numbers here ...
    }

    score -= (targetLen - searchLen)/2 // penality for longer targets

    if(isSubstring)          score /= 1+searchLen*searchLen*1 // bonus for being a full substring
    if(isSubstringBeginning) score /= 1+searchLen*searchLen*1 // bonus for substring starting on a beginningIndex

    score -= (targetLen - searchLen)/2 // penality for longer targets

    return score
    }

    if(!successStrict) {
    if(isSubstring) for(var i=0; i<searchLen; ++i) matchesSimple[i] = substringIndex+i // at this point it's safe to overwrite matchehsSimple with substr matches
    var matchesBest = matchesSimple
    var score = calculateScore(matchesBest)
    } else {
    if(isSubstringBeginning) {
        for(var i=0; i<searchLen; ++i) matchesSimple[i] = substringIndex+i // at this point it's safe to overwrite matchehsSimple with substr matches
        var matchesBest = matchesSimple
        var score = calculateScore(matchesSimple)
    } else {
        var matchesBest = matchesStrict
        var score = calculateScore(matchesStrict)
    }
    }

    prepared._score = score

    for(var i = 0; i < searchLen; ++i) prepared._indexes[i] = matchesBest[i]
    prepared._indexes.len = searchLen

    const result    = new Result()
    result.target   = prepared.target
    result._score   = prepared._score
    result._indexes = prepared._indexes
    return result
}
var algorithmSpaces = (preparedSearch, target, allowPartialMatch) => {
    var seen_indexes = new Set()
    var score = 0
    var result = NULL

    var first_seen_index_last_search = 0
    var searches = preparedSearch.spaceSearches
    var searchesLen = searches.length
    var changeslen = 0

    // Return _nextBeginningIndexes back to its normal state
    var resetNextBeginningIndexes = () => {
    for(let i=changeslen-1; i>=0; i--) target._nextBeginningIndexes[nextBeginningIndexesChanges[i*2 + 0]] = nextBeginningIndexesChanges[i*2 + 1]
    }

    var hasAtLeast1Match = false
    for(var i=0; i<searchesLen; ++i) {
    allowPartialMatchScores[i] = NEGATIVE_INFINITY
    var search = searches[i]

    result = algorithm(search, target)
    if(allowPartialMatch) {
        if(result === NULL) continue
        hasAtLeast1Match = true
    } else {
        if(result === NULL) {resetNextBeginningIndexes(); return NULL}
    }

    // if not the last search, we need to mutate _nextBeginningIndexes for the next search
    var isTheLastSearch = i === searchesLen - 1
    if(!isTheLastSearch) {
        var indexes = result._indexes

        var indexesIsConsecutiveSubstring = true
        for(let i=0; i<indexes.len-1; i++) {
        if(indexes[i+1] - indexes[i] !== 1) {
            indexesIsConsecutiveSubstring = false; break;
        }
        }

        if(indexesIsConsecutiveSubstring) {
        var newBeginningIndex = indexes[indexes.len-1] + 1
        var toReplace = target._nextBeginningIndexes[newBeginningIndex-1]
        for(let i=newBeginningIndex-1; i>=0; i--) {
            if(toReplace !== target._nextBeginningIndexes[i]) break
            target._nextBeginningIndexes[i] = newBeginningIndex
            nextBeginningIndexesChanges[changeslen*2 + 0] = i
            nextBeginningIndexesChanges[changeslen*2 + 1] = toReplace
            changeslen++
        }
        }
    }

    score += result._score / searchesLen
    allowPartialMatchScores[i] = result._score / searchesLen

    // dock points based on order otherwise "c man" returns Manifest.cpp instead of CheatManager.h
    if(result._indexes[0] < first_seen_index_last_search) {
        score -= (first_seen_index_last_search - result._indexes[0]) * 2
    }
    first_seen_index_last_search = result._indexes[0]

    for(var j=0; j<result._indexes.len; ++j) seen_indexes.add(result._indexes[j])
    }

    if(allowPartialMatch && !hasAtLeast1Match) return NULL

    resetNextBeginningIndexes()

    // allows a search with spaces that's an exact substring to score well
    var allowSpacesResult = algorithm(preparedSearch, target, /*allowSpaces=*/true)
    if(allowSpacesResult !== NULL && allowSpacesResult._score > score) {
    if(allowPartialMatch) {
        for(var i=0; i<searchesLen; ++i) {
        allowPartialMatchScores[i] = allowSpacesResult._score / searchesLen
        }
    }
    return allowSpacesResult
    }

    if(allowPartialMatch) result = target
    result._score = score

    var i = 0
    for (let index of seen_indexes) result._indexes[i++] = index
    result._indexes.len = i

    return result
}

// we use this instead of just .normalize('NFD').replace(/[\u0300-\u036f]/g, '') because that screws with japanese characters
var remove_accents = (str) => str.replace(/\p{Script=Latin}+/gu, match => match.normalize('NFD')).replace(/[\u0300-\u036f]/g, '')

var prepareLowerInfo = (str) => {
    str = remove_accents(str)
    var strLen = str.length
    var lower = str.toLowerCase()
    var lowerCodes = [] // new Array(strLen)    sparse array is too slow
    var bitflags = 0
    var containsSpace = false // space isn't stored in bitflags because of how searching with a space works

    for(var i = 0; i < strLen; ++i) {
    var lowerCode = lowerCodes[i] = lower.charCodeAt(i)

    if(lowerCode === 32) {
        containsSpace = true
        continue // it's important that we don't set any bitflags for space
    }

    var bit = lowerCode>=97&&lowerCode<=122 ? lowerCode-97 // alphabet
            : lowerCode>=48&&lowerCode<=57  ? 26           // numbers
                                                            // 3 bits available
            : lowerCode<=127                ? 30           // other ascii
            :                                 31           // other utf8
    bitflags |= 1<<bit
    }

    return {lowerCodes:lowerCodes, bitflags:bitflags, containsSpace:containsSpace, _lower:lower}
}
var prepareBeginningIndexes = (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
}
var prepareNextBeginningIndexes = (target) => {
    target = remove_accents(target)
    var targetLen = target.length
    var beginningIndexes = 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
}

var preparedCache       = new Map()
var preparedSearchCache = new Map()

// the theory behind these being globals is to reduce garbage collection by not making new arrays
var matchesSimple = []; var matchesStrict = []
var nextBeginningIndexesChanges = [] // allows straw berry to match strawberry well, by modifying the end of a substring to be considered a beginning index for the rest of the search
var keysSpacesBestScores = []; var allowPartialMatchScores = []
var tmpTargets = []; var tmpResults = []

// 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
// prop = obj => obj.tags.join() ??ms
var getValue = (obj, prop) => {
    var tmp = obj[prop]; if(tmp !== undefined) return tmp
    if(typeof prop === 'function') return prop(obj) // this should run first. but that makes string props slower
    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
}

var isPrepared = (x) => { return typeof x === 'object' && typeof x._bitflags === 'number' }
var INFINITY = Infinity; var NEGATIVE_INFINITY = -INFINITY
var noResults = []; noResults.total = 0
var NULL = null

var noTarget = prepare('')

// Hacked version of https://github.com/lemire/FastPriorityQueue.js
var fastpriorityqueue=r=>{var e=[],o=0,a={},v=r=>{for(var a=0,v=e[a],c=1;c<o;){var s=c+1;a=c,s<o&&e[s]._score<e[c]._score&&(a=s),e[a-1>>1]=e[a],c=1+(a<<1)}for(var f=a-1>>1;a>0&&v._score<e[f]._score;f=(a=f)-1>>1)e[a]=e[f];e[a]=v};return a.add=(r=>{var a=o;e[o++]=r;for(var v=a-1>>1;a>0&&r._score<e[v]._score;v=(a=v)-1>>1)e[a]=e[v];e[a]=r}),a.poll=(r=>{if(0!==o){var a=e[0];return e[0]=e[--o],v(),a}}),a.peek=(r=>{if(0!==o)return e[0]}),a.replaceTop=(r=>{e[0]=r,v()}),a}
var q = fastpriorityqueue() // reuse this