DevTools: Replace binarySearch with lowerBound and upperBound functions
This allows to avoid index-mapping-to-negative-axis-trick in
binarySearch and its usages.
It also makes insertionIndexForObjectInListSortedByFunction to work in
O(log(n)) time instead of O(n).
R=caseq@chromium.org
Review URL: https://codereview.chromium.org/18828002
git-svn-id: svn://svn.chromium.org/blink/trunk@153679 bbb929c8-8fbe-4397-9dbb-9b2b20218538
diff --git a/LayoutTests/inspector/utilities-expected.txt b/LayoutTests/inspector/utilities-expected.txt
index 45f26b9..2bf8bf4 100644
--- a/LayoutTests/inspector/utilities-expected.txt
+++ b/LayoutTests/inspector/utilities-expected.txt
@@ -3,6 +3,10 @@
Running: binaryIndexOfTest
+Running: lowerBoundTest
+
+Running: upperBoundTest
+
Running: qselectTest
Array: []
Reference: {}
diff --git a/LayoutTests/inspector/utilities.html b/LayoutTests/inspector/utilities.html
index 013eb0d..d38fc8d 100644
--- a/LayoutTests/inspector/utilities.html
+++ b/LayoutTests/inspector/utilities.html
@@ -16,14 +16,14 @@
[-100, -50, 0, 50, 100],
[-100, -14, -13, -12, -11, -10, -1]
];
-
+
function testArray(array)
{
function comparator(a, b)
{
return a < b ? -1 : (a > b ? 1 : 0);
}
-
+
for (var i = -100; i <= 100; ++i) {
var reference = array.indexOf(i);
var actual = array.binaryIndexOf(i, comparator);
@@ -31,12 +31,72 @@
}
return true;
}
-
+
for (var i = 0, l = testArrays.length; i < l; ++i)
testArray(testArrays[i]);
next();
},
+ function lowerBoundTest(next)
+ {
+ var testArrays = [
+ [],
+ [1],
+ [-1, -1, 0, 0, 0, 0, 2, 3, 4, 4, 4, 7, 9, 9, 9]
+ ];
+
+ function testArray(array, useComparator)
+ {
+ function comparator(a, b)
+ {
+ return a < b ? -1 : (a > b ? 1 : 0);
+ }
+
+ for (var value = -2; value <= 12; ++value) {
+ var index = useComparator ? array.lowerBound(value, comparator) : array.lowerBound(value);
+ InspectorTest.assertTrue(0 <= index && index <= array.length, "index is within bounds");
+ InspectorTest.assertTrue(index === 0 || array[index - 1] < value, "array[index - 1] < value");
+ InspectorTest.assertTrue(index === array.length || array[index] >= value, "array[index] >= value");
+ }
+ }
+
+ for (var i = 0, l = testArrays.length; i < l; ++i) {
+ testArray(testArrays[i], false);
+ testArray(testArrays[i], true);
+ }
+ next();
+ },
+
+ function upperBoundTest(next)
+ {
+ var testArrays = [
+ [],
+ [1],
+ [-1, -1, 0, 0, 0, 0, 2, 3, 4, 4, 4, 7, 9, 9, 9]
+ ];
+
+ function testArray(array, useComparator)
+ {
+ function comparator(a, b)
+ {
+ return a < b ? -1 : (a > b ? 1 : 0);
+ }
+
+ for (var value = -2; value <= 12; ++value) {
+ var index = useComparator ? array.upperBound(value, comparator) : array.upperBound(value);
+ InspectorTest.assertTrue(0 <= index && index <= array.length, "index is within bounds");
+ InspectorTest.assertTrue(index === 0 || array[index - 1] <= value, "array[index - 1] <= value");
+ InspectorTest.assertTrue(index === array.length || array[index] > value, "array[index] > value");
+ }
+ }
+
+ for (var i = 0, l = testArrays.length; i < l; ++i) {
+ testArray(testArrays[i], false);
+ testArray(testArrays[i], true);
+ }
+ next();
+ },
+
function qselectTest(next)
{
var testArrays = [
diff --git a/Source/devtools/front_end/DefaultTextEditor.js b/Source/devtools/front_end/DefaultTextEditor.js
index 9783478..93abe95 100644
--- a/Source/devtools/front_end/DefaultTextEditor.js
+++ b/Source/devtools/front_end/DefaultTextEditor.js
@@ -1429,7 +1429,7 @@
return 0;
return value - object.startColumn;
}
- var index = binarySearch(column, highlight.ranges, compare);
+ var index = highlight.ranges.binaryIndexOf(column, compare);
if (index >= 0) {
var range = highlight.ranges[index];
return {
diff --git a/Source/devtools/front_end/MemoryStatistics.js b/Source/devtools/front_end/MemoryStatistics.js
index 743fa1f..9ca0ac2 100644
--- a/Source/devtools/front_end/MemoryStatistics.js
+++ b/Source/devtools/front_end/MemoryStatistics.js
@@ -264,18 +264,12 @@
{
return value - sample.time;
}
- var firstIndex = binarySearch(start, this._counters, comparator);
- var lastIndex = binarySearch(end, this._counters, comparator);
- if (firstIndex < 0)
- firstIndex = Math.max(0, -firstIndex - 2);
- if (lastIndex < 0)
- lastIndex = Math.min(-lastIndex - 1, this._counters.length - 1);
// Maximum index of element whose time <= start.
- this._minimumIndex = firstIndex;
+ this._minimumIndex = Number.constrain(this._counters.upperBound(start, comparator) - 1, 0, this._counters.length - 1);
// Minimum index of element whose time >= end.
- this._maximumIndex = lastIndex;
+ this._maximumIndex = Number.constrain(this._counters.lowerBound(end, comparator), 0, this._counters.length - 1);
// Current window bounds.
this._minTime = start;
diff --git a/Source/devtools/front_end/externs.js b/Source/devtools/front_end/externs.js
index a19f206..28c0480 100644
--- a/Source/devtools/front_end/externs.js
+++ b/Source/devtools/front_end/externs.js
@@ -87,8 +87,18 @@
/** @param {boolean=} onlyFirst */
Array.prototype.remove = function(obj, onlyFirst) {}
Array.prototype.keySet = function() {}
-/** @return {number} */
-Array.prototype.upperBound = function(anchor) {}
+/**
+ * @param {*} object
+ * @param {function(*,*):number=} comparator
+ * @return {number}
+ */
+Array.prototype.lowerBound = function(object, comparator) {}
+/**
+ * @param {*} object
+ * @param {function(*,*):number=} comparator
+ * @return {number}
+ */
+Array.prototype.upperBound = function(object, comparator) {}
/** @return {number} */
Array.prototype.binaryIndexOf = function(anchor) {}
Array.prototype.sortRange = function(comparator, leftBound, rightBound, k) {}
diff --git a/Source/devtools/front_end/utilities.js b/Source/devtools/front_end/utilities.js
index f94e3b9..98ca021 100644
--- a/Source/devtools/front_end/utilities.js
+++ b/Source/devtools/front_end/utilities.js
@@ -330,30 +330,6 @@
}
});
-Object.defineProperty(Array.prototype, "upperBound",
-{
- /**
- * @param {number} value
- * @return {number}
- * @this {Array.<number>}
- */
- value: function(value)
- {
- var first = 0;
- var count = this.length;
- while (count > 0) {
- var step = count >> 1;
- var middle = first + step;
- if (value >= this[middle]) {
- first = middle + 1;
- count -= step + 1;
- } else
- count = step;
- }
- return first;
- }
-});
-
Object.defineProperty(Array.prototype, "rotate",
{
/**
@@ -470,45 +446,84 @@
}
});
-/**
- * @param {*} object
- * @param {Array.<*>} array
- * @param {function(*, *): number} comparator
- * @return {number}
- */
-function binarySearch(object, array, comparator)
+Object.defineProperty(Array.prototype, "lowerBound",
{
- var first = 0;
- var last = array.length - 1;
-
- while (first <= last) {
- var mid = (first + last) >> 1;
- var c = comparator(object, array[mid]);
- if (c > 0)
- first = mid + 1;
- else if (c < 0)
- last = mid - 1;
- else
- return mid;
+ /**
+ * Return index of the leftmost element that is equal or greater
+ * than the specimen object. If there's no such element (i.e. all
+ * elements are smaller than the specimen) returns array.length.
+ * The function works for sorted array.
+ *
+ * @this {Array.<*>}
+ * @param {*} object
+ * @param {function(*,*):number=} comparator
+ * @return {number}
+ */
+ value: function(object, comparator)
+ {
+ function defaultComparator(a, b)
+ {
+ return a - b;
+ }
+ comparator = comparator || defaultComparator;
+ var l = 0;
+ var r = this.length;
+ while (l < r) {
+ var m = (l + r) >> 1;
+ if (comparator(object, this[m]) > 0)
+ l = m + 1;
+ else
+ r = m;
+ }
+ return r;
}
+});
- // Return the nearest lesser index negated minus 2, i.e.:
- // "-1" means "-1", "-2" means "0, "-3" means "1", etc.
- return -(first + 1);
-}
+Object.defineProperty(Array.prototype, "upperBound",
+{
+ /**
+ * Return index of the leftmost element that is greater
+ * than the specimen object. If there's no such element (i.e. all
+ * elements are smaller than the specimen) returns array.length.
+ * The function works for sorted array.
+ *
+ * @this {Array.<*>}
+ * @param {*} object
+ * @param {function(*,*):number=} comparator
+ * @return {number}
+ */
+ value: function(object, comparator)
+ {
+ function defaultComparator(a, b)
+ {
+ return a - b;
+ }
+ comparator = comparator || defaultComparator;
+ var l = 0;
+ var r = this.length;
+ while (l < r) {
+ var m = (l + r) >> 1;
+ if (comparator(object, this[m]) >= 0)
+ l = m + 1;
+ else
+ r = m;
+ }
+ return r;
+ }
+});
Object.defineProperty(Array.prototype, "binaryIndexOf",
{
/**
- * @param {*} value
- * @param {function(*, *): number} comparator
- * @return {number}
* @this {Array.<*>}
+ * @param {*} value
+ * @param {function(*,*):number} comparator
+ * @return {number}
*/
value: function(value, comparator)
{
- var result = binarySearch(value, this, comparator);
- return result >= 0 ? result : -1;
+ var index = this.lowerBound(value, comparator);
+ return index < this.length && comparator(value, this[index]) === 0 ? index : -1;
}
});
@@ -541,30 +556,18 @@
});
/**
- * @param {*} anObject
- * @param {Array.<*>} aList
- * @param {function(*, *)} aFunction
+ * @param {*} object
+ * @param {Array.<*>} list
+ * @param {function(*,*):number=} comparator
* @param {boolean=} insertionIndexAfter
* @return {number}
*/
-function insertionIndexForObjectInListSortedByFunction(anObject, aList, aFunction, insertionIndexAfter)
+function insertionIndexForObjectInListSortedByFunction(object, list, comparator, insertionIndexAfter)
{
- var index = binarySearch(anObject, aList, aFunction);
- if (index < 0) {
- // See binarySearch implementation.
- return -index - 1;
- }
-
- if (!insertionIndexAfter) {
- // Return the first occurence of an item in the list.
- while (index > 0 && aFunction(anObject, aList[index - 1]) === 0)
- index--;
- return index;
- }
- // Return the last occurence of an item in the list.
- while (index < aList.length && aFunction(anObject, aList[index]) === 0)
- index++;
- return index;
+ if (insertionIndexAfter)
+ return list.upperBound(object, comparator);
+ else
+ return list.lowerBound(object, comparator);
}
/**
