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..0b833e2cb18cb884f0a1205c430d63e8ba179bfa |
--- /dev/null |
+++ b/third_party/WebKit/Source/core/editing/markers/SpellCheckMarkerList.cpp |
@@ -0,0 +1,77 @@ |
+// 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 <algorithm> |
+ |
+namespace blink { |
+ |
+SpellCheckMarkerList::SpellCheckMarkerList(DocumentMarker::MarkerType type) |
+ : m_type(type) {} |
+ |
+DocumentMarker::MarkerType SpellCheckMarkerList::allowedMarkerType() const { |
+ return m_type; |
+} |
+ |
+bool SpellCheckMarkerList::isSpellCheckMarkerList() const { |
+ return true; |
+} |
+ |
+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::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 |