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
32using 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 \
82if(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.
107static 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.
130static 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.
157static 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
178SmartRange::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
194SmartRange::~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
208bool 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
220bool 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
232void 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
244const QList<SmartRange*>& SmartRange::childRanges() const
245{
246 return m_childRanges;
247}
248
249SmartRange * 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
259SmartRange * 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
267void 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
323void 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
363SmartRange * 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
402SmartRange * 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
421int SmartRange::overlapCount() const
422{
423 return m_overlapCount;
424}
425
426QList<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
452SmartRange * 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
469SmartRange * 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
523Document* SmartRange::document( ) const
524{
525 return smartStart().document();
526}
527
528void 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
543void SmartRange::dissociateAction( KAction * action )
544{
545 m_associatedActions.removeAll(action);
546 if (!m_associatedActions.count())
547 checkFeedback();
548}
549
550void SmartRange::clearAssociatedActions( )
551{
552 m_associatedActions.clear();
553 checkFeedback();
554}
555
556SmartRange::InsertBehaviors SmartRange::insertBehavior( ) const
557{
558 return ((smartStart().insertBehavior() == SmartCursor::MoveOnInsert) ? DoNotExpand : ExpandLeft) | ((smartEnd().insertBehavior() == SmartCursor::MoveOnInsert) ? ExpandRight : DoNotExpand);
559}
560
561void 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
567void SmartRange::clearChildRanges()
568{
569 foreach (SmartRange* r, m_childRanges)
570 r->removeText();
571}
572
573void 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
582void 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
594void 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
620void 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
636Attribute::Ptr SmartRange::attribute( ) const
637{
638 return m_attribute;
639}
640
641QStringList SmartRange::text( bool block ) const
642{
643 return document()->textLines(*this, block);
644}
645
646bool SmartRange::replaceText( const QStringList & text, bool block )
647{
648 return document()->replaceText(*this, text, block);
649}
650
651bool SmartRange::removeText( bool block )
652{
653 return document()->removeText(*this, block);
654}
655
656static bool rangeEndLessThan(const SmartRange* s1, const SmartRange* s2) {
657 return s1->end() < s2->end();
658}
659
660void 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
687void 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
865bool SmartRange::isSmartRange( ) const
866{
867 return true;
868}
869
870SmartRange* SmartRange::toSmartRange( ) const
871{
872 return const_cast<SmartRange*>(this);
873}
874
875bool 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
886const QList< SmartRangeWatcher * > & SmartRange::watchers( ) const
887{
888 return m_watchers;
889}
890
891void SmartRange::addWatcher( SmartRangeWatcher * watcher )
892{
893 if (!m_watchers.contains(watcher))
894 m_watchers.append(watcher);
895
896 checkFeedback();
897}
898
899void SmartRange::removeWatcher( SmartRangeWatcher * watcher )
900{
901 m_watchers.removeAll(watcher);
902 checkFeedback();
903}
904
905SmartRangeNotifier * SmartRange::primaryNotifier( )
906{
907 if (m_notifiers.isEmpty())
908 m_notifiers.append(createNotifier());
909
910 return m_notifiers.first();
911}
912
913const QList< SmartRangeNotifier * > SmartRange::notifiers( ) const
914{
915 return m_notifiers;
916}
917
918void SmartRange::addNotifier( SmartRangeNotifier * notifier )
919{
920 if (!m_notifiers.contains(notifier))
921 m_notifiers.append(notifier);
922
923 checkFeedback();
924}
925
926void SmartRange::removeNotifier( SmartRangeNotifier * notifier )
927{
928 m_notifiers.removeAll(notifier);
929 checkFeedback();
930}
931
932void 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
942void SmartRange::checkFeedback( )
943{
944}
945
946// kate: space-indent on; indent-width 2; replace-tabs on;
947