diff options
author | Rebecca Turner <me@re-becca.org> | 2016-05-06 15:22:02 -0700 |
---|---|---|
committer | Jeremiah Senkpiel <fishrock123@rocketmail.com> | 2016-05-10 14:45:28 -0400 |
commit | 5c36cfc8438d28ee5050ee6d5c383cf9c5b895fb (patch) | |
tree | 6165b1b2ee92982a1e157ac29c924b516771780d /deps/npm/node_modules/readable-stream/node_modules/unreachable-branch-transform/node_modules/recast/node_modules/source-map/lib/quick-sort.js | |
parent | 101dd1ed789175311ab22f9a32dfc480f127bc68 (diff) | |
download | android-node-v8-5c36cfc8438d28ee5050ee6d5c383cf9c5b895fb.tar.gz android-node-v8-5c36cfc8438d28ee5050ee6d5c383cf9c5b895fb.tar.bz2 android-node-v8-5c36cfc8438d28ee5050ee6d5c383cf9c5b895fb.zip |
deps: upgrade npm to 3.8.9
Contains the following three npm releases:
https://github.com/npm/npm/releases/tag/v3.8.7
https://github.com/npm/npm/releases/tag/v3.8.8
https://github.com/npm/npm/releases/tag/v3.8.9
PR-URL: https://github.com/nodejs/node/pull/6664
Reviewed-By: Myles Borins <myles.borins@gmail.com>
Reviewed-By: Jeremiah Senkpiel <fishrock123@rocketmail.com>
Diffstat (limited to 'deps/npm/node_modules/readable-stream/node_modules/unreachable-branch-transform/node_modules/recast/node_modules/source-map/lib/quick-sort.js')
-rw-r--r-- | deps/npm/node_modules/readable-stream/node_modules/unreachable-branch-transform/node_modules/recast/node_modules/source-map/lib/quick-sort.js | 115 |
1 files changed, 115 insertions, 0 deletions
diff --git a/deps/npm/node_modules/readable-stream/node_modules/unreachable-branch-transform/node_modules/recast/node_modules/source-map/lib/quick-sort.js b/deps/npm/node_modules/readable-stream/node_modules/unreachable-branch-transform/node_modules/recast/node_modules/source-map/lib/quick-sort.js new file mode 100644 index 0000000000..f92823cea5 --- /dev/null +++ b/deps/npm/node_modules/readable-stream/node_modules/unreachable-branch-transform/node_modules/recast/node_modules/source-map/lib/quick-sort.js @@ -0,0 +1,115 @@ +/* -*- 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`. + + /** + * 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) <= 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); + } + } + + /** + * 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. + */ + exports.quickSort = function (ary, comparator) { + doQuickSort(ary, comparator, 0, ary.length - 1); + }; +} |