DevTools: Replace binarySearch with lowerBound and upperBound functions

DevTools: Replace binarySearch with lowerBound and upperBound functions

This allows to avoid index-mapping-to-negative-axis-trick in
binarySearch and its usages.
It also makes insertionIndexForObjectInListSortedByFunction to work in
O(log(n)) time instead of O(n).

R=caseq@chromium.org

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=153679

[alph, 2013-07-08 08:54:26]

Could you please take a look.

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

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:381: * @param {function(*,*):number=}
comparator
Would you mind to add space after colon?

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:410: * @param {function(*,*):number=}
comparator
Ditto.

[aandrey, 2013-07-08 09:40:37]

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:379: * @this {Array.<*>}
alphabetical order plz

[alph, 2013-07-08 09:56:37]

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:379: * @this {Array.<*>}
On 2013/07/08 09:40:38, aandrey wrote:
> alphabetical order plz
Sorry, what?

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:381: * @param {function(*,*):number=}
comparator
On 2013/07/08 09:18:23, eustas.ru wrote:
> Would you mind to add space after colon?
Added a space after comma as well if you don't mind.

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:410: * @param {function(*,*):number=}
comparator
On 2013/07/08 09:18:23, eustas.ru wrote:
> Ditto.

Done.

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

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:379: * @this {Array.<*>}
On 2013/07/08 09:56:38, alph wrote:
> On 2013/07/08 09:40:38, aandrey wrote:
> > alphabetical order plz
> Sorry, what?

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

[alph, 2013-07-08 10:08:14]

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:379: * @this {Array.<*>}
On 2013/07/08 10:00:51, aandrey wrote:
> On 2013/07/08 09:56:38, alph wrote:
> > On 2013/07/08 09:40:38, aandrey wrote:
> > > alphabetical order plz
> > Sorry, what?
> 
> * @param ...
> * @return ...
> * @this ...

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.

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

https://codereview.chromium.org/18828002/diff/7001/Source/devtools/front_end/...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/7001/Source/devtools/front_end/...
Source/devtools/front_end/utilities.js:386: comparator = comparator ||
function(a, b) { return a - b; }
nit: we don't inline non-empty anonymous functions.
function defaultComparator(a, b)
{
    return a - b;
}
if (!comparator)
    comparator = defaultComparator;

https://codereview.chromium.org/18828002/diff/7001/Source/devtools/front_end/...
Source/devtools/front_end/utilities.js:421: l = m + 1;
This one looks wrong.

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

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:381: * @param {function(*,*):number=}
comparator
On 2013/07/08 09:18:23, eustas.ru wrote:
> Would you mind to add space after colon?

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

[alph, 2013-07-08 14:32:27]

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/1/Source/devtools/front_end/uti...
Source/devtools/front_end/utilities.js:381: * @param {function(*,*):number=}
comparator
On 2013/07/08 14:06:07, caseq wrote:
> On 2013/07/08 09:18:23, eustas.ru wrote:
> > Would you mind to add space after colon?
> 
> We don't do this in the majority of cases (470 without the space vs. 7 with
> space)

ok. reverted.

https://codereview.chromium.org/18828002/diff/7001/Source/devtools/front_end/...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/7001/Source/devtools/front_end/...
Source/devtools/front_end/utilities.js:386: comparator = comparator ||
function(a, b) { return a - b; }
On 2013/07/08 13:32:16, caseq wrote:
> nit: we don't inline non-empty anonymous functions.
> function defaultComparator(a, b)
> {
>     return a - b;
> }
> if (!comparator)
>     comparator = defaultComparator;

Done.

https://codereview.chromium.org/18828002/diff/7001/Source/devtools/front_end/...
Source/devtools/front_end/utilities.js:421: l = m + 1;
On 2013/07/08 13:32:16, caseq wrote:
> This one looks wrong.

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]

https://codereview.chromium.org/18828002/diff/7001/Source/devtools/front_end/...
File Source/devtools/front_end/utilities.js (right):

https://codereview.chromium.org/18828002/diff/7001/Source/devtools/front_end/...
Source/devtools/front_end/utilities.js:421: l = m + 1;
On 2013/07/08 14:32:28, alph wrote:
> On 2013/07/08 13:32:16, caseq wrote:
> > This one looks wrong.
> 
> 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?

Sorry, I take it back. lgtm.

[alph, 2013-07-08 15:42:56]

Committed patchset #6 manually as r153679 (presubmit successful).