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'use strict'; 6 7/** 8 * @fileoverview Helper functions for doing intersections and iteration 9 * over sorted arrays and intervals. 10 * 11 */ 12base.exportTo('base', function() { 13 /** 14 * Finds the first index in the array whose value is >= loVal. 15 * 16 * The key for the search is defined by the mapFn. This array must 17 * be prearranged such that ary.map(mapFn) would also be sorted in 18 * ascending order. 19 * 20 * @param {Array} ary An array of arbitrary objects. 21 * @param {function():*} mapFn Callback that produces a key value 22 * from an element in ary. 23 * @param {number} loVal Value for which to search. 24 * @return {Number} Offset o into ary where all ary[i] for i <= o 25 * are < loVal, or ary.length if loVal is greater than all elements in 26 * the array. 27 */ 28 function findLowIndexInSortedArray(ary, mapFn, loVal) { 29 if (ary.length == 0) 30 return 1; 31 32 var low = 0; 33 var high = ary.length - 1; 34 var i, comparison; 35 var hitPos = -1; 36 while (low <= high) { 37 i = Math.floor((low + high) / 2); 38 comparison = mapFn(ary[i]) - loVal; 39 if (comparison < 0) { 40 low = i + 1; continue; 41 } else if (comparison > 0) { 42 high = i - 1; continue; 43 } else { 44 hitPos = i; 45 high = i - 1; 46 } 47 } 48 // return where we hit, or failing that the low pos 49 return hitPos != -1 ? hitPos : low; 50 } 51 52 /** 53 * Finds an index in an array of intervals that either 54 * intersects the provided loVal, or if no intersection is found, 55 * the index of the first interval whose start is > loVal. 56 * 57 * The array of intervals is defined implicitly via two mapping functions 58 * over the provided ary. mapLoFn determines the lower value of the interval, 59 * mapWidthFn the width. Intersection is lower-inclusive, e.g. [lo,lo+w). 60 * 61 * The array of intervals formed by this mapping must be non-overlapping and 62 * sorted in ascending order by loVal. 63 * 64 * @param {Array} ary An array of objects that can be converted into sorted 65 * nonoverlapping ranges [x,y) using the mapLoFn and mapWidth. 66 * @param {function():*} mapLoFn Callback that produces the low value for the 67 * interval represented by an element in the array. 68 * @param {function():*} mapWidthFn Callback that produces the width for the 69 * interval represented by an element in the array. 70 * @param {number} loVal The low value for the search. 71 * @return {Number} An index in the array that intersects or is first-above 72 * loVal, -1 if none found and loVal is below than all the intervals, 73 * ary.length if loVal is greater than all the intervals. 74 */ 75 function findLowIndexInSortedIntervals(ary, mapLoFn, mapWidthFn, loVal) { 76 var first = findLowIndexInSortedArray(ary, mapLoFn, loVal); 77 if (first == 0) { 78 if (loVal >= mapLoFn(ary[0]) && 79 loVal < mapLoFn(ary[0]) + mapWidthFn(ary[0], 0)) { 80 return 0; 81 } else { 82 return -1; 83 } 84 } else if (first < ary.length) { 85 if (loVal >= mapLoFn(ary[first]) && 86 loVal < mapLoFn(ary[first]) + mapWidthFn(ary[first], first)) { 87 return first; 88 } else if (loVal >= mapLoFn(ary[first - 1]) && 89 loVal < mapLoFn(ary[first - 1]) + 90 mapWidthFn(ary[first - 1], first - 1)) { 91 return first - 1; 92 } else { 93 return ary.length; 94 } 95 } else if (first == ary.length) { 96 if (loVal >= mapLoFn(ary[first - 1]) && 97 loVal < mapLoFn(ary[first - 1]) + 98 mapWidthFn(ary[first - 1], first - 1)) { 99 return first - 1; 100 } else { 101 return ary.length; 102 } 103 } else { 104 return ary.length; 105 } 106 } 107 108 /** 109 * Calls cb for all intervals in the implicit array of intervals 110 * defnied by ary, mapLoFn and mapHiFn that intersect the range 111 * [loVal,hiVal) 112 * 113 * This function uses the same scheme as findLowIndexInSortedArray 114 * to define the intervals. The same restrictions on sortedness and 115 * non-overlappingness apply. 116 * 117 * @param {Array} ary An array of objects that can be converted into sorted 118 * nonoverlapping ranges [x,y) using the mapLoFn and mapWidth. 119 * @param {function():*} mapLoFn Callback that produces the low value for the 120 * interval represented by an element in the array. 121 * @param {function():*} mapLoFn Callback that produces the width for the 122 * interval represented by an element in the array. 123 * @param {number} The low value for the search, inclusive. 124 * @param {number} loVal The high value for the search, non inclusive. 125 * @param {function():*} cb The function to run for intersecting intervals. 126 */ 127 function iterateOverIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal, 128 hiVal, cb) { 129 if (ary.length == 0) 130 return; 131 132 if (loVal > hiVal) return; 133 134 var i = findLowIndexInSortedArray(ary, mapLoFn, loVal); 135 if (i == -1) { 136 return; 137 } 138 if (i > 0) { 139 var hi = mapLoFn(ary[i - 1]) + mapWidthFn(ary[i - 1], i - 1); 140 if (hi >= loVal) { 141 cb(ary[i - 1]); 142 } 143 } 144 if (i == ary.length) { 145 return; 146 } 147 148 for (var n = ary.length; i < n; i++) { 149 var lo = mapLoFn(ary[i]); 150 if (lo >= hiVal) 151 break; 152 cb(ary[i]); 153 } 154 } 155 156 /** 157 * Non iterative version of iterateOverIntersectingIntervals. 158 * 159 * @return {Array} Array of elements in ary that intersect loVal, hiVal. 160 */ 161 function getIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal, hiVal) { 162 var tmp = []; 163 iterateOverIntersectingIntervals(ary, mapLoFn, mapWidthFn, loVal, hiVal, 164 function(d) { 165 tmp.push(d); 166 }); 167 return tmp; 168 } 169 170 return { 171 findLowIndexInSortedArray: findLowIndexInSortedArray, 172 findLowIndexInSortedIntervals: findLowIndexInSortedIntervals, 173 iterateOverIntersectingIntervals: iterateOverIntersectingIntervals, 174 getIntersectingIntervals: getIntersectingIntervals 175 }; 176}); 177