Bug 118609 - Web Inspector: Replace binarySearch with lowerBound and upperBound functions
Summary: Web Inspector: Replace binarySearch with lowerBound and upperBound functions
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Inspector (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
URL:
Keywords: BlinkMergeCandidate, InRadar
Depends on:
Blocks:
 
Reported: 2013-07-12 10:40 PDT by Timothy Hatcher
Modified: 2014-02-21 16:05 PST (History)
4 users (show)

See Also:


Attachments
patch (15.30 KB, patch)
2014-02-21 00:20 PST, Chi Wai Lau
no flags Details | Formatted Diff | Diff
patch (14.64 KB, patch)
2014-02-21 14:27 PST, Chi Wai Lau
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Timothy Hatcher 2013-07-12 10:40:22 PDT
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/
Comment 1 Radar WebKit Bug Importer 2013-07-12 10:40:40 PDT
<rdar://problem/14428765>
Comment 2 Chi Wai Lau 2014-02-21 00:20:02 PST
Created attachment 224837 [details]
patch
Comment 3 Timothy Hatcher 2014-02-21 09:30:22 PST
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.
Comment 4 Chi Wai Lau 2014-02-21 14:27:40 PST
Created attachment 224909 [details]
patch
Comment 5 Timothy Hatcher 2014-02-21 15:02:35 PST
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.
Comment 6 WebKit Commit Bot 2014-02-21 16:05:33 PST
Comment on attachment 224909 [details]
patch

Clearing flags on attachment: 224909

Committed r164512: <http://trac.webkit.org/changeset/164512>
Comment 7 WebKit Commit Bot 2014-02-21 16:05:36 PST
All reviewed patches have been landed.  Closing bug.