1 | /* This file is part of the KDE libraries |
2 | Copyright (C) 2003-2005 Hamish Rodda <rodda@kde.org> |
3 | Copyright (C) 2008 David Nolden <david.nolden.kdevelop@art-master.de> |
4 | |
5 | This library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Library General Public |
7 | License version 2 as published by the Free Software Foundation. |
8 | |
9 | This library is distributed in the hope that it will be useful, |
10 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 | Library General Public License for more details. |
13 | |
14 | You should have received a copy of the GNU Library General Public License |
15 | along with this library; see the file COPYING.LIB. If not, write to |
16 | the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
17 | Boston, MA 02110-1301, USA. |
18 | */ |
19 | |
20 | #include "smartrange.h" |
21 | |
22 | #include <QtCore/QStack> |
23 | |
24 | #include "document.h" |
25 | #include "view.h" |
26 | #include "attribute.h" |
27 | #include "rangefeedback.h" |
28 | |
29 | #include <kaction.h> |
30 | #include <kdebug.h> |
31 | |
32 | using namespace KTextEditor; |
33 | |
34 | //Uncomment this to enable debugging of the child-order. If it is enabled, an assertion will |
35 | //be triggered when the order is violated. |
36 | //This is slow. |
37 | // #define SHOULD_DEBUG_CHILD_ORDER |
38 | |
39 | //Uncomment this to debug the m_overlapCount values. When it is enabled, |
40 | //extensive tests will be done to verify that the values are true, |
41 | //and an assertion is triggered when not. |
42 | //This is very slow, especially with many child-ranges. |
43 | // #define SHOULD_DEBUG_OVERLAP |
44 | |
45 | #ifdef SHOULD_DEBUG_CHILD_ORDER |
46 | #define DEBUG_CHILD_ORDER \ |
47 | {\ |
48 | KTextEditor::Cursor lastEnd = KTextEditor::Cursor(-1,-1);\ |
49 | for(int a = 0; a < m_childRanges.size(); ++a) {\ |
50 | Q_ASSERT(m_childRanges[a]->end() >= lastEnd);\ |
51 | Q_ASSERT(m_childRanges[a]->start() >= start());\ |
52 | Q_ASSERT(m_childRanges[a]->end() <= end());\ |
53 | lastEnd = m_childRanges[a]->end();\ |
54 | }\ |
55 | }\ |
56 | |
57 | #else |
58 | #define DEBUG_CHILD_ORDER |
59 | #endif |
60 | |
61 | #ifdef SHOULD_DEBUG_OVERLAP |
62 | #define DEBUG_CHILD_OVERLAP \ |
63 | {\ |
64 | QVector<int> counter(m_childRanges.size(), 0);\ |
65 | \ |
66 | for(int a = 0; a < m_childRanges.size(); ++a) {\ |
67 | const SmartRange& overlapper(*m_childRanges[a]);\ |
68 | for(int b = 0; b < a; ++b) {\ |
69 | const SmartRange& overlapped(*m_childRanges[b]);\ |
70 | Q_ASSERT(overlapped.end() <= overlapper.end());\ |
71 | if(overlapped.end() > overlapper.start()) {\ |
72 | ++counter[b];\ |
73 | }\ |
74 | }\ |
75 | }\ |
76 | for(int a = 0; a < m_childRanges.size(); ++a) {\ |
77 | Q_ASSERT(m_childRanges[a]->m_overlapCount == counter[a]);\ |
78 | }\ |
79 | }\ |
80 | |
81 | #define DEBUG_PARENT_OVERLAP \ |
82 | if(m_parentRange) {\ |
83 | QVector<int> counter(m_parentRange->m_childRanges.size(), 0);\ |
84 | \ |
85 | for(int a = 0; a < m_parentRange->m_childRanges.size(); ++a) {\ |
86 | const SmartRange& overlapper(*m_parentRange->m_childRanges[a]);\ |
87 | for(int b = 0; b < a; ++b) {\ |
88 | const SmartRange& overlapped(*m_parentRange->m_childRanges[b]);\ |
89 | Q_ASSERT(overlapped.end() <= overlapper.end());\ |
90 | if(overlapped.end() > overlapper.start()) {\ |
91 | ++counter[b];\ |
92 | }\ |
93 | }\ |
94 | }\ |
95 | for(int a = 0; a < m_parentRange->m_childRanges.size(); ++a) {\ |
96 | Q_ASSERT(m_parentRange->m_childRanges[a]->m_overlapCount == counter[a]);\ |
97 | }\ |
98 | }\ |
99 | |
100 | #else |
101 | #define DEBUG_CHILD_OVERLAP |
102 | #define DEBUG_PARENT_OVERLAP |
103 | #endif |
104 | |
105 | ///Returns the index of the first range that ends behind @p pos |
106 | ///The list must be sorted by the ranges end-positions. |
107 | static int lowerBound(const QList<SmartRange*>& ranges, const Cursor& pos) |
108 | { |
109 | int begin = 0; |
110 | int n = ranges.count(); |
111 | |
112 | int half; |
113 | int middle; |
114 | |
115 | while (n > 0) { |
116 | half = n >> 1; |
117 | middle = begin + half; |
118 | if(ranges[middle]->end() > pos) { |
119 | n = half; |
120 | }else{ |
121 | begin = middle + 1; |
122 | n -= half + 1; |
123 | } |
124 | } |
125 | return begin; |
126 | } |
127 | |
128 | ///Searches for the given range, or a lower bound for the given position. Does not work correctly in case of overlaps, |
129 | ///but for that case we have a fallback. Only for use in findIndex. |
130 | static int lowerBoundRange(const QList<SmartRange*>& ranges, const Cursor& pos, const SmartRange* range) |
131 | { |
132 | int begin = 0; |
133 | int n = ranges.count(); |
134 | |
135 | int half; |
136 | int middle; |
137 | |
138 | while (n > 0) { |
139 | half = n >> 1; |
140 | middle = begin + half; |
141 | if(ranges[begin] == range) |
142 | return begin; |
143 | if(ranges[middle] == range) |
144 | return middle; |
145 | |
146 | if(ranges[middle]->end() > pos) { |
147 | n = half; |
148 | }else{ |
149 | begin = middle + 1; |
150 | n -= half + 1; |
151 | } |
152 | } |
153 | return begin; |
154 | } |
155 | |
156 | ///Finds the index of the given SmartRange in the sorted list using binary search. Uses @param range For searching, and @param smartRange for equality comparison. |
157 | static int findIndex(const QList<SmartRange*>& ranges, const SmartRange* smartRange, const Range* range) { |
158 | int index = lowerBoundRange(ranges, range->start(), smartRange); |
159 | int childCount = ranges.count(); |
160 | |
161 | //In case of degenerated ranges, we may have found the wrong index. |
162 | while(index < childCount && ranges[index] != smartRange) |
163 | ++index; |
164 | |
165 | if(index == childCount) { |
166 | //During rangeChanged the order may temporarily be inconsistent, so we use indexOf as fallback |
167 | return ranges.indexOf(const_cast<SmartRange*>(smartRange)); |
168 | /* if(smartRange != range) //Try again finding the range, using the smart-range only |
169 | return findIndex(ranges, smartRange, smartRange);*/ |
170 | |
171 | // Q_ASSERT(ranges.indexOf(const_cast<SmartRange*>(smartRange)) == -1); |
172 | return -1; |
173 | } |
174 | |
175 | return index; |
176 | } |
177 | |
178 | SmartRange::SmartRange(SmartCursor* start, SmartCursor* end, SmartRange * parent, InsertBehaviors insertBehavior ) |
179 | : Range(start, end) |
180 | , m_attribute(0L) |
181 | , m_parentRange(parent) |
182 | , m_ownsAttribute(false) |
183 | , m_overlapCount(0) |
184 | { |
185 | setInsertBehavior(insertBehavior); |
186 | |
187 | // Not calling setParentRange here...: |
188 | // 1) subclasses are not yet constructed |
189 | // 2) it would otherwise give the wrong impression |
190 | if (m_parentRange) |
191 | m_parentRange->insertChildRange(this); |
192 | } |
193 | |
194 | SmartRange::~SmartRange( ) |
195 | { |
196 | deleteChildRanges(); |
197 | |
198 | setParentRange(0L); |
199 | |
200 | /*if (!m_deleteCursors) |
201 | { |
202 | // Save from deletion in the parent |
203 | m_start = 0L; |
204 | m_end = 0L; |
205 | }*/ |
206 | } |
207 | |
208 | bool SmartRange::confineToRange(const Range& range) |
209 | { |
210 | if (!Range::confineToRange(range)) |
211 | // Don't need to check if children should be confined, they already are |
212 | return false; |
213 | |
214 | foreach (SmartRange* child, m_childRanges) |
215 | child->confineToRange(*this); |
216 | |
217 | return true; |
218 | } |
219 | |
220 | bool SmartRange::expandToRange(const Range& range) |
221 | { |
222 | if (!Range::expandToRange(range)) |
223 | // Don't need to check if parents should be expanded, they already are |
224 | return false; |
225 | |
226 | if (parentRange()) |
227 | parentRange()->expandToRange(*this); |
228 | |
229 | return true; |
230 | } |
231 | |
232 | void SmartRange::setRange(const Range& range) |
233 | { |
234 | if (range == *this) |
235 | return; |
236 | |
237 | Range old = *this; |
238 | |
239 | Range::setRange(range); |
240 | |
241 | DEBUG_CHILD_OVERLAP |
242 | } |
243 | |
244 | const QList<SmartRange*>& SmartRange::childRanges() const |
245 | { |
246 | return m_childRanges; |
247 | } |
248 | |
249 | SmartRange * SmartRange::childBefore( const SmartRange * range ) const |
250 | { |
251 | int index = findIndex(m_childRanges, range, range); |
252 | |
253 | if (--index >= 0) |
254 | return m_childRanges[index]; |
255 | |
256 | return 0L; |
257 | } |
258 | |
259 | SmartRange * SmartRange::childAfter( const SmartRange * range ) const |
260 | { |
261 | int index = findIndex(m_childRanges, range, range); |
262 | if (index != -1 && ++index < m_childRanges.count()) |
263 | return m_childRanges[index]; |
264 | return 0L; |
265 | } |
266 | |
267 | void SmartRange::insertChildRange( SmartRange * newChild ) |
268 | { |
269 | DEBUG_CHILD_OVERLAP |
270 | |
271 | Q_ASSERT(newChild->parentRange() == this); |
272 | |
273 | // A new child has been added, so expand this range if required. |
274 | expandToRange(*newChild); |
275 | |
276 | DEBUG_CHILD_ORDER |
277 | |
278 | int insertAt = lowerBound(m_childRanges, newChild->end()); |
279 | m_childRanges.insert(insertAt, newChild); |
280 | |
281 | //Increase the overlap of previous ranges |
282 | for(int current = insertAt-1; current >= 0; --current) { |
283 | SmartRange& range(*m_childRanges[current]); |
284 | Q_ASSERT(range.end() <= newChild->end()); |
285 | |
286 | if(range.end() > newChild->start()) { |
287 | ++range.m_overlapCount; |
288 | }else{ |
289 | //range.end() <= start(), The range does not overlap, and the same applies for all earlier ranges |
290 | break; |
291 | } |
292 | } |
293 | |
294 | //Increase this ranges overlap from already existing ranges |
295 | for(int current = insertAt+1; current < m_childRanges.size(); ++current) { |
296 | SmartRange& range(*m_childRanges[current]); |
297 | Q_ASSERT(range.end() >= newChild->end()); |
298 | |
299 | if(range.start() < newChild->end()) |
300 | ++newChild->m_overlapCount; //The range overlaps newChild |
301 | |
302 | if(!range.m_overlapCount) |
303 | break; //If this follower-range isn't overlapped by any other ranges, we can break here. |
304 | } |
305 | |
306 | DEBUG_CHILD_OVERLAP |
307 | |
308 | DEBUG_CHILD_ORDER |
309 | |
310 | QMutableListIterator<SmartRange*> it = m_childRanges; |
311 | it.toBack(); |
312 | |
313 | foreach (SmartRangeNotifier* n, m_notifiers) |
314 | emit n->childRangeInserted(this, newChild); |
315 | |
316 | foreach (SmartRangeWatcher* w, m_watchers) |
317 | w->childRangeInserted(this, newChild); |
318 | |
319 | DEBUG_CHILD_OVERLAP |
320 | DEBUG_CHILD_ORDER |
321 | } |
322 | |
323 | void SmartRange::removeChildRange(SmartRange* child) |
324 | { |
325 | DEBUG_CHILD_OVERLAP |
326 | |
327 | int index = findIndex(m_childRanges, child, child); |
328 | if (index != -1) { |
329 | m_childRanges.removeAt(index); |
330 | |
331 | //Reduce the overlap with all previously overlapping ranges(parentChildren is still sorted by the old end-position) |
332 | for(int current = index-1; current >= 0; --current) { |
333 | SmartRange& range(*m_childRanges[current]); |
334 | Q_ASSERT(range.end() <= child->end()); |
335 | if(range.end() <= child->start()) { |
336 | break; //This range did not overlap before, the same applies for all earlier ranges because of the order |
337 | }else{ |
338 | if(range.m_overlapCount) { |
339 | --range.m_overlapCount; |
340 | } else { |
341 | //May happen with more than 64 overlaps |
342 | #ifdef SHOULD_DEBUG_OVERLAP |
343 | Q_ASSERT(0); |
344 | #endif |
345 | } |
346 | } |
347 | } |
348 | |
349 | DEBUG_CHILD_OVERLAP |
350 | |
351 | child->m_overlapCount = 0; //It has no neighbors any more, so no overlap |
352 | |
353 | foreach (SmartRangeNotifier* n, m_notifiers) |
354 | emit n->childRangeInserted(this, child); |
355 | |
356 | foreach (SmartRangeWatcher* w, m_watchers) |
357 | w->childRangeInserted(this, child); |
358 | } |
359 | |
360 | DEBUG_CHILD_OVERLAP |
361 | } |
362 | |
363 | SmartRange * SmartRange::mostSpecificRange( const Range & input ) const |
364 | { |
365 | if (!input.isValid()) |
366 | return 0L; |
367 | |
368 | if (contains(input)) { |
369 | int child = lowerBound(m_childRanges, input.start()); |
370 | |
371 | SmartRange* mostSpecific = 0; |
372 | |
373 | while(child != m_childRanges.size()) { |
374 | SmartRange* r = m_childRanges[child]; |
375 | if(r->contains(input)) { |
376 | SmartRange* candidate = r->mostSpecificRange(input); |
377 | if(mostSpecific == 0 || |
378 | ((candidate->end() - candidate->start()) < (mostSpecific->end() - mostSpecific->start())) || |
379 | (candidate->end() < mostSpecific->end())) |
380 | mostSpecific = candidate; |
381 | } |
382 | |
383 | if(r->m_overlapCount == 0) |
384 | break; |
385 | |
386 | ++child; //We have to iterate as long as there is overlapping ranges |
387 | } |
388 | |
389 | if(mostSpecific) |
390 | return mostSpecific; |
391 | else |
392 | return const_cast<SmartRange*>(this); |
393 | |
394 | } else if (parentRange()) { |
395 | return parentRange()->mostSpecificRange(input); |
396 | |
397 | } else { |
398 | return 0L; |
399 | } |
400 | } |
401 | |
402 | SmartRange * SmartRange::firstRangeContaining( const Cursor & pos ) const |
403 | { |
404 | if (!pos.isValid()) |
405 | return 0L; |
406 | |
407 | if (contains(pos)) { |
408 | if (parentRange() && parentRange()->contains(pos)) |
409 | return parentRange()->firstRangeContaining(pos); |
410 | |
411 | return const_cast<SmartRange*>(this); |
412 | |
413 | } else { |
414 | if (!parentRange()) |
415 | return 0L; |
416 | |
417 | return parentRange()->firstRangeContaining(pos); |
418 | } |
419 | } |
420 | |
421 | int SmartRange::overlapCount() const |
422 | { |
423 | return m_overlapCount; |
424 | } |
425 | |
426 | QList<SmartRange*> SmartRange::deepestRangesContaining(const Cursor& pos) const |
427 | { |
428 | QList<SmartRange*> ret; |
429 | |
430 | if(!contains(pos)) |
431 | return ret; |
432 | |
433 | int child = lowerBound(m_childRanges, pos); |
434 | |
435 | while(child != m_childRanges.size()) { |
436 | SmartRange* r = m_childRanges[child]; |
437 | //The list will be unchanged if the range doesn't contain the position |
438 | ret += r->deepestRangesContaining(pos); |
439 | |
440 | if(r->m_overlapCount == 0) |
441 | break; |
442 | |
443 | ++child; //We have to iterate as long as there is overlapping ranges |
444 | } |
445 | |
446 | if(!ret.isEmpty()) |
447 | return ret; |
448 | else |
449 | return ret << const_cast<SmartRange*>(this); |
450 | } |
451 | |
452 | SmartRange * SmartRange::deepestRangeContaining( const Cursor & pos, QStack<SmartRange*>* rangesEntered, QStack<SmartRange*>* rangesExited ) const |
453 | { |
454 | if (!pos.isValid()) { |
455 | // Just leave all ranges |
456 | if (rangesExited) { |
457 | SmartRange* range = const_cast<SmartRange*>(this); |
458 | while (range) { |
459 | rangesExited->append(range); |
460 | range = range->parentRange(); |
461 | } |
462 | } |
463 | return 0L; |
464 | } |
465 | |
466 | return deepestRangeContainingInternal(pos, rangesEntered, rangesExited, true); |
467 | } |
468 | |
469 | SmartRange * SmartRange::deepestRangeContainingInternal( const Cursor & pos, QStack<SmartRange*>* rangesEntered, QStack<SmartRange*>* rangesExited, bool first ) const |
470 | { |
471 | if (contains(pos)) { |
472 | if (!first && rangesEntered) |
473 | rangesEntered->push(const_cast<SmartRange*>(this)); |
474 | |
475 | int child = lowerBound(m_childRanges, pos); |
476 | |
477 | QStack<SmartRange*> mostSpecificStack; |
478 | SmartRange* mostSpecific = 0; |
479 | |
480 | while(child != m_childRanges.size()) { |
481 | SmartRange* r = m_childRanges[child]; |
482 | if(r->contains(pos)) { |
483 | QStack<SmartRange*> candidateStack; |
484 | SmartRange* candidateRange = r->deepestRangeContainingInternal(pos, rangesEntered ? &candidateStack : 0, 0); |
485 | |
486 | Q_ASSERT(!rangesEntered || !candidateStack.isEmpty()); |
487 | Q_ASSERT(candidateRange); |
488 | |
489 | if(!mostSpecific || |
490 | ((candidateRange->end() - candidateRange->start()) < (mostSpecific->end() - mostSpecific->start())) || |
491 | (candidateRange->end() < mostSpecific->end())) { |
492 | mostSpecific = candidateRange; |
493 | mostSpecificStack = candidateStack; |
494 | } |
495 | } |
496 | |
497 | if(r->m_overlapCount == 0) |
498 | break; |
499 | |
500 | ++child; //We have to iterate as long as there is overlapping ranges |
501 | } |
502 | |
503 | if(mostSpecific) { |
504 | if(rangesEntered) |
505 | *rangesEntered += mostSpecificStack; |
506 | return mostSpecific; |
507 | } |
508 | |
509 | return const_cast<SmartRange*>(this); |
510 | |
511 | } else { |
512 | if (rangesExited) |
513 | rangesExited->push(const_cast<SmartRange*>(this)); |
514 | |
515 | if (!parentRange()) |
516 | return 0L; |
517 | |
518 | // first is true, because the parentRange won't be "entered" on first descent |
519 | return parentRange()->deepestRangeContainingInternal(pos, rangesEntered, rangesExited, true); |
520 | } |
521 | } |
522 | |
523 | Document* SmartRange::document( ) const |
524 | { |
525 | return smartStart().document(); |
526 | } |
527 | |
528 | void SmartRange::associateAction( KAction * action ) |
529 | { |
530 | m_associatedActions.append(action); |
531 | |
532 | bool enable = false; |
533 | if (View* v = document()->activeView()) |
534 | if (contains(v->cursorPosition())) |
535 | enable = true; |
536 | |
537 | action->setEnabled(enable); |
538 | |
539 | if (m_associatedActions.count() == 1) |
540 | checkFeedback(); |
541 | } |
542 | |
543 | void SmartRange::dissociateAction( KAction * action ) |
544 | { |
545 | m_associatedActions.removeAll(action); |
546 | if (!m_associatedActions.count()) |
547 | checkFeedback(); |
548 | } |
549 | |
550 | void SmartRange::clearAssociatedActions( ) |
551 | { |
552 | m_associatedActions.clear(); |
553 | checkFeedback(); |
554 | } |
555 | |
556 | SmartRange::InsertBehaviors SmartRange::insertBehavior( ) const |
557 | { |
558 | return ((smartStart().insertBehavior() == SmartCursor::MoveOnInsert) ? DoNotExpand : ExpandLeft) | ((smartEnd().insertBehavior() == SmartCursor::MoveOnInsert) ? ExpandRight : DoNotExpand); |
559 | } |
560 | |
561 | void SmartRange::setInsertBehavior(SmartRange::InsertBehaviors behavior) |
562 | { |
563 | static_cast<SmartCursor*>(m_start)->setInsertBehavior((behavior & ExpandLeft) ? SmartCursor::StayOnInsert : SmartCursor::MoveOnInsert); |
564 | static_cast<SmartCursor*>(m_end)->setInsertBehavior((behavior & ExpandRight) ? SmartCursor::MoveOnInsert : SmartCursor::StayOnInsert); |
565 | } |
566 | |
567 | void SmartRange::clearChildRanges() |
568 | { |
569 | foreach (SmartRange* r, m_childRanges) |
570 | r->removeText(); |
571 | } |
572 | |
573 | void SmartRange::deleteChildRanges() |
574 | { |
575 | // FIXME: Probably more efficient to prevent them from unlinking themselves? |
576 | qDeleteAll(m_childRanges); |
577 | |
578 | // i.e. this is probably already clear |
579 | m_childRanges.clear(); |
580 | } |
581 | |
582 | void SmartRange::clearAndDeleteChildRanges( ) |
583 | { |
584 | // FIXME: Probably more efficient to prevent them from unlinking themselves? |
585 | foreach (SmartRange* r, m_childRanges) |
586 | r->removeText(); |
587 | |
588 | qDeleteAll(m_childRanges); |
589 | |
590 | // i.e. this is probably already clear |
591 | m_childRanges.clear(); |
592 | } |
593 | |
594 | void SmartRange::setParentRange( SmartRange * r ) |
595 | { |
596 | if (m_parentRange == r) |
597 | return; |
598 | |
599 | DEBUG_PARENT_OVERLAP |
600 | |
601 | if (m_parentRange) |
602 | m_parentRange->removeChildRange(this); |
603 | |
604 | SmartRange* oldParent = m_parentRange; |
605 | |
606 | m_parentRange = r; |
607 | |
608 | if (m_parentRange) |
609 | m_parentRange->insertChildRange(this); |
610 | |
611 | foreach (SmartRangeNotifier* n, m_notifiers) |
612 | emit n->parentRangeChanged(this, m_parentRange, oldParent); |
613 | |
614 | foreach (SmartRangeWatcher* w, m_watchers) |
615 | w->parentRangeChanged(this, m_parentRange, oldParent); |
616 | |
617 | DEBUG_PARENT_OVERLAP |
618 | } |
619 | |
620 | void SmartRange::setAttribute( Attribute::Ptr attribute ) |
621 | { |
622 | if (attribute == m_attribute) |
623 | return; |
624 | |
625 | Attribute::Ptr prev = m_attribute; |
626 | |
627 | m_attribute = attribute; |
628 | |
629 | foreach (SmartRangeNotifier* n, m_notifiers) |
630 | emit n->rangeAttributeChanged(this, attribute, prev); |
631 | |
632 | foreach (SmartRangeWatcher* w, m_watchers) |
633 | w->rangeAttributeChanged(this, attribute, prev); |
634 | } |
635 | |
636 | Attribute::Ptr SmartRange::attribute( ) const |
637 | { |
638 | return m_attribute; |
639 | } |
640 | |
641 | QStringList SmartRange::text( bool block ) const |
642 | { |
643 | return document()->textLines(*this, block); |
644 | } |
645 | |
646 | bool SmartRange::replaceText( const QStringList & text, bool block ) |
647 | { |
648 | return document()->replaceText(*this, text, block); |
649 | } |
650 | |
651 | bool SmartRange::removeText( bool block ) |
652 | { |
653 | return document()->removeText(*this, block); |
654 | } |
655 | |
656 | static bool rangeEndLessThan(const SmartRange* s1, const SmartRange* s2) { |
657 | return s1->end() < s2->end(); |
658 | } |
659 | |
660 | void SmartRange::rebuildChildStructure() { |
661 | |
662 | ///Re-order |
663 | qStableSort(m_childRanges.begin(), m_childRanges.end(), rangeEndLessThan); |
664 | DEBUG_CHILD_ORDER |
665 | ///Update overlap |
666 | for(int a = 0; a < m_childRanges.size(); ++a) { |
667 | SmartRange& overlapper(*m_childRanges[a]); |
668 | overlapper.m_overlapCount = 0; |
669 | |
670 | //Increase the overlap of overlapped ranegs |
671 | for(int current = a-1; current >= 0; --current) { |
672 | SmartRange& range(*m_childRanges[current]); |
673 | Q_ASSERT(range.end() <= overlapper.end()); |
674 | |
675 | if(range.end() > overlapper.start()) { |
676 | ++range.m_overlapCount; |
677 | }else{ |
678 | //range.end() <= start(), The range does not overlap, and the same applies for all earlier ranges |
679 | break; |
680 | } |
681 | } |
682 | } |
683 | |
684 | DEBUG_CHILD_OVERLAP |
685 | } |
686 | |
687 | void SmartRange::rangeChanged( Cursor* c, const Range& from ) |
688 | { |
689 | #ifdef SHOULD_DEBUG_CHILD_ORDER |
690 | if (parentRange() ) { |
691 | //Make sure the child-order is correct, in respect to "from" |
692 | QList<SmartRange*>& parentChildren(parentRange()->m_childRanges); |
693 | |
694 | int index = findIndex(parentChildren, this, &from); |
695 | Q_ASSERT(index != -1); |
696 | Q_ASSERT(parentChildren[index] == this); |
697 | const Range* lastRange = 0; |
698 | for(int a = 0; a < index; ++a) { |
699 | if(lastRange) { |
700 | Q_ASSERT(lastRange->end() <= parentChildren[a]->end()); |
701 | } |
702 | lastRange = parentChildren[a]; |
703 | } |
704 | |
705 | if(lastRange) { |
706 | Q_ASSERT(lastRange->end() <= from.end()); |
707 | } |
708 | |
709 | if(index+1 < parentChildren.size()) { |
710 | Q_ASSERT(from.end() <= parentChildren[index+1]->end()); |
711 | } |
712 | lastRange = &from; |
713 | |
714 | for(int a = index+1; a < parentChildren.size(); ++a) { |
715 | if(lastRange) { |
716 | Q_ASSERT(lastRange->end() <= parentChildren[a]->end()); |
717 | } |
718 | lastRange = parentChildren[a]; |
719 | } |
720 | } |
721 | #endif |
722 | Range::rangeChanged(c, from); |
723 | |
724 | // Decide whether the parent range has expanded or contracted, if there is one |
725 | if (parentRange() ) { |
726 | QList<SmartRange*>& parentChildren(parentRange()->m_childRanges); |
727 | |
728 | int index = findIndex(parentChildren, this, &from); |
729 | Q_ASSERT(index != -1); |
730 | Q_ASSERT(parentChildren[index] == this); |
731 | |
732 | //Reduce the overlap with all previously overlapping ranges(parentChildren is still sorted by the old end-position) |
733 | for(int current = index-1; current >= 0; --current) { |
734 | SmartRange& range(*parentChildren[current]); |
735 | Q_ASSERT(range.end() <= from.end()); |
736 | if(range.end() <= from.start()) { |
737 | // break; //This range did not overlap before, the same applies for all earlier ranges because of the order |
738 | }else{ |
739 | if(range.m_overlapCount) { |
740 | --range.m_overlapCount; |
741 | }else{ |
742 | #ifdef SHOULD_DEBUG_OVERLAP |
743 | Q_ASSERT(0); |
744 | #endif |
745 | } |
746 | } |
747 | } |
748 | |
749 | //Decrease this ranges overlap from existing ranges behind, since it may be moved so it isn't overlapped any more |
750 | for(int current = index+1; current < parentChildren.size(); ++current) { |
751 | SmartRange& range(*parentChildren[current]); |
752 | Q_ASSERT(range.end() >= from.end()); |
753 | |
754 | if(range.start() < from.end()) |
755 | --m_overlapCount; //The range overlaps newChild |
756 | |
757 | if(!range.m_overlapCount) |
758 | break; //If this follower-range isn't overlapped by any other ranges, we can break here. |
759 | } |
760 | |
761 | if(from.end() != end()) { |
762 | //Update the order in the parent, the ranges must be strictly sorted |
763 | if(from.end() > end()) { |
764 | //Bubble backwards, the position has been reduced |
765 | while(index > 0 && parentChildren[index-1]->end() > end()) { |
766 | parentChildren[index] = parentChildren[index-1]; |
767 | parentChildren[index-1] = this; |
768 | --index; |
769 | } |
770 | }else{ |
771 | //Bubble forwards, the position has moved forwards |
772 | while( index+1 < parentChildren.size() && (parentChildren[index+1]->end() < end()) ) { |
773 | parentChildren[index] = parentChildren[index+1]; |
774 | parentChildren[index+1] = this; |
775 | ++index; |
776 | } |
777 | } |
778 | } |
779 | Q_ASSERT(parentChildren[index] == this); |
780 | |
781 | //Increase the overlap |
782 | for(int current = index-1; current >= 0; --current) { |
783 | SmartRange& range(*parentChildren[current]); |
784 | Q_ASSERT(range.end() <= end()); |
785 | |
786 | if(range.end() > start()) { |
787 | ++range.m_overlapCount; |
788 | }else{ |
789 | //range.end() <= start(), The range does not overlap, and the same applies for all earlier ranges |
790 | break; |
791 | } |
792 | } |
793 | |
794 | //Increase this ranges overlap from existing ranges behind, since it may have been moved |
795 | for(int current = index+1; current < parentChildren.size(); ++current) { |
796 | SmartRange& range(*parentChildren[current]); |
797 | Q_ASSERT(range.end() >= end()); |
798 | |
799 | if(range.start() < end()) |
800 | ++m_overlapCount; //The range overlaps newChild |
801 | |
802 | if(!range.m_overlapCount) |
803 | break; //If this follower-range isn't overlapped by any other ranges, we can break here. |
804 | } |
805 | |
806 | DEBUG_CHILD_ORDER |
807 | DEBUG_PARENT_OVERLAP |
808 | |
809 | //Expand the parent in the end, so the overlap is consistent when the parent gets control |
810 | if ((start() < from.start() || end() > from.end())) |
811 | parentRange()->expandToRange(*this); |
812 | } |
813 | |
814 | DEBUG_CHILD_OVERLAP |
815 | |
816 | |
817 | // Contract child ranges if required |
818 | if(!m_childRanges.isEmpty()) { |
819 | if (start() > from.start()) { |
820 | foreach(SmartRange* child, m_childRanges) { |
821 | if(child->start() < start()) |
822 | child->start() = start(); |
823 | else if(!child->m_overlapCount) |
824 | break; //We can safely break here, because the child is not overlapped |
825 | } |
826 | } |
827 | |
828 | if (end() < from.end()) { |
829 | |
830 | //We have to create a copy of the child-ranges, because their order may change |
831 | QList<SmartRange*> oldChildRanges = m_childRanges; |
832 | |
833 | for(int a = oldChildRanges.size()-1; a >= 0; --a) { |
834 | if(oldChildRanges[a]->end() <= end()) |
835 | break; //Child-ranges are sorted by the end-cursor, so we can just break here. |
836 | oldChildRanges[a]->end() = end(); |
837 | } |
838 | } |
839 | } |
840 | |
841 | DEBUG_CHILD_ORDER |
842 | DEBUG_CHILD_OVERLAP |
843 | |
844 | // SmartCursor and its subclasses take care of adjusting ranges if the tree |
845 | // structure is being used. |
846 | foreach (SmartRangeNotifier* n, m_notifiers) |
847 | if (n->wantsDirectChanges()) { |
848 | emit n->rangePositionChanged(this); |
849 | emit n->rangeContentsChanged(this); |
850 | |
851 | if (start() == end()) |
852 | emit n->rangeEliminated(this); |
853 | } |
854 | |
855 | foreach (SmartRangeWatcher* w, m_watchers) |
856 | if (w->wantsDirectChanges()) { |
857 | w->rangePositionChanged(this); |
858 | w->rangeContentsChanged(this); |
859 | |
860 | if (start() == end()) |
861 | w->rangeEliminated(this); |
862 | } |
863 | } |
864 | |
865 | bool SmartRange::isSmartRange( ) const |
866 | { |
867 | return true; |
868 | } |
869 | |
870 | SmartRange* SmartRange::toSmartRange( ) const |
871 | { |
872 | return const_cast<SmartRange*>(this); |
873 | } |
874 | |
875 | bool SmartRange::hasParent( SmartRange * parent ) const |
876 | { |
877 | if (parentRange() == parent) |
878 | return true; |
879 | |
880 | if (parentRange()) |
881 | return parentRange()->hasParent(parent); |
882 | |
883 | return false; |
884 | } |
885 | |
886 | const QList< SmartRangeWatcher * > & SmartRange::watchers( ) const |
887 | { |
888 | return m_watchers; |
889 | } |
890 | |
891 | void SmartRange::addWatcher( SmartRangeWatcher * watcher ) |
892 | { |
893 | if (!m_watchers.contains(watcher)) |
894 | m_watchers.append(watcher); |
895 | |
896 | checkFeedback(); |
897 | } |
898 | |
899 | void SmartRange::removeWatcher( SmartRangeWatcher * watcher ) |
900 | { |
901 | m_watchers.removeAll(watcher); |
902 | checkFeedback(); |
903 | } |
904 | |
905 | SmartRangeNotifier * SmartRange::primaryNotifier( ) |
906 | { |
907 | if (m_notifiers.isEmpty()) |
908 | m_notifiers.append(createNotifier()); |
909 | |
910 | return m_notifiers.first(); |
911 | } |
912 | |
913 | const QList< SmartRangeNotifier * > SmartRange::notifiers( ) const |
914 | { |
915 | return m_notifiers; |
916 | } |
917 | |
918 | void SmartRange::addNotifier( SmartRangeNotifier * notifier ) |
919 | { |
920 | if (!m_notifiers.contains(notifier)) |
921 | m_notifiers.append(notifier); |
922 | |
923 | checkFeedback(); |
924 | } |
925 | |
926 | void SmartRange::removeNotifier( SmartRangeNotifier * notifier ) |
927 | { |
928 | m_notifiers.removeAll(notifier); |
929 | checkFeedback(); |
930 | } |
931 | |
932 | void SmartRange::deletePrimaryNotifier( ) |
933 | { |
934 | if (m_notifiers.isEmpty()) |
935 | return; |
936 | |
937 | SmartRangeNotifier* n = m_notifiers.first(); |
938 | removeNotifier(n); |
939 | delete n; |
940 | } |
941 | |
942 | void SmartRange::checkFeedback( ) |
943 | { |
944 | } |
945 | |
946 | // kate: space-indent on; indent-width 2; replace-tabs on; |
947 | |