DevTools: Replace binarySearch with lowerBound and upperBound functions

Source/devtools/front_end/utilities.js

Index: Source/devtools/front_end/utilities.js
diff --git a/Source/devtools/front_end/utilities.js b/Source/devtools/front_end/utilities.js
index aae8f428d0cd1cdbe3d13af71b71121dec03cbf6..5019edc87aded736bb612043fb08b54845d964e6 100644
--- a/Source/devtools/front_end/utilities.js
+++ b/Source/devtools/front_end/utilities.js
@@ -254,28 +254,6 @@ Object.defineProperty(Array.prototype, "keySet",
     }
 });
 
-Object.defineProperty(Array.prototype, "upperBound",
-{
-    /**
-     * @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",
 {
     /**
@@ -390,42 +368,76 @@ Object.defineProperty(Array.prototype, "qselect",
     }
 });
 
-/**
- * @param {*} object
- * @param {Array.<*>} array
- * @param {function(*, *):number} comparator
- */
-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.<*>}

[aandrey, 2013/07/08 09:40:38]

alphabetical order plz

[alph, 2013/07/08 09:56:38]

Sorry, what?

[aandrey, 2013/07/08 10:00:51]

* @param ...
* @return ...
* @this ...

[alph, 2013/07/08 10:08:15]

grep -a1 "@this" *
shows that @this is used at the first place everywhere in devtools fe. I don't
think alphabetic sort is needed here, as the number of items is quite small.

+     * @param {*} object
+     * @param {function(*,*):number=} comparator

[eustas, 2013/07/08 09:18:23]

Would you mind to add space after colon?

[alph, 2013/07/08 09:56:38]

Added a space after comma as well if you don't mind.

[caseq, 2013/07/08 14:06:07]

We don't do this in the majority of cases (470 without the space vs. 7 with
space)

[alph, 2013/07/08 14:32:28]

ok. reverted.

+     * @return {number}
+     */
+    value: function(object, comparator)
+    {
+        comparator = comparator || function(a, b) { return a - b; }
+        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

[eustas, 2013/07/08 09:18:23]

Ditto.

[alph, 2013/07/08 09:56:38]

Done.

+     * @return {number}
+     */
+    value: function(object, comparator)
+    {
+        comparator = comparator || function(a, b) { return a - b; }
+        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",
 {
     /**
      * @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;
     }
 });
 
@@ -458,29 +470,18 @@ Object.defineProperty(Array.prototype, "peekLast",
 });
 
 /**
- * @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);
 }
 
 /**