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