OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org) | 2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org) |
3 * (C) 1999 Antti Koivisto (koivisto@kde.org) | 3 * (C) 1999 Antti Koivisto (koivisto@kde.org) |
4 * (C) 2001 Dirk Mueller (mueller@kde.org) | 4 * (C) 2001 Dirk Mueller (mueller@kde.org) |
5 * (C) 2006 Alexey Proskuryakov (ap@webkit.org) | 5 * (C) 2006 Alexey Proskuryakov (ap@webkit.org) |
6 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved. | 6 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved. |
7 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.t orchmobile.com/) | 7 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.t orchmobile.com/) |
8 * Copyright (C) Research In Motion Limited 2010. All rights reserved. | 8 * Copyright (C) Research In Motion Limited 2010. All rights reserved. |
9 * | 9 * |
10 * This library is free software; you can redistribute it and/or | 10 * This library is free software; you can redistribute it and/or |
(...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
126 return; | 126 return; |
127 ASSERT(!m_markers.isEmpty()); | 127 ASSERT(!m_markers.isEmpty()); |
128 | 128 |
129 RefPtr<Range> textPiece = markedText.range(); | 129 RefPtr<Range> textPiece = markedText.range(); |
130 int startOffset = textPiece->startOffset(); | 130 int startOffset = textPiece->startOffset(); |
131 int endOffset = textPiece->endOffset(); | 131 int endOffset = textPiece->endOffset(); |
132 removeMarkers(textPiece->startContainer(), startOffset, endOffset - star tOffset, markerTypes, shouldRemovePartiallyOverlappingMarker); | 132 removeMarkers(textPiece->startContainer(), startOffset, endOffset - star tOffset, markerTypes, shouldRemovePartiallyOverlappingMarker); |
133 } | 133 } |
134 } | 134 } |
135 | 135 |
136 static bool startsFurther(const DocumentMarker& lhv, const DocumentMarker& rhv) | |
groby-ooo-7-16
2013/09/13 18:05:48
Chromium preference is putting helper functions in
tony
2013/09/13 18:18:49
Most blink code uses static functions, but I don't
| |
137 { | |
138 return lhv.startOffset() < rhv.startOffset(); | |
139 } | |
140 | |
141 static bool doesNotOverlap(const DocumentMarker& lhv, const DocumentMarker& rhv) | |
groby-ooo-7-16
2013/09/17 11:52:42
I just woke up at 4am to realize this does not wor
pstanek
2013/09/17 12:46:30
I thought about the same but I convinced myself it
groby-ooo-7-16
2013/09/17 14:20:26
Do-while is fine - but in line 194, you use doesNo
pstanek
2013/09/17 14:48:05
But with lower_bound() we find the first overlappi
groby-ooo-7-16
2013/09/17 17:14:09
Yes, but the vector is unsorted with respect to en
pstanek
2013/09/17 17:30:41
Ah :/
On 2013/09/17 17:14:09, groby wrote:
pstanek
2013/09/17 17:39:45
Then to make this efficient markers would have to
groby-ooo-7-16
2013/09/17 18:39:37
Separating them by type would certainly be helpful
pstanek
2013/09/18 10:49:46
Yes. The assumptions seem to be right but I fear u
groby-ooo-7-16
2013/09/18 18:24:08
Postponing this seems fine to me. (If you do, you
| |
142 { | |
143 return lhv.endOffset() < rhv.startOffset(); | |
144 } | |
145 | |
136 // Markers are stored in order sorted by their start offset. | 146 // Markers are stored in order sorted by their start offset. |
137 // Markers of the same type do not overlap each other. | 147 // Markers of the same type do not overlap each other. |
138 | 148 |
139 void DocumentMarkerController::addMarker(Node* node, const DocumentMarker& newMa rker) | 149 void DocumentMarkerController::addMarker(Node* node, const DocumentMarker& newMa rker) |
140 { | 150 { |
141 ASSERT(newMarker.endOffset() >= newMarker.startOffset()); | 151 ASSERT(newMarker.endOffset() >= newMarker.startOffset()); |
142 if (newMarker.endOffset() == newMarker.startOffset()) | 152 if (newMarker.endOffset() == newMarker.startOffset()) |
143 return; | 153 return; |
144 | 154 |
145 m_possiblyExistingMarkerTypes.add(newMarker.type()); | 155 m_possiblyExistingMarkerTypes.add(newMarker.type()); |
146 | 156 |
147 OwnPtr<MarkerList>& list = m_markers.add(node, nullptr).iterator->value; | 157 OwnPtr<MarkerList>& list = m_markers.add(node, nullptr).iterator->value; |
148 | 158 |
149 if (!list) { | 159 if (!list) { |
150 list = adoptPtr(new MarkerList); | 160 list = adoptPtr(new MarkerList); |
151 list->append(RenderedDocumentMarker(newMarker)); | 161 list->append(RenderedDocumentMarker(newMarker)); |
152 } else { | 162 } else { |
153 RenderedDocumentMarker toInsert(newMarker); | 163 RenderedDocumentMarker toInsert(newMarker); |
154 size_t numMarkers = list->size(); | 164 if (list->last().endOffset() >= newMarker.startOffset()) { |
groby-ooo-7-16
2013/09/13 18:05:48
Isn't that covered by lower_bound already?
pstanek
2013/09/14 08:18:50
Yes, but the point was to avoid searching if no me
groby-ooo-7-16
2013/09/17 02:23:47
You probably want '>', though. if last.end == new.
pstanek
2013/09/17 13:54:00
But this if controls entering merging block so we'
groby-ooo-7-16
2013/09/17 14:34:41
Sigh. I misread that, sorry.
Done.
On 2013/09/17
| |
155 size_t i; | 165 if (toInsert.type() != DocumentMarker::TextMatch) { |
156 // Iterate over all markers whose start offset is less than or equal to the new marker's. | 166 mergeOverlapping(list.get(), toInsert); |
157 // If one of them is of the same type as the new marker and touches it o r intersects with it | 167 } else { |
158 // (there is at most one), remove it and adjust the new marker's start o ffset to encompass it. | 168 MarkerList::iterator pos = std::lower_bound(list->begin(), list- >end(), toInsert, startsFurther); |
159 for (i = 0; i < numMarkers; ++i) { | 169 if (pos != list->end()) |
groby-ooo-7-16
2013/09/13 18:05:48
AFAIK, insert works for pos == list->end()-list->b
pstanek
2013/09/17 16:57:00
Done.
| |
160 DocumentMarker marker = list->at(i); | 170 list->insert(pos - list->begin(), RenderedDocumentMarker(toI nsert)); |
161 if (marker.startOffset() > toInsert.startOffset()) | 171 else |
162 break; | 172 list->append(RenderedDocumentMarker(toInsert)); |
163 if (marker.type() == toInsert.type() && marker.type() != DocumentMar ker::TextMatch && marker.endOffset() >= toInsert.startOffset()) { | |
164 toInsert.setStartOffset(marker.startOffset()); | |
165 list->remove(i); | |
166 numMarkers--; | |
167 break; | |
168 } | 173 } |
174 } else { | |
175 list->append(RenderedDocumentMarker(toInsert)); | |
169 } | 176 } |
170 size_t j = i; | |
171 // Iterate over all markers whose end offset is less than or equal to th e new marker's, | |
172 // removing markers of the same type as the new marker which touch it or intersect with it, | |
173 // adjusting the new marker's end offset to cover them if necessary. | |
174 while (j < numMarkers) { | |
175 DocumentMarker marker = list->at(j); | |
176 if (marker.startOffset() > toInsert.endOffset()) | |
177 break; | |
178 if (marker.type() == toInsert.type() && marker.type() != DocumentMar ker::TextMatch) { | |
179 list->remove(j); | |
180 if (toInsert.endOffset() <= marker.endOffset()) { | |
181 toInsert.setEndOffset(marker.endOffset()); | |
182 break; | |
183 } | |
184 numMarkers--; | |
185 } else | |
186 j++; | |
187 } | |
188 // At this point i points to the node before which we want to insert. | |
189 list->insert(i, RenderedDocumentMarker(toInsert)); | |
190 } | 177 } |
191 | 178 |
192 // repaint the affected node | 179 // repaint the affected node |
193 if (node->renderer()) | 180 if (node->renderer()) |
194 node->renderer()->repaint(); | 181 node->renderer()->repaint(); |
195 } | 182 } |
196 | 183 |
184 void DocumentMarkerController::mergeOverlapping(MarkerList* list, DocumentMarker & toInsert) | |
groby-ooo-7-16
2013/09/13 18:05:48
I think this can be simplified - find the first ov
pstanek
2013/09/14 08:18:50
This is exactly what it does. upper_bound is used
groby-ooo-7-16
2013/09/17 02:23:47
Caveat:I might be missing something and all this m
pstanek
2013/09/17 16:20:38
I'll try to combine your approach with the origina
pstanek
2013/09/17 16:57:00
Done. (at least partially)
| |
185 { | |
186 // Iterate over all markers whose start offset is less than or equal to the new marker's. | |
187 // If one of them is of the same type as the new marker and touches it or in tersects with it | |
188 // (there is at most one), remove it and adjust the new marker's start offse t to encompass it. | |
189 size_t numMarkers = list->size(); | |
190 MarkerList::iterator end = std::upper_bound(list->begin(), list->end(), toIn sert, startsFurther); | |
191 MarkerList::iterator overlapping = list->begin(); | |
192 size_t offset = 0; | |
193 do { | |
194 overlapping = std::lower_bound(overlapping + offset, end, toInsert, does NotOverlap); | |
195 offset = 1; | |
196 } while (overlapping != end && overlapping->type() != toInsert.type()); | |
197 | |
198 size_t index = numMarkers; | |
199 if (overlapping != list->end()) | |
200 index = overlapping - list->begin(); | |
201 if (overlapping != end) { | |
202 toInsert.setStartOffset(overlapping->startOffset()); | |
203 list->remove(index); | |
204 --numMarkers; | |
205 } | |
206 | |
207 // Iterate over all markers whose end offset is less than or equal to the ne w marker's, | |
208 // removing markers of the same type as the new marker which touch it or int ersect with it, | |
209 // adjusting the new marker's end offset to cover them if necessary. | |
210 for (size_t i = index; i < numMarkers;) { | |
211 DocumentMarker marker = list->at(i); | |
groby-ooo-7-16
2013/09/17 02:23:47
Calling at() will bounds-check each element - iter
pstanek
2013/09/17 16:57:00
Done.
| |
212 if (marker.startOffset() > toInsert.endOffset()) | |
213 break; | |
214 if (marker.type() == toInsert.type()) { | |
215 list->remove(i); | |
216 if (toInsert.endOffset() <= marker.endOffset()) { | |
217 toInsert.setEndOffset(marker.endOffset()); | |
218 break; | |
groby-ooo-7-16
2013/09/17 02:23:47
Why break here? Couldn't we potentially have more
pstanek
2013/09/17 16:57:00
Done.
| |
219 } | |
220 --numMarkers; | |
221 } else { | |
222 ++i; | |
223 } | |
224 } | |
225 // At this point index points to the node before which we want to insert. | |
226 list->insert(index, RenderedDocumentMarker(toInsert)); | |
227 } | |
228 | |
197 // copies markers from srcNode to dstNode, applying the specified shift delta to the copies. The shift is | 229 // copies markers from srcNode to dstNode, applying the specified shift delta to the copies. The shift is |
198 // useful if, e.g., the caller has created the dstNode from a non-prefix substri ng of the srcNode. | 230 // useful if, e.g., the caller has created the dstNode from a non-prefix substri ng of the srcNode. |
199 void DocumentMarkerController::copyMarkers(Node* srcNode, unsigned startOffset, int length, Node* dstNode, int delta) | 231 void DocumentMarkerController::copyMarkers(Node* srcNode, unsigned startOffset, int length, Node* dstNode, int delta) |
200 { | 232 { |
201 if (length <= 0) | 233 if (length <= 0) |
202 return; | 234 return; |
203 | 235 |
204 if (!possiblyHasMarkers(DocumentMarker::AllMarkers())) | 236 if (!possiblyHasMarkers(DocumentMarker::AllMarkers())) |
205 return; | 237 return; |
206 ASSERT(!m_markers.isEmpty()); | 238 ASSERT(!m_markers.isEmpty()); |
(...skipping 449 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
656 | 688 |
657 } // namespace WebCore | 689 } // namespace WebCore |
658 | 690 |
659 #ifndef NDEBUG | 691 #ifndef NDEBUG |
660 void showDocumentMarkers(const WebCore::DocumentMarkerController* controller) | 692 void showDocumentMarkers(const WebCore::DocumentMarkerController* controller) |
661 { | 693 { |
662 if (controller) | 694 if (controller) |
663 controller->showMarkers(); | 695 controller->showMarkers(); |
664 } | 696 } |
665 #endif | 697 #endif |
OLD | NEW |