diff options
| author | Adam Mathes <adam@adammathes.com> | 2026-02-14 14:46:37 -0800 |
|---|---|---|
| committer | Adam Mathes <adam@adammathes.com> | 2026-02-14 14:46:37 -0800 |
| commit | afa87af01c79a9baa539f2992d32154d2a4739bd (patch) | |
| tree | 92c7416db734270a2fee1d72ee9cc119379ff8e1 /vanilla/node_modules/source-map-js/lib/quick-sort.js | |
| parent | 3b927e84d200402281f68181cd4253bc77e5528d (diff) | |
| download | neko-afa87af01c79a9baa539f2992d32154d2a4739bd.tar.gz neko-afa87af01c79a9baa539f2992d32154d2a4739bd.tar.bz2 neko-afa87af01c79a9baa539f2992d32154d2a4739bd.zip | |
task: delete vanilla js prototype\n\n- Removed vanilla/ directory and web/dist/vanilla directory\n- Updated Makefile, Dockerfile, and CI workflow to remove vanilla references\n- Cleaned up web/web.go to remove vanilla embed and routes\n- Verified build and tests pass\n\nCloses NK-2tcnmq
Diffstat (limited to 'vanilla/node_modules/source-map-js/lib/quick-sort.js')
| -rw-r--r-- | vanilla/node_modules/source-map-js/lib/quick-sort.js | 132 |
1 files changed, 0 insertions, 132 deletions
diff --git a/vanilla/node_modules/source-map-js/lib/quick-sort.js b/vanilla/node_modules/source-map-js/lib/quick-sort.js deleted file mode 100644 index 23f9eda..0000000 --- a/vanilla/node_modules/source-map-js/lib/quick-sort.js +++ /dev/null @@ -1,132 +0,0 @@ -/* -*- 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 - */ - -// It turns out that some (most?) JavaScript engines don't self-host -// `Array.prototype.sort`. This makes sense because C++ will likely remain -// faster than JS when doing raw CPU-intensive sorting. However, when using a -// custom comparator function, calling back and forth between the VM's C++ and -// JIT'd JS is rather slow *and* loses JIT type information, resulting in -// worse generated code for the comparator function than would be optimal. In -// fact, when sorting with a comparator, these costs outweigh the benefits of -// sorting in C++. By using our own JS-implemented Quick Sort (below), we get -// a ~3500ms mean speed-up in `bench/bench.html`. - -function SortTemplate(comparator) { - -/** - * Swap the elements indexed by `x` and `y` in the array `ary`. - * - * @param {Array} ary - * The array. - * @param {Number} x - * The index of the first item. - * @param {Number} y - * The index of the second item. - */ -function swap(ary, x, y) { - var temp = ary[x]; - ary[x] = ary[y]; - ary[y] = temp; -} - -/** - * Returns a random integer within the range `low .. high` inclusive. - * - * @param {Number} low - * The lower bound on the range. - * @param {Number} high - * The upper bound on the range. - */ -function randomIntInRange(low, high) { - return Math.round(low + (Math.random() * (high - low))); -} - -/** - * The Quick Sort algorithm. - * - * @param {Array} ary - * An array to sort. - * @param {function} comparator - * Function to use to compare two items. - * @param {Number} p - * Start index of the array - * @param {Number} r - * End index of the array - */ -function doQuickSort(ary, comparator, p, r) { - // If our lower bound is less than our upper bound, we (1) partition the - // array into two pieces and (2) recurse on each half. If it is not, this is - // the empty array and our base case. - - if (p < r) { - // (1) Partitioning. - // - // The partitioning chooses a pivot between `p` and `r` and moves all - // elements that are less than or equal to the pivot to the before it, and - // all the elements that are greater than it after it. The effect is that - // once partition is done, the pivot is in the exact place it will be when - // the array is put in sorted order, and it will not need to be moved - // again. This runs in O(n) time. - - // Always choose a random pivot so that an input array which is reverse - // sorted does not cause O(n^2) running time. - var pivotIndex = randomIntInRange(p, r); - var i = p - 1; - - swap(ary, pivotIndex, r); - var pivot = ary[r]; - - // Immediately after `j` is incremented in this loop, the following hold - // true: - // - // * Every element in `ary[p .. i]` is less than or equal to the pivot. - // - // * Every element in `ary[i+1 .. j-1]` is greater than the pivot. - for (var j = p; j < r; j++) { - if (comparator(ary[j], pivot, false) <= 0) { - i += 1; - swap(ary, i, j); - } - } - - swap(ary, i + 1, j); - var q = i + 1; - - // (2) Recurse on each half. - - doQuickSort(ary, comparator, p, q - 1); - doQuickSort(ary, comparator, q + 1, r); - } -} - - return doQuickSort; -} - -function cloneSort(comparator) { - let template = SortTemplate.toString(); - let templateFn = new Function(`return ${template}`)(); - return templateFn(comparator); -} - -/** - * Sort the given array in-place with the given comparator function. - * - * @param {Array} ary - * An array to sort. - * @param {function} comparator - * Function to use to compare two items. - */ - -let sortCache = new WeakMap(); -exports.quickSort = function (ary, comparator, start = 0) { - let doQuickSort = sortCache.get(comparator); - if (doQuickSort === void 0) { - doQuickSort = cloneSort(comparator); - sortCache.set(comparator, doQuickSort); - } - doQuickSort(ary, comparator, start, ary.length - 1); -}; |
