modules/array.js

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