Home | History | Annotate | Download | only in src 
      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 
      6 /**
      7  * @fileoverview Helper functions for doing intersections and iteration
      8  * over sorted arrays and intervals.
      9  *
     10  */
     11 base.exportTo('tracing', function() {
     12   /**
     13    * Finds the first index in the array whose value is >= loVal.
     14    *
     15    * The key for the search is defined by the mapFn. This array must
     16    * be prearranged such that ary.map(mapFn) would also be sorted in
     17    * ascending order.
     18    *
     19    * @param {Array} ary An array of arbitrary objects.
     20    * @param {function():*} mapFn Callback that produces a key value
     21    *     from an element in ary.
     22    * @param {number} loVal Value for which to search.
     23    * @return {Number} Offset o into ary where all ary[i] for i <= o
     24    *     are < loVal, or ary.length if loVal is greater than all elements in
     25    *     the array.
     26    */
     27   function findLowIndexInSortedArray(ary, mapFn, loVal) {
     28     if (ary.length == 0)
     29       return 1;
     30 
     31     var low = 0;
     32     var high = ary.length - 1;
     33     var i, comparison;
     34     var hitPos = -1;
     35     while (low <= high) {
     36       i = Math.floor((low + high) / 2);
     37       comparison = mapFn(ary[i]) - loVal;
     38       if (comparison < 0) {
     39         low = i + 1; continue;
     40       } else if (comparison > 0) {
     41         high = i - 1; continue;
     42       } else {
     43         hitPos = i;
     44         high = i - 1;
     45       }
     46     }
     47     // return where we hit, or failing that the low pos
     48     return hitPos != -1 ? hitPos : low;
     49   }
     50 
     51   /**
     52    * Finds an index in an array of intervals that either
     53    * intersects the provided loVal, or if no intersection is found,
     54    * the index of the first interval whose start is > loVal.
     55    *
     56    * The array of intervals is defined implicitly via two mapping functions
     57    * over the provided ary. mapLoFn determines the lower value of the interval,
     58    * mapWidthFn the width. Intersection is lower-inclusive, e.g. [lo,lo+w).
     59    *
     60    * The array of intervals formed by this mapping must be non-overlapping and
     61    * sorted in ascending order by loVal.
     62    *
     63    * @param {Array} ary An array of objects that can be converted into sorted
     64    *     nonoverlapping ranges [x,y) using the mapLoFn and mapWidth.
     65    * @param {function():*} mapLoFn Callback that produces the low value for the
     66    *     interval represented by an  element in the array.
     67    * @param {function():*} mapLoFn Callback that produces the width for the
     68    *     interval represented by an  element in the array.
     69    * @param {number} loVal The low value for the search.
     70    * @return {Number} An index in the array that intersects or is first-above
     71    *     loVal, -1 if none found and loVal is below than all the intervals,
     72    *     ary.length if loVal is greater than all the intervals.
     73    */
     74   function findLowIndexInSortedIntervals(ary, mapLoFn, mapWidthFn, loVal) {
     75     var first = findLowIndexInSortedArray(ary, mapLoFn, loVal);
     76     if (first == 0) {
     77       if (loVal >= mapLoFn(ary[0]) &&
     78           loVal < mapLoFn(ary[0] + mapWidthFn(ary[0]))) {
     79         return 0;
     80       } else {
     81         return -1;
     82       }
     83     } else if (first <= ary.length &&
     84                loVal >= mapLoFn(ary[first - 1]) &&
     85                loVal < mapLoFn(ary[first - 1]) + mapWidthFn(ary[first - 1])) {
     86       return first - 1;
     87     } else {
     88       return ary.length;
     89     }
     90   }
     91 
     92   /**
     93    * Calls cb for all intervals in the implicit array of intervals
     94    * defnied by ary, mapLoFn and mapHiFn that intersect the range
     95    * [loVal,hiVal)
     96    *
     97    * This function uses the same scheme as findLowIndexInSortedArray
     98    * to define the intervals. The same restrictions on sortedness and
     99    * non-overlappingness apply.
    100    *
    101    * @param {Array} ary An array of objects that can be converted into sorted
    102    * nonoverlapping ranges [x,y) using the mapLoFn and mapWidth.
    103    * @param {function():*} mapLoFn Callback that produces the low value for the
    104    * interval represented by an element in the array.
    105    * @param {function():*} mapLoFn Callback that produces the width for the
    106    * interval represented by an element in the array.
    107    * @param {number} The low value for the search, inclusive.
    108    * @param {number} loVal The high value for the search, non inclusive.
    109    * @param {function():*} cb The function to run for intersecting intervals.
    110    */
    111   function iterateOverIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal,
    112                                             hiVal, cb) {
    113     if (ary.length == 0)
    114       return;
    115 
    116     if (loVal > hiVal) return;
    117 
    118     var i = findLowIndexInSortedArray(ary, mapLoFn, loVal);
    119     if (i == -1) {
    120       return;
    121     }
    122     if (i > 0) {
    123       var hi = mapLoFn(ary[i - 1]) + mapWidthFn(ary[i - 1]);
    124       if (hi >= loVal) {
    125         cb(ary[i - 1]);
    126       }
    127     }
    128     if (i == ary.length) {
    129       return;
    130     }
    131 
    132     for (var n = ary.length; i < n; i++) {
    133       var lo = mapLoFn(ary[i]);
    134       if (lo >= hiVal)
    135         break;
    136       cb(ary[i]);
    137     }
    138   }
    139 
    140   /**
    141    * Non iterative version of iterateOverIntersectingIntervals.
    142    *
    143    * @return {Array} Array of elements in ary that intersect loVal, hiVal.
    144    */
    145   function getIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal, hiVal) {
    146     var tmp = [];
    147     iterateOverIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal, hiVal,
    148                                      function(d) {
    149                                        tmp.push(d);
    150                                      });
    151     return tmp;
    152   }
    153 
    154   return {
    155     findLowIndexInSortedArray: findLowIndexInSortedArray,
    156     findLowIndexInSortedIntervals: findLowIndexInSortedIntervals,
    157     iterateOverIntersectingIntervals: iterateOverIntersectingIntervals,
    158     getIntersectingIntervals: getIntersectingIntervals
    159   };
    160 });
    161