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