src/third_party/trace-viewer/third_party/tvcm/src/tvcm/sorted_array_utils.js

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 'use strict';
   6
   7 /**
   8  * @fileoverview Helper functions for doing intersections and iteration
   9  * over sorted arrays and intervals.
  10  *
  11  */
  12 tvcm.exportTo('tvcm', function() {
  13   /**
  14    * Finds the first index in the array whose value is >= loVal.
  15    *
  16    * The key for the search is defined by the mapFn. This array must
  17    * be prearranged such that ary.map(mapFn) would also be sorted in
  18    * ascending order.
  19    *
  20    * @param {Array} ary An array of arbitrary objects.
  21    * @param {function():*} mapFn Callback that produces a key value
  22    *     from an element in ary.
  23    * @param {number} loVal Value for which to search.
  24    * @return {Number} Offset o into ary where all ary[i] for i <= o
  25    *     are < loVal, or ary.length if loVal is greater than all elements in
  26    *     the array.
  27    */
  28   function findLowIndexInSortedArray(ary, mapFn, loVal) {
  29     if (ary.length == 0)
  30       return 1;
  31
  32     var low = 0;
  33     var high = ary.length - 1;
  34     var i, comparison;
  35     var hitPos = -1;
  36     while (low <= high) {
  37       i = Math.floor((low + high) / 2);
  38       comparison = mapFn(ary[i]) - loVal;
  39       if (comparison < 0) {
  40         low = i + 1; continue;
  41       } else if (comparison > 0) {
  42         high = i - 1; continue;
  43       } else {
  44         hitPos = i;
  45         high = i - 1;
  46       }
  47     }
  48     // return where we hit, or failing that the low pos
  49     return hitPos != -1 ? hitPos : low;
  50   }
  51
  52   /**
  53    * Finds an index in an array of intervals that either
  54    * intersects the provided loVal, or if no intersection is found,
  55    * the index of the first interval whose start is > loVal.
  56    *
  57    * The array of intervals is defined implicitly via two mapping functions
  58    * over the provided ary. mapLoFn determines the lower value of the interval,
  59    * mapWidthFn the width. Intersection is lower-inclusive, e.g. [lo,lo+w).
  60    *
  61    * The array of intervals formed by this mapping must be non-overlapping and
  62    * sorted in ascending order by loVal.
  63    *
  64    * @param {Array} ary An array of objects that can be converted into sorted
  65    *     nonoverlapping ranges [x,y) using the mapLoFn and mapWidth.
  66    * @param {function():*} mapLoFn Callback that produces the low value for the
  67    *     interval represented by an  element in the array.
  68    * @param {function():*} mapWidthFn Callback that produces the width for the
  69    *     interval represented by an  element in the array.
  70    * @param {number} loVal The low value for the search.
  71    * @return {Number} An index in the array that intersects or is first-above
  72    *     loVal, -1 if none found and loVal is below than all the intervals,
  73    *     ary.length if loVal is greater than all the intervals.
  74    */
  75   function findLowIndexInSortedIntervals(ary, mapLoFn, mapWidthFn, loVal) {
  76     var first = findLowIndexInSortedArray(ary, mapLoFn, loVal);
  77     if (first == 0) {
  78       if (loVal >= mapLoFn(ary[0]) &&
  79           loVal < mapLoFn(ary[0]) + mapWidthFn(ary[0], 0)) {
  80         return 0;
  81       } else {
  82         return -1;
  83       }
  84     } else if (first < ary.length) {
  85       if (loVal >= mapLoFn(ary[first]) &&
  86           loVal < mapLoFn(ary[first]) + mapWidthFn(ary[first], first)) {
  87         return first;
  88       } else if (loVal >= mapLoFn(ary[first - 1]) &&
  89                  loVal < mapLoFn(ary[first - 1]) +
  90                  mapWidthFn(ary[first - 1], first - 1)) {
  91         return first - 1;
  92       } else {
  93         return ary.length;
  94       }
  95     } else if (first == ary.length) {
  96       if (loVal >= mapLoFn(ary[first - 1]) &&
  97           loVal < mapLoFn(ary[first - 1]) +
  98           mapWidthFn(ary[first - 1], first - 1)) {
  99         return first - 1;
 100       } else {
 101         return ary.length;
 102       }
 103     } else {
 104       return ary.length;
 105     }
 106   }
 107
 108   /**
 109    * Calls cb for all intervals in the implicit array of intervals
 110    * defnied by ary, mapLoFn and mapHiFn that intersect the range
 111    * [loVal,hiVal)
 112    *
 113    * This function uses the same scheme as findLowIndexInSortedArray
 114    * to define the intervals. The same restrictions on sortedness and
 115    * non-overlappingness apply.
 116    *
 117    * @param {Array} ary An array of objects that can be converted into sorted
 118    * nonoverlapping ranges [x,y) using the mapLoFn and mapWidth.
 119    * @param {function():*} mapLoFn Callback that produces the low value for the
 120    * interval represented by an element in the array.
 121    * @param {function():*} mapLoFn Callback that produces the width for the
 122    * interval represented by an element in the array.
 123    * @param {number} The low value for the search, inclusive.
 124    * @param {number} loVal The high value for the search, non inclusive.
 125    * @param {function():*} cb The function to run for intersecting intervals.
 126    */
 127   function iterateOverIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal,
 128                                             hiVal, cb) {
 129     if (ary.length == 0)
 130       return;
 131
 132     if (loVal > hiVal) return;
 133
 134     var i = findLowIndexInSortedArray(ary, mapLoFn, loVal);
 135     if (i == -1) {
 136       return;
 137     }
 138     if (i > 0) {
 139       var hi = mapLoFn(ary[i - 1]) + mapWidthFn(ary[i - 1], i - 1);
 140       if (hi >= loVal) {
 141         cb(ary[i - 1]);
 142       }
 143     }
 144     if (i == ary.length) {
 145       return;
 146     }
 147
 148     for (var n = ary.length; i < n; i++) {
 149       var lo = mapLoFn(ary[i]);
 150       if (lo >= hiVal)
 151         break;
 152       cb(ary[i]);
 153     }
 154   }
 155
 156   /**
 157    * Non iterative version of iterateOverIntersectingIntervals.
 158    *
 159    * @return {Array} Array of elements in ary that intersect loVal, hiVal.
 160    */
 161   function getIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal, hiVal) {
 162     var tmp = [];
 163     iterateOverIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal, hiVal,
 164                                      function(d) {
 165                                        tmp.push(d);
 166                                      });
 167     return tmp;
 168   }
 169
 170   /**
 171    * Finds the element in the array whose value is closest to |val|.
 172    *
 173    * The same restrictions on sortedness as for findLowIndexInSortedArray apply.
 174    *
 175    * @param {Array} ary An array of arbitrary objects.
 176    * @param {function():*} mapFn Callback that produces a key value
 177    *     from an element in ary.
 178    * @param {number} val Value for which to search.
 179    * @param {number} maxDiff Maximum allowed difference in value between |val|
 180    *     and an element's value.
 181    * @return {object} Object in the array whose value is closest to |val|, or
 182    *     null if no object is within range.
 183    */
 184   function findClosestElementInSortedArray(ary, mapFn, val, maxDiff) {
 185     if (ary.length === 0)
 186       return null;
 187
 188     var aftIdx = findLowIndexInSortedArray(ary, mapFn, val);
 189     var befIdx = aftIdx > 0 ? aftIdx - 1 : 0;
 190
 191     if (aftIdx === ary.length)
 192       aftIdx -= 1;
 193
 194     var befDiff = Math.abs(val - mapFn(ary[befIdx]));
 195     var aftDiff = Math.abs(val - mapFn(ary[aftIdx]));
 196
 197     if (befDiff > maxDiff && aftDiff > maxDiff)
 198       return null;
 199
 200     var idx = befDiff < aftDiff ? befIdx : aftIdx;
 201     return ary[idx];
 202   }
 203
 204   /**
 205    * Finds the closest interval in the implicit array of intervals
 206    * defined by ary, mapLoFn and mapHiFn.
 207    *
 208    * This function uses the same scheme as findLowIndexInSortedArray
 209    * to define the intervals. The same restrictions on sortedness and
 210    * non-overlappingness apply.
 211    *
 212    * @param {Array} ary An array of objects that can be converted into sorted
 213    *     nonoverlapping ranges [x,y) using the mapLoFn and mapHiFn.
 214    * @param {function():*} mapLoFn Callback that produces the low value for the
 215    *     interval represented by an element in the array.
 216    * @param {function():*} mapHiFn Callback that produces the high for the
 217    *     interval represented by an element in the array.
 218    * @param {number} val The value for the search.
 219    * @param {number} maxDiff Maximum allowed difference in value between |val|
 220    *     and an interval's low or high value.
 221    * @return {interval} Interval in the array whose high or low value is closest
 222    *     to |val|, or null if no interval is within range.
 223    */
 224   function findClosestIntervalInSortedIntervals(ary, mapLoFn, mapHiFn, val,
 225                                                 maxDiff) {
 226     if (ary.length === 0)
 227       return null;
 228
 229     var idx = findLowIndexInSortedArray(ary, mapLoFn, val);
 230     if (idx > 0)
 231       idx -= 1;
 232
 233     var hiInt = ary[idx];
 234     var loInt = hiInt;
 235
 236     if (val > mapHiFn(hiInt) && idx + 1 < ary.length)
 237       loInt = ary[idx + 1];
 238
 239     var loDiff = Math.abs(val - mapLoFn(loInt));
 240     var hiDiff = Math.abs(val - mapHiFn(hiInt));
 241
 242     if (loDiff > maxDiff && hiDiff > maxDiff)
 243       return null;
 244
 245     if (loDiff < hiDiff)
 246       return loInt;
 247     else
 248       return hiInt;
 249   }
 250
 251   return {
 252     findLowIndexInSortedArray: findLowIndexInSortedArray,
 253     findLowIndexInSortedIntervals: findLowIndexInSortedIntervals,
 254     iterateOverIntersectingIntervals: iterateOverIntersectingIntervals,
 255     getIntersectingIntervals: getIntersectingIntervals,
 256     findClosestElementInSortedArray: findClosestElementInSortedArray,
 257     findClosestIntervalInSortedIntervals: findClosestIntervalInSortedIntervals
 258   };
 259 });