DocumentMarkerList refactor as an interface

third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.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/SpellCheckMarkerList.h"
+
+#include "core/editing/markers/DocumentMarkerListEditor.h"
+
+namespace blink {
+
+SpellCheckMarkerList::SpellCheckMarkerList(DocumentMarker::MarkerType type)
+    : m_type(type) {}
+
+DocumentMarker::MarkerType SpellCheckMarkerList::allowedMarkerType() const {
+  return m_type;
+}
+
+bool SpellCheckMarkerList::empty() const {
+  return m_markers.isEmpty();
+}
+
+DocumentMarker* SpellCheckMarkerList::at(size_t index) {
+  return m_markers[index].get();
+}
+
+void SpellCheckMarkerList::add(DocumentMarker* marker) {
+  DCHECK_EQ(marker->type(), allowedMarkerType())
+      << "Marker of type " << marker->type() << " added; should be of type "
+      << allowedMarkerType();
+  // 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 (m_markers.isEmpty() ||
+      m_markers.back()->endOffset() < marker->startOffset()) {
+    m_markers.push_back(marker);
+    return;
+  }
+
+  const auto& firstOverlappingIt = std::lower_bound(
+      m_markers.begin(), m_markers.end(), marker,
+      [](const Member<DocumentMarker>& lhv, const DocumentMarker* rhv) {
+        return lhv->endOffset() < rhv->startOffset();
+      });
+
+  size_t index = firstOverlappingIt - m_markers.begin();
+  m_markers.insert(index, marker);
+  const auto& insertedIt = m_markers.begin() + index;
+
+  unsigned newStart = marker->startOffset();
+  unsigned newEnd = marker->endOffset();
+
+  iterator it;
+  for (it = insertedIt + 1;
+       it != m_markers.end() && (*it)->startOffset() <= newEnd; ++it) {
+    newStart = std::min(newStart, (*it)->startOffset());
+    newEnd = std::max(newEnd, (*it)->endOffset());
+  }
+  m_markers.erase(index + 1, it - (insertedIt + 1));
+
+  (*insertedIt)->setStartOffset(newStart);
+  (*insertedIt)->setEndOffset(newEnd);
+}
+
+void SpellCheckMarkerList::clear() {
+  m_markers.clear();
+}
+
+void SpellCheckMarkerList::appendMarkersToInputList(
+    DocumentMarkerVector* list) const {
+  DocumentMarkerListEditor::appendMarkersToInputList(m_markers, list);
+}
+
+DocumentMarkerList::DidCopyMarkerOrNot SpellCheckMarkerList::copyMarkers(
+    unsigned startOffset,
+    int length,
+    DocumentMarkerList* dstList,
+    int delta) {
+  return DocumentMarkerListEditor::copySortedMarkers(&m_markers, startOffset,
+                                                     length, dstList, delta);
+}
+
+DocumentMarkerList::DidRemoveMarkerOrNot SpellCheckMarkerList::removeMarkers(
+    unsigned startOffset,
+    int length,
+    bool shouldRemovePartiallyOverlappingMarkers) {
+  return DocumentMarkerListEditor::removeSortedMarkers(
+      &m_markers, startOffset, length, shouldRemovePartiallyOverlappingMarkers);
+}
+
+DocumentMarkerList::DidShiftMarkerOrNot SpellCheckMarkerList::shiftMarkers(
+    unsigned offset,
+    unsigned oldLength,
+    unsigned newLength) {
+  return DocumentMarkerListEditor::shiftSortedMarkers(&m_markers, offset,
+                                                      oldLength, newLength);
+}
+
+DEFINE_TRACE(SpellCheckMarkerList) {
+  visitor->trace(m_markers);
+  DocumentMarkerList::trace(visitor);
+}
+
+void SpellCheckMarkerList::removeMarkersForWords(const String& nodeText,
+                                                 const Vector<String>& words) {
+  // Build a second vector and swap with m_markers to avoid O(n^2) performance
+  HeapVector<Member<DocumentMarker>> newMarkerList;
+  std::copy_if(m_markers.begin(), m_markers.end(),
+               std::back_inserter(newMarkerList),
+               [&nodeText, &words](Member<DocumentMarker> marker) {
+                 unsigned start = marker->startOffset();
+                 unsigned length = marker->endOffset() - marker->startOffset();
+                 const String& markerText = nodeText.substring(start, length);
+                 return !words.contains(markerText);
+               });
+
+  std::swap(m_markers, newMarkerList);
+}
+
+}  // namespace blink