modules/array.js

   1 /**
   2  * (C) Copyright 2004-2007 Shawn Betts
   3  * (C) Copyright 2007-2010 John J. Foerch
   4  * (C) Copyright 2007-2008 Jeremy Maitin-Shepard
   5  *
   6  * Use, modification, and distribution are subject to the terms specified in the
   7  * COPYING file.
   8 **/
   9
  10 /**
  11  * array_p returns true if its argument is an array, otherwise false.
  12  */
  13 function array_p (ob) {
  14     return ob && ob.constructor &&
  15         ob.constructor.name == "Array" || false;
  16 }
  17
  18 /**
  19  * make_array returns its argument unchanged if it is already an array, an
  20  * empty array if its argument is undefined, otherwise an array containing
  21  * its object as the sole element.
  22  */
  23 function make_array (ob) {
  24     if (array_p(ob))
  25         return ob;
  26     if (ob === undefined)
  27         return [];
  28     return [ob];
  29 }
  30
  31
  32 /**
  33  * array_find returns the first element in the given array that satisfies
  34  * predicate p.  returns null on failure.
  35  */
  36 function array_find (ar, p) {
  37     for (var i = 0, n = ar.length; i < n; ++i) {
  38         if (p(ar[i]))
  39             return ar[i];
  40     }
  41     return null;
  42 }
  43
  44
  45 /**
  46  * array_find_index returns the index of the first element in the array
  47  * that satisfies predicate p.  returns -1 on failure.
  48  */
  49 function array_find_index (ar, p) {
  50     for (var i = 0, n = ar.length; i < n; ++i) {
  51         if (p(ar[i]))
  52             return i;
  53     }
  54     return -1;
  55 }
  56
  57
  58 /**
  59  * remove_duplicates_filter returns a function that can be used in
  60  * Array.filter.  It removes duplicates.  Optional argument cmp is a
  61  * comparison function to test equality.  The default comparison function
  62  * tests equality of the string representation of the objects, making it
  63  * unsuitable for use filtering a list of objects of compound data types.
  64  */
  65 function remove_duplicates_filter (cmp) {
  66     if (cmp) {
  67         let acc = [];
  68         return function (x) {
  69             if (acc.some(function (y) cmp(x, y)))
  70                 return false;
  71             acc.push(x);
  72             return true;
  73         };
  74     }
  75     let acc = {};
  76     return function (x) {
  77         if (acc[x]) return false;
  78         acc[x] = 1;
  79         return true;
  80     };
  81 }
  82
  83
  84 /**
  85  * Given an array, switches places on the subarrays at index i1 to i2 and j1 to
  86  * j2. Leaves the rest of the array unchanged.
  87  */
  88 function switch_subarrays (arr, i1, i2, j1, j2) {
  89     return arr.slice(0, i1) +
  90         arr.slice(j1, j2) +
  91         arr.slice(i2, j1) +
  92         arr.slice(i1, i2) +
  93         arr.slice(j2, arr.length);
  94 }
  95
  96
  97 /**
  98  * splice_ranges: Given an ordered array of non-overlapping ranges,
  99  * represented as elements of [start, end], insert a new range into the
 100  * array, extending, replacing, or merging existing ranges as needed.
 101  * Mutates `arr' in place, but returns the reference to it.
 102  *
 103  * Examples:
 104  *
 105  * splice_range([[1,3],[4,6], 5, 8)
 106  *  => [[1,3],[4,8]]
 107  *
 108  * splice_range([[1,3],[4,6],[7,10]], 2, 8)
 109  *  => [[1,10]]
 110  */
 111 function splice_range (arr, start, end) {
 112     for (var i = 0; i < arr.length; ++i) {
 113         let [n,m] = arr[i];
 114         if (start > m)
 115             continue;
 116         if (end < n) {
 117             arr.splice(i, 0, [start, end]);
 118             break;
 119         }
 120         if (start < n)
 121             arr[i][0] = start;
 122
 123         if (end >= n) {
 124             /*
 125              * The range we are inserting overlaps the current
 126              * range. We need to scan right to see if it also contains any other
 127              * ranges entirely, and remove them if necessary.
 128              */
 129             var j = i;
 130             while (j < arr.length && end >= arr[j][0])
 131                 j++;
 132             j--;
 133             arr[i][1] = Math.max(end, arr[j][1]);
 134             arr.splice(i + 1, j - i);
 135             break;
 136         }
 137     }
 138     if (start > arr[arr.length - 1][1])
 139         arr.push([start, end]);
 140     return arr;
 141 }
 142
 143
 144 provide("array");