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

[caseq, 2013/07/08 13:32:16]

nit: we don't inline non-empty anonymous functions.
function defaultComparator(a, b)
{
    return a - b;
}
if (!comparator)
    comparator = defaultComparator;

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

Done.

+        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
+     * @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;

[caseq, 2013/07/08 13:32:16]

This one looks wrong.

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

Looks correct to me. It the object is greater (or equal) to the current element
then its upper bound must be somewhere to the right. In other words element at
upper bound index cannot be equal or less than the object.

Mind to hint for a counter example?

[caseq, 2013/07/08 14:57:45]

Sorry, I take it back. lgtm.

+            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 {function(*, *):number} comparator
+     * @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();
     }
 }