Refactor SpellCheckMarkerListImpl::Add()

third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerListImpl.cpp

 // Copyright 2017 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "core/editing/markers/SpellCheckMarkerListImpl.h"
 
 #include "core/editing/markers/DocumentMarkerListEditor.h"
 
 namespace blink {
 
 bool SpellCheckMarkerListImpl::IsEmpty() const {
   return markers_.IsEmpty();
 }
 
 void SpellCheckMarkerListImpl::Add(DocumentMarker* marker) {
   if (markers_.IsEmpty() ||
       markers_.back()->EndOffset() < marker->StartOffset()) {
     markers_.push_back(marker);
     return;
   }
 
+  // Find first marker that ends after the one being inserted starts. If any
+  // markers overlap the one being inserted, this is the first one.
   auto first_overlapping = std::lower_bound(

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

nit: s/auto/const auto&/

       markers_.begin(), markers_.end(), marker,
       [](const Member<DocumentMarker>& marker_in_list,
          const DocumentMarker* marker_to_insert) {
         return marker_in_list->EndOffset() < marker_to_insert->StartOffset();
       });
 
-  size_t index = first_overlapping - markers_.begin();
-  markers_.insert(index, marker);
-  const auto inserted = markers_.begin() + index;
-  first_overlapping = inserted + 1;
-  // TODO(rlanday): optimize this loop so it runs in O(N) time and not O(N^2)
-  for (const auto i = first_overlapping;
-       i != markers_.end() &&
-       (*i)->StartOffset() <= (*inserted)->EndOffset();) {
-    (*inserted)->SetStartOffset(
-        std::min((*inserted)->StartOffset(), (*i)->StartOffset()));
-    (*inserted)->SetEndOffset(
-        std::max((*inserted)->EndOffset(), (*i)->EndOffset()));
-    markers_.erase(i - markers_.begin());
+  // If this marker does not overlap the one being inserted, insert before it
+  // and we are done.
+  if (marker->EndOffset() < (*first_overlapping)->StartOffset()) {

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

We should also go into this branch if |first_overlapping == markers_.end()|

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

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]

You are right.

+    markers_.insert(first_overlapping - markers_.begin(), marker);
+    return;
   }
+
+  // Otherwise, find the last overlapping marker, replace the first marker with
+  // the newly-inserted marker (to get the new description), set its start and
+  // end offsets to include all the overlapped markers, and erase the rest of
+  // the old markers.
+
+  auto last_overlapping = std::upper_bound(

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

nit: rename it to |past_last_overlapping| to reduce confusion

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

nit: s/auto/const auto&/

+      first_overlapping, markers_.end(), marker,
+      [](const DocumentMarker* marker_to_insert,
+         const Member<DocumentMarker>& marker_in_list) {
+        return marker_to_insert->EndOffset() < marker_in_list->StartOffset();
+      });
+
+  marker->SetStartOffset(
+      std::min(marker->StartOffset(), (*first_overlapping)->StartOffset()));
+  marker->SetEndOffset(
+      std::max(marker->EndOffset(), (*(last_overlapping - 1))->EndOffset()));
+
+  *first_overlapping = marker;
+  size_t num_to_erase = last_overlapping - (first_overlapping + 1);

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

nit: const size_t

+  markers_.erase(first_overlapping + 1 - markers_.begin(), num_to_erase);
 }
 
 void SpellCheckMarkerListImpl::Clear() {
   markers_.clear();
 }
 
 const HeapVector<Member<DocumentMarker>>& SpellCheckMarkerListImpl::GetMarkers()
     const {
   return markers_;
 }
@@ skipping 32 matching lines @@
     const String& marker_text = node_text.Substring(start, length);
     if (words.Contains(marker_text)) {
       markers_.erase(j - 1);
       removed_markers = true;
     }
   }
   return removed_markers;
 }
 
 }  // namespace blink