modules/array.js

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