source: trip-planner-front/node_modules/stable/stable.js@ 1ad8e64

Last change on this file since 1ad8e64 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 2.9 KB
Line 
1//! stable.js 0.1.8, https://github.com/Two-Screen/stable
2//! © 2018 Angry Bytes and contributors. MIT licensed.
3
4(function (global, factory) {
5 typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :
6 typeof define === 'function' && define.amd ? define(factory) :
7 (global.stable = factory());
8}(this, (function () { 'use strict';
9
10 // A stable array sort, because `Array#sort()` is not guaranteed stable.
11 // This is an implementation of merge sort, without recursion.
12
13 var stable = function (arr, comp) {
14 return exec(arr.slice(), comp)
15 };
16
17 stable.inplace = function (arr, comp) {
18 var result = exec(arr, comp);
19
20 // This simply copies back if the result isn't in the original array,
21 // which happens on an odd number of passes.
22 if (result !== arr) {
23 pass(result, null, arr.length, arr);
24 }
25
26 return arr
27 };
28
29 // Execute the sort using the input array and a second buffer as work space.
30 // Returns one of those two, containing the final result.
31 function exec(arr, comp) {
32 if (typeof(comp) !== 'function') {
33 comp = function (a, b) {
34 return String(a).localeCompare(b)
35 };
36 }
37
38 // Short-circuit when there's nothing to sort.
39 var len = arr.length;
40 if (len <= 1) {
41 return arr
42 }
43
44 // Rather than dividing input, simply iterate chunks of 1, 2, 4, 8, etc.
45 // Chunks are the size of the left or right hand in merge sort.
46 // Stop when the left-hand covers all of the array.
47 var buffer = new Array(len);
48 for (var chk = 1; chk < len; chk *= 2) {
49 pass(arr, comp, chk, buffer);
50
51 var tmp = arr;
52 arr = buffer;
53 buffer = tmp;
54 }
55
56 return arr
57 }
58
59 // Run a single pass with the given chunk size.
60 var pass = function (arr, comp, chk, result) {
61 var len = arr.length;
62 var i = 0;
63 // Step size / double chunk size.
64 var dbl = chk * 2;
65 // Bounds of the left and right chunks.
66 var l, r, e;
67 // Iterators over the left and right chunk.
68 var li, ri;
69
70 // Iterate over pairs of chunks.
71 for (l = 0; l < len; l += dbl) {
72 r = l + chk;
73 e = r + chk;
74 if (r > len) r = len;
75 if (e > len) e = len;
76
77 // Iterate both chunks in parallel.
78 li = l;
79 ri = r;
80 while (true) {
81 // Compare the chunks.
82 if (li < r && ri < e) {
83 // This works for a regular `sort()` compatible comparator,
84 // but also for a simple comparator like: `a > b`
85 if (comp(arr[li], arr[ri]) <= 0) {
86 result[i++] = arr[li++];
87 }
88 else {
89 result[i++] = arr[ri++];
90 }
91 }
92 // Nothing to compare, just flush what's left.
93 else if (li < r) {
94 result[i++] = arr[li++];
95 }
96 else if (ri < e) {
97 result[i++] = arr[ri++];
98 }
99 // Both iterators are at the chunk ends.
100 else {
101 break
102 }
103 }
104 }
105 };
106
107 return stable;
108
109})));
Note: See TracBrowser for help on using the repository browser.