Diff
Modified: trunk/LayoutTests/ChangeLog (164511 => 164512)
--- trunk/LayoutTests/ChangeLog 2014-02-22 00:05:25 UTC (rev 164511)
+++ trunk/LayoutTests/ChangeLog 2014-02-22 00:10:53 UTC (rev 164512)
@@ -1,3 +1,13 @@
+2014-02-21 Chi Wai Lau <c...@apple.com>
+
+ Web Inspector: Replace binarySearch with lowerBound and upperBound functions
+ https://bugs.webkit.org/show_bug.cgi?id=118609
+
+ Reviewed by Timothy Hatcher.
+
+ * inspector/utilities-expected.txt:
+ * inspector/utilities.html:
+
2014-02-21 Daniel Bates <daba...@apple.com>
[Win] fast/table/col-and-colgroup-offsets.html - offsetHeight differs from Mac results
Modified: trunk/LayoutTests/inspector/utilities-expected.txt (164511 => 164512)
--- trunk/LayoutTests/inspector/utilities-expected.txt 2014-02-22 00:05:25 UTC (rev 164511)
+++ trunk/LayoutTests/inspector/utilities-expected.txt 2014-02-22 00:10:53 UTC (rev 164512)
@@ -3,6 +3,11 @@
Running: binaryIndexOfTest
+Running: lowerBoundTest
+
+Running: upperBoundTest
+
+
Running: qselectTest
Array: []
Reference: {}
Modified: trunk/LayoutTests/inspector/utilities.html (164511 => 164512)
--- trunk/LayoutTests/inspector/utilities.html 2014-02-22 00:05:25 UTC (rev 164511)
+++ trunk/LayoutTests/inspector/utilities.html 2014-02-22 00:10:53 UTC (rev 164512)
@@ -36,6 +36,68 @@
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)
{
@@ -60,13 +122,13 @@
min: sorted[0],
median: sorted[Math.floor(sorted.length / 2)],
max: sorted[sorted.length - 1]
- }
+ };
var actual = {
min: array.slice(0).qselect(0),
median: array.slice(0).qselect(Math.floor(array.length / 2)),
max: array.slice(0).qselect(array.length - 1)
- }
+ };
InspectorTest.addResult("Array: " + JSON.stringify(array));
InspectorTest.addResult("Reference: " + JSON.stringify(reference));
InspectorTest.addResult("Actual: " + JSON.stringify(actual));
Modified: trunk/Source/WebInspectorUI/ChangeLog (164511 => 164512)
--- trunk/Source/WebInspectorUI/ChangeLog 2014-02-22 00:05:25 UTC (rev 164511)
+++ trunk/Source/WebInspectorUI/ChangeLog 2014-02-22 00:10:53 UTC (rev 164512)
@@ -1,3 +1,18 @@
+2014-02-21 Chi Wai Lau <c...@apple.com>
+
+ Web Inspector: Replace binarySearch with lowerBound and upperBound functions
+ https://bugs.webkit.org/show_bug.cgi?id=118609
+
+ Reviewed by Timothy Hatcher.
+
+ This makes insertionIndexForObjectInListSortedByFunction work in O(log(n)) time instead of O(n).
+
+ * UserInterface/BinarySearch.js: Removed.
+ * UserInterface/Main.html:
+ * UserInterface/Utilities.js:
+ * WebInspectorUI.vcxproj/WebInspectorUI.vcxproj:
+ * WebInspectorUI.vcxproj/WebInspectorUI.vcxproj.filters:
+
2014-02-21 Brian Burg <bb...@apple.com>
Web Inspector: animate breakpoint tree elements when probe samples are received
Deleted: trunk/Source/WebInspectorUI/UserInterface/BinarySearch.js (164511 => 164512)
--- trunk/Source/WebInspectorUI/UserInterface/BinarySearch.js 2014-02-22 00:05:25 UTC (rev 164511)
+++ trunk/Source/WebInspectorUI/UserInterface/BinarySearch.js 2014-02-22 00:10:53 UTC (rev 164512)
@@ -1,85 +0,0 @@
-/*
- * Copyright (C) 2011 Google Inc. All rights reserved.
- * Copyright (C) 2007, 2013 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are
- * met:
- *
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above
- * copyright notice, this list of conditions and the following disclaimer
- * in the documentation and/or other materials provided with the
- * distribution.
- * * Neither the name of Google Inc. nor the names of its
- * contributors may be used to endorse or promote products derived from
- * this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-/**
- * @param {*} object
- * @param {Array.<*>} array
- * @param {function(*, *)} comparator
- */
-function binarySearch(object, array, comparator)
-{
- 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 the nearest lesser index, "-1" means "0, "-2" means "1", etc.
- return -(first + 1);
-}
-
-Object.defineProperty(Array.prototype, "binaryIndexOf", { value: function(value, comparator)
-{
- var result = binarySearch(value, this, comparator);
- return result >= 0 ? result : -1;
-}});
-
-/**
- * @param {*} anObject
- * @param {Array.<*>} aList
- * @param {function(*, *)} aFunction
- */
-function insertionIndexForObjectInListSortedByFunction(anObject, aList, aFunction)
-{
- var index = binarySearch(anObject, aList, aFunction);
- if (index < 0)
- // See binarySearch implementation.
- return -index - 1;
- else {
- // Return the first occurance of an item in the list.
- while (index > 0 && aFunction(anObject, aList[index - 1]) === 0)
- index--;
- return index;
- }
-}
-
-function insertObjectIntoSortedArray(value, array, compareFunction)
-{
- array.splice(insertionIndexForObjectInListSortedByFunction(value, array, compareFunction), 0, value);
-}
Modified: trunk/Source/WebInspectorUI/UserInterface/Main.html (164511 => 164512)
--- trunk/Source/WebInspectorUI/UserInterface/Main.html 2014-02-22 00:05:25 UTC (rev 164511)
+++ trunk/Source/WebInspectorUI/UserInterface/Main.html 2014-02-22 00:10:53 UTC (rev 164512)
@@ -215,7 +215,6 @@
<script src=""
<script src=""
<script src=""
- <script src=""
<script src=""
<script src=""
<script src=""
Modified: trunk/Source/WebInspectorUI/UserInterface/Utilities.js (164511 => 164512)
--- trunk/Source/WebInspectorUI/UserInterface/Utilities.js 2014-02-22 00:05:25 UTC (rev 164511)
+++ trunk/Source/WebInspectorUI/UserInterface/Utilities.js 2014-02-22 00:10:53 UTC (rev 164512)
@@ -426,25 +426,6 @@
}
});
-Object.defineProperty(Array.prototype, "upperBound",
-{
- 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(String.prototype, "trimMiddle",
{
value: function(maxLength)
@@ -954,3 +935,78 @@
return new RegExp(regexString, regExpFlags);
}
+
+Object.defineProperty(Array.prototype, "lowerBound",
+{
+ // 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.
+ 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, "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.
+ 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",
+{
+ value: function(value, comparator)
+ {
+ var index = this.lowerBound(value, comparator);
+ return index < this.length && comparator(value, this[index]) === 0 ? index : -1;
+ }
+});
+
+function insertionIndexForObjectInListSortedByFunction(object, list, comparator, insertionIndexAfter)
+{
+ if (insertionIndexAfter) {
+ return list.upperBound(object, comparator);
+ } else {
+ return list.lowerBound(object, comparator);
+ }
+}
+
+function insertObjectIntoSortedArray(object, array, comparator)
+{
+ array.splice(insertionIndexForObjectInListSortedByFunction(object, array, comparator), 0, object);
+}
Modified: trunk/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj (164511 => 164512)
--- trunk/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj 2014-02-22 00:05:25 UTC (rev 164511)
+++ trunk/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj 2014-02-22 00:10:53 UTC (rev 164512)
@@ -236,7 +236,6 @@
<None Include="..\UserInterface\ApplicationCacheManifest.js" />
<None Include="..\UserInterface\ApplicationCacheManifestTreeElement.js" />
<None Include="..\UserInterface\ApplicationCacheObserver.js" />
- <None Include="..\UserInterface\BinarySearch.js" />
<None Include="..\UserInterface\BlankStylePropertiesSection.js" />
<None Include="..\UserInterface\BottomUpProfileDataGridTree.js" />
<None Include="..\UserInterface\BoxModelDetailsSectionRow.css" />
Modified: trunk/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj.filters (164511 => 164512)
--- trunk/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj.filters 2014-02-22 00:05:25 UTC (rev 164511)
+++ trunk/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj.filters 2014-02-22 00:10:53 UTC (rev 164512)
@@ -69,9 +69,6 @@
<None Include="..\UserInterface\ApplicationCacheObserver.js">
<Filter>UserInterface</Filter>
</None>
- <None Include="..\UserInterface\BinarySearch.js">
- <Filter>UserInterface</Filter>
- </None>
<None Include="..\UserInterface\BlankStylePropertiesSection.js">
<Filter>UserInterface</Filter>
</None>
