Refactor SpellCheckMarkerListImpl::Add()

Refactor SpellCheckMarkerListImpl::Add()

Currently, the way this method inserts markers (except for the case where we
can insert at the end of the list) is inefficient. Its runtime is quadratic in
the number of markers being merged. We can make this more efficient by binary
searching for both the start and end of the overlapped range, and then erasing
the whole range (minus one marker, which we swap with the newly-inserted marker)
in one go. This method should now always run in time no worse than linear in the
number of markers.

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

[rlanday, 2017-06-02 22:23:00]

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

[Xiaocheng, 2017-06-03 03:17:31]

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

https://codereview.chromium.org/2915373002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListImpl.cpp:33:
if (marker->EndOffset() < (*first_overlapping)->StartOffset()) {
We should also go into this branch if |first_overlapping == markers_.end()|

https://codereview.chromium.org/2915373002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListImpl.cpp:43:
auto last_overlapping = std::upper_bound(
nit: rename it to |past_last_overlapping| to reduce confusion

https://codereview.chromium.org/2915373002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListImpl.cpp:56:
size_t num_to_erase = last_overlapping - (first_overlapping + 1);
nit: const size_t

[rlanday, 2017-06-03 15:02:03]

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

https://codereview.chromium.org/2915373002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListImpl.cpp:33:
if (marker->EndOffset() < (*first_overlapping)->StartOffset()) {
On 2017/06/03 at 03:17:31, Xiaocheng wrote:
> We should also go into this branch if |first_overlapping == markers_.end()|

I think the "insert at end without overlap" case is handled by the check at the
top:

if (markers_.back()->EndOffset() < marker->StartOffset())

[Xiaocheng, 2017-06-03 19:00:40]

lgtm

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

https://codereview.chromium.org/2915373002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListImpl.cpp:33:
if (marker->EndOffset() < (*first_overlapping)->StartOffset()) {
On 2017/06/03 at 15:02:03, rlanday wrote:
> On 2017/06/03 at 03:17:31, Xiaocheng wrote:
> > We should also go into this branch if |first_overlapping == markers_.end()|
> 
> I think the "insert at end without overlap" case is handled by the check at
the top:
> 
> if (markers_.back()->EndOffset() < marker->StartOffset())

You are right.

[yosin_UTC9, 2017-06-05 02:28:56]

lgtm % nits

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

https://codereview.chromium.org/2915373002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListImpl.cpp:24:
auto first_overlapping = std::lower_bound(
nit: s/auto/const auto&/

https://codereview.chromium.org/2915373002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListImpl.cpp:43:
auto last_overlapping = std::upper_bound(
nit: s/auto/const auto&/

[rlanday, 2017-06-05 17:11:41]

The CQ bit was checked by rlanday@chromium.org

[rlanday, 2017-06-05 17:11:42]

The patchset sent to the CQ was uploaded after l-g-t-m from yosin@chromium.org,
xiaochengh@chromium.org
Link to the patchset: https://codereview.chromium.org/2915373002/#ps20001
(title: "const auto&")

[commit-bot: I haz the power, 2017-06-05 17:12:03]

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-05 19:12:14]

CQ is committing da patch.

Bot data: {"patchset_id": 20001, "attempt_start_ts": 1496682701855890,
"parent_rev": "9d6e481415f080dc155b17c18997c752f1eaa293", "commit_rev":
"f1a451ab5d6f0a8ec7c3e389fb61c34f363768c4"}

[commit-bot: I haz the power, 2017-06-05 19:12:25]

Description was changed from

==========
Refactor SpellCheckMarkerListImpl::Add()

Currently, the way this method inserts markers (except for the case where we
can insert at the end of the list) is inefficient. Its runtime is quadratic in
the number of markers being merged. We can make this more efficient by binary
searching for both the start and end of the overlapped range, and then erasing
the whole range (minus one marker, which we swap with the newly-inserted marker)
in one go. This method should now always run in time no worse than linear in the
number of markers.

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

to

==========
Refactor SpellCheckMarkerListImpl::Add()

Currently, the way this method inserts markers (except for the case where we
can insert at the end of the list) is inefficient. Its runtime is quadratic in
the number of markers being merged. We can make this more efficient by binary
searching for both the start and end of the overlapped range, and then erasing
the whole range (minus one marker, which we swap with the newly-inserted marker)
in one go. This method should now always run in time no worse than linear in the
number of markers.

BUG=707867

Review-Url: https://codereview.chromium.org/2915373002
Cr-Commit-Position: refs/heads/master@{#477051}
Committed:
https://chromium.googlesource.com/chromium/src/+/f1a451ab5d6f0a8ec7c3e389fb61...
==========

[commit-bot: I haz the power, 2017-06-05 19:12:26]

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