Bug 118609 – Web Inspector: Replace binarySearch with lowerBound and upperBound functions

• Status: RESOLVED
• Resolution: FIXED
• Component: Web Inspector

[Timothy Hatcher]

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).

https://chromium.googlesource.com/chromium/blink/+/9541aa09240296b72409baf107c38c5efe7004be%5E%21/

[Radar WebKit Bug Importer]

<rdar://problem/14428765>

[Chi Wai Lau]

Created attachment 224837 [details]
patch

[Timothy Hatcher]

Comment on attachment 224837 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=224837&action=review

Thanks for fixing this! Can you upload a new patch with these tweaks?

> Source/WebInspectorUI/ChangeLog:5
> +        Web Inspector: Replace binarySearch with lowerBound and upperBound functions
> +        https://bugs.webkit.org/show_bug.cgi?id=118609
> +

Can you add the reasoning bellow the title? "This makes insertionIndexForObjectInListSortedByFunction work in O(log(n)) time instead of O(n)."

> Source/WebInspectorUI/ChangeLog:13
> +        (.):
> +        (.value):
> +        (object):

Our script gets confused by Object.defineProperty. Can you manually fix this?

> Source/WebInspectorUI/UserInterface/Utilities.js:939
> +
> +

Double new line.

> Source/WebInspectorUI/UserInterface/Utilities.js:946
> +    /**
> +     * 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.

Lets just use // for these comments.

> Source/WebInspectorUI/UserInterface/Utilities.js:951
> +     *
> +     * @this {Array.<*>}
> +     * @param {*} object
> +     * @param {function(*,*):number=} comparator
> +     * @return {number}

We don't use these JSDoc comments. We intend to remove them from our existing code. Lets not add more.

> Source/WebInspectorUI/UserInterface/Utilities.js:979
> +    /**
> +     * 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.

Ditto.

> Source/WebInspectorUI/UserInterface/Utilities.js:984
> +     *
> +     * @this {Array.<*>}
> +     * @param {*} object
> +     * @param {function(*,*):number=} comparator
> +     * @return {number}

Ditto.

> Source/WebInspectorUI/UserInterface/Utilities.js:991
> +        function defaultComparator(a, b)
> +        {
> +            return a - b;
> +        }

Lets move this function out next to insertObjectIntoSortedArray, since it can be shared.

> Source/WebInspectorUI/UserInterface/Utilities.js:1013
> +    /**
> +     * @this {Array.<*>}
> +     * @param {*} value
> +     * @param {function(*,*):number} comparator
> +     * @return {number}
> +     */

Ditto.

> Source/WebInspectorUI/UserInterface/Utilities.js:1027
> +/**
> + * @param {*} object
> + * @param {Array.<*>} list
> + * @param {function(*,*):number=} comparator
> + * @param {boolean=} insertionIndexAfter
> + * @return {number}
> + */

Ditto.

> Source/WebInspectorUI/UserInterface/Utilities.js:1041
> +/**
> + * @param {*} object
> + * @param {Array.<*>} array
> + * @param {function(*,*):number=} comparator
> + */

Ditto.

[Chi Wai Lau]

Created attachment 224909 [details]
patch

[Timothy Hatcher]

Comment on attachment 224909 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=224909&action=review

> LayoutTests/ChangeLog:9
> +        * inspector/utilities-expected.txt:
> +        * inspector/utilities.html:

These tests are not run anymore and are being removed in bug 129168.

[WebKit Commit Bot]

Comment on attachment 224909 [details]
patch

Clearing flags on attachment: 224909

Committed r164512: <http://trac.webkit.org/changeset/164512>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.