text: 'use strict';
  /* @flow */
  
  var quantileSorted = require('./quantile_sorted');
  var quickselect = require('./quickselect');
  
  /**
   * The [quantile](https://en.wikipedia.org/wiki/Quantile):
   * this is a population quantile, since we assume to know the entire
   * dataset in this library. This is an implementation of the
   * [Quantiles of a Population](http://en.wikipedia.org/wiki/Quantile#Quantiles_of_a_population)
   * algorithm from wikipedia.
   *
   * Sample is a one-dimensional array of numbers,
   * and p is either a decimal number from 0 to 1 or an array of decimal
   * numbers from 0 to 1.
   * In terms of a k/q quantile, p = k/q - it's just dealing with fractions or dealing
   * with decimal values.
   * When p is an array, the result of the function is also an array containing the appropriate
   * quantiles in input order
   *
   * @param {Array<number>} x sample of one or more numbers
   * @param {number} p the desired quantile, as a number between 0 and 1
   * @returns {number} quantile
   * @example
   * quantile([3, 6, 7, 8, 8, 9, 10, 13, 15, 16, 20], 0.5); // => 9
   */
  function quantile(x /*: Array<number> */, p /*: Array<number> | number */) {
      var copy = x.slice();
  
      if (Array.isArray(p)) {
          // rearrange elements so that each element corresponding to a requested
          // quantile is on a place it would be if the array was fully sorted
          multiQuantileSelect(copy, p);
          // Initialize the result array
          var results = [];
          // For each requested quantile
          for (var i = 0; i < p.length; i++) {
              results[i] = quantileSorted(copy, p[i]);
          }
          return results;
      } else {
          var idx = quantileIndex(copy.length, p);
          quantileSelect(copy, idx, 0, copy.length - 1);
          return quantileSorted(copy, p);
      }
  }
  
  function quantileSelect(arr, k, left, right) {
      if (k % 1 === 0) {
          quickselect(arr, k, left, right);
      } else {
          k = Math.floor(k);
          quickselect(arr, k, left, right);
          quickselect(arr, k + 1, k + 1, right);
      }
  }
  
  function multiQuantileSelect(arr, p) {
      var indices = [0];
      for (var i = 0; i < p.length; i++) {
          indices.push(quantileIndex(arr.length, p[i]));
      }
      indices.push(arr.length - 1);
      indices.sort(compare);
  
      var stack = [0, indices.length - 1];
  
      while (stack.length) {
          var r = Math.ceil(stack.pop());
          var l = Math.floor(stack.pop());
          if (r - l <= 1) continue;
  
          var m = Math.floor((l + r) / 2);
          quantileSelect(arr, indices[m], indices[l], indices[r]);
  
          stack.push(l, m, m, r);
      }
  }
  
  function compare(a, b) {
      return a - b;
  }
  
  function quantileIndex(len /*: number */, p /*: number */)/*:number*/ {
      var idx = len * p;
      if (p === 1) {
          // If p is 1, directly return the last index
          return len - 1;
      } else if (p === 0) {
          // If p is 0, directly return the first index
          return 0;
      } else if (idx % 1 !== 0) {
          // If index is not integer, return the next index in array
          return Math.ceil(idx) - 1;
      } else if (len % 2 === 0) {
          // If the list has even-length, we'll return the middle of two indices
          // around quantile to indicate that we need an average value of the two
          return idx - 0.5;
      } else {
          // Finally, in the simple case of an integer index
          // with an odd-length list, return the index
          return idx;
      }
  }
  
  module.exports = quantile;
  