Refactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}ependent

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

Index: third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp
diff --git a/third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp
index b629b20b3212183d45bdf9cba90c1df3961766e7..e7777fdc2b60af54f82c081d71f2f0dfa6a072c4 100644
--- a/third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp
+++ b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp
@@ -80,52 +80,52 @@ bool DocumentMarkerListEditor::RemoveMarkers(MarkerList* list,
   return doc_dirty;
 }
 
-// TODO(rlanday): make this not take O(n^2) time when all the markers are
-// removed
 bool DocumentMarkerListEditor::ShiftMarkersContentDependent(
     MarkerList* list,
     unsigned offset,
     unsigned old_length,
     unsigned new_length) {
+  // Construct new list and swap so this method can run in O(n) time
+  MarkerList new_list;
   bool did_shift_marker = false;
   for (MarkerList::iterator it = list->begin(); it != list->end(); ++it) {
     DocumentMarker& marker = **it;
 
     // marked text is neither changed nor shifted
-    if (marker.EndOffset() <= offset)
+    if (marker.EndOffset() <= offset) {
+      new_list.push_back(marker);
       continue;
+    }
 
     // marked text is (potentially) changed by edit, remove marker
     if (marker.StartOffset() < offset + old_length) {
-      list->erase(it - list->begin());
-      --it;
       did_shift_marker = true;
       continue;
     }
 
     // marked text is shifted but not changed
     marker.ShiftOffsets(new_length - old_length);
+    new_list.push_back(marker);
     did_shift_marker = true;
   }
 
+  std::swap(*list, new_list);

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

nit: |*list = std::move(new_list);|
Let's do C++11-ish, we don't need to make |new_list| to have contents of |list|.

   return did_shift_marker;

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

Could you get rid of |did_shift_marker|?

Once we have |new_lsit|, we could write:

if (list->size() == new_list.size())
  return false;
*list = std::move(new_list);
return true;

[rlanday, 2017/06/02 15:23:01]

I don't think this is quite right because we want to return true if a marker is
shifted (without being removed), but your code returns false.

 }
 
-// TODO(rlanday): make this not take O(n^2) time when all the markers are
-// removed
 bool DocumentMarkerListEditor::ShiftMarkersContentIndependent(
     MarkerList* list,
     unsigned offset,
     unsigned old_length,
     unsigned new_length) {
+  // Construct new list and swap so this method can run in O(n) time
+  MarkerList new_list;
   bool did_shift_marker = false;
   for (MarkerList::iterator it = list->begin(); it != list->end(); ++it) {
     DocumentMarker& marker = **it;
     Optional<DocumentMarker::MarkerOffsets> result =
         marker.ComputeOffsetsAfterShift(offset, old_length, new_length);
     if (result == WTF::nullopt) {
-      list->erase(it - list->begin());
-      --it;
       did_shift_marker = true;
       continue;
     }
@@ -136,8 +136,11 @@ bool DocumentMarkerListEditor::ShiftMarkersContentIndependent(
       marker.SetStartOffset(result.value().start_offset);
       marker.SetEndOffset(result.value().end_offset);
     }
+
+    new_list.push_back(marker);
   }
 
+  std::swap(*list, new_list);

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

nit: |*list = std::move(new_list);|
Let's do C++11-ish, we don't need to make |new_list| to have contents of |list|.

   return did_shift_marker;

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

Could you get rid of |did_shift_marker|?

Once we have |new_lsit|, we could write:

if (list->size() == new_list.size())
  return false;
*list = std::move(new_list);
return true;

 }