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