vnfmarket/src/main/webapp/vnfmarket/node_modules/source-map/lib/source-map/quick-sort.js

   1 /* -*- Mode: js; js-indent-level: 2; -*- */
   2 /*
   3  * Copyright 2011 Mozilla Foundation and contributors
   4  * Licensed under the New BSD license. See LICENSE or:
   5  * http://opensource.org/licenses/BSD-3-Clause
   6  */
   7 if (typeof define !== 'function') {
   8     var define = require('amdefine')(module, require);
   9 }
  10 define(function (require, exports, module) {
  11
  12   // It turns out that some (most?) JavaScript engines don't self-host
  13   // `Array.prototype.sort`. This makes sense because C++ will likely remain
  14   // faster than JS when doing raw CPU-intensive sorting. However, when using a
  15   // custom comparator function, calling back and forth between the VM's C++ and
  16   // JIT'd JS is rather slow *and* loses JIT type information, resulting in
  17   // worse generated code for the comparator function than would be optimal. In
  18   // fact, when sorting with a comparator, these costs outweigh the benefits of
  19   // sorting in C++. By using our own JS-implemented Quick Sort (below), we get
  20   // a ~3500ms mean speed-up in `bench/bench.html`.
  21
  22   /**
  23    * Swap the elements indexed by `x` and `y` in the array `ary`.
  24    *
  25    * @param {Array} ary
  26    *        The array.
  27    * @param {Number} x
  28    *        The index of the first item.
  29    * @param {Number} y
  30    *        The index of the second item.
  31    */
  32   function swap(ary, x, y) {
  33     var temp = ary[x];
  34     ary[x] = ary[y];
  35     ary[y] = temp;
  36   }
  37
  38   /**
  39    * Returns a random integer within the range `low .. high` inclusive.
  40    *
  41    * @param {Number} low
  42    *        The lower bound on the range.
  43    * @param {Number} high
  44    *        The upper bound on the range.
  45    */
  46   function randomIntInRange(low, high) {
  47     return Math.round(low + (Math.random() * (high - low)));
  48   }
  49
  50   /**
  51    * The Quick Sort algorithm.
  52    *
  53    * @param {Array} ary
  54    *        An array to sort.
  55    * @param {function} comparator
  56    *        Function to use to compare two items.
  57    * @param {Number} p
  58    *        Start index of the array
  59    * @param {Number} r
  60    *        End index of the array
  61    */
  62   function doQuickSort(ary, comparator, p, r) {
  63     // If our lower bound is less than our upper bound, we (1) partition the
  64     // array into two pieces and (2) recurse on each half. If it is not, this is
  65     // the empty array and our base case.
  66
  67     if (p < r) {
  68       // (1) Partitioning.
  69       //
  70       // The partitioning chooses a pivot between `p` and `r` and moves all
  71       // elements that are less than or equal to the pivot to the before it, and
  72       // all the elements that are greater than it after it. The effect is that
  73       // once partition is done, the pivot is in the exact place it will be when
  74       // the array is put in sorted order, and it will not need to be moved
  75       // again. This runs in O(n) time.
  76
  77       // Always choose a random pivot so that an input array which is reverse
  78       // sorted does not cause O(n^2) running time.
  79       var pivotIndex = randomIntInRange(p, r);
  80       var i = p - 1;
  81
  82       swap(ary, pivotIndex, r);
  83       var pivot = ary[r];
  84
  85       // Immediately after `j` is incremented in this loop, the following hold
  86       // true:
  87       //
  88       //   * Every element in `ary[p .. i]` is less than or equal to the pivot.
  89       //
  90       //   * Every element in `ary[i+1 .. j-1]` is greater than the pivot.
  91       for (var j = p; j < r; j++) {
  92         if (comparator(ary[j], pivot) <= 0) {
  93           i += 1;
  94           swap(ary, i, j);
  95         }
  96       }
  97
  98       swap(ary, i + 1, j);
  99       var q = i + 1;
 100
 101       // (2) Recurse on each half.
 102
 103       doQuickSort(ary, comparator, p, q - 1);
 104       doQuickSort(ary, comparator, q + 1, r);
 105     }
 106   }
 107
 108   /**
 109    * Sort the given array in-place with the given comparator function.
 110    *
 111    * @param {Array} ary
 112    *        An array to sort.
 113    * @param {function} comparator
 114    *        Function to use to compare two items.
 115    */
 116   exports.quickSort = function (ary, comparator) {
 117     doQuickSort(ary, comparator, 0, ary.length - 1);
 118   };
 119
 120 });