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  * remove_duplicates_filter returns a function that can be used in
  34  * Array.filter.  It removes duplicates.  Optional argument cmp is a
  35  * comparison function to test equality.  The default comparison function
  36  * tests equality of the string representation of the objects, making it
  37  * unsuitable for use filtering a list of objects of compound data types.
  38  */
  39 function remove_duplicates_filter (cmp) {
  40     if (cmp) {
  41         let acc = [];
  42         return function (x) {
  43             if (acc.some(function (y) cmp(x, y)))
  44                 return false;
  45             acc.push(x);
  46             return true;
  47         };
  48     }
  49     let acc = {};
  50     return function (x) {
  51         if (acc[x]) return false;
  52         acc[x] = 1;
  53         return true;
  54     };
  55 }
  56
  57
  58 /**
  59  * Given an array, switches places on the subarrays at index i1 to i2 and j1 to
  60  * j2. Leaves the rest of the array unchanged.
  61  */
  62 function switch_subarrays (arr, i1, i2, j1, j2) {
  63     return arr.slice(0, i1) +
  64         arr.slice(j1, j2) +
  65         arr.slice(i2, j1) +
  66         arr.slice(i1, i2) +
  67         arr.slice(j2, arr.length);
  68 }
  69
  70
  71 /**
  72  * splice_ranges: Given an ordered array of non-overlapping ranges,
  73  * represented as elements of [start, end], insert a new range into the
  74  * array, extending, replacing, or merging existing ranges as needed.
  75  * Mutates `arr' in place, but returns the reference to it.
  76  *
  77  * Examples:
  78  *
  79  * splice_range([[1,3],[4,6], 5, 8)
  80  *  => [[1,3],[4,8]]
  81  *
  82  * splice_range([[1,3],[4,6],[7,10]], 2, 8)
  83  *  => [[1,10]]
  84  */
  85 function splice_range (arr, start, end) {
  86     for (var i = 0; i < arr.length; ++i) {
  87         let [n,m] = arr[i];
  88         if (start > m)
  89             continue;
  90         if (end < n) {
  91             arr.splice(i, 0, [start, end]);
  92             break;
  93         }
  94         if (start < n)
  95             arr[i][0] = start;
  96
  97         if (end >= n) {
  98             /*
  99              * The range we are inserting overlaps the current
 100              * range. We need to scan right to see if it also contains any other
 101              * ranges entirely, and remove them if necessary.
 102              */
 103             var j = i;
 104             while (j < arr.length && end >= arr[j][0])
 105                 j++;
 106             j--;
 107             arr[i][1] = Math.max(end, arr[j][1]);
 108             arr.splice(i + 1, j - i);
 109             break;
 110         }
 111     }
 112     if (start > arr[arr.length - 1][1])
 113         arr.push([start, end]);
 114     return arr;
 115 }
 116
 117 provide("array");