DocumentMarkerList refactor as an interface

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
new file mode 100644
index 0000000000000000000000000000000000000000..28d592ccd0daf927f39a5eacd2804f1fb80b1128
--- /dev/null
+++ b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp
@@ -0,0 +1,183 @@
+// 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"
+
+namespace blink {
+
+DocumentMarkerVector::iterator
+DocumentMarkerListEditor::GetPosOfFirstMarkerNotEndingBeforeInSortedList(
+    DocumentMarkerVector* marker_list,
+    size_t start_offset) {
+  return std::upper_bound(
+      marker_list->begin(), marker_list->end(), start_offset,
+      [](size_t start_offset, const Member<DocumentMarker>& rhv) -> bool {
+        return start_offset < rhv->EndOffset();
+      });
+}
+
+DocumentMarkerList::DidMoveMarkerOrNot
+DocumentMarkerListEditor::MoveUnsortedMarkers(DocumentMarkerVector* marker_list,
+                                              int length,
+                                              DocumentMarkerList* dst_list) {
+  return MoveMarkersHelper(marker_list, length, dst_list, false);
+}
+
+DocumentMarkerList::DidMoveMarkerOrNot
+DocumentMarkerListEditor::MoveSortedMarkers(DocumentMarkerVector* marker_list,
+                                            int length,
+                                            DocumentMarkerList* dst_list) {
+  return MoveMarkersHelper(marker_list, length, dst_list, true);
+}
+
+DocumentMarkerList::DidRemoveMarkerOrNot
+DocumentMarkerListEditor::RemoveUnsortedMarkers(
+    DocumentMarkerVector* marker_list,
+    unsigned start_offset,
+    int length) {
+  unsigned end_offset = start_offset + length;
+  DocumentMarkerList::DidRemoveMarkerOrNot didRemoveMarker =
+      DocumentMarkerList::DidRemoveMarkerOrNot::kDidNotRemoveMarker;
+
+  for (auto it = marker_list->begin(); it != marker_list->end(); ++it) {
+    const DocumentMarker& marker = **it;
+
+    // markers have non-empty overlap
+    if (marker.StartOffset() < end_offset &&
+        marker.EndOffset() > start_offset) {
+      // Erase by doing a swap-and-shrink to get O(1) performance
+      std::swap(*it, marker_list->back());
+      marker_list->Shrink(marker_list->size() - 1);
+      --it;
+
+      didRemoveMarker =
+          DocumentMarkerList::DidRemoveMarkerOrNot::kDidRemoveMarker;
+    }
+  }
+
+  return didRemoveMarker;
+}
+
+DocumentMarkerList::DocumentMarkerList::DidRemoveMarkerOrNot
+DocumentMarkerListEditor::RemoveSortedMarkers(DocumentMarkerVector* marker_list,
+                                              unsigned start_offset,
+                                              int length) {
+  unsigned end_offset = start_offset + length;
+
+  const auto startPos =
+      GetPosOfFirstMarkerNotEndingBeforeInSortedList(marker_list, start_offset);
+  auto it = startPos;
+  for (; it != marker_list->end(); ++it) {
+    if ((*it)->StartOffset() >= end_offset)
+      break;
+  }
+
+  // it should now point at the first marker *not* to be removed (or at
+  // marker_list->end())
+  marker_list->erase(startPos - marker_list->begin(), it - startPos);
+
+  if (it == startPos)
+    return DocumentMarkerList::DidRemoveMarkerOrNot::kDidNotRemoveMarker;
+
+  return DocumentMarkerList::DidRemoveMarkerOrNot::kDidRemoveMarker;
+}
+
+DocumentMarkerList::DidShiftMarkerOrNot
+DocumentMarkerListEditor::ShiftUnsortedMarkers(
+    DocumentMarkerVector* marker_list,
+    unsigned offset,
+    unsigned old_length,
+    unsigned new_length) {
+  DocumentMarkerList::DidShiftMarkerOrNot didShift =
+      DocumentMarkerList::DidShiftMarkerOrNot::kDidNotShiftMarker;
+  for (auto it = marker_list->begin(); it != marker_list->end(); ++it) {
+    DocumentMarker& marker = **it;
+    Optional<DocumentMarker::MarkerOffsets> result =
+        marker.ComputeOffsetsAfterShift(offset, old_length, new_length);
+
+    if (result == WTF::kNullopt) {
+      didShift = DocumentMarkerList::DidShiftMarkerOrNot::kDidShiftMarker;
+      // Erase by doing a swap-and-shrink to get O(1) performance
+      std::swap(*it, marker_list->back());
+      marker_list->Shrink(marker_list->size() - 1);
+      --it;
+      continue;
+    }
+
+    if (result.value().start_offset != marker.StartOffset() ||
+        result.value().end_offset != marker.EndOffset()) {
+      marker.SetStartOffset(result.value().start_offset);
+      marker.SetEndOffset(result.value().end_offset);
+
+      didShift = DocumentMarkerList::DidShiftMarkerOrNot::kDidShiftMarker;
+    }
+  }
+
+  return didShift;
+}
+
+DocumentMarkerList::DidShiftMarkerOrNot
+DocumentMarkerListEditor::ShiftSortedMarkers(DocumentMarkerVector* marker_list,
+                                             unsigned offset,
+                                             unsigned old_length,
+                                             unsigned new_length) {
+  DocumentMarkerVector newMarkerList;
+  DocumentMarkerList::DidShiftMarkerOrNot didShift =
+      DocumentMarkerList::DidShiftMarkerOrNot::kDidNotShiftMarker;
+  for (Member<DocumentMarker> marker : *marker_list) {
+    Optional<DocumentMarker::MarkerOffsets> result =
+        marker->ComputeOffsetsAfterShift(offset, old_length, new_length);
+
+    if (result == WTF::kNullopt) {
+      didShift = DocumentMarkerList::DidShiftMarkerOrNot::kDidShiftMarker;
+      continue;
+    }
+
+    if (result.value().start_offset != marker->StartOffset() ||
+        result.value().end_offset != marker->EndOffset()) {
+      marker->SetStartOffset(result.value().start_offset);
+      marker->SetEndOffset(result.value().end_offset);
+
+      didShift = DocumentMarkerList::DidShiftMarkerOrNot::kDidShiftMarker;
+    }
+
+    newMarkerList.push_back(marker);
+  }
+
+  swap(*marker_list, newMarkerList);
+  return didShift;
+}
+
+DocumentMarkerList::DidMoveMarkerOrNot
+DocumentMarkerListEditor::MoveMarkersHelper(DocumentMarkerVector* marker_list,
+                                            int length,
+                                            DocumentMarkerList* dst_list,
+                                            bool is_sorted) {
+  DocumentMarkerList::DidMoveMarkerOrNot didMoveMarker =
+      DocumentMarkerList::DidMoveMarkerOrNot::kDidNotMoveMarker;
+  unsigned end_offset = length - 1;
+
+  for (auto it = marker_list->begin(); it != marker_list->end(); ++it) {
+    DocumentMarker& marker = **it;
+    if (marker.StartOffset() > end_offset) {
+      if (is_sorted)
+        break;
+      continue;
+    }
+
+    // pin the marker to the specified range and apply the shift delta
+    if (marker.StartOffset() <= end_offset) {

[rlanday, 2017/04/11 02:59:09]

This is redundant, I will remove

+      didMoveMarker = DocumentMarkerList::DidMoveMarkerOrNot::kDidMoveMarker;
+
+      if (marker.EndOffset() > end_offset)
+        marker.SetEndOffset(end_offset);
+
+      dst_list->Add(&marker);
+    }
+  }
+
+  return didMoveMarker;
+}
+
+}  // namespace blink