Attachment 224909 Details for Bug 118609 – patch

[patch] patch

bug-118609-20140221142739.patch (text/plain), 14.64 KB, created by Chi Wai Lau on 2014-02-21 14:27:40 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Chi Wai Lau

Created: 2014-02-21 14:27:40 PST

Size: 14.64 KB

patch

obsolete

>Subversion Revision: 164436
>diff --git a/Source/WebInspectorUI/ChangeLog b/Source/WebInspectorUI/ChangeLog
>index a2c196f84c000a9c4c3fafd85878be85f1dad9a3..b72e5895c2b82fbeb8c39753de08b2dfb0620c87 100644
>--- a/Source/WebInspectorUI/ChangeLog
>+++ b/Source/WebInspectorUI/ChangeLog
>@@ -1,3 +1,18 @@
>+2014-02-21  Chi Wai Lau  <clau@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-20  Antoine Quint  <graouts@webkit.org>
> 
>         Web Inspector: create a CodeMirrorEditingController superclass
>diff --git a/Source/WebInspectorUI/UserInterface/BinarySearch.js b/Source/WebInspectorUI/UserInterface/BinarySearch.js
>deleted file mode 100644
>index c652d6ef83dcb31872cc27de5979d832bf2e66a9..0000000000000000000000000000000000000000
>--- a/Source/WebInspectorUI/UserInterface/BinarySearch.js
>+++ /dev/null
>@@ -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);
>-}
>diff --git a/Source/WebInspectorUI/UserInterface/Main.html b/Source/WebInspectorUI/UserInterface/Main.html
>index 30d3f429274e41ec35120d448178a636c4076792..654df8f834fb964305151b8045639e0550899bb4 100644
>--- a/Source/WebInspectorUI/UserInterface/Main.html
>+++ b/Source/WebInspectorUI/UserInterface/Main.html
>@@ -214,7 +214,6 @@
>     <script src="SourceCode.js"></script>
>     <script src="Resource.js"></script>
>     <script src="ResourceCollection.js"></script>
>-    <script src="BinarySearch.js"></script>
>     <script src="EditingSupport.js"></script>
>     <script src="KeyboardShortcut.js"></script>
>     <script src="NavigationBar.js"></script>
>diff --git a/Source/WebInspectorUI/UserInterface/Utilities.js b/Source/WebInspectorUI/UserInterface/Utilities.js
>index 4a19d2311949cb962aeb1f8141f84ab31e784032..6a4071791a6bf2970b4dd0474c0c4c51bc633edf 100644
>--- a/Source/WebInspectorUI/UserInterface/Utilities.js
>+++ b/Source/WebInspectorUI/UserInterface/Utilities.js
>@@ -426,25 +426,6 @@ Object.defineProperty(Array.prototype, "keySet",
>     }
> });
> 
>-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 @@ function simpleGlobStringToRegExp(globString, regExpFlags)
> 
>     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);
>+}
>diff --git a/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj b/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj
>index 43d6f2453907207d8924b4c7b65cdfff387d139c..199854b71e69d94a85e5130fed260c988371ad53 100644
>--- a/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj
>+++ b/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj
>@@ -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" />
>diff --git a/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj.filters b/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj.filters
>index b50a60ce060adcfd9b05d1151852e7f63308816a..917d6718db9b2f7db438a65a3c685aa680f305f8 100644
>--- a/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj.filters
>+++ b/Source/WebInspectorUI/WebInspectorUI.vcxproj/WebInspectorUI.vcxproj.filters
>@@ -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>
>diff --git a/LayoutTests/ChangeLog b/LayoutTests/ChangeLog
>index 7b67eaef6139fcae6d3fc81fec7b758d3dd0eb22..d242fd2ab596eb57693d1d4fca60027a022a81ea 100644
>--- a/LayoutTests/ChangeLog
>+++ b/LayoutTests/ChangeLog
>@@ -1,3 +1,13 @@
>+2014-02-21  Chi Wai Lau  <clau@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-20  MichaÅ PakuÅa vel Rutka  <m.pakula@samsung.com>
> 
>         Unreviewed EFL gardening
>diff --git a/LayoutTests/inspector/utilities-expected.txt b/LayoutTests/inspector/utilities-expected.txt
>index 45f26b937c5d910339934657688e4a9ff8e406aa..3b664d8f01c519117cc387b83016de155837318f 100644
>--- a/LayoutTests/inspector/utilities-expected.txt
>+++ b/LayoutTests/inspector/utilities-expected.txt
>@@ -3,6 +3,11 @@ This test checks Web Inspector utilities.
> 
> Running: binaryIndexOfTest
> 
>+Running: lowerBoundTest
>+
>+Running: upperBoundTest
>+
>+
> Running: qselectTest
> Array: []
> Reference: {}
>diff --git a/LayoutTests/inspector/utilities.html b/LayoutTests/inspector/utilities.html
>index 013eb0d3c25e714507c9f57e86427c51d863e7b8..9471d5503bc9c0ae971bf89de1cda468e8a838c7 100644
>--- a/LayoutTests/inspector/utilities.html
>+++ b/LayoutTests/inspector/utilities.html
>@@ -36,6 +36,68 @@ function test()
>                 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 @@ function test()
>                     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));

Actions: View | Formatted Diff | Diff

Attachments on bug 118609: 224837 | 224909