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 */
11base.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