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