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