/**

* @author Richard Davey <rich@photonstorm.com>

* @copyright 2019 Photon Storm Ltd.

* @license {@link https://github.com/photonstorm/phaser/blob/master/license.txt|MIT License}

*/

//! stable.js 0.1.6, https://github.com/Two-Screen/stable

//! © 2017 Angry Bytes and contributors. MIT licensed.

/**

* @namespace Phaser.Utils.Array.StableSortFunctions

*/

(function() {

/**

* A stable array sort, because `Array#sort()` is not guaranteed stable.

* This is an implementation of merge sort, without recursion.

*

* @function Phaser.Utils.Array.StableSort

* @since 3.0.0

*

* @param {array} arr - The input array to be sorted.

* @param {function} comp - The comparison handler.

*

* @return {array} The sorted result.

*/

var stable = function(arr, comp) {

return exec(arr.slice(), comp);

};

/**

* Sort the input array and simply copy it back if the result isn't in the original array, which happens on an odd number of passes.

*

* @function Phaser.Utils.Array.StableSortFunctions.inplace

* @memberof Phaser.Utils.Array.StableSortFunctions

* @since 3.0.0

*

* @param {array} arr - The input array.

* @param {function} comp - The comparison handler.

*

* @return {array} The sorted array.

*/

stable.inplace = function(arr, comp) {

var result = exec(arr, comp);

// This simply copies back if the result isn't in the original array,

// which happens on an odd number of passes.

if (result !== arr) {

pass(result, null, arr.length, arr);

}

return arr;

};

// Execute the sort using the input array and a second buffer as work space.

// Returns one of those two, containing the final result.

function exec(arr, comp) {

if (typeof(comp) !== 'function') {

comp = function(a, b) {

return String(a).localeCompare(b);

};

}

// Short-circuit when there's nothing to sort.

var len = arr.length;

if (len <= 1) {

return arr;

}

// Rather than dividing input, simply iterate chunks of 1, 2, 4, 8, etc.

// Chunks are the size of the left or right hand in merge sort.

// Stop when the left-hand covers all of the array.

var buffer = new Array(len);

for (var chk = 1; chk < len; chk *= 2) {

pass(arr, comp, chk, buffer);

var tmp = arr;

arr = buffer;

buffer = tmp;

}

return arr;

}

// Run a single pass with the given chunk size.

var pass = function(arr, comp, chk, result) {

var len = arr.length;

var i = 0;

// Step size / double chunk size.

var dbl = chk * 2;

// Bounds of the left and right chunks.

var l, r, e;

// Iterators over the left and right chunk.

var li, ri;

// Iterate over pairs of chunks.

for (l = 0; l < len; l += dbl) {

r = l + chk;

e = r + chk;

if (r > len) r = len;

if (e > len) e = len;

// Iterate both chunks in parallel.

li = l;

ri = r;

while (true) {

// Compare the chunks.

if (li < r && ri < e) {

// This works for a regular `sort()` compatible comparator,

// but also for a simple comparator like: `a > b`

if (comp(arr[li], arr[ri]) <= 0) {

result[i++] = arr[li++];

}

else {

result[i++] = arr[ri++];

}

}

// Nothing to compare, just flush what's left.

else if (li < r) {

result[i++] = arr[li++];

}

else if (ri < e) {

result[i++] = arr[ri++];

}

// Both iterators are at the chunk ends.

else {

break;

}

}

}

};

// Export using CommonJS or to the window.

if (typeof(module) !== 'undefined') {

module.exports = stable;

}

else {

window.stable = stable;

}

})();