Add DocumentMarkerList in preparation for DocumentMarkerController refactor

third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.h

Index: third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.h
diff --git a/third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.h b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.h
new file mode 100644
index 0000000000000000000000000000000000000000..d709c1cd19e7506410ae037e37d16b207a8e8566
--- /dev/null
+++ b/third_party/WebKit/Source/core/editing/markers/DocumentMarkerList.h
@@ -0,0 +1,68 @@
+// 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.
+
+#ifndef DocumentMarkerList_h
+#define DocumentMarkerList_h
+
+#include "core/editing/markers/DocumentMarker.h"
+#include "platform/heap/Handle.h"
+
+namespace blink {
+
+class CORE_EXPORT DocumentMarkerList
+    : public GarbageCollected<DocumentMarkerList> {
+ public:
+  explicit DocumentMarkerList();
+  using iterator = Member<DocumentMarker>*;
+  using const_iterator = const Member<DocumentMarker>*;
+
+  virtual DocumentMarker::MarkerType allowedMarkerType() const = 0;
+  virtual bool isEditingMarkerList() const;
+  virtual bool isSpellCheckMarkerList() const;
+
+  size_t size() const { return m_markers.size(); }
+  bool empty() const { return m_markers.isEmpty(); }
+  DocumentMarker* at(size_t index) { return m_markers[index].get(); }
+
+  virtual void add(DocumentMarker*);
+  virtual void clear();
+
+  iterator begin() { return m_markers.begin(); }
+  iterator end() { return m_markers.end(); }
+  const_iterator begin() const { return m_markers.begin(); }
+  const_iterator end() const { return m_markers.end(); }
+
+  void appendMarkersToInputList(DocumentMarkerVector* list) const;
+
+  enum DidCopyMarkerOrNot { DidNotCopyMarker, DidCopyMarker };

[Xiaocheng, 2017/03/27 22:38:20]

nit: use |enum class|. Ditto for the other two.

+  DidCopyMarkerOrNot copyMarkers(unsigned startOffset,

[Xiaocheng, 2017/03/27 22:38:20]

These functions also have quadratic running time...

Anyway, I don't prioritize it because we don't have performance bug reports.

You can optimize them to linear if you like, as long as it doesn't make the code
too hacky. Or putting a "TODO(editing-dev): Optimize its running time to
linear." there is good enough for me.

[rlanday, 2017/03/27 23:57:40]

- copyMarkers() appears to be O(n) to me when inserting into a list where add()
runs in O(1) time, O(n^2) if inserting into a SpellCheckMarkerList where each
insert takes O(n) time (to keep the list sorted). We could potentially optimize
this to O(n log n) time by adding complexity here and in SpellCheckMarkerList,
but I don't think it's worth it for now

- removeMarkers() does appear to be O(n^2) for both the sorted and non-sorted
cases and is already a mess, I might try to clean this up (by putting the
markers into a second list and swapping)

- shiftMarkers() also appears to be O(n^2) for both cases, I think this is easy
to fix by creating a second list and swapping

[rlanday, 2017/03/28 00:06:19]

Actually I think copyMarkers() is only ever going to be used to copy into a
sorted list from another sorted list, so I think this is already going to be
O(n)

+                                 int length,
+                                 DocumentMarkerList* dstList,
+                                 int delta) const;
+
+  enum DidRemoveMarkerOrNot { DidNotRemoveMarker, DidRemoveMarker };
+  DidRemoveMarkerOrNot removeMarkers(
+      unsigned startOffset,
+      int length,
+      bool shouldRemovePartiallyOverlappingMarkers);
+
+  enum DidShiftMarkerOrNot { DidNotShiftMarker, DidShiftMarker };
+  DidShiftMarkerOrNot shiftMarkers(unsigned offset,
+                                   unsigned oldLength,
+                                   unsigned newLength);
+
+  DECLARE_VIRTUAL_TRACE();
+
+ protected:
+  iterator getPosOfFirstMarkerNotEndingBefore(size_t startOffset);
+  virtual bool markerListIsSorted() const = 0;
+
+  HeapVector<Member<DocumentMarker>> m_markers;
+
+  DISALLOW_COPY_AND_ASSIGN(DocumentMarkerList);
+};
+
+}  // namespace blink
+
+#endif  // DocumentMarkerList_h