Add DocumentMarkerListEditor

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..e066912213179841d0c11228a9e5692da8d33413
--- /dev/null
+++ b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp
@@ -0,0 +1,222 @@
+// 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();
+      });
+}
+
+bool DocumentMarkerListEditor::MoveUnsortedMarkers(
+    DocumentMarkerVector* marker_list,
+    int length,
+    DocumentMarkerList* dst_list) {
+  DCHECK_GT(length, 0);
+  bool didMoveMarker = false;
+  unsigned end_offset = length - 1;
+
+  DocumentMarkerVector marker_list_after_move;
+
+  for (Member<DocumentMarker> marker : *marker_list) {
+    if (marker->StartOffset() > end_offset) {
+      marker_list_after_move.push_back(marker);
+      continue;
+    }
+
+    // pin the marker to the specified range
+    if (marker->EndOffset() > end_offset)
+      marker->SetEndOffset(end_offset);
+
+    dst_list->Add(marker);
+    didMoveMarker = true;
+  }
+
+  std::swap(*marker_list, marker_list_after_move);
+
+  return didMoveMarker;
+}
+
+bool DocumentMarkerListEditor::MoveSortedMarkers(
+    DocumentMarkerVector* marker_list,
+    int length,
+    DocumentMarkerList* dst_list) {
+  DCHECK_GT(length, 0);
+  bool didMoveMarker = false;
+  unsigned end_offset = length - 1;
+
+  DocumentMarkerVector::iterator it;
+  for (it = marker_list->begin(); it != marker_list->end(); ++it) {
+    DocumentMarker& marker = **it;
+    if (marker.StartOffset() > end_offset)
+      break;
+
+    // pin the marker to the specified range
+    if (marker.EndOffset() > end_offset)
+      marker.SetEndOffset(end_offset);
+
+    dst_list->Add(&marker);
+    didMoveMarker = true;
+  }
+
+  // Remove the range of markers that were moved to dstNode
+  marker_list->erase(0, it - marker_list->begin());
+
+  return didMoveMarker;
+}
+
+bool DocumentMarkerListEditor::RemoveUnsortedMarkers(
+    DocumentMarkerVector* marker_list,
+    unsigned start_offset,
+    int length) {
+  unsigned end_offset = start_offset + length;
+  bool didRemoveMarker = false;
+
+  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 = true;
+    }
+  }
+
+  return didRemoveMarker;
+}
+
+bool 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 false;
+
+  return true;
+}
+
+bool DocumentMarkerListEditor::ShiftUnsortedMarkers(
+    DocumentMarkerVector* marker_list,
+    unsigned offset,
+    unsigned old_length,
+    unsigned new_length) {
+  bool didShiftMarker = false;
+  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) {
+      didShiftMarker = true;
+      // 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);
+
+      didShiftMarker = true;
+    }
+  }
+
+  return didShiftMarker;
+}
+
+bool DocumentMarkerListEditor::ShiftSortedMarkers(
+    DocumentMarkerVector* marker_list,
+    unsigned offset,
+    unsigned old_length,
+    unsigned new_length) {
+  DocumentMarkerVector newMarkerList;
+  bool didShiftMarker = false;
+  for (Member<DocumentMarker> marker : *marker_list) {
+    Optional<DocumentMarker::MarkerOffsets> result =
+        marker->ComputeOffsetsAfterShift(offset, old_length, new_length);
+
+    if (result == WTF::kNullopt) {
+      didShiftMarker = true;
+      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);
+
+      didShiftMarker = true;
+    }
+
+    newMarkerList.push_back(marker);
+  }
+
+  swap(*marker_list, newMarkerList);
+  return didShiftMarker;
+}
+
+bool DocumentMarkerListEditor::MoveMarkersHelper(
+    DocumentMarkerVector* marker_list,
+    int length,
+    DocumentMarkerList* dst_list,
+    bool is_sorted) {
+  DCHECK_GT(length, 0);
+  bool didMoveMarker = false;
+  unsigned end_offset = length - 1;
+
+  DocumentMarkerVector::iterator it;
+  for (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
+    didMoveMarker = true;
+
+    if (marker.EndOffset() > end_offset)
+      marker.SetEndOffset(end_offset);
+
+    dst_list->Add(&marker);
+  }
+
+  // Remove the range of markers that were moved to dstNode
+  marker_list->erase(0, it - marker_list->begin());
+
+  return didMoveMarker;
+}
+
+}  // namespace blink