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
|
return did_shift_marker; |
yosin_UTC9
2017/06/02 04:28:56
Could you get rid of |did_shift_marker|?
Once we
rlanday
2017/06/02 15:23:01
I don't think this is quite right because we want
|
} |
-// 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
|
return did_shift_marker; |
yosin_UTC9
2017/06/02 04:28:56
Could you get rid of |did_shift_marker|?
Once we
|
} |