mirror of
https://repo.dactyloidae.xyz/Dactyloidae/UXP.git
synced 2026-08-15 08:53:07 +09:00
276 lines
23 KiB
JavaScript
276 lines
23 KiB
JavaScript
|
function run_test() {
|
||
|
|
for (var k in SOURCE_MAP_TEST_MODULE) {
|
||
|
|
if (/^test/.test(k)) {
|
||
|
|
SOURCE_MAP_TEST_MODULE[k](assert);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
var SOURCE_MAP_TEST_MODULE =
|
||
|
|
/******/ (function(modules) { // webpackBootstrap
|
||
|
|
/******/ // The module cache
|
||
|
|
/******/ var installedModules = {};
|
||
|
|
/******/
|
||
|
|
/******/ // The require function
|
||
|
|
/******/ function __webpack_require__(moduleId) {
|
||
|
|
/******/
|
||
|
|
/******/ // Check if module is in cache
|
||
|
|
/******/ if(installedModules[moduleId])
|
||
|
|
/******/ return installedModules[moduleId].exports;
|
||
|
|
/******/
|
||
|
|
/******/ // Create a new module (and put it into the cache)
|
||
|
|
/******/ var module = installedModules[moduleId] = {
|
||
|
|
/******/ exports: {},
|
||
|
|
/******/ id: moduleId,
|
||
|
|
/******/ loaded: false
|
||
|
|
/******/ };
|
||
|
|
/******/
|
||
|
|
/******/ // Execute the module function
|
||
|
|
/******/ modules[moduleId].call(module.exports, module, module.exports, __webpack_require__);
|
||
|
|
/******/
|
||
|
|
/******/ // Flag the module as loaded
|
||
|
|
/******/ module.loaded = true;
|
||
|
|
/******/
|
||
|
|
/******/ // Return the exports of the module
|
||
|
|
/******/ return module.exports;
|
||
|
|
/******/ }
|
||
|
|
/******/
|
||
|
|
/******/
|
||
|
|
/******/ // expose the modules object (__webpack_modules__)
|
||
|
|
/******/ __webpack_require__.m = modules;
|
||
|
|
/******/
|
||
|
|
/******/ // expose the module cache
|
||
|
|
/******/ __webpack_require__.c = installedModules;
|
||
|
|
/******/
|
||
|
|
/******/ // __webpack_public_path__
|
||
|
|
/******/ __webpack_require__.p = "";
|
||
|
|
/******/
|
||
|
|
/******/ // Load entry module and return exports
|
||
|
|
/******/ return __webpack_require__(0);
|
||
|
|
/******/ })
|
||
|
|
/************************************************************************/
|
||
|
|
/******/ ([
|
||
|
|
/* 0 */
|
||
|
|
/***/ function(module, exports, __webpack_require__) {
|
||
|
|
|
||
|
|
/* -*- Mode: js; js-indent-level: 2; -*- */
|
||
|
|
/*
|
||
|
|
* Copyright 2011 Mozilla Foundation and contributors
|
||
|
|
* Licensed under the New BSD license. See LICENSE or:
|
||
|
|
* http://opensource.org/licenses/BSD-3-Clause
|
||
|
|
*/
|
||
|
|
{
|
||
|
|
var binarySearch = __webpack_require__(1);
|
||
|
|
|
||
|
|
function numberCompare(a, b) {
|
||
|
|
return a - b;
|
||
|
|
}
|
||
|
|
|
||
|
|
exports['test too high with default (glb) bias'] = function (assert) {
|
||
|
|
var needle = 30;
|
||
|
|
var haystack = [2,4,6,8,10,12,14,16,18,20];
|
||
|
|
|
||
|
|
assert.doesNotThrow(function () {
|
||
|
|
binarySearch.search(needle, haystack, numberCompare);
|
||
|
|
});
|
||
|
|
|
||
|
|
assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare)], 20);
|
||
|
|
};
|
||
|
|
|
||
|
|
exports['test too low with default (glb) bias'] = function (assert) {
|
||
|
|
var needle = 1;
|
||
|
|
var haystack = [2,4,6,8,10,12,14,16,18,20];
|
||
|
|
|
||
|
|
assert.doesNotThrow(function () {
|
||
|
|
binarySearch.search(needle, haystack, numberCompare);
|
||
|
|
});
|
||
|
|
|
||
|
|
assert.equal(binarySearch.search(needle, haystack, numberCompare), -1);
|
||
|
|
};
|
||
|
|
|
||
|
|
exports['test too high with lub bias'] = function (assert) {
|
||
|
|
var needle = 30;
|
||
|
|
var haystack = [2,4,6,8,10,12,14,16,18,20];
|
||
|
|
|
||
|
|
assert.doesNotThrow(function () {
|
||
|
|
binarySearch.search(needle, haystack, numberCompare);
|
||
|
|
});
|
||
|
|
|
||
|
|
assert.equal(binarySearch.search(needle, haystack, numberCompare,
|
||
|
|
binarySearch.LEAST_UPPER_BOUND), -1);
|
||
|
|
};
|
||
|
|
|
||
|
|
exports['test too low with lub bias'] = function (assert) {
|
||
|
|
var needle = 1;
|
||
|
|
var haystack = [2,4,6,8,10,12,14,16,18,20];
|
||
|
|
|
||
|
|
assert.doesNotThrow(function () {
|
||
|
|
binarySearch.search(needle, haystack, numberCompare);
|
||
|
|
});
|
||
|
|
|
||
|
|
assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare,
|
||
|
|
binarySearch.LEAST_UPPER_BOUND)], 2);
|
||
|
|
};
|
||
|
|
|
||
|
|
exports['test exact search'] = function (assert) {
|
||
|
|
var needle = 4;
|
||
|
|
var haystack = [2,4,6,8,10,12,14,16,18,20];
|
||
|
|
|
||
|
|
assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare)], 4);
|
||
|
|
};
|
||
|
|
|
||
|
|
exports['test fuzzy search with default (glb) bias'] = function (assert) {
|
||
|
|
var needle = 19;
|
||
|
|
var haystack = [2,4,6,8,10,12,14,16,18,20];
|
||
|
|
|
||
|
|
assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare)], 18);
|
||
|
|
};
|
||
|
|
|
||
|
|
exports['test fuzzy search with lub bias'] = function (assert) {
|
||
|
|
var needle = 19;
|
||
|
|
var haystack = [2,4,6,8,10,12,14,16,18,20];
|
||
|
|
|
||
|
|
assert.equal(haystack[binarySearch.search(needle, haystack, numberCompare,
|
||
|
|
binarySearch.LEAST_UPPER_BOUND)], 20);
|
||
|
|
};
|
||
|
|
|
||
|
|
exports['test multiple matches'] = function (assert) {
|
||
|
|
var needle = 5;
|
||
|
|
var haystack = [1, 1, 2, 5, 5, 5, 13, 21];
|
||
|
|
|
||
|
|
assert.equal(binarySearch.search(needle, haystack, numberCompare,
|
||
|
|
binarySearch.LEAST_UPPER_BOUND), 3);
|
||
|
|
};
|
||
|
|
|
||
|
|
exports['test multiple matches at the beginning'] = function (assert) {
|
||
|
|
var needle = 1;
|
||
|
|
var haystack = [1, 1, 2, 5, 5, 5, 13, 21];
|
||
|
|
|
||
|
|
assert.equal(binarySearch.search(needle, haystack, numberCompare,
|
||
|
|
binarySearch.LEAST_UPPER_BOUND), 0);
|
||
|
|
};
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
/***/ },
|
||
|
|
/* 1 */
|
||
|
|
/***/ function(module, exports) {
|
||
|
|
|
||
|
|
/* -*- Mode: js; js-indent-level: 2; -*- */
|
||
|
|
/*
|
||
|
|
* Copyright 2011 Mozilla Foundation and contributors
|
||
|
|
* Licensed under the New BSD license. See LICENSE or:
|
||
|
|
* http://opensource.org/licenses/BSD-3-Clause
|
||
|
|
*/
|
||
|
|
{
|
||
|
|
exports.GREATEST_LOWER_BOUND = 1;
|
||
|
|
exports.LEAST_UPPER_BOUND = 2;
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Recursive implementation of binary search.
|
||
|
|
*
|
||
|
|
* @param aLow Indices here and lower do not contain the needle.
|
||
|
|
* @param aHigh Indices here and higher do not contain the needle.
|
||
|
|
* @param aNeedle The element being searched for.
|
||
|
|
* @param aHaystack The non-empty array being searched.
|
||
|
|
* @param aCompare Function which takes two elements and returns -1, 0, or 1.
|
||
|
|
* @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
|
||
|
|
* 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
|
||
|
|
* closest element that is smaller than or greater than the one we are
|
||
|
|
* searching for, respectively, if the exact element cannot be found.
|
||
|
|
*/
|
||
|
|
function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias) {
|
||
|
|
// This function terminates when one of the following is true:
|
||
|
|
//
|
||
|
|
// 1. We find the exact element we are looking for.
|
||
|
|
//
|
||
|
|
// 2. We did not find the exact element, but we can return the index of
|
||
|
|
// the next-closest element.
|
||
|
|
//
|
||
|
|
// 3. We did not find the exact element, and there is no next-closest
|
||
|
|
// element than the one we are searching for, so we return -1.
|
||
|
|
var mid = Math.floor((aHigh - aLow) / 2) + aLow;
|
||
|
|
var cmp = aCompare(aNeedle, aHaystack[mid], true);
|
||
|
|
if (cmp === 0) {
|
||
|
|
// Found the element we are looking for.
|
||
|
|
return mid;
|
||
|
|
}
|
||
|
|
else if (cmp > 0) {
|
||
|
|
// Our needle is greater than aHaystack[mid].
|
||
|
|
if (aHigh - mid > 1) {
|
||
|
|
// The element is in the upper half.
|
||
|
|
return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias);
|
||
|
|
}
|
||
|
|
|
||
|
|
// The exact needle element was not found in this haystack. Determine if
|
||
|
|
// we are in termination case (3) or (2) and return the appropriate thing.
|
||
|
|
if (aBias == exports.LEAST_UPPER_BOUND) {
|
||
|
|
return aHigh < aHaystack.length ? aHigh : -1;
|
||
|
|
} else {
|
||
|
|
return mid;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
// Our needle is less than aHaystack[mid].
|
||
|
|
if (mid - aLow > 1) {
|
||
|
|
// The element is in the lower half.
|
||
|
|
return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias);
|
||
|
|
}
|
||
|
|
|
||
|
|
// we are in termination case (3) or (2) and return the appropriate thing.
|
||
|
|
if (aBias == exports.LEAST_UPPER_BOUND) {
|
||
|
|
return mid;
|
||
|
|
} else {
|
||
|
|
return aLow < 0 ? -1 : aLow;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* This is an implementation of binary search which will always try and return
|
||
|
|
* the index of the closest element if there is no exact hit. This is because
|
||
|
|
* mappings between original and generated line/col pairs are single points,
|
||
|
|
* and there is an implicit region between each of them, so a miss just means
|
||
|
|
* that you aren't on the very start of a region.
|
||
|
|
*
|
||
|
|
* @param aNeedle The element you are looking for.
|
||
|
|
* @param aHaystack The array that is being searched.
|
||
|
|
* @param aCompare A function which takes the needle and an element in the
|
||
|
|
* array and returns -1, 0, or 1 depending on whether the needle is less
|
||
|
|
* than, equal to, or greater than the element, respectively.
|
||
|
|
* @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or
|
||
|
|
* 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the
|
||
|
|
* closest element that is smaller than or greater than the one we are
|
||
|
|
* searching for, respectively, if the exact element cannot be found.
|
||
|
|
* Defaults to 'binarySearch.GREATEST_LOWER_BOUND'.
|
||
|
|
*/
|
||
|
|
exports.search = function search(aNeedle, aHaystack, aCompare, aBias) {
|
||
|
|
if (aHaystack.length === 0) {
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
|
||
|
|
var index = recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack,
|
||
|
|
aCompare, aBias || exports.GREATEST_LOWER_BOUND);
|
||
|
|
if (index < 0) {
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
|
||
|
|
// We have found either the exact element, or the next-closest element than
|
||
|
|
// the one we are searching for. However, there may be more than one such
|
||
|
|
// element. Make sure we always return the smallest of these.
|
||
|
|
while (index - 1 >= 0) {
|
||
|
|
if (aCompare(aHaystack[index], aHaystack[index - 1], true) !== 0) {
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
--index;
|
||
|
|
}
|
||
|
|
|
||
|
|
return index;
|
||
|
|
};
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
/***/ }
|
||
|
|
/******/ ]);
|
||
|
|
//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJzb3VyY2VzIjpbIndlYnBhY2s6Ly8vd2VicGFjay9ib290c3RyYXAgYmI3MjVjOTVmZTk3YzY1OTQ3OGMiLCJ3ZWJwYWNrOi8vLy4vdGVzdC90ZXN0LWJpbmFyeS1zZWFyY2guanMiLCJ3ZWJwYWNrOi8vLy4vbGliL2JpbmFyeS1zZWFyY2guanMiXSwibmFtZXMiOltdLCJtYXBwaW5ncyI6Ijs7Ozs7Ozs7Ozs7QUFBQTtBQUNBOztBQUVBO0FBQ0E7O0FBRUE7QUFDQTtBQUNBOztBQUVBO0FBQ0E7QUFDQSx1QkFBZTtBQUNmO0FBQ0E7QUFDQTs7QUFFQTtBQUNBOztBQUVBO0FBQ0E7O0FBRUE7QUFDQTtBQUNBOzs7QUFHQTtBQUNBOztBQUVBO0FBQ0E7O0FBRUE7QUFDQTs7QUFFQTtBQUNBOzs7Ozs7O0FDdENBLGlCQUFnQixvQkFBb0I7QUFDcEM7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7O0FBRUE7QUFDQTtBQUNBOztBQUVBO0FBQ0E7QUFDQTs7QUFFQTtBQUNBO0FBQ0EsTUFBSzs7QUFFTDtBQUNBOztBQUVBO0FBQ0E7QUFDQTs7QUFFQTtBQUNBO0FBQ0EsTUFBSzs7QUFFTDtBQUNBOztBQUVBO0FBQ0E7QUFDQTs7QUFFQTtBQUNBO0FBQ0EsTUFBSzs7QUFFTDtBQUNBO0FBQ0E7O0FBRUE7QUFDQTtBQUNBOztBQUVBO0FBQ0E7QUFDQSxNQUFLOztBQUVMO0FBQ0E7QUFDQTs7QUFFQTtBQUNBO0FBQ0E7O0FBRUE7QUFDQTs7QUFFQTtBQUNBO0FBQ0E7O0FBRUE7QUFDQTs7QUFFQTtBQUNBO0FBQ0E7O0FBRUE7QUFDQTtBQUNBOztBQUVBO0FBQ0E7QUFDQTs7QUFFQTtBQUNBO0FBQ0E7O0FBRUE7QUFDQTtBQUNBOztBQUVBO0FBQ0E7QUFDQTtBQUNBOzs7Ozs7O0FDaEdBLGlCQUFnQixvQkFBb0I7QUFDcEM7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTs7QUFFQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBOztBQUVBO0FBQ0E7QUFDQTtBQUNBO0FBQ0EsUUFBTztBQUNQO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTs7QUFFQTtBQUNBO0FBQ0E7QUFDQSxRQUFPO0FBQ1A7QUFDQTtBQUNBO0FBQ0E7O0FBRUE7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7O0FBRUE7QUFDQTtBQUNBO0FBQ0E7QUFDQTs7QUFFQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7QUFDQTtBQUNBO0FBQ0E7O0FBRUE7QUFDQTtBQUNBIiwiZmlsZSI6InRlc3RfYmluYXJ5X3NlYXJjaC5qcyIsInNvdXJjZXNDb250ZW50IjpbIiBcdC8vIFRoZSBtb2R1bGUgY2FjaGVcbiBcdHZhciBpbnN0YWxsZWRNb2R1bGVzID0ge307XG5cbiBcdC8vIFRoZSByZXF1aXJlIGZ1bmN0aW9uXG4gXHRmdW5jdGlvbiBfX3dlYnBhY2tfcmVxdWlyZV9fKG1vZHVsZUlkKSB7XG5cbiBcdFx0Ly8gQ2hlY2sgaWYgbW9kdWxlIGlzIGluIGNhY2hlXG4gXHRcdGlmKGluc3RhbGxlZE1vZHVsZXNbbW9kdWxlSWRdKVxuIFx0XHRcdHJldHVybiBpbnN0YWxsZWRNb2R1bGVzW21vZHVsZUlkXS5leHBvcnRzO1xuXG4gXHRcdC8vIENyZWF0ZSBhIG5ldyBtb2R1bGUgKGFuZCBwdXQgaXQgaW50byB0aGUgY2FjaGUpXG4gXHRcdHZhciBtb2R1bGUgPSBpbnN0YWxsZWRNb2R1bGVzW21vZHVsZUlkXSA9IHtcbiBcdFx0XHRleHBvcnRzOiB7fSxcbiBcdFx0XHRpZDogbW9kdWxlSWQsXG4gXHRcdFx0bG9hZGVkOiBmYWxzZVxuIFx0XHR9O1xuXG4gXHRcdC8vIEV4ZWN1dGUgdGhlIG1vZHVsZSBmdW5jdGlvblxuIFx0XHRtb2R1bGVzW21vZHVsZUlkXS5jYWxsKG1vZHVsZS5leHBvcnRzLCBtb2R1bGUsIG1vZHVsZS5leHBvcnRzLCBfX3dlYnBhY2tfcmVxdWlyZV9fKTtcblxuIFx0XHQvLyBGbGFnIHRoZSBtb2R1bGUgYXMgbG9hZGVkXG4gXHRcdG1vZHVsZS5sb2FkZWQgPSB0cnVlO1xuXG4gXHRcdC8vIFJldHVybiB0aGUgZXhwb3J0cyBvZiB0aGUgbW9kdWxlXG4gXHRcdHJldHVybiBtb2R1bGUuZXhwb3J0cztcbiBcdH1cblxuXG4gXHQvLyBleHBvc2UgdGhlIG1vZHVsZXMgb2JqZWN0IChfX3dlYnBhY2tfbW9kdWxlc19fKVxuIFx0X193ZWJwYWNrX3JlcXVpcmVfXy5tID0gbW9kdWxlcztcblxuIFx0Ly8gZXhwb3NlIHRoZSBtb2R1bGUgY2FjaGVcbiBcdF9fd2VicGFja19yZXF1aXJlX18uYyA9IGluc3RhbGxlZE1vZHVsZXM7XG5cbiBcdC8vIF9fd2VicGFja19wdWJsaWNfcGF0aF9fXG4gXHRfX3dlYnBhY2tfcmVxdWlyZV9fLnAgPSBcIlwiO1xuXG4gXHQvLyBMb2FkIGVudHJ5IG1vZHVsZSBhbmQgcmV0dXJuIGV4cG9ydHNcbiBcdHJldHVybiBfX3dlYnBhY2tfcmVxdWlyZV9fKDApO1xuXG5cblxuLyoqIFdFQlBBQ0sgRk9PVEVSICoqXG4gKiogd2VicGFjay9ib290c3RyYXAgYmI3MjVjOTVmZTk3YzY1OTQ3OGNcbiAqKi8iLCIvKiAtKi0gTW9kZToganM7IGpzLWluZGVudC1sZXZlbDogMjsgLSotICovXG4vKlxuICogQ29weXJpZ2h0IDIwMTEgTW96aWxsYSBGb3VuZGF0aW9uIGFuZCBjb250cmlidXRvcnNcbiAqIExpY2Vuc2VkIHVuZGVyIHRoZSBOZXcgQlNEIGxpY2Vuc2UuIFNlZSBMSUNFTlNFIG9yOlxuICogaHR0cDovL29wZW5zb3VyY2Uub3JnL2xpY2Vuc2VzL0JTRC0zLUNsYXVzZVxuICovXG57XG4gIHZhciBiaW5hcnlTZWFyY2ggPSByZXF1aXJlKCcuLi9saWIvYmluYXJ5LXNlYXJjaCcpO1xuXG4gIGZ1bmN0aW9uIG51bWJlckNvbXBhcmUoYSwgYikge1xuICAgIHJldHVybiBhIC0gYjtcbiAgfVxuXG4gIGV4cG9ydHNbJ3Rlc3QgdG9vIGhpZ2ggd2l0aCBkZWZhdWx0IChnbGIpIGJpYXMnXSA9IGZ1bmN0aW9uIChhc3NlcnQpIHtcbiAgICB2YXIgbmVlZGxlID0gMzA7XG4gICAgdmFyIGhheXN0YWNrID0gWzIsNCw2LDgsMTAsMTIsMTQsMTYsMTgsMjBdO1xuXG4gICAgYXNzZXJ0LmRvZXNOb3RUaHJvdyhmdW5jdGlvbiAoKSB7XG4gI
|