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

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: tracing/tracing/base/sorted_array_utils.html

Issue 2771723003: [tracing] Move math utilities from base into their own subdirectory (attempt 2) (Closed)
Patch Set: rebase Created 3 years, 9 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 side-by-side diff with in-line comments
Download patch
« no previous file with comments | « tracing/tracing/base/sinebow_color_generator.html ('k') | tracing/tracing/base/sorted_array_utils_test.html » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: tracing/tracing/base/sorted_array_utils.html
diff --git a/tracing/tracing/base/sorted_array_utils.html b/tracing/tracing/base/sorted_array_utils.html
deleted file mode 100644
index 7ba5e1c70b2d66738fbb6f30e3ed531de7d6d6aa..0000000000000000000000000000000000000000
--- a/tracing/tracing/base/sorted_array_utils.html
+++ /dev/null
@@ -1,331 +0,0 @@
-<!DOCTYPE html>
-<!--
-Copyright (c) 2014 The Chromium Authors. All rights reserved.
-Use of this source code is governed by a BSD-style license that can be
-found in the LICENSE file.
--->
-<link rel="import" href="/tracing/base/base.html">
-<script>
-'use strict';
-
-/**
- * @fileoverview Helper functions for doing intersections and iteration
- * over sorted arrays and intervals.
- *
- */
-tr.exportTo('tr.b', function() {
- /**
- * Finds the first index in the array whose value is >= loVal.
- *
- * The key for the search is defined by the mapFn. This array must
- * be prearranged such that ary.map(mapFn) would also be sorted in
- * ascending order.
- *
- * @param {Array} ary An array of arbitrary objects.
- * @param {function():*} mapFn Callback that produces a key value
- * from an element in ary.
- * @param {number} loVal Value for which to search.
- * @return {Number} Offset o into ary where all ary[i] for i <= o
- * are < loVal, or ary.length if loVal is greater than all elements in
- * the array.
- */
- function findLowIndexInSortedArray(ary, mapFn, loVal) {
- if (ary.length === 0)
- return 1;
-
- var low = 0;
- var high = ary.length - 1;
- var i;
- var comparison;
- var hitPos = -1;
- while (low <= high) {
- i = Math.floor((low + high) / 2);
- comparison = mapFn(ary[i]) - loVal;
- if (comparison < 0) {
- low = i + 1; continue;
- } else if (comparison > 0) {
- high = i - 1; continue;
- } else {
- hitPos = i;
- high = i - 1;
- }
- }
- // return where we hit, or failing that the low pos
- return hitPos !== -1 ? hitPos : low;
- }
-
- // From devtools/front_end/platform/utilities.js upperBound
- function findHighIndexInSortedArray(ary, mapFn, loVal, hiVal) {
- var lo = loVal || 0;
- var hi = hiVal !== undefined ? hiVal : ary.length;
- while (lo < hi) {
- var mid = (lo + hi) >> 1;
- if (mapFn(ary[mid]) >= 0)
- lo = mid + 1;
- else
- hi = mid;
- }
- return hi;
- }
-
- /**
- * Finds an index in an array of intervals that either intersects
- * the provided loVal, or if no intersection is found, -1 or ary.length.
- *
- * The array of intervals is defined implicitly via two mapping functions
- * over the provided ary. mapLoFn determines the lower value of the interval,
- * mapWidthFn the width. Intersection is lower-inclusive, e.g. [lo,lo+w).
- *
- * The array of intervals formed by this mapping must be non-overlapping and
- * sorted in ascending order by loVal.
- *
- * @param {Array} ary An array of objects that can be converted into sorted
- * nonoverlapping ranges [x,y) using the mapLoFn and mapWidth.
- * @param {function():*} mapLoFn Callback that produces the low value for the
- * interval represented by an element in the array.
- * @param {function():*} mapWidthFn Callback that produces the width for the
- * interval represented by an element in the array.
- * @param {number} loVal The low value for the search.
- * @return {Number} An index in the array that intersects or is first-above
- * loVal, -1 if none found and loVal is below than all the intervals,
- * ary.length if loVal is greater than all the intervals.
- */
- function findIndexInSortedIntervals(ary, mapLoFn, mapWidthFn, loVal) {
- var first = findLowIndexInSortedArray(ary, mapLoFn, loVal);
- if (first === 0) {
- if (loVal >= mapLoFn(ary[0]) &&
- loVal < mapLoFn(ary[0]) + mapWidthFn(ary[0], 0))
- return 0;
- return -1;
- }
-
- if (first < ary.length) {
- if (loVal >= mapLoFn(ary[first]) &&
- loVal < mapLoFn(ary[first]) + mapWidthFn(ary[first], first))
- return first;
- if (loVal >= mapLoFn(ary[first - 1]) &&
- loVal < mapLoFn(ary[first - 1]) +
- mapWidthFn(ary[first - 1], first - 1))
- return first - 1;
- return ary.length;
- }
-
- if (first === ary.length) {
- if (loVal >= mapLoFn(ary[first - 1]) &&
- loVal < mapLoFn(ary[first - 1]) +
- mapWidthFn(ary[first - 1], first - 1))
- return first - 1;
- return ary.length;
- }
-
- return ary.length;
- }
-
- /**
- * Finds an index in an array of sorted closed intervals that either
- * intersects the provided val, or if no intersection is found, -1 or
- * ary.length.
- *
- * The array of intervals is defined implicitly via two mapping functions
- * over the provided ary. mapLoFn determines the lower value of the interval,
- * mapHiFn the high. Intersection is closed, e.g. [lo,hi], unlike with
- * findIndexInSortedIntervals, which is right-open.
- *
- * The array of intervals formed by this mapping must be non-overlapping, and
- * sorted in ascending order by val.
- *
- * @param {Array} ary An array of objects that can be converted into sorted
- * nonoverlapping ranges [x,y) using the mapLoFn and mapWidth.
- * @param {function():*} mapLoFn Callback that produces the low value for the
- * interval represented by an element in the array.
- * @param {function():*} mapHiFn Callback that produces the high for the
- * interval represented by an element in the array.
- * @param {number} val The value for the search.
- * @return {Number} An index in the array that intersects or is first-above
- * val, -1 if none found and val is below than all the intervals,
- * ary.length if val is greater than all the intervals.
- */
- function findIndexInSortedClosedIntervals(ary, mapLoFn, mapHiFn, val) {
- var i = findLowIndexInSortedArray(ary, mapLoFn, val);
- if (i === 0) {
- if (val >= mapLoFn(ary[0], 0) &&
- val <= mapHiFn(ary[0], 0))
- return 0;
- return -1;
- }
-
- if (i < ary.length) {
- if (val >= mapLoFn(ary[i - 1], i - 1) &&
- val <= mapHiFn(ary[i - 1], i - 1))
- return i - 1;
- if (val >= mapLoFn(ary[i], i) &&
- val <= mapHiFn(ary[i], i))
- return i;
- return ary.length;
- }
-
- if (i === ary.length) {
- if (val >= mapLoFn(ary[i - 1], i - 1) &&
- val <= mapHiFn(ary[i - 1], i - 1))
- return i - 1;
- return ary.length;
- }
-
- return ary.length;
- }
-
- /**
- * Calls cb for all intervals in the implicit array of intervals
- * defnied by ary, mapLoFn and mapHiFn that intersect the range
- * [loVal,hiVal)
- *
- * This function uses the same scheme as findLowIndexInSortedArray
- * to define the intervals. The same restrictions on sortedness and
- * non-overlappingness apply.
- *
- * @param {Array} ary An array of objects that can be converted into sorted
- * nonoverlapping ranges [x,y) using the mapLoFn and mapWidth.
- * @param {function():*} mapLoFn Callback that produces the low value for the
- * interval represented by an element in the array.
- * @param {function():*} mapWidthFn Callback that produces the width for the
- * interval represented by an element in the array.
- * @param {number} loVal The low value for the search, inclusive.
- * @param {number} hiVal The high value for the search, non inclusive.
- * @param {function():*} cb The function to run for intersecting intervals.
- */
- function iterateOverIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal,
- hiVal, cb) {
- if (ary.length === 0)
- return;
-
- if (loVal > hiVal) return;
-
- var i = findLowIndexInSortedArray(ary, mapLoFn, loVal);
- if (i === -1) {
- return;
- }
- if (i > 0) {
- var hi = mapLoFn(ary[i - 1]) + mapWidthFn(ary[i - 1], i - 1);
- if (hi >= loVal) {
- cb(ary[i - 1], i - 1);
- }
- }
- if (i === ary.length) {
- return;
- }
-
- for (var n = ary.length; i < n; i++) {
- var lo = mapLoFn(ary[i]);
- if (lo >= hiVal)
- break;
- cb(ary[i], i);
- }
- }
-
- /**
- * Non iterative version of iterateOverIntersectingIntervals.
- *
- * @return {Array} Array of elements in ary that intersect loVal, hiVal.
- */
- function getIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal, hiVal) {
- var tmp = [];
- iterateOverIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal, hiVal,
- function(d) {
- tmp.push(d);
- });
- return tmp;
- }
-
- /**
- * Finds the element in the array whose value is closest to |val|.
- *
- * The same restrictions on sortedness as for findLowIndexInSortedArray apply.
- *
- * @param {Array} ary An array of arbitrary objects.
- * @param {function():*} mapFn Callback that produces a key value
- * from an element in ary.
- * @param {number} val Value for which to search.
- * @param {number} maxDiff Maximum allowed difference in value between |val|
- * and an element's value.
- * @return {object} Object in the array whose value is closest to |val|, or
- * null if no object is within range.
- */
- function findClosestElementInSortedArray(ary, mapFn, val, maxDiff) {
- if (ary.length === 0)
- return null;
-
- var aftIdx = findLowIndexInSortedArray(ary, mapFn, val);
- var befIdx = aftIdx > 0 ? aftIdx - 1 : 0;
-
- if (aftIdx === ary.length)
- aftIdx -= 1;
-
- var befDiff = Math.abs(val - mapFn(ary[befIdx]));
- var aftDiff = Math.abs(val - mapFn(ary[aftIdx]));
-
- if (befDiff > maxDiff && aftDiff > maxDiff)
- return null;
-
- var idx = befDiff < aftDiff ? befIdx : aftIdx;
- return ary[idx];
- }
-
- /**
- * Finds the closest interval in the implicit array of intervals
- * defined by ary, mapLoFn and mapHiFn.
- *
- * This function uses the same scheme as findLowIndexInSortedArray
- * to define the intervals. The same restrictions on sortedness and
- * non-overlappingness apply.
- *
- * @param {Array} ary An array of objects that can be converted into sorted
- * nonoverlapping ranges [x,y) using the mapLoFn and mapHiFn.
- * @param {function():*} mapLoFn Callback that produces the low value for the
- * interval represented by an element in the array.
- * @param {function():*} mapHiFn Callback that produces the high for the
- * interval represented by an element in the array.
- * @param {number} val The value for the search.
- * @param {number} maxDiff Maximum allowed difference in value between |val|
- * and an interval's low or high value.
- * @return {interval} Interval in the array whose high or low value is closest
- * to |val|, or null if no interval is within range.
- */
- function findClosestIntervalInSortedIntervals(ary, mapLoFn, mapHiFn, val,
- maxDiff) {
- if (ary.length === 0)
- return null;
-
- var idx = findLowIndexInSortedArray(ary, mapLoFn, val);
- if (idx > 0)
- idx -= 1;
-
- var hiInt = ary[idx];
- var loInt = hiInt;
-
- if (val > mapHiFn(hiInt) && idx + 1 < ary.length)
- loInt = ary[idx + 1];
-
- var loDiff = Math.abs(val - mapLoFn(loInt));
- var hiDiff = Math.abs(val - mapHiFn(hiInt));
-
- if (loDiff > maxDiff && hiDiff > maxDiff)
- return null;
-
- if (loDiff < hiDiff)
- return loInt;
-
- return hiInt;
- }
-
- return {
- findLowIndexInSortedArray,
- findHighIndexInSortedArray,
- findIndexInSortedIntervals,
- findIndexInSortedClosedIntervals,
- iterateOverIntersectingIntervals,
- getIntersectingIntervals,
- findClosestElementInSortedArray,
- findClosestIntervalInSortedIntervals,
- };
-});
-</script>
« no previous file with comments | « tracing/tracing/base/sinebow_color_generator.html ('k') | tracing/tracing/base/sorted_array_utils_test.html » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698