Make DocumentMarkerListEditor::RemoveMarkers() more efficient

Make DocumentMarkerListEditor::RemoveMarkers() more efficient

The current implementation of this method does a binary search to get the first
marker to be removed, then linearly walks the markers, erasing all that fall in
the specified range. This can potentially take time quadratic in the number of
markers to be removed, and always takes at least log N time.

This new implementation finds both the start point and end point of the range to
be erased in log N time, then does a single erase operation that takes time
linear in the number of markers to be removed. So the asymptotic lower bound
stays the same and the asymptotic upper bound is improved from quadratic to
linear.

I've also added a few more test cases to DocumentMarkerListEditor test to verify
the new implementation works correctly.

BUG=707867
Review-Url: https://codereview.chromium.org/2922623002
Cr-Commit-Position: refs/heads/master@{#476551}
Committed: https://chromium.googlesource.com/chromium/src/+/38610ad5a07527b89be3116610c2c3bff822d5e8

[rlanday, 2017-06-02 01:03:53]

rlanday@chromium.org changed reviewers:
+ xiaochengh@chromium.org, yosin@chromium.org

[rlanday, 2017-06-02 01:03:56]

The CQ bit was checked by rlanday@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-06-02 01:04:47]

Dry run: CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-06-02 01:04:49]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-06-02 01:04:50]

Dry run: CQ cannot get SignCLA result. Please try later.

[yosin_UTC9, 2017-06-02 01:11:45]

The CQ bit was checked by yosin@chromium.org

[yosin_UTC9, 2017-06-02 01:11:45]

lgtm

https://codereview.chromium.org/2922623002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp
(right):

https://codereview.chromium.org/2922623002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:59: 
nit: Please remove an extra blank line.

[commit-bot: I haz the power, 2017-06-02 01:12:40]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[rlanday, 2017-06-02 01:13:37]

Woah woah woah, let me fix the nit first :)

[yosin_UTC9, 2017-06-02 01:15:26]

On 2017/06/02 at 01:13:37, rlanday wrote:
> Woah woah woah, let me fix the nit first :)

Oops, sorry...

[rlanday, 2017-06-02 01:23:47]

The CQ bit was checked by rlanday@chromium.org

[rlanday, 2017-06-02 01:23:48]

The patchset sent to the CQ was uploaded after l-g-t-m from yosin@chromium.org
Link to the patchset: https://codereview.chromium.org/2922623002/#ps20001
(title: "Remove blank line")

[commit-bot: I haz the power, 2017-06-02 01:24:18]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-06-02 03:26:12]

CQ is committing da patch.

Bot data: {"patchset_id": 20001, "attempt_start_ts": 1496366627608460,
"parent_rev": "bb2881f8de65ec1c7d64d92ce414a5f108a86270", "commit_rev":
"38610ad5a07527b89be3116610c2c3bff822d5e8"}

[commit-bot: I haz the power, 2017-06-02 03:26:22]

Description was changed from

==========
Make DocumentMarkerListEditor::RemoveMarkers() more efficient

The current implementation of this method does a binary search to get the first
marker to be removed, then linearly walks the markers, erasing all that fall in
the specified range. This can potentially take time quadratic in the number of
markers to be removed, and always takes at least log N time.

This new implementation finds both the start point and end point of the range to
be erased in log N time, then does a single erase operation that takes time
linear in the number of markers to be removed. So the asymptotic lower bound
stays the same and the asymptotic upper bound is improved from quadratic to
linear.

I've also added a few more test cases to DocumentMarkerListEditor test to verify
the new implementation works correctly.

BUG=707867
==========

to

==========
Make DocumentMarkerListEditor::RemoveMarkers() more efficient

The current implementation of this method does a binary search to get the first
marker to be removed, then linearly walks the markers, erasing all that fall in
the specified range. This can potentially take time quadratic in the number of
markers to be removed, and always takes at least log N time.

This new implementation finds both the start point and end point of the range to
be erased in log N time, then does a single erase operation that takes time
linear in the number of markers to be removed. So the asymptotic lower bound
stays the same and the asymptotic upper bound is improved from quadratic to
linear.

I've also added a few more test cases to DocumentMarkerListEditor test to verify
the new implementation works correctly.

BUG=707867

Review-Url: https://codereview.chromium.org/2922623002
Cr-Commit-Position: refs/heads/master@{#476551}
Committed:
https://chromium.googlesource.com/chromium/src/+/38610ad5a07527b89be3116610c2...
==========

[commit-bot: I haz the power, 2017-06-02 03:26:24]

Committed patchset #2 (id:20001) as
https://chromium.googlesource.com/chromium/src/+/38610ad5a07527b89be3116610c2...