DocumentMarkerList refactor as an interface

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

Index: third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
diff --git a/third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp b/third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..a30726a144d3f0c1ef3cbf53268c394f2afeab8c
--- /dev/null
+++ b/third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp
@@ -0,0 +1,115 @@
+// 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/SpellCheckMarkerList.h"
+
+#include "core/editing/markers/DocumentMarkerListEditor.h"
+
+namespace blink {
+
+SpellCheckMarkerList::SpellCheckMarkerList(DocumentMarker::MarkerType type)
+    : type_(type) {}
+
+DocumentMarker::MarkerType SpellCheckMarkerList::GetAllowedMarkerType() const {
+  return type_;
+}
+
+bool SpellCheckMarkerList::Empty() const {
+  return markers_.IsEmpty();
+}
+
+DocumentMarker* SpellCheckMarkerList::At(size_t index) {
+  return markers_[index].Get();
+}
+
+void SpellCheckMarkerList::Add(DocumentMarker* marker) {
+  DCHECK_EQ(marker->GetType(), GetAllowedMarkerType())
+      << "Marker of type " << marker->GetType() << " added; should be of type "
+      << GetAllowedMarkerType();
+  // Optimize case where (non-merging) markers are being added in order so we
+  // can add n markers in O(n) time instead of O(n log n)
+  if (markers_.IsEmpty() ||
+      markers_.back()->EndOffset() < marker->StartOffset()) {
+    markers_.push_back(marker);
+    return;
+  }
+
+  const auto& firstOverlappingIt = std::lower_bound(
+      markers_.begin(), markers_.end(), marker,
+      [](const Member<DocumentMarker>& lhv, const DocumentMarker* rhv) {
+        return lhv->EndOffset() < rhv->StartOffset();
+      });
+
+  size_t index = firstOverlappingIt - markers_.begin();
+  markers_.insert(index, marker);
+  const auto& insertedIt = markers_.begin() + index;
+
+  unsigned newStart = marker->StartOffset();
+  unsigned newEnd = marker->EndOffset();
+
+  DocumentMarkerVector::iterator it;
+  for (it = insertedIt + 1;
+       it != markers_.end() && (*it)->StartOffset() <= newEnd; ++it) {
+    newStart = std::min(newStart, (*it)->StartOffset());
+    newEnd = std::max(newEnd, (*it)->EndOffset());
+  }
+  markers_.erase(index + 1, it - (insertedIt + 1));
+
+  (*insertedIt)->SetStartOffset(newStart);
+  (*insertedIt)->SetEndOffset(newEnd);
+}
+
+void SpellCheckMarkerList::Clear() {
+  markers_.Clear();
+}
+
+void SpellCheckMarkerList::AppendMarkersToInputList(
+    DocumentMarkerVector* list) const {
+  list->AppendVector(markers_);
+}
+
+DocumentMarkerList::DidMoveMarkerOrNot SpellCheckMarkerList::MoveMarkers(
+    int length,
+    DocumentMarkerList* dst_list) {
+  return DocumentMarkerListEditor::MoveSortedMarkers(&markers_, length,
+                                                     dst_list);
+}
+
+DocumentMarkerList::DidRemoveMarkerOrNot SpellCheckMarkerList::RemoveMarkers(
+    unsigned start_offset,
+    int length) {
+  return DocumentMarkerListEditor::RemoveSortedMarkers(&markers_, start_offset,
+                                                       length);
+}
+
+DocumentMarkerList::DidShiftMarkerOrNot SpellCheckMarkerList::ShiftMarkers(
+    unsigned offset,
+    unsigned old_length,
+    unsigned new_length) {
+  return DocumentMarkerListEditor::ShiftSortedMarkers(&markers_, offset,
+                                                      old_length, new_length);
+}
+
+DEFINE_TRACE(SpellCheckMarkerList) {
+  visitor->Trace(markers_);
+  DocumentMarkerList::Trace(visitor);
+}
+
+void SpellCheckMarkerList::RemoveMarkersForWords(const String& node_text,
+                                                 const Vector<String>& words) {
+  // Build a second vector and swap with markers_ to avoid O(n^2) performance
+  HeapVector<Member<DocumentMarker>> new_marker_list;
+  std::copy_if(markers_.begin(), markers_.end(),
+               std::back_inserter(new_marker_list),
+               [&node_text, &words](Member<DocumentMarker> marker) {
+                 unsigned start = marker->StartOffset();
+                 unsigned length = marker->EndOffset() - marker->StartOffset();
+                 const String& marker_text = node_text.Substring(start, length);
+                 return !words.Contains(marker_text);
+               });
+
+  std::swap(markers_, new_marker_list);
+}
+
+}  // namespace blink