{"version":3,"file":"index.cjs","sources":["../src/kernel/_choice.js","../src/kernel/_randint.js","../src/api/random.js","../src/api/randint.js","../src/api/choice.js","../src/kernel/_randfloat.js","../src/api/randfloat.js","../src/kernel/_randrange.js","../src/api/randrange.js","../src/kernel/_waterman.js","../src/api/reservoir.js","../src/kernel/_fisheryates.js","../src/api/sample.js","../src/kernel/_shuffle.js","../src/api/shuffle.js","../src/kernel/_fisheryates_inside_out.js","../src/api/shuffled.js"],"sourcesContent":["/**\n * Builds a choice function given a randint function.\n *\n * @param {Function} randint The randint function.\n * @return {Function} The choice function.\n */\nconst _choice = (randint) => {\n\t/**\n\t * Sample a single element from an array.\n\t *\n\t * @param {Array} a The input array.\n\t * @param {number} i Inclusive left bound.\n\t * @param {number} j Non-inclusive right bound.\n\t * @return {any} The sampled element.\n\t */\n\tconst choice = (a, i, j) => {\n\t\tconst x = randint(i, j);\n\t\treturn a[x];\n\t};\n\n\treturn choice;\n};\n\nexport default _choice;\n","/**\n * Builds a randint function given a random number generator.\n *\n * @param {Function} random A function taking no arguments that returns a\n * double uniformly at random in the interval [0, 1).\n *\n * @return {Function} A randint function.\n */\nconst _randint = (random) => {\n\t/**\n\t * Returns an integer in interval [i, j[ (i included, j excluded)\n\t * according to a uniform distribution.\n\t *\n\t * @param {number} i The inclusive left bound\n\t * @param {number} j The non-inclusive right bound\n\t * @return {number} An integer in the interval [i, j[ taken uniformly at\n\t * random.\n\t */\n\tconst randint = (i, j) => i + Math.floor(random() * (j - i));\n\treturn randint;\n};\n\nexport default _randint;\n","/**\n * Returns a double in the interval [0, 1) using JavaScript Math.random().\n * @return {number}\n */\nconst random = () => {\n\treturn Math.random();\n};\n\nexport default random;\n","import _randint from '../kernel/_randint.js';\nimport random from './random.js';\n\n/**\n * Returns an integer in interval [i, j[ (i included, j excluded)\n * according to a uniform distribution.\n *\n * @function\n * @param {number} i The inclusive left bound\n * @param {number} j The non-inclusive right bound\n * @return {number} An integer in the interval [i, j[ taken uniformly at\n * random.\n */\nconst randint = _randint(random);\nexport default randint;\n","import _choice from '../kernel/_choice.js';\nimport randint from './randint.js';\n\n/**\n * Sample a single element from an array.\n *\n * @function\n * @param {Array} a The input array.\n * @param {number} i Inclusive left bound.\n * @param {number} j Non-inclusive right bound.\n * @return {any} The sampled element.\n */\nconst choice = _choice(randint);\nexport default choice;\n","/**\n * Builds a randfloat function given a random number generator.\n *\n * @param {Function} random A function taking no arguments that returns a\n * double uniformly at random in the interval [0, 1).\n *\n * @return {Function} A randfloat function.\n */\nconst _randfloat = (random) => {\n\t/**\n\t * Returns a double in interval [i, j[ (i included, j excluded)\n\t * according to a uniform distribution.\n\t *\n\t * @param {number} i The inclusive left bound\n\t * @param {number} j The non-inclusive right bound\n\t * @return {number} A double in the interval [i, j[ taken uniformly at\n\t * random.\n\t */\n\tconst randfloat = (i, j) => i + random() * (j - i);\n\treturn randfloat;\n};\n\nexport default _randfloat;\n","import _randfloat from '../kernel/_randfloat.js';\nimport random from './random.js';\n\n/**\n * Returns a double in interval [i, j[ (i included, j excluded)\n * according to a uniform distribution.\n *\n * @function\n * @param {number} i The inclusive left bound\n * @param {number} j The non-inclusive right bound\n * @return {number} A double in the interval [i, j[ taken uniformly at\n * random.\n */\nconst randfloat = _randfloat(random);\nexport default randfloat;\n","/**\n * Builds a randrange function given a randint function.\n *\n * @param {Function} randint The randint function.\n * @return {Function} The choice function.\n */\nconst _randrange = (randint) => {\n\t/**\n\t * Pick an element from range(start, stop, step) uniformly at random.\n\t *\n\t * Return an element from range(start, stop, step) selected uniformly at random.\n\t * If step is positive, this set corresponds to\n\t * {x: x in [start, stop[ AND x % step = 0}.\n\t * If step is negative, the range has to be given in reverse order, that is,\n\t * largest value first, smallest value second. Both the starting value and the\n\t * step value are optional. By default the starting value is <code>0</code>.\n\t * The default for the step value is <code>1</code>.\n\t *\n\t * TODO: Handle empty ranges.\n\t *\n\t * @param {number} [start=0] - The starting value.\n\t * @param {number} stop - The stopping value.\n\t * @param {number} [step=1] - The step value.\n\t * @return {number} The picked element.\n\t */\n\tconst randrange = (start, stop, step) => {\n\t\tif (stop === undefined) return randint(0, start);\n\t\tif (step === undefined) step = 1;\n\n\t\tif (stop >= start) {\n\t\t\treturn start + step * randint(0, Math.floor((stop - start) / step));\n\t\t}\n\n\t\treturn start + step * randint(0, Math.floor((start - stop) / -step));\n\t};\n\n\treturn randrange;\n};\n\nexport default _randrange;\n","import _randrange from '../kernel/_randrange.js';\nimport randint from './randint.js';\n\n/**\n * Pick an element from range(start, stop, step) uniformly at random.\n *\n * Return an element from range(start, stop, step) selected uniformly at random.\n * If step is positive, this set corresponds to\n * {x: x in [start, stop[ AND x % step = 0}.\n * If step is negative, the range has to be given in reverse order, that is,\n * largest value first, smallest value second. Both the starting value and the\n * step value are optional. By default the starting value is <code>0</code>.\n * The default for the step value is <code>1</code>.\n *\n * TODO: Handle empty ranges.\n *\n * @function\n * @param {number} [start=0] - The starting value.\n * @param {number} stop - The stopping value.\n * @param {number} [step=1] - The step value.\n * @return {number} The picked element.\n */\nconst randrange = _randrange(randint);\nexport default randrange;\n","/**\n * Construct a sampling function using Algorithm R due to Alan Waterman (both\n * name and attribution are due to Knuth).\n *\n * @param {Function} randint The randint function.\n * @return {Function} The sample function.\n */\nconst _waterman = (randint) => {\n\t/**\n\t * Samples k items uniformly at random from an iterable of unknown size.\n\t *\n\t * We want each item to have probability k/n of being selected.\n\t *\n\t * The algorithm works as follows:\n\t *   1. We initialize a candidate sample with the first k items.\n\t *   2. For each remaining item i, decide whether to insert it in the\n\t *   candidate sample with probability k/i, evicting an item from the\n\t *   candidate sample at random, or to discard it immediately (with\n\t *   probability 1-k/i),\n\t *\n\t * To prove that the obtained probability of inclusion for each item is correct\n\t * we multiply two probabilities:\n\t *   1. The probability of entering the candidate sample.\n\t *   2. The probability of staying in the candidate sample until the end.\n\t *\n\t * For items 1 to k, probability 1. is 1, and probability 2. is\n\t * (1-1/(k+1))(1-1/(k+2))...(1-1/n)\n\t * = (k/(k+1))((k+1)/(k+2))...((n-1)/n) which telescopes to k/n.\n\t *\n\t * For items i = k+1 to n, where probability 1. is k/i, and probability 2.\n\t * is (1-1/(i+1))(1-1/(i+2))...(1-1/n)\n\t * = (i/(i+1))((i+1)/(i+2))...((n-1)/n) which telescopes to i/n.\n\t *\n\t * NOTE: Could also implement so that it yields after each input item.\n\t * NOTE: One can reduce the expected number of random bits needed by\n\t * avoiding generating any number above k-1:\n\t *   - First we branch on whether i < k.\n\t *   - Then we generate the random number between 0 and k-1 only if needed.\n\t *\n\t * To decide on the branch, flip a biased coin with parameter p = k/n.\n\t * To do so, flip a fair coin until it differs from the binary\n\t * representation of k/n (0.10110101...).\n\t * The computation can be made efficient by realizing several things:\n\t *   - k is fixed and smaller than n (so divmod step can be skipped)\n\t *   - k/(n+1) < k/n (so we can avoid recomputing if the biased flip > k/n)\n\t *\n\t * This would reduce the number of necessary random bits from O(n log n) to\n\t * expected O(n).\n\t *\n\t * @param {number} k The size of the sample.\n\t * @param {Iterable} iterable The input iterable.\n\t * @param {Array} [output=new Array(k)] The output array.\n\t * @return {Array} The output array.\n\t */\n\tconst sample = (k, iterable, output = new Array(k)) => {\n\t\tconst it = iterable[Symbol.iterator]();\n\n\t\tlet n = 0;\n\n\t\tfor (; n < k; ++n) {\n\t\t\tconst {value, done} = it.next();\n\t\t\tif (done) return output;\n\t\t\toutput[n] = value;\n\t\t}\n\n\t\tfor (; ; ++n) {\n\t\t\tconst {value, done} = it.next();\n\t\t\tif (done) return output;\n\t\t\tconst i = randint(0, n);\n\t\t\tif (i < k) output[i] = value;\n\t\t}\n\t};\n\n\treturn sample;\n};\n\nexport default _waterman;\n","import _waterman from '../kernel/_waterman.js';\nimport randint from './randint.js';\n\n/**\n * Reservoir sampling.\n *\n * @function\n * @param {number} k The size of the sample.\n * @param {Iterable} iterable The input iterable.\n * @param {Array} [output=new Array(k)] The output array.\n * @return {Array} The output array.\n */\nconst reservoir = _waterman(randint);\nexport default reservoir;\n","/**\n * Sample elements from an array using Fisher-Yates method.\n *\n * NOTE: The original description of the algorithm by Fisher and Yates [1] had\n * unnecessary bookkeeping which made the algorithm run in O(n * (j-i)) time.\n * This implementation follows Durstenfeld's [2] and Knuth's [3] descriptions\n * which yield O(n) running time.\n *\n * For more information see the excellent \"Fisher–Yates shuffle\" page on\n * Wikipedia [4]. Fisher and Yates description is referred there as\n * \"Fisher and Yate's original method\" or \"pencil-and-paper method\".\n * The more efficient implementation described by Durstenfeld and Knuth is\n * referred there as \"the modern method\".\n *\n * [1] Fisher, Ronald A.; Yates, Frank (1938). Statistical tables for\n *     biological, agricultural and medical research.\n * [2] Durstenfeld, R. (July 1964). \"Algorithm 235: Random permutation\"\n * [3] Knuth, Donald E. (1969). Seminumerical algorithms. The Art of Computer\n *     Programming Volume 2.\n * [4] https://en.wikipedia.org/wiki/Fisher–Yates_shuffle\n *\n * @param {Function} randint The randint function.\n * @return {Function} The sampling function.\n */\nconst _fisheryates = (randint) => {\n\t/**\n\t * Take a sample of size n (without replacement) from the items i through\n\t * j-1 of the input array. This is done in-place. The sample can be\n\t * retrieved from position i to i+n.\n\t *\n\t * @param {number} n The size of the sample.\n\t * @param {Array} a The input array.\n\t * @param {number} i The inclusive left bound.\n\t * @param {number} j The non-inclusive right bound.\n\t */\n\tconst sample = (n, a, i, j) => {\n\t\t// We will swap at most n elements\n\t\t// NOTE: When n = j - i, the last swap swaps a[j-1] with itself,\n\t\t// which is a NOOP. /!\\ HOWEVER, the last swap is NOT a NOOP when\n\t\t// n < j - i. Hence we cannot let k = i + n - 1 in general.\n\t\tconst k = i + n;\n\n\t\tfor (; i < k; ++i) {\n\t\t\t// Choose any index p in the remaining array\n\t\t\tconst p = randint(i, j);\n\n\t\t\t// Swap selected element with the first remaining element.\n\t\t\tconst tmp = a[i];\n\t\t\ta[i] = a[p];\n\t\t\ta[p] = tmp;\n\t\t}\n\t};\n\n\treturn sample;\n};\n\nexport default _fisheryates;\n","import _fisheryates from '../kernel/_fisheryates.js';\nimport randint from './randint.js';\n\n/**\n * Take a sample of size n (without replacement) from the items i through\n * j-1 of the input array. This is done in-place. The sample can be retrieved\n * from position i to i+n.\n *\n * @function\n * @param {number} n The size of the sample.\n * @param {Array} a The input array.\n * @param {number} i The inclusive left bound.\n * @param {number} j The non-inclusive right bound.\n */\nconst sample = _fisheryates(randint);\nexport default sample;\n","/**\n * Shuffle the array by sampling the entire array.\n *\n * @param {Function} sample The sample function.\n * @return {Function} The shuffle function.\n */\nconst _shuffle = (sample) => {\n\t/**\n\t * Shuffle array in-place between positions i and j-1 (inclusive).\n\t * The other positions are left untouched.\n\t *\n\t * @param {Array} a The input array.\n\t * @param {number} i The inclusive left bound.\n\t * @param {number} j The non-inclusive right bound.\n\t */\n\tconst shuffle = (a, i, j) => sample(j - i, a, i, j);\n\treturn shuffle;\n};\n\nexport default _shuffle;\n","import _shuffle from '../kernel/_shuffle.js';\nimport sample from './sample.js';\n\n/**\n * Shuffle array in-place between positions i and j-1 (inclusive).\n * The other positions are left untouched.\n * @function\n * @param {Array} a The input array.\n * @param {number} i The inclusive left bound.\n * @param {number} j The non-inclusive right bound.\n */\nconst shuffle = _shuffle(sample);\nexport default shuffle;\n","/**\n * Shuffle elements of an iterable using an inside-out implementation of the\n * Fisher-Yates method.\n *\n * One can observe that if the input contains n elements, the loop has exactly\n * n! possible outcomes: one for the first iteration, two for the second, three\n * for the third, etc., the number of outcomes of a loop being the product of\n * the number of outcomes for each iteration. Given a perfect randint function,\n * each iteration's outcomes are equally likely, and independent of other\n * iterations outcomes.  The proof below shows that these outcomes are\n * distinct.\n *\n * To see that this method yields the correct result (assume perfect randint):\n *   1. Observe that it is correct when the input is empty.\n *   2. By induction:\n *     - Induction hypothesis: assume it is correct when the input consists of\n *       n elements.\n *     - We almost insert the (n+1)th element at one of the n+1 possible\n *       insertion position in the output array. Almost because we move the\n *       element that is at the insertion position at the end instead of\n *       shifting the elements right of the insertion position to make room for\n *       the inserted element.\n *     - Ideally, since we inserted the last element at one of the n+1\n *       positions, we would like that the elements inserted earlier form one\n *       of n! permutations uniformly at random after moving the element under\n *       the insertion position. This is true because the permutations that we\n *       obtain after this move are in one-to-one correspondance with the n!\n *       distinct permutations that can be obtained before the move. These are\n *       equally likely to be produced by the induction hypothesis.\n *\n * @param {Function} randint The randint function.\n * @return {Function} The sampling function.\n */\nconst _fisheryates_inside_out = (randint) => {\n\t/**\n\t * Given an input iterable, constructs an array containing the elements of\n\t * the input shuffled uniformly at random.\n\t *\n\t * @param {Iterable} iterable The input iterable.\n\t * @param {Array} [output=[]] The constructed array.\n\t * @return {Array} The constructed array.\n\t */\n\tconst shuffled = (iterable, output = []) => {\n\t\tlet n = 0;\n\t\tfor (const item of iterable) {\n\t\t\tconst i = randint(-1, n);\n\t\t\tif (i === -1) output.push(item);\n\t\t\telse {\n\t\t\t\toutput.push(output[i]);\n\t\t\t\toutput[i] = item;\n\t\t\t}\n\n\t\t\t++n;\n\t\t}\n\n\t\treturn output;\n\t};\n\n\treturn shuffled;\n};\n\nexport default _fisheryates_inside_out;\n","import _fisheryates_inside_out from '../kernel/_fisheryates_inside_out.js';\nimport randint from './randint.js';\n\n/**\n * Given an input iterable, constructs an array containing the elements of the\n * input shuffled uniformly at random.\n *\n * @function\n * @param {Iterable} iterable The input iterable.\n * @return {Array} The constructed array.\n */\nconst shuffled = _fisheryates_inside_out(randint);\nexport default shuffled;\n"],"names":["randint","a","i","j","random","Math","floor","_randint","_choice","_randfloat","start","stop","step","undefined","_randrange","k","iterable","output","Array","it","Symbol","iterator","n","next","done","value","_waterman","p","tmp","_fisheryates","sample","_shuffle","item","push","_fisheryates_inside_out"],"mappings":"AAMA,MAAgB,SAACA,GAchB,OALe,SAACC,EAAGC,EAAGC,GAErB,OAAOF,EADGD,EAAQE,EAAGC,QCRN,SAACC,GAWjB,OADgB,SAACF,EAAGC,UAAMD,EAAIG,KAAKC,MAAMF,KAAYD,EAAID,QCd3C,WACd,OAAOG,KAAKD,YCQGG,EAASH,KCDVI,EAAQR,KCJJ,SAACI,GAWnB,OADkB,SAACF,EAAGC,UAAMD,EAAIE,KAAYD,EAAID,OCL/BO,EAAWL,KCPV,SAACJ,GA8BnB,OAXkB,SAACU,EAAOC,EAAMC,GAC/B,YAAaC,IAATF,EAA2BX,EAAQ,EAAGU,SAC7BG,IAATD,IAAoBA,EAAO,GAE3BD,GAAQD,EACJA,EAAQE,EAAOZ,EAAQ,EAAGK,KAAKC,OAAOK,EAAOD,GAASE,IAGvDF,EAAQE,EAAOZ,EAAQ,EAAGK,KAAKC,OAAOI,EAAQC,IAASC,SCX9CE,EAAWd,KCfX,SAACA,GAkElB,OAnBe,SAACe,EAAGC,EAAUC,YAAAA,IAAAA,EAAS,IAAIC,MAAMH,IAK/C,IAJA,IAAMI,EAAKH,EAASI,OAAOC,YAEvBC,EAAI,EAEDA,EAAIP,IAAKO,EAAG,CAClB,MAAsBH,EAAGI,OACzB,KADcC,KACJ,OAAOP,EACjBA,EAAOK,KAFAG,MAKR,QAAWH,EAAG,CACb,MAAsBH,EAAGI,OAAlBE,IAAAA,MACP,KADcD,KACJ,OAAOP,EACjB,IAAMf,EAAIF,EAAQ,EAAGsB,GACjBpB,EAAIa,IAAGE,EAAOf,GAAKuB,QCzDRC,EAAU1B,KCYP,SAACA,GA6BrB,OAlBe,SAACsB,EAAGrB,EAAGC,EAAGC,GAOxB,IAFA,IAAMY,EAAIb,EAAIoB,EAEPpB,EAAIa,IAAKb,EAAG,CAElB,IAAMyB,EAAI3B,EAAQE,EAAGC,GAGfyB,EAAM3B,EAAEC,GACdD,EAAEC,GAAKD,EAAE0B,GACT1B,EAAE0B,GAAKC,OCnCKC,EAAa7B,KCRX,SAAC8B,GAUjB,OADgB,SAAC7B,EAAGC,EAAGC,UAAM2B,EAAO3B,EAAID,EAAGD,EAAGC,EAAGC,OCJlC4B,EAASD,6GCsBzB,MAAgC,SAAC9B,GAyBhC,OAhBiB,SAACgB,EAAUC,YAAAA,IAAAA,EAAS,IAEpC,IADA,MAAIK,EAAI,8qBACWN,kBAAU,KAAlBgB,UACJ9B,EAAIF,GAAS,EAAGsB,IACX,IAAPpB,EAAUe,EAAOgB,KAAKD,IAEzBf,EAAOgB,KAAKhB,EAAOf,IACnBe,EAAOf,GAAK8B,KAGXV,EAGH,OAAOL,MC5CQiB,EAAwBlC"}