aboutsummaryrefslogtreecommitdiffstats
path: root/vanilla/node_modules/source-map-js/lib/quick-sort.js
diff options
context:
space:
mode:
authorAdam Mathes <adam@adammathes.com>2026-02-14 14:46:37 -0800
committerAdam Mathes <adam@adammathes.com>2026-02-14 14:46:37 -0800
commitafa87af01c79a9baa539f2992d32154d2a4739bd (patch)
tree92c7416db734270a2fee1d72ee9cc119379ff8e1 /vanilla/node_modules/source-map-js/lib/quick-sort.js
parent3b927e84d200402281f68181cd4253bc77e5528d (diff)
downloadneko-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.js132
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);
-};