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