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