import defined from "./defined.js";
|
import DeveloperError from "./DeveloperError.js";
|
|
var leftScratchArray = [];
|
var rightScratchArray = [];
|
|
function merge(array, compare, userDefinedObject, start, middle, end) {
|
var leftLength = middle - start + 1;
|
var rightLength = end - middle;
|
|
var left = leftScratchArray;
|
var right = rightScratchArray;
|
|
var i;
|
var j;
|
|
for (i = 0; i < leftLength; ++i) {
|
left[i] = array[start + i];
|
}
|
|
for (j = 0; j < rightLength; ++j) {
|
right[j] = array[middle + j + 1];
|
}
|
|
i = 0;
|
j = 0;
|
for (var k = start; k <= end; ++k) {
|
var leftElement = left[i];
|
var rightElement = right[j];
|
if (
|
i < leftLength &&
|
(j >= rightLength ||
|
compare(leftElement, rightElement, userDefinedObject) <= 0)
|
) {
|
array[k] = leftElement;
|
++i;
|
} else if (j < rightLength) {
|
array[k] = rightElement;
|
++j;
|
}
|
}
|
}
|
|
function sort(array, compare, userDefinedObject, start, end) {
|
if (start >= end) {
|
return;
|
}
|
|
var middle = Math.floor((start + end) * 0.5);
|
sort(array, compare, userDefinedObject, start, middle);
|
sort(array, compare, userDefinedObject, middle + 1, end);
|
merge(array, compare, userDefinedObject, start, middle, end);
|
}
|
|
/**
|
* A stable merge sort.
|
*
|
* @function mergeSort
|
* @param {Array} array The array to sort.
|
* @param {mergeSortComparator} comparator The function to use to compare elements in the array.
|
* @param {*} [userDefinedObject] Any item to pass as the third parameter to <code>comparator</code>.
|
*
|
* @example
|
* // Assume array contains BoundingSpheres in world coordinates.
|
* // Sort them in ascending order of distance from the camera.
|
* var position = camera.positionWC;
|
* Cesium.mergeSort(array, function(a, b, position) {
|
* return Cesium.BoundingSphere.distanceSquaredTo(b, position) - Cesium.BoundingSphere.distanceSquaredTo(a, position);
|
* }, position);
|
*/
|
function mergeSort(array, comparator, userDefinedObject) {
|
//>>includeStart('debug', pragmas.debug);
|
if (!defined(array)) {
|
throw new DeveloperError("array is required.");
|
}
|
if (!defined(comparator)) {
|
throw new DeveloperError("comparator is required.");
|
}
|
//>>includeEnd('debug');
|
|
var length = array.length;
|
var scratchLength = Math.ceil(length * 0.5);
|
|
// preallocate space in scratch arrays
|
leftScratchArray.length = scratchLength;
|
rightScratchArray.length = scratchLength;
|
|
sort(array, comparator, userDefinedObject, 0, length - 1);
|
|
// trim scratch arrays
|
leftScratchArray.length = 0;
|
rightScratchArray.length = 0;
|
}
|
|
/**
|
* A function used to compare two items while performing a merge sort.
|
* @callback mergeSortComparator
|
*
|
* @param {*} a An item in the array.
|
* @param {*} b An item in the array.
|
* @param {*} [userDefinedObject] An object that was passed to {@link mergeSort}.
|
* @returns {Number} Returns a negative value if <code>a</code> is less than <code>b</code>,
|
* a positive value if <code>a</code> is greater than <code>b</code>, or
|
* 0 if <code>a</code> is equal to <code>b</code>.
|
*
|
* @example
|
* function compareNumbers(a, b, userDefinedObject) {
|
* return a - b;
|
* }
|
*/
|
export default mergeSort;
|
