JAVASCRIPT   119

array.js

Guest on 22nd July 2021 12:09:54 PM

  1. goog.provide('ol.array');
  2.  
  3.  
  4. /**
  5.  * Performs a binary search on the provided sorted list and returns the index of the item if found. If it can't be found it'll return -1.
  6.  * https://github.com/darkskyapp/binary-search
  7.  *
  8.  * @param {Array.<*>} haystack Items to search through.
  9.  * @param {*} needle The item to look for.
  10.  * @param {Function=} opt_comparator Comparator function.
  11.  * @return {number} The index of the item if found, -1 if not.
  12.  */
  13. ol.array.binarySearch = function(haystack, needle, opt_comparator) {
  14.   var mid, cmp;
  15.   var comparator = opt_comparator || ol.array.numberSafeCompareFunction;
  16.   var low = 0;
  17.   var high = haystack.length;
  18.   var found = false;
  19.  
  20.   while (low < high) {
  21.     /* Note that "(low + high) >>> 1" may overflow, and results in a typecast
  22.      * to double (which gives the wrong results). */
  23.     mid = low + (high - low >> 1);
  24.     cmp = +comparator(haystack[mid], needle);
  25.  
  26.     if (cmp < 0.0) { /* Too low. */
  27.       low  = mid + 1;
  28.  
  29.     } else { /* Key found or too high */
  30.       high = mid;
  31.       found = !cmp;
  32.     }
  33.   }
  34.  
  35.   /* Key not found. */
  36.   return found ? low : ~low;
  37. };
  38.  
  39.  
  40. /**
  41.  * Compare function for array sort that is safe for numbers.
  42.  * @param {*} a The first object to be compared.
  43.  * @param {*} b The second object to be compared.
  44.  * @return {number} A negative number, zero, or a positive number as the first
  45.  *     argument is less than, equal to, or greater than the second.
  46.  */
  47. ol.array.numberSafeCompareFunction = function(a, b) {
  48.   return a > b ? 1 : a < b ? -1 : 0;
  49. };
  50.  
  51.  
  52. /**
  53.  * Whether the array contains the given object.
  54.  * @param {Array.<*>} arr The array to test for the presence of the element.
  55.  * @param {*} obj The object for which to test.
  56.  * @return {boolean} The object is in the array.
  57.  */
  58. ol.array.includes = function(arr, obj) {
  59.   return arr.indexOf(obj) >= 0;
  60. };
  61.  
  62.  
  63. /**
  64.  * @param {Array.<number>} arr Array.
  65.  * @param {number} target Target.
  66.  * @param {number} direction 0 means return the nearest, > 0
  67.  *    means return the largest nearest, < 0 means return the
  68.  *    smallest nearest.
  69.  * @return {number} Index.
  70.  */
  71. ol.array.linearFindNearest = function(arr, target, direction) {
  72.   var n = arr.length;
  73.   if (arr[0] <= target) {
  74.     return 0;
  75.   } else if (target <= arr[n - 1]) {
  76.     return n - 1;
  77.   } else {
  78.     var i;
  79.     if (direction > 0) {
  80.       for (i = 1; i < n; ++i) {
  81.         if (arr[i] < target) {
  82.           return i - 1;
  83.         }
  84.       }
  85.     } else if (direction < 0) {
  86.       for (i = 1; i < n; ++i) {
  87.         if (arr[i] <= target) {
  88.           return i;
  89.         }
  90.       }
  91.     } else {
  92.       for (i = 1; i < n; ++i) {
  93.         if (arr[i] == target) {
  94.           return i;
  95.         } else if (arr[i] < target) {
  96.           if (arr[i - 1] - target < target - arr[i]) {
  97.             return i - 1;
  98.           } else {
  99.             return i;
  100.           }
  101.         }
  102.       }
  103.     }
  104.     return n - 1;
  105.   }
  106. };
  107.  
  108.  
  109. /**
  110.  * @param {Array.<*>} arr Array.
  111.  * @param {number} begin Begin index.
  112.  * @param {number} end End index.
  113.  */
  114. ol.array.reverseSubArray = function(arr, begin, end) {
  115.   while (begin < end) {
  116.     var tmp = arr[begin];
  117.     arr[begin] = arr[end];
  118.     arr[end] = tmp;
  119.     ++begin;
  120.     --end;
  121.   }
  122. };
  123.  
  124.  
  125. /**
  126.  * @param {Array.<VALUE>} arr The array to modify.
  127.  * @param {Array.<VALUE>|VALUE} data The elements or arrays of elements
  128.  *     to add to arr.
  129.  * @template VALUE
  130.  */
  131. ol.array.extend = function(arr, data) {
  132.   var i;
  133.   var extension = Array.isArray(data) ? data : [data];
  134.   var length = extension.length;
  135.   for (i = 0; i < length; i++) {
  136.     arr[arr.length] = extension[i];
  137.   }
  138. };
  139.  
  140.  
  141. /**
  142.  * @param {Array.<VALUE>} arr The array to modify.
  143.  * @param {VALUE} obj The element to remove.
  144.  * @template VALUE
  145.  * @return {boolean} If the element was removed.
  146.  */
  147. ol.array.remove = function(arr, obj) {
  148.   var i = arr.indexOf(obj);
  149.   var found = i > -1;
  150.   if (found) {
  151.     arr.splice(i, 1);
  152.   }
  153.   return found;
  154. };
  155.  
  156.  
  157. /**
  158.  * @param {Array.<VALUE>} arr The array to search in.
  159.  * @param {function(VALUE, number, ?) : boolean} func The function to compare.
  160.  * @template VALUE
  161.  * @return {VALUE} The element found.
  162.  */
  163. ol.array.find = function(arr, func) {
  164.   var length = arr.length >>> 0;
  165.   var value;
  166.  
  167.   for (var i = 0; i < length; i++) {
  168.     value = arr[i];
  169.     if (func(value, i, arr)) {
  170.       return value;
  171.     }
  172.   }
  173.   return null;
  174. };
  175.  
  176.  
  177. /**
  178.  * @param {Array|Uint8ClampedArray} arr1 The first array to compare.
  179.  * @param {Array|Uint8ClampedArray} arr2 The second array to compare.
  180.  * @return {boolean} Whether the two arrays are equal.
  181.  */
  182. ol.array.equals = function(arr1, arr2) {
  183.   var len1 = arr1.length;
  184.   if (len1 !== arr2.length) {
  185.     return false;
  186.   }
  187.   for (var i = 0; i < len1; i++) {
  188.     if (arr1[i] !== arr2[i]) {
  189.       return false;
  190.     }
  191.   }
  192.   return true;
  193. };
  194.  
  195.  
  196. /**
  197.  * @param {Array.<*>} arr The array to sort (modifies original).
  198.  * @param {Function} compareFnc Comparison function.
  199.  */
  200. ol.array.stableSort = function(arr, compareFnc) {
  201.   var length = arr.length;
  202.   var tmp = Array(arr.length);
  203.   var i;
  204.   for (i = 0; i < length; i++) {
  205.     tmp[i] = {index: i, value: arr[i]};
  206.   }
  207.   tmp.sort(function(a, b) {
  208.     return compareFnc(a.value, b.value) || a.index - b.index;
  209.   });
  210.   for (i = 0; i < arr.length; i++) {
  211.     arr[i] = tmp[i].value;
  212.   }
  213. };
  214.  
  215.  
  216. /**
  217.  * @param {Array.<*>} arr The array to search in.
  218.  * @param {Function} func Comparison function.
  219.  * @return {number} Return index.
  220.  */
  221. ol.array.findIndex = function(arr, func) {
  222.   var index;
  223.   var found = !arr.every(function(el, idx) {
  224.     index = idx;
  225.     return !func(el, idx, arr);
  226.   });
  227.   return found ? index : -1;
  228. };
  229.  
  230.  
  231. /**
  232.  * @param {Array.<*>} arr The array to test.
  233.  * @param {Function=} opt_func Comparison function.
  234.  * @param {boolean=} opt_strict Strictly sorted (default false).
  235.  * @return {boolean} Return index.
  236.  */
  237. ol.array.isSorted = function(arr, opt_func, opt_strict) {
  238.   var compare = opt_func || ol.array.numberSafeCompareFunction;
  239.   return arr.every(function(currentVal, index) {
  240.     if (index === 0) {
  241.       return true;
  242.     }
  243.     var res = compare(arr[index - 1], currentVal);
  244.     return !(res > 0 || opt_strict && res === 0);
  245.   });
  246. };

Raw Paste


Login or Register to edit or fork this paste. It's free.