DevTools: Replace binarySearch with lowerBound and upperBound functions

Source/devtools/front_end/utilities.js

 /*
  * Copyright (C) 2007 Apple Inc.  All rights reserved.
  * Copyright (C) 2012 Google 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:
  *
  * 1.  Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer.
@@ skipping 236 matching lines @@
      */
     value: function()
     {
         var keys = {};
         for (var i = 0; i < this.length; ++i)
             keys[this[i]] = true;
         return keys;
     }
 });
 
-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",
 {
     /**
      * @this {Array.<*>}
      * @param {number} index
      * @return {Array.<*>}
      */
     value: function(index)
     {
         var result = [];
@@ skipping 94 matching lines @@
             if (pivotPosition === k)
                 return this[k];
             else if (pivotPosition > k)
                 high = pivotPosition - 1;
             else
                 low = pivotPosition + 1;
         }
     }
 });
 
-/**
- * @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;
+    /**
+     * 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;
+    }
+});
 
-    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;
+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;
     }
-
-    // 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, "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;
     }
 });
 
 Object.defineProperty(Array.prototype, "select",
 {
     /**
      * @this {Array.<*>}
      * @param {string} field
      * @return {Array.<*>}
      */
@@ skipping 12 matching lines @@
      * @this {Array.<*>}
      * @return {*}
      */
     value: function()
     {
         return this[this.length - 1];
     }
 });
 
 /**
- * @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);
 }
 
 /**
  * @param {string} format
  * @param {...*} var_arg
  */
 String.sprintf = function(format, var_arg)
 {
     return String.vsprintf(format, Array.prototype.slice.call(arguments, 1));
 }
@@ skipping 695 matching lines @@
         console.assert(this._pendingIncomingCallbacksCount > 0);
         if (userCallback) {
             var args = Array.prototype.slice.call(arguments, 1);
             userCallback.apply(null, args);
         }
         if (!--this._pendingIncomingCallbacksCount && this._outgoingCallback)
             this._outgoingCallback();
     }
 }