Refactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}ependent

third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.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/DocumentMarkerListEditor.h"
 
 #include "core/editing/markers/SpellCheckMarkerListImpl.h"
 
 namespace blink {
 
@@ skipping 62 matching lines @@
     if (marker.StartOffset() >= end_offset)
       break;
 
     list->erase(i - list->begin());
     doc_dirty = true;
   }
 
   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;
     }
 
     if (marker.StartOffset() != result.value().start_offset ||
         marker.EndOffset() != result.value().end_offset) {
       did_shift_marker = true;
       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;

 }
 
 }  // namespace blink