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