/*
The original code comes from:
  https://github.com/farzher/fuzzysort/

This exact copy has been modified to work with Microsoft's JScript.
*/

/*
WHAT: SublimeText-like Fuzzy Search

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


// 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 ActiveXObject("Scripting.Dictionary");
var preparedSearchCache = new ActiveXObject("Scripting.Dictionary");
var noResults = []; noResults.total = 0
var matchesSimple = []; var 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 (!prop) return null
  if(!(prop instanceof Array)) 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

var 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
  },

  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.Item(target)
    if(targetPrepared !== undefined) return targetPrepared
    targetPrepared = fuzzysort.prepare(target)
    preparedCache.Item(target) = targetPrepared
    return targetPrepared
  },
  getPreparedSearch: function(search) {
    if(search.length > 999) return fuzzysort.prepareSearch(search) // don't cache huge searches
    var searchPrepared = preparedSearchCache.Item(search)
    if(searchPrepared !== undefined) return searchPrepared
    searchPrepared = fuzzysort.prepareSearch(search)
    preparedSearchCache.Item(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
  }
}

