Home | History | Annotate | Download | only in base 
      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 base.exportTo('base', 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   return {
    171     findLowIndexInSortedArray: findLowIndexInSortedArray,
    172     findLowIndexInSortedIntervals: findLowIndexInSortedIntervals,
    173     iterateOverIntersectingIntervals: iterateOverIntersectingIntervals,
    174     getIntersectingIntervals: getIntersectingIntervals
    175   };
    176 });
    177