Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(244)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: tracing/tracing/base/math/sorted_array_utils.html

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

Powered by Google App Engine
This is Rietveld 408576698