Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 :
21 : #include <algorithm>
22 : #include <functional>
23 : #include <SwNumberTree.hxx>
24 : #include <osl/diagnose.h>
25 :
26 : using std::vector;
27 : using std::find;
28 :
29 :
30 9383 : SwNumberTreeNode::SwNumberTreeNode()
31 : : mChildren(),
32 : mpParent( 0 ),
33 : mnNumber( 0 ),
34 : mbContinueingPreviousSubTree( false ),
35 : mbPhantom( false ),
36 9383 : mItLastValid()
37 : {
38 9383 : mItLastValid = mChildren.end();
39 9383 : }
40 :
41 13038 : SwNumberTreeNode::~SwNumberTreeNode()
42 : {
43 6519 : if (GetChildCount() > 0)
44 : {
45 0 : if (HasOnlyPhantoms())
46 : {
47 0 : delete *mChildren.begin();
48 :
49 0 : mChildren.clear();
50 0 : mItLastValid = mChildren.end();
51 : }
52 : else
53 : {
54 : OSL_FAIL("lost children!");
55 : }
56 : }
57 :
58 : OSL_ENSURE( IsPhantom() || mpParent == NULL, ": I'm not supposed to have a parent.");
59 :
60 6519 : mpParent = (SwNumberTreeNode *) 0xdeadbeef;
61 :
62 : OSL_ENSURE(mChildren.empty(), "children left!");
63 6519 : }
64 :
65 672 : SwNumberTreeNode * SwNumberTreeNode::CreatePhantom()
66 : {
67 672 : SwNumberTreeNode * pNew = NULL;
68 :
69 1650 : if (! mChildren.empty() &&
70 978 : (*mChildren.begin())->IsPhantom())
71 : {
72 : OSL_FAIL("phantom already present");
73 : }
74 : else
75 : {
76 672 : pNew = Create();
77 672 : pNew->SetPhantom(true);
78 672 : pNew->mpParent = this;
79 :
80 : std::pair<tSwNumberTreeChildren::iterator, bool> aInsert =
81 672 : mChildren.insert(pNew);
82 :
83 672 : if (! aInsert.second)
84 : {
85 : OSL_FAIL("insert of phantom failed!");
86 :
87 0 : delete pNew;
88 0 : pNew = NULL;
89 : }
90 : }
91 :
92 672 : return pNew;
93 : }
94 :
95 526 : SwNumberTreeNode * SwNumberTreeNode::GetRoot() const
96 : {
97 526 : SwNumberTreeNode * pResult = mpParent;
98 :
99 526 : if (pResult)
100 1245 : while (pResult->mpParent)
101 193 : pResult = pResult->mpParent;
102 :
103 526 : return pResult;
104 : }
105 :
106 8608 : void SwNumberTreeNode::ClearObsoletePhantoms()
107 : {
108 8608 : tSwNumberTreeChildren::iterator aIt = mChildren.begin();
109 :
110 8608 : if (aIt != mChildren.end() && (*aIt)->IsPhantom())
111 : {
112 801 : (*aIt)->ClearObsoletePhantoms();
113 :
114 801 : if ((*aIt)->mChildren.empty())
115 : {
116 : // #i60652#
117 : // Because <mChildren.erase(aIt)> could destroy the element, which
118 : // is referenced by <mItLastValid>, it's needed to adjust
119 : // <mItLastValid> before erasing <aIt>.
120 503 : SetLastValid(mChildren.end());
121 :
122 503 : delete *aIt;
123 503 : mChildren.erase(aIt);
124 : }
125 : }
126 8608 : }
127 :
128 778 : void SwNumberTreeNode::ValidateHierarchical(const SwNumberTreeNode * pNode) const
129 : {
130 : tSwNumberTreeChildren::const_iterator aValidateIt =
131 778 : GetIterator(pNode);
132 :
133 778 : if (aValidateIt != mChildren.end())
134 : {
135 : OSL_ENSURE((*aValidateIt)->mpParent == this, "wrong parent");
136 :
137 778 : tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
138 :
139 : // -->
140 : // improvement:
141 : // - Only one time checked for <mChildren.end()>.
142 : // - Less checks for each loop run.
143 : // correction:
144 : // - consider case that current node isn't counted and isn't the first
145 : // child of its parent. In this case the number of last counted child
146 : // of the previous node determines the start value for the following
147 : // children loop, if all children have to be validated and the first
148 : // one doesn't restart the counting.
149 778 : SwNumberTree::tSwNumTreeNumber nTmpNumber( 0 );
150 778 : if (aIt != mChildren.end())
151 493 : nTmpNumber = (*aIt)->mnNumber;
152 : else
153 : {
154 285 : aIt = mChildren.begin();
155 285 : (*aIt)->mbContinueingPreviousSubTree = false;
156 :
157 : // determine default start value
158 : // consider the case that the first child isn't counted.
159 285 : nTmpNumber = (*aIt)->GetStartValue();
160 313 : if ( !(*aIt)->IsCounted() &&
161 28 : ( !(*aIt)->HasCountedChildren() || (*aIt)->IsPhantom() ) )
162 : {
163 28 : --nTmpNumber;
164 : }
165 :
166 : // determine special start value for the case that first child
167 : // doesn't restart the numbering and the parent node isn't counted
168 : // and isn't the first child.
169 285 : const bool bParentCounted( IsCounted() &&
170 179 : ( !IsPhantom() ||
171 464 : HasPhantomCountedParent() ) );
172 809 : if ( !(*aIt)->IsRestart() &&
173 524 : GetParent() && !bParentCounted )
174 : {
175 : tSwNumberTreeChildren::const_iterator aParentChildIt =
176 106 : GetParent()->GetIterator( this );
177 226 : while ( aParentChildIt != GetParent()->mChildren.begin() )
178 : {
179 20 : --aParentChildIt;
180 20 : SwNumberTreeNode* pPrevNode( *aParentChildIt );
181 20 : if ( pPrevNode->GetChildCount() > 0 )
182 : {
183 0 : (*aIt)->mbContinueingPreviousSubTree = true;
184 0 : nTmpNumber = (*(pPrevNode->mChildren.rbegin()))->GetNumber();
185 0 : if ( (*aIt)->IsCounted() &&
186 0 : ( !(*aIt)->IsPhantom() ||
187 0 : (*aIt)->HasPhantomCountedParent() ) )
188 : {
189 0 : ++nTmpNumber;
190 : }
191 0 : break;
192 : }
193 20 : else if ( pPrevNode->IsCounted() )
194 : {
195 6 : break;
196 : }
197 : else
198 : {
199 : // Previous node has no children and is not counted.
200 : // Thus, next turn and check for the previous node.
201 : }
202 : }
203 : }
204 :
205 285 : (*aIt)->mnNumber = nTmpNumber;
206 : }
207 :
208 2071 : while (aIt != aValidateIt)
209 : {
210 515 : ++aIt;
211 515 : (*aIt)->mbContinueingPreviousSubTree = false;
212 :
213 : // --> only for counted nodes the number
214 : // has to be adjusted, compared to the previous node.
215 : // this condition is hold also for nodes, which restart the numbering.
216 515 : if ( (*aIt)->IsCounted() )
217 : {
218 491 : if ((*aIt)->IsRestart())
219 0 : nTmpNumber = (*aIt)->GetStartValue();
220 : else
221 491 : ++nTmpNumber;
222 : }
223 :
224 515 : (*aIt)->mnNumber = nTmpNumber;
225 : }
226 :
227 778 : SetLastValid(aIt, true);
228 : }
229 778 : }
230 :
231 216 : void SwNumberTreeNode::ValidateContinuous(const SwNumberTreeNode * pNode) const
232 : {
233 216 : tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
234 :
235 216 : SwNumberTree::tSwNumTreeNumber nTmpNumber = 0;
236 :
237 1080 : do
238 : {
239 216 : if (aIt == mChildren.end())
240 : {
241 18 : aIt = mChildren.begin();
242 :
243 18 : nTmpNumber = GetStartValue();
244 : }
245 : else
246 198 : ++aIt;
247 :
248 216 : if (aIt != mChildren.end())
249 : {
250 216 : SwNumberTreeNode * pPred = (*aIt)->GetPred();
251 :
252 : // #i64311#
253 : // correct consideration of phantoms
254 : // correct consideration of restart at a number tree node
255 216 : if ( pPred )
256 : {
257 198 : if ( !(*aIt)->IsCounted() )
258 : // #i65284#
259 24 : nTmpNumber = pPred->GetNumber( pPred->GetParent() != (*aIt)->GetParent() );
260 : else
261 : {
262 174 : if ( (*aIt)->IsRestart() )
263 0 : nTmpNumber = (*aIt)->GetStartValue();
264 : else
265 174 : nTmpNumber = pPred->GetNumber( pPred->GetParent() != (*aIt)->GetParent() ) + 1;
266 : }
267 : }
268 : else
269 : {
270 18 : if ( !(*aIt)->IsCounted() )
271 0 : nTmpNumber = GetStartValue() - 1;
272 : else
273 : {
274 18 : if ( (*aIt)->IsRestart() )
275 0 : nTmpNumber = (*aIt)->GetStartValue();
276 : else
277 18 : nTmpNumber = GetStartValue();
278 : }
279 : }
280 :
281 216 : (*aIt)->mnNumber = nTmpNumber;
282 : }
283 : }
284 864 : while (aIt != mChildren.end() && *aIt != pNode);
285 :
286 : // #i74748# - applied patch from garnier_romain
287 : // number tree node has to be validated.
288 216 : SetLastValid( aIt, true );
289 216 : }
290 :
291 2971 : void SwNumberTreeNode::Validate(const SwNumberTreeNode * pNode) const
292 : {
293 2971 : if (! IsValid(pNode))
294 : {
295 994 : if (IsContinuous())
296 216 : ValidateContinuous(pNode);
297 : else
298 778 : ValidateHierarchical(pNode);
299 : }
300 2971 : }
301 :
302 0 : void SwNumberTreeNode::ValidateTree()
303 : {
304 0 : if (! IsContinuous())
305 : {
306 : {
307 0 : tSwNumberTreeChildren::reverse_iterator aIt = mChildren.rbegin();
308 :
309 0 : if (aIt != mChildren.rend())
310 0 : Validate(*aIt);
311 : }
312 : {
313 0 : tSwNumberTreeChildren::iterator aIt;
314 :
315 0 : for (aIt = mChildren.begin(); aIt != mChildren.end(); ++aIt)
316 0 : (*aIt)->ValidateTree();
317 : }
318 : }
319 : else
320 : {
321 0 : SwNumberTreeNode * pNode = GetLastDescendant();
322 :
323 0 : if (pNode && pNode->mpParent)
324 0 : pNode->mpParent->Validate(pNode);
325 : }
326 0 : }
327 :
328 2956 : void SwNumberTreeNode::_GetNumberVector(vector<SwNumberTree::tSwNumTreeNumber> & rVector,
329 : bool bValidate) const
330 : {
331 2956 : if (mpParent)
332 : {
333 1992 : mpParent->_GetNumberVector(rVector, bValidate);
334 1992 : rVector.push_back(GetNumber(bValidate));
335 : }
336 2956 : }
337 :
338 2 : SwNumberTreeNode * SwNumberTreeNode::GetFirstNonPhantomChild()
339 : {
340 2 : if (IsPhantom())
341 1 : return (*mChildren.begin())->GetFirstNonPhantomChild();
342 :
343 1 : return this;
344 : }
345 :
346 : /** Moves all children of this node that are greater than a given node
347 : to the destination node.
348 : */
349 66 : void SwNumberTreeNode::MoveGreaterChildren( SwNumberTreeNode& _rCompareNode,
350 : SwNumberTreeNode& _rDestNode )
351 : {
352 66 : if ( mChildren.empty() )
353 66 : return;
354 :
355 : // determine first child, which has to move to <_rDestNode>
356 66 : tSwNumberTreeChildren::iterator aItUpper( mChildren.end() );
357 134 : if ((*mChildren.begin())->IsPhantom() &&
358 68 : _rCompareNode.LessThan(*(*mChildren.begin())->GetFirstNonPhantomChild()))
359 : {
360 0 : aItUpper = mChildren.begin();
361 : }
362 : else
363 : {
364 66 : aItUpper = mChildren.upper_bound(&_rCompareNode);
365 : }
366 :
367 : // move children
368 66 : if (aItUpper != mChildren.end())
369 : {
370 0 : tSwNumberTreeChildren::iterator aIt;
371 0 : for (aIt = aItUpper; aIt != mChildren.end(); ++aIt)
372 0 : (*aIt)->mpParent = &_rDestNode;
373 :
374 0 : _rDestNode.mChildren.insert(aItUpper, mChildren.end());
375 :
376 : // #i60652#
377 : // Because <mChildren.erase(aItUpper, mChildren.end())> could destroy
378 : // the element, which is referenced by <mItLastValid>, it's needed to
379 : // adjust <mItLastValid> before erasing <aIt>.
380 0 : SetLastValid( mChildren.end() );
381 :
382 0 : mChildren.erase(aItUpper, mChildren.end());
383 :
384 : // #i60652#
385 0 : if ( !mChildren.empty() )
386 : {
387 0 : SetLastValid( --(mChildren.end()) );
388 : }
389 : }
390 :
391 : #ifdef __SW_NUMBER_TREE_SANITY_CHECK
392 : if (! IsSane(false) || ! IsSane(&_rDestNode))
393 : clog << __FUNCTION__ << "insanity!" << endl;
394 : #endif
395 : }
396 :
397 298 : void SwNumberTreeNode::MoveChildren(SwNumberTreeNode * pDest)
398 : {
399 298 : if (! mChildren.empty())
400 : {
401 298 : tSwNumberTreeChildren::iterator aItBegin = mChildren.begin();
402 298 : SwNumberTreeNode * pMyFirst = *mChildren.begin();
403 :
404 : // #i60652#
405 : // Because <mChildren.erase(aItBegin)> could destroy the element,
406 : // which is referenced by <mItLastValid>, it's needed to adjust
407 : // <mItLastValid> before erasing <aItBegin>.
408 298 : SetLastValid(mChildren.end());
409 :
410 298 : if (pMyFirst->IsPhantom())
411 : {
412 167 : SwNumberTreeNode * pDestLast = NULL;
413 :
414 167 : if (pDest->mChildren.empty())
415 167 : pDestLast = pDest->CreatePhantom();
416 : else
417 0 : pDestLast = *pDest->mChildren.rbegin();
418 :
419 167 : pMyFirst->MoveChildren(pDestLast);
420 :
421 167 : delete pMyFirst;
422 167 : mChildren.erase(aItBegin);
423 :
424 167 : aItBegin = mChildren.begin();
425 : }
426 :
427 298 : tSwNumberTreeChildren::iterator aIt;
428 642 : for (aIt = mChildren.begin(); aIt != mChildren.end(); ++aIt)
429 344 : (*aIt)->mpParent = pDest;
430 :
431 298 : pDest->mChildren.insert(mChildren.begin(), mChildren.end());
432 298 : mChildren.clear();
433 : // <stl::set.clear()> destroys all existing iterators.
434 : // Thus, <mItLastValid> is also destroyed and reset becomes necessary
435 298 : mItLastValid = mChildren.end();
436 : }
437 :
438 : OSL_ENSURE(mChildren.empty(), "MoveChildren failed!");
439 :
440 : #ifdef __SW_NUMBER_TREE_SANITY_CHECK
441 : OSL_ENSURE(IsSane(false) && pDest->IsSane(false), "insanity!");
442 : #endif
443 298 : }
444 :
445 5441 : void SwNumberTreeNode::AddChild( SwNumberTreeNode * pChild,
446 : const int nDepth )
447 : {
448 : /*
449 : Algorithm:
450 :
451 : Search first child A that is greater than pChild,
452 : A may be the end of children.
453 : If nDepth > 0 then
454 : {
455 : if A is first child then
456 : create new phantom child B at beginning of child list
457 : else
458 : B is A
459 :
460 : Add child to B with depth nDepth - 1.
461 : }
462 : else
463 : {
464 : Insert pNode before A.
465 :
466 : if A has predecessor B then
467 : remove children of B that are greater as A and insert them as
468 : children of A.
469 : }
470 :
471 : */
472 :
473 5441 : if ( nDepth < 0 )
474 : {
475 : OSL_FAIL( "<SwNumberTreeNode::AddChild(..)> - parameter <nDepth> out of valid range. Serious defect -> please inform OD." );
476 0 : return;
477 : }
478 :
479 5441 : if ( pChild->GetParent() != NULL || pChild->GetChildCount() > 0 )
480 : {
481 : OSL_FAIL("only orphans allowed.");
482 0 : return;
483 : }
484 :
485 5441 : if (nDepth > 0)
486 : {
487 : tSwNumberTreeChildren::iterator aInsertDeepIt =
488 2685 : mChildren.upper_bound(pChild);
489 :
490 : OSL_ENSURE(! (aInsertDeepIt != mChildren.end() &&
491 : (*aInsertDeepIt)->IsPhantom()), " unexspected phantom");
492 :
493 :
494 2685 : if (aInsertDeepIt == mChildren.begin())
495 : {
496 308 : SwNumberTreeNode * pNew = CreatePhantom();
497 :
498 308 : SetLastValid(mChildren.end());
499 :
500 308 : if (pNew)
501 308 : pNew->AddChild(pChild, nDepth - 1);
502 : }
503 : else
504 : {
505 2377 : --aInsertDeepIt;
506 2377 : (*aInsertDeepIt)->AddChild(pChild, nDepth - 1);
507 : }
508 :
509 : }
510 : else
511 : {
512 2756 : pChild->PreAdd();
513 : std::pair<tSwNumberTreeChildren::iterator, bool> aResult =
514 2756 : mChildren.insert(pChild);
515 :
516 2756 : if (aResult.second)
517 : {
518 2756 : pChild->mpParent = this;
519 2756 : bool bNotification = pChild->IsNotificationEnabled();
520 2756 : tSwNumberTreeChildren::iterator aInsertedIt = aResult.first;
521 :
522 2756 : if (aInsertedIt != mChildren.begin())
523 : {
524 2357 : tSwNumberTreeChildren::iterator aPredIt = aInsertedIt;
525 2357 : --aPredIt;
526 :
527 : // -->
528 : // Move greater children of previous node to new child.
529 : // This has to be done recursively on the children levels.
530 : // Initialize loop variables <pPrevChildNode> and <pDestNode>
531 : // for loop on children levels.
532 2357 : SwNumberTreeNode* pPrevChildNode( *aPredIt );
533 2357 : SwNumberTreeNode* pDestNode( pChild );
534 7203 : while ( pDestNode && pPrevChildNode &&
535 2423 : pPrevChildNode->GetChildCount() > 0 )
536 : {
537 : // move children
538 66 : pPrevChildNode->MoveGreaterChildren( *pChild, *pDestNode );
539 :
540 : // prepare next loop:
541 : // - search of last child of <pPrevChildNode
542 : // - If found, determine destination node
543 66 : if ( pPrevChildNode->GetChildCount() > 0 )
544 : {
545 : tSwNumberTreeChildren::reverse_iterator aIt =
546 66 : pPrevChildNode->mChildren.rbegin();
547 66 : pPrevChildNode = *aIt;
548 : // determine new destination node
549 66 : if ( pDestNode->GetChildCount() > 0 )
550 : {
551 0 : pDestNode = *(pDestNode->mChildren.begin());
552 0 : if ( !pDestNode->IsPhantom() )
553 : {
554 0 : pDestNode = pDestNode->mpParent->CreatePhantom();
555 : }
556 : }
557 : else
558 : {
559 66 : pDestNode = pDestNode->CreatePhantom();
560 : }
561 : }
562 : else
563 : {
564 : // ready -> break loop.
565 0 : break;
566 : }
567 : }
568 : // assure that unnessary created phantoms at <pChild> are deleted.
569 2357 : pChild->ClearObsoletePhantoms();
570 :
571 2357 : if ((*aPredIt)->IsValid())
572 0 : SetLastValid(aPredIt);
573 : }
574 : else
575 399 : SetLastValid(mChildren.end());
576 :
577 2756 : ClearObsoletePhantoms();
578 :
579 2756 : if( bNotification )
580 : {
581 : // invalidation of not counted parent
582 : // and notification of its siblings.
583 0 : if ( !IsCounted() )
584 : {
585 0 : InvalidateMe();
586 0 : NotifyInvalidSiblings();
587 : }
588 0 : NotifyInvalidChildren();
589 : }
590 : }
591 : }
592 :
593 : #ifdef __SW_NUMBER_TREE_SANITY_CHECK
594 : if (! IsSane(false))
595 : clog << __FUNCTION__ << ": insanity!" << endl;
596 : #endif
597 : }
598 :
599 2694 : void SwNumberTreeNode::RemoveChild(SwNumberTreeNode * pChild)
600 : {
601 : /*
602 : Algorithm:
603 :
604 : if pChild has predecessor A then
605 : B is A
606 : else
607 : create phantom child B at beginning of child list
608 :
609 : Move children of pChild to B.
610 : */
611 :
612 2694 : if (pChild->IsPhantom())
613 : {
614 : OSL_FAIL("not applicable to phantoms!");
615 :
616 2694 : return;
617 : }
618 :
619 2694 : tSwNumberTreeChildren::const_iterator aRemoveIt = GetIterator(pChild);
620 :
621 2694 : if (aRemoveIt != mChildren.end())
622 : {
623 2694 : SwNumberTreeNode * pRemove = *aRemoveIt;
624 :
625 2694 : pRemove->mpParent = NULL;
626 :
627 2694 : tSwNumberTreeChildren::const_iterator aItPred = mChildren.end();
628 :
629 2694 : if (aRemoveIt == mChildren.begin())
630 : {
631 990 : if (! pRemove->mChildren.empty())
632 : {
633 131 : CreatePhantom();
634 :
635 131 : aItPred = mChildren.begin();
636 : }
637 : }
638 : else
639 : {
640 1704 : aItPred = aRemoveIt;
641 1704 : --aItPred;
642 : }
643 :
644 2694 : if (! pRemove->mChildren.empty())
645 : {
646 131 : pRemove->MoveChildren(*aItPred);
647 131 : (*aItPred)->InvalidateTree();
648 131 : (*aItPred)->NotifyInvalidChildren();
649 : }
650 :
651 : // #i60652#
652 : // Because <mChildren.erase(aRemoveIt)> could destroy the element,
653 : // which is referenced by <mItLastValid>, it's needed to adjust
654 : // <mItLastValid> before erasing <aRemoveIt>.
655 2694 : if (aItPred != mChildren.end() && (*aItPred)->IsPhantom())
656 131 : SetLastValid(mChildren.end());
657 : else
658 2563 : SetLastValid(aItPred);
659 :
660 2694 : mChildren.erase(aRemoveIt);
661 :
662 2694 : NotifyInvalidChildren();
663 : }
664 : else
665 : {
666 : OSL_FAIL("RemoveChild: failed!");
667 : }
668 :
669 2694 : pChild->PostRemove();
670 : }
671 :
672 2694 : void SwNumberTreeNode::RemoveMe()
673 : {
674 2694 : if (mpParent)
675 : {
676 2694 : SwNumberTreeNode * pSavedParent = mpParent;
677 :
678 2694 : pSavedParent->RemoveChild(this);
679 :
680 7170 : while (pSavedParent && pSavedParent->IsPhantom() &&
681 1345 : pSavedParent->HasOnlyPhantoms())
682 437 : pSavedParent = pSavedParent->GetParent();
683 :
684 2694 : if (pSavedParent)
685 2694 : pSavedParent->ClearObsoletePhantoms();
686 :
687 : #ifdef __SW_NUMBER_TREE_SANITY_CHECK
688 : if (! IsSane(false))
689 : clog << __FUNCTION__ << ": insanity!" << endl;
690 : #endif
691 : }
692 2694 : }
693 :
694 2359 : bool SwNumberTreeNode::IsValid() const
695 : {
696 2359 : return mpParent ? mpParent->IsValid(this) : false;
697 : }
698 :
699 2190 : SwNumberTree::tSwNumTreeNumber SwNumberTreeNode::GetNumber(bool bValidate)
700 : const
701 : {
702 2190 : if (bValidate && mpParent)
703 1992 : mpParent->Validate(this);
704 :
705 2190 : return mnNumber;
706 : }
707 :
708 0 : bool SwNumberTreeNode::IsContinueingPreviousSubTree() const
709 : {
710 0 : return mbContinueingPreviousSubTree;
711 : }
712 :
713 :
714 964 : vector<SwNumberTree::tSwNumTreeNumber> SwNumberTreeNode::GetNumberVector() const
715 : {
716 964 : vector<SwNumberTree::tSwNumTreeNumber> aResult;
717 :
718 964 : _GetNumberVector(aResult);
719 :
720 964 : return aResult;
721 : }
722 :
723 5330 : bool SwNumberTreeNode::IsValid(const SwNumberTreeNode * pChild) const
724 : {
725 5330 : bool bResult = false;
726 :
727 5330 : if (mItLastValid != mChildren.end())
728 : {
729 2668 : if (pChild && pChild->mpParent == this)
730 : {
731 2668 : bResult = ! (*mItLastValid)->LessThan(*pChild);
732 : }
733 : }
734 :
735 5330 : return bResult;
736 : }
737 :
738 22730 : bool SwNumberTreeNode::IsPhantom() const
739 : {
740 22730 : return mbPhantom;
741 : }
742 :
743 672 : void SwNumberTreeNode::SetPhantom(bool _bPhantom)
744 : {
745 672 : mbPhantom = _bPhantom;
746 672 : }
747 :
748 2048 : bool SwNumberTreeNode::HasOnlyPhantoms() const
749 : {
750 2048 : bool bResult = false;
751 :
752 2048 : if (GetChildCount() == 1)
753 : {
754 965 : tSwNumberTreeChildren::const_iterator aIt = mChildren.begin();
755 :
756 965 : bResult = (*aIt)->IsPhantom() && (*aIt)->HasOnlyPhantoms();
757 : }
758 1083 : else if (GetChildCount() == 0)
759 437 : bResult = true;
760 :
761 2048 : return bResult;
762 : }
763 :
764 645 : bool SwNumberTreeNode::IsCounted() const
765 : {
766 645 : return !IsPhantom() ||
767 645 : ( IsCountPhantoms() && HasCountedChildren() );
768 : }
769 :
770 94 : bool SwNumberTreeNode::HasPhantomCountedParent() const
771 : {
772 94 : bool bRet( false );
773 :
774 : OSL_ENSURE( IsPhantom(),
775 : "<SwNumberTreeNode::HasPhantomCountedParent()> - wrong usage of method - it's only for phantoms" );
776 94 : if ( IsPhantom() && mpParent )
777 : {
778 94 : if ( mpParent == GetRoot() )
779 : {
780 69 : bRet = true;
781 : }
782 25 : else if ( !mpParent->IsPhantom() )
783 : {
784 1 : bRet = mpParent->IsCounted();
785 : }
786 : else
787 : {
788 24 : bRet = mpParent->IsCounted() && mpParent->HasPhantomCountedParent();
789 : }
790 : }
791 :
792 94 : return bRet;
793 : }
794 :
795 0 : bool SwNumberTreeNode::IsFirst(const SwNumberTreeNode * pNode) const
796 : {
797 0 : tSwNumberTreeChildren::const_iterator aIt = mChildren.begin();
798 :
799 0 : if ((*aIt)->IsPhantom())
800 0 : ++aIt;
801 :
802 0 : return *aIt == pNode;
803 : }
804 :
805 0 : bool SwNumberTreeNode::IsFirst() const
806 : {
807 0 : bool bResult = true;
808 :
809 0 : if (GetParent())
810 : {
811 0 : if (GetParent()->IsFirst(this))
812 : {
813 0 : SwNumberTreeNode * pNode = GetParent();
814 :
815 0 : while (pNode)
816 : {
817 0 : if (!pNode->IsPhantom() && pNode->GetParent())
818 : {
819 0 : bResult = false;
820 0 : break;
821 : }
822 :
823 0 : pNode = pNode->GetParent();
824 : }
825 :
826 : // If node isn't the first child, it is the second child and the
827 : // first child is a phanton. In this case check, if the first phantom
828 : // child have only phanton children
829 0 : if ( bResult &&
830 0 : this != *(GetParent()->mChildren.begin()) &&
831 0 : !(*(GetParent()->mChildren.begin()))->HasOnlyPhantoms() )
832 : {
833 0 : bResult = false;
834 : }
835 : }
836 : else
837 0 : bResult = false;
838 : }
839 :
840 0 : return bResult;
841 : }
842 :
843 441 : void SwNumberTreeNode::SetLevelInListTree( const int nLevel )
844 : {
845 441 : if ( nLevel < 0 )
846 : {
847 : OSL_FAIL( "<SwNumberTreeNode::SetLevelInListTree(..)> - parameter <nLevel> out of valid range. Serious defect -> please inform OD." );
848 441 : return;
849 : }
850 :
851 : OSL_ENSURE( GetParent(),
852 : "<SwNumberTreeNode::SetLevelInListTree(..)> - can only be called for number tree nodes in a list tree" );
853 441 : if ( GetParent() )
854 : {
855 441 : if ( nLevel != GetLevelInListTree() )
856 : {
857 57 : SwNumberTreeNode* pRootTreeNode = GetRoot();
858 : OSL_ENSURE( pRootTreeNode,
859 : "<SwNumberTreeNode::SetLevelInListTree(..)> - no root tree node found. Serious defect -> please inform OD." );
860 :
861 57 : RemoveMe();
862 57 : pRootTreeNode->AddChild( this, nLevel );
863 : }
864 : }
865 : }
866 :
867 41918 : int SwNumberTreeNode::GetLevelInListTree() const
868 : {
869 41918 : if (mpParent)
870 30334 : return mpParent->GetLevelInListTree() + 1;
871 :
872 11584 : return -1;
873 : }
874 :
875 : SwNumberTreeNode::tSwNumberTreeChildren::size_type
876 20921 : SwNumberTreeNode::GetChildCount() const
877 : {
878 20921 : return mChildren.size();
879 : }
880 :
881 : #ifdef __SW_NUMBER_TREE_SANITY_CHECK
882 : bool SwNumberTreeNode::IsSane(bool bRecursive) const
883 : {
884 : vector<const SwNumberTreeNode*> aParents;
885 :
886 : return IsSane(bRecursive, aParents);
887 : }
888 :
889 : bool SwNumberTreeNode::IsSane(bool bRecursive,
890 : vector<const SwNumberTreeNode *> rParents)
891 : const
892 : {
893 : bool bResult = true;
894 :
895 : tSwNumberTreeChildren::const_iterator aIt;
896 :
897 : if (find(rParents.begin(), rParents.end(), this) != rParents.end())
898 : {
899 : OSL_FAIL(" I'm my own ancestor!");
900 :
901 : bResult = false;
902 : }
903 :
904 : if (! rParents.empty() && rParents.back() != mpParent)
905 : {
906 : OSL_FAIL(" I'm a bastard!");
907 :
908 : bResult = false;
909 : }
910 :
911 : rParents.push_back(this);
912 :
913 : bool bFirst = true;
914 : for (aIt = mChildren.begin(); aIt != mChildren.end(); ++aIt)
915 : {
916 : if (*aIt)
917 : {
918 : if ((*aIt)->IsPhantom())
919 : {
920 : if ((*aIt)->HasOnlyPhantoms())
921 : {
922 : bResult = false;
923 : }
924 :
925 : if (! bFirst)
926 : {
927 : OSL_FAIL(" found phantom not at first position.");
928 :
929 : bResult = false;
930 : }
931 : }
932 :
933 : if ((*aIt)->mpParent != (SwNumberTreeNode *) this)
934 : {
935 : OSL_FAIL("found a bastard");
936 :
937 : bResult = false;
938 : }
939 :
940 : if (mpParent)
941 : {
942 : if (!(*aIt)->IsPhantom() && (*aIt)->LessThan(*this))
943 : {
944 : OSL_FAIL(" found child less than me");
945 :
946 : bResult = false;
947 : }
948 : }
949 : }
950 : else
951 : {
952 : OSL_FAIL("found child that is NULL");
953 : bResult = false;
954 : }
955 :
956 : if (bRecursive)
957 : bResult = (*aIt)->IsSane(bRecursive, rParents) && bResult;
958 : }
959 :
960 : rParents.pop_back();
961 :
962 : return bResult;
963 : }
964 : #endif // __SW_NUMBER_TREE_SANITY_CHECK
965 :
966 : SwNumberTreeNode::tSwNumberTreeChildren::const_iterator
967 7231 : SwNumberTreeNode::GetIterator(const SwNumberTreeNode * pChild) const
968 : {
969 : tSwNumberTreeChildren::const_iterator aItResult =
970 7231 : mChildren.find(const_cast<SwNumberTreeNode *>(pChild));
971 :
972 : OSL_ENSURE( aItResult != mChildren.end(),
973 : "something went wrong getting the iterator for a child");
974 :
975 7231 : return aItResult;
976 : }
977 :
978 40820 : bool SwNumberTreeNodeLessThan(const SwNumberTreeNode * pA,
979 : const SwNumberTreeNode * pB)
980 : {
981 40820 : bool bResult = false;
982 :
983 40820 : if (pA == NULL && pB != NULL)
984 0 : bResult = true;
985 40820 : else if (pA != NULL && pB != NULL)
986 40820 : bResult = pA->LessThan(*pB);
987 :
988 40820 : return bResult;
989 : }
990 :
991 198 : SwNumberTreeNode * SwNumberTreeNode::GetLastDescendant() const
992 : {
993 198 : SwNumberTreeNode * pResult = NULL;
994 198 : tSwNumberTreeChildren::const_reverse_iterator aIt = mChildren.rbegin();
995 :
996 198 : if (aIt != mChildren.rend())
997 : {
998 0 : pResult = (*aIt)->GetLastDescendant();
999 :
1000 0 : if (! pResult)
1001 0 : pResult = *aIt;
1002 : }
1003 :
1004 198 : return pResult;
1005 : }
1006 :
1007 0 : bool SwNumberTreeNode::LessThan(const SwNumberTreeNode & rTreeNode) const
1008 : {
1009 0 : return this < &rTreeNode;
1010 : }
1011 :
1012 216 : SwNumberTreeNode * SwNumberTreeNode::GetPred(bool bSibling) const
1013 : {
1014 216 : SwNumberTreeNode * pResult = NULL;
1015 :
1016 216 : if (mpParent)
1017 : {
1018 : tSwNumberTreeChildren::const_iterator aIt =
1019 216 : mpParent->GetIterator(this);
1020 :
1021 216 : if ( aIt == mpParent->mChildren.begin() )
1022 : {
1023 : // #i64311#
1024 : // root node is no valid predecessor
1025 18 : pResult = mpParent->GetParent() ? mpParent : NULL;
1026 : }
1027 : else
1028 : {
1029 198 : --aIt;
1030 :
1031 198 : if ( !bSibling )
1032 198 : pResult = (*aIt)->GetLastDescendant();
1033 : else
1034 0 : pResult = (*aIt);
1035 :
1036 198 : if (! pResult)
1037 198 : pResult = (*aIt);
1038 : }
1039 : }
1040 :
1041 216 : return pResult;
1042 : }
1043 :
1044 5196 : void SwNumberTreeNode::SetLastValid
1045 : ( SwNumberTreeNode::tSwNumberTreeChildren::const_iterator aItValid,
1046 : bool bValidating ) const
1047 : {
1048 : OSL_ENSURE( (aItValid == mChildren.end() || GetIterator(*aItValid) != mChildren.end()),
1049 : "last-valid iterator");
1050 :
1051 22204 : if (
1052 : bValidating ||
1053 13600 : aItValid == mChildren.end() ||
1054 8604 : (mItLastValid != mChildren.end() &&
1055 0 : (*aItValid)->LessThan(**mItLastValid))
1056 : )
1057 : {
1058 3492 : mItLastValid = aItValid;
1059 : // invalidation of children of next not counted is needed
1060 3492 : if ( GetParent() )
1061 : {
1062 : tSwNumberTreeChildren::const_iterator aParentChildIt =
1063 2247 : GetParent()->GetIterator( this );
1064 2247 : ++aParentChildIt;
1065 2247 : if ( aParentChildIt != GetParent()->mChildren.end() )
1066 : {
1067 423 : SwNumberTreeNode* pNextNode( *aParentChildIt );
1068 423 : if ( !pNextNode->IsCounted() )
1069 : {
1070 0 : pNextNode->InvalidateChildren();
1071 : }
1072 : }
1073 : }
1074 : }
1075 :
1076 : {
1077 5196 : if (IsContinuous())
1078 : {
1079 1280 : tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
1080 :
1081 1280 : if (aIt != mChildren.end())
1082 216 : ++aIt;
1083 : else
1084 1064 : aIt = mChildren.begin();
1085 :
1086 26362 : while (aIt != mChildren.end())
1087 : {
1088 23802 : (*aIt)->InvalidateTree();
1089 :
1090 23802 : ++aIt;
1091 : }
1092 :
1093 1280 : SetLastValid(bValidating);
1094 : }
1095 : }
1096 5196 : }
1097 :
1098 1280 : void SwNumberTreeNode::SetLastValid(bool bValidating) const
1099 : {
1100 1280 : if (mpParent)
1101 : {
1102 0 : tSwNumberTreeChildren::const_iterator aIt = mpParent->GetIterator(this);
1103 :
1104 0 : mpParent->SetLastValid(aIt, bValidating);
1105 : }
1106 1280 : }
1107 :
1108 27683 : void SwNumberTreeNode::InvalidateTree() const
1109 : {
1110 : // do not call SetInvalid, would cause loop !!!
1111 27683 : mItLastValid = mChildren.end();
1112 :
1113 27683 : tSwNumberTreeChildren::const_iterator aIt;
1114 :
1115 30720 : for (aIt = mChildren.begin(); aIt != mChildren.end(); ++aIt)
1116 3037 : (*aIt)->InvalidateTree();
1117 27683 : }
1118 :
1119 2 : void SwNumberTreeNode::Invalidate(SwNumberTreeNode * pChild)
1120 : {
1121 2 : if (pChild->IsValid())
1122 : {
1123 0 : tSwNumberTreeChildren::const_iterator aIt = GetIterator(pChild);
1124 :
1125 0 : if (aIt != mChildren.begin())
1126 0 : --aIt;
1127 : else
1128 0 : aIt = mChildren.end();
1129 :
1130 0 : SetLastValid(aIt);
1131 :
1132 : }
1133 2 : }
1134 :
1135 2 : void SwNumberTreeNode::InvalidateMe()
1136 : {
1137 2 : if (mpParent)
1138 2 : mpParent->Invalidate(this);
1139 2 : }
1140 :
1141 1077 : void SwNumberTreeNode::ValidateMe()
1142 : {
1143 1077 : if (mpParent)
1144 979 : mpParent->Validate(this);
1145 1077 : }
1146 :
1147 26226 : void SwNumberTreeNode::Notify()
1148 : {
1149 26226 : if (IsNotifiable())
1150 : {
1151 1846 : if (! IsPhantom())
1152 1077 : NotifyNode();
1153 :
1154 1846 : tSwNumberTreeChildren::iterator aIt;
1155 :
1156 4538 : for (aIt = mChildren.begin(); aIt != mChildren.end(); ++aIt)
1157 2692 : (*aIt)->Notify();
1158 : }
1159 26226 : }
1160 :
1161 3448 : void SwNumberTreeNode::NotifyInvalidChildren()
1162 : {
1163 3448 : if (IsNotifiable())
1164 : {
1165 3138 : tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
1166 :
1167 3138 : if (aIt == mChildren.end())
1168 3138 : aIt = mChildren.begin();
1169 : else
1170 0 : ++aIt;
1171 :
1172 29712 : while (aIt != mChildren.end())
1173 : {
1174 23436 : (*aIt)->Notify();
1175 :
1176 23436 : ++aIt;
1177 : }
1178 : // notification of next not counted node is also needed.
1179 3138 : if ( GetParent() )
1180 : {
1181 : tSwNumberTreeChildren::const_iterator aParentChildIt =
1182 1190 : GetParent()->GetIterator( this );
1183 1190 : ++aParentChildIt;
1184 1190 : if ( aParentChildIt != GetParent()->mChildren.end() )
1185 : {
1186 259 : SwNumberTreeNode* pNextNode( *aParentChildIt );
1187 259 : if ( !pNextNode->IsCounted() )
1188 : {
1189 6 : pNextNode->NotifyInvalidChildren();
1190 : }
1191 : }
1192 : }
1193 :
1194 : }
1195 :
1196 3448 : if (IsContinuous() && mpParent)
1197 0 : mpParent->NotifyInvalidChildren();
1198 3448 : }
1199 :
1200 2 : void SwNumberTreeNode::NotifyInvalidSiblings()
1201 : {
1202 2 : if (mpParent != NULL)
1203 2 : mpParent->NotifyInvalidChildren();
1204 2 : }
1205 :
1206 : // #i81002#
1207 70 : const SwNumberTreeNode* SwNumberTreeNode::GetPrecedingNodeOf(
1208 : const SwNumberTreeNode& rNode ) const
1209 : {
1210 70 : const SwNumberTreeNode* pPrecedingNode( 0 );
1211 :
1212 70 : if ( GetChildCount() > 0 )
1213 : {
1214 : tSwNumberTreeChildren::const_iterator aUpperBoundIt =
1215 70 : mChildren.upper_bound( const_cast<SwNumberTreeNode*>(&rNode) );
1216 70 : if ( aUpperBoundIt != mChildren.begin() )
1217 : {
1218 43 : --aUpperBoundIt;
1219 43 : pPrecedingNode = (*aUpperBoundIt)->GetPrecedingNodeOf( rNode );
1220 : }
1221 : }
1222 :
1223 70 : if ( pPrecedingNode == 0 && GetRoot() )
1224 : {
1225 : // <this> node has no children or the given node precedes all its children
1226 : // and the <this> node isn't the root node.
1227 : // Thus, compare the given node with the <this> node in order to check,
1228 : // if the <this> node precedes the given node.
1229 27 : if ( !(rNode.LessThan( *this )) )
1230 : {
1231 27 : pPrecedingNode = this;
1232 : }
1233 : }
1234 :
1235 70 : return pPrecedingNode;
1236 : }
1237 :
1238 0 : void SwNumberTreeNode::NotifyNodesOnListLevel( const int nListLevel )
1239 : {
1240 0 : if ( nListLevel < 0 )
1241 : {
1242 : OSL_FAIL( "<SwNumberTreeNode::NotifyNodesOnListLevel(..)> - invalid list level provided" );
1243 0 : return;
1244 : }
1245 :
1246 0 : SwNumberTreeNode* pRootNode = GetParent() ? GetRoot() : this;
1247 :
1248 0 : pRootNode->NotifyChildrenOnDepth( nListLevel );
1249 : }
1250 :
1251 0 : void SwNumberTreeNode::NotifyChildrenOnDepth( const int nDepth )
1252 : {
1253 : OSL_ENSURE( nDepth >= 0,
1254 : "<SwNumberTreeNode::NotifyChildrenOnDepth(..)> - misusage" );
1255 :
1256 : SwNumberTreeNode::tSwNumberTreeChildren::iterator aChildIter =
1257 0 : mChildren.begin();
1258 0 : while ( aChildIter != mChildren.end() )
1259 : {
1260 0 : if ( nDepth == 0 )
1261 : {
1262 0 : (*aChildIter)->NotifyNode();
1263 : }
1264 : else
1265 : {
1266 0 : (*aChildIter)->NotifyChildrenOnDepth( nDepth - 1 );
1267 : }
1268 :
1269 0 : ++aChildIter;
1270 : }
1271 0 : }
1272 :
1273 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
