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 119836 : SwNumberTreeNode::SwNumberTreeNode()
29 : : mChildren(),
30 : mpParent( 0 ),
31 : mnNumber( 0 ),
32 : mbContinueingPreviousSubTree( false ),
33 : mbPhantom( false ),
34 119836 : mItLastValid()
35 : {
36 119836 : mItLastValid = mChildren.end();
37 119836 : }
38 :
39 239582 : SwNumberTreeNode::~SwNumberTreeNode()
40 : {
41 119791 : 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 119791 : mpParent = reinterpret_cast<SwNumberTreeNode *>(0xdeadbeef);
59 :
60 : OSL_ENSURE(mChildren.empty(), "children left!");
61 119791 : }
62 :
63 1215 : SwNumberTreeNode * SwNumberTreeNode::CreatePhantom()
64 : {
65 1215 : SwNumberTreeNode * pNew = NULL;
66 :
67 3962 : if (! mChildren.empty() &&
68 2166 : (*mChildren.begin())->IsPhantom())
69 : {
70 : OSL_FAIL("phantom already present");
71 : }
72 : else
73 : {
74 1215 : pNew = Create();
75 1215 : pNew->SetPhantom(true);
76 1215 : pNew->mpParent = this;
77 :
78 : std::pair<tSwNumberTreeChildren::iterator, bool> aInsert =
79 1215 : mChildren.insert(pNew);
80 :
81 1215 : if (! aInsert.second)
82 : {
83 : OSL_FAIL("insert of phantom failed!");
84 :
85 0 : delete pNew;
86 0 : pNew = NULL;
87 : }
88 : }
89 :
90 1215 : return pNew;
91 : }
92 :
93 886 : SwNumberTreeNode * SwNumberTreeNode::GetRoot() const
94 : {
95 886 : SwNumberTreeNode * pResult = mpParent;
96 :
97 886 : if (pResult)
98 2300 : while (pResult->mpParent)
99 528 : pResult = pResult->mpParent;
100 :
101 886 : return pResult;
102 : }
103 :
104 19843 : void SwNumberTreeNode::ClearObsoletePhantoms()
105 : {
106 19843 : tSwNumberTreeChildren::iterator aIt = mChildren.begin();
107 :
108 19843 : if (aIt != mChildren.end() && (*aIt)->IsPhantom())
109 : {
110 2194 : (*aIt)->ClearObsoletePhantoms();
111 :
112 2194 : 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 1126 : SetLastValid(mChildren.end());
119 :
120 1126 : delete *aIt;
121 1126 : mChildren.erase(aIt);
122 : }
123 : }
124 19843 : }
125 :
126 2744 : void SwNumberTreeNode::ValidateHierarchical(const SwNumberTreeNode * pNode) const
127 : {
128 : tSwNumberTreeChildren::const_iterator aValidateIt =
129 2744 : GetIterator(pNode);
130 :
131 2744 : if (aValidateIt != mChildren.end())
132 : {
133 : OSL_ENSURE((*aValidateIt)->mpParent == this, "wrong parent");
134 :
135 2744 : 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 2744 : SwNumberTree::tSwNumTreeNumber nTmpNumber( 0 );
148 2744 : if (aIt != mChildren.end())
149 2163 : nTmpNumber = (*aIt)->mnNumber;
150 : else
151 : {
152 581 : aIt = mChildren.begin();
153 581 : (*aIt)->mbContinueingPreviousSubTree = false;
154 :
155 : // determine default start value
156 : // consider the case that the first child isn't counted.
157 581 : nTmpNumber = (*aIt)->GetStartValue();
158 639 : if ( !(*aIt)->IsCounted() &&
159 29 : ( !(*aIt)->HasCountedChildren() || (*aIt)->IsPhantom() ) )
160 : {
161 29 : --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 1613 : const bool bParentCounted( IsCounted() &&
168 563 : ( !IsPhantom() ||
169 628 : HasPhantomCountedParent() ) );
170 1692 : if ( !(*aIt)->IsRestart() &&
171 821 : GetParent() && !bParentCounted )
172 : {
173 : tSwNumberTreeChildren::const_iterator aParentChildIt =
174 65 : GetParent()->GetIterator( this );
175 131 : 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 581 : (*aIt)->mnNumber = nTmpNumber;
204 : }
205 :
206 7676 : while (aIt != aValidateIt)
207 : {
208 2188 : ++aIt;
209 2188 : (*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 2188 : if ( (*aIt)->IsCounted() )
215 : {
216 2163 : if ((*aIt)->IsRestart())
217 170 : nTmpNumber = (*aIt)->GetStartValue();
218 : else
219 1993 : ++nTmpNumber;
220 : }
221 :
222 2188 : (*aIt)->mnNumber = nTmpNumber;
223 : }
224 :
225 2744 : SetLastValid(aIt, true);
226 : }
227 2744 : }
228 :
229 373 : void SwNumberTreeNode::ValidateContinuous(const SwNumberTreeNode * pNode) const
230 : {
231 373 : tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
232 :
233 746 : do
234 : {
235 373 : if (aIt == mChildren.end())
236 : {
237 25 : aIt = mChildren.begin();
238 : }
239 : else
240 348 : ++aIt;
241 :
242 373 : if (aIt != mChildren.end())
243 : {
244 373 : SwNumberTree::tSwNumTreeNumber nTmpNumber = 0;
245 373 : SwNumberTreeNode * pPred = (*aIt)->GetPred();
246 :
247 : // #i64311#
248 : // correct consideration of phantoms
249 : // correct consideration of restart at a number tree node
250 373 : if ( pPred )
251 : {
252 348 : if ( !(*aIt)->IsCounted() )
253 : // #i65284#
254 0 : nTmpNumber = pPred->GetNumber( pPred->GetParent() != (*aIt)->GetParent() );
255 : else
256 : {
257 348 : if ( (*aIt)->IsRestart() )
258 0 : nTmpNumber = (*aIt)->GetStartValue();
259 : else
260 348 : nTmpNumber = pPred->GetNumber( pPred->GetParent() != (*aIt)->GetParent() ) + 1;
261 : }
262 : }
263 : else
264 : {
265 25 : if ( !(*aIt)->IsCounted() )
266 0 : nTmpNumber = GetStartValue() - 1;
267 : else
268 : {
269 25 : if ( (*aIt)->IsRestart() )
270 0 : nTmpNumber = (*aIt)->GetStartValue();
271 : else
272 25 : nTmpNumber = GetStartValue();
273 : }
274 : }
275 :
276 373 : (*aIt)->mnNumber = nTmpNumber;
277 : }
278 : }
279 1119 : while (aIt != mChildren.end() && *aIt != pNode);
280 :
281 : // #i74748# - applied patch from garnier_romain
282 : // number tree node has to be validated.
283 373 : SetLastValid( aIt, true );
284 373 : }
285 :
286 19481 : void SwNumberTreeNode::Validate(const SwNumberTreeNode * pNode) const
287 : {
288 19481 : if (! IsValid(pNode))
289 : {
290 3117 : if (IsContinuous())
291 373 : ValidateContinuous(pNode);
292 : else
293 2744 : ValidateHierarchical(pNode);
294 : }
295 19481 : }
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 26660 : void SwNumberTreeNode::_GetNumberVector(vector<SwNumberTree::tSwNumTreeNumber> & rVector,
324 : bool bValidate) const
325 : {
326 26660 : if (mpParent)
327 : {
328 16575 : mpParent->_GetNumberVector(rVector, bValidate);
329 16575 : rVector.push_back(GetNumber(bValidate));
330 : }
331 26660 : }
332 :
333 109 : SwNumberTreeNode * SwNumberTreeNode::GetFirstNonPhantomChild()
334 : {
335 109 : if (IsPhantom())
336 63 : return (*mChildren.begin())->GetFirstNonPhantomChild();
337 :
338 46 : 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 685 : void SwNumberTreeNode::MoveGreaterChildren( SwNumberTreeNode& _rCompareNode,
345 : SwNumberTreeNode& _rDestNode )
346 : {
347 685 : if ( mChildren.empty() )
348 685 : return;
349 :
350 : // determine first child, which has to move to <_rDestNode>
351 685 : tSwNumberTreeChildren::iterator aItUpper( mChildren.end() );
352 1462 : if ((*mChildren.begin())->IsPhantom() &&
353 777 : _rCompareNode.LessThan(*(*mChildren.begin())->GetFirstNonPhantomChild()))
354 : {
355 0 : aItUpper = mChildren.begin();
356 : }
357 : else
358 : {
359 685 : aItUpper = mChildren.upper_bound(&_rCompareNode);
360 : }
361 :
362 : // move children
363 685 : if (aItUpper != mChildren.end())
364 : {
365 116 : tSwNumberTreeChildren::iterator aIt;
366 232 : for (aIt = aItUpper; aIt != mChildren.end(); ++aIt)
367 116 : (*aIt)->mpParent = &_rDestNode;
368 :
369 116 : _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 116 : SetLastValid( mChildren.end() );
376 :
377 116 : mChildren.erase(aItUpper, mChildren.end());
378 :
379 : // #i60652#
380 116 : 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 396 : void SwNumberTreeNode::MoveChildren(SwNumberTreeNode * pDest)
393 : {
394 396 : if (! mChildren.empty())
395 : {
396 396 : tSwNumberTreeChildren::iterator aItBegin = mChildren.begin();
397 396 : 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 396 : SetLastValid(mChildren.end());
404 :
405 396 : if (pMyFirst->IsPhantom())
406 : {
407 89 : SwNumberTreeNode * pDestLast = NULL;
408 :
409 89 : if (pDest->mChildren.empty())
410 89 : pDestLast = pDest->CreatePhantom();
411 : else
412 0 : pDestLast = *pDest->mChildren.rbegin();
413 :
414 89 : pMyFirst->MoveChildren(pDestLast);
415 :
416 89 : delete pMyFirst;
417 89 : mChildren.erase(aItBegin);
418 :
419 89 : aItBegin = mChildren.begin();
420 : }
421 :
422 396 : tSwNumberTreeChildren::iterator aIt;
423 1041 : for (aIt = mChildren.begin(); aIt != mChildren.end(); ++aIt)
424 645 : (*aIt)->mpParent = pDest;
425 :
426 396 : pDest->mChildren.insert(mChildren.begin(), mChildren.end());
427 396 : mChildren.clear();
428 : // <stl::set.clear()> destroys all existing iterators.
429 : // Thus, <mItLastValid> is also destroyed and reset becomes necessary
430 396 : 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 396 : }
439 :
440 8540 : 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 8540 : 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 8540 : if ( pChild->GetParent() != NULL || pChild->GetChildCount() > 0 )
475 : {
476 : OSL_FAIL("only orphans allowed.");
477 0 : return;
478 : }
479 :
480 8540 : if (nDepth > 0)
481 : {
482 : tSwNumberTreeChildren::iterator aInsertDeepIt =
483 2353 : mChildren.upper_bound(pChild);
484 :
485 : OSL_ENSURE(! (aInsertDeepIt != mChildren.end() &&
486 : (*aInsertDeepIt)->IsPhantom()), " unexspected phantom");
487 :
488 2353 : if (aInsertDeepIt == mChildren.begin())
489 : {
490 251 : SwNumberTreeNode * pNew = CreatePhantom();
491 :
492 251 : SetLastValid(mChildren.end());
493 :
494 251 : if (pNew)
495 251 : pNew->AddChild(pChild, nDepth - 1);
496 : }
497 : else
498 : {
499 2102 : --aInsertDeepIt;
500 2102 : (*aInsertDeepIt)->AddChild(pChild, nDepth - 1);
501 : }
502 :
503 : }
504 : else
505 : {
506 6187 : pChild->PreAdd();
507 : std::pair<tSwNumberTreeChildren::iterator, bool> aResult =
508 6187 : mChildren.insert(pChild);
509 :
510 6187 : if (aResult.second)
511 : {
512 6187 : pChild->mpParent = this;
513 6187 : bool bNotification = pChild->IsNotificationEnabled();
514 6187 : tSwNumberTreeChildren::iterator aInsertedIt = aResult.first;
515 :
516 6187 : if (aInsertedIt != mChildren.begin())
517 : {
518 5275 : tSwNumberTreeChildren::iterator aPredIt = aInsertedIt;
519 5275 : --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 5275 : SwNumberTreeNode* pPrevChildNode( *aPredIt );
527 5275 : SwNumberTreeNode* pDestNode( pChild );
528 16963 : while ( pDestNode && pPrevChildNode &&
529 5844 : pPrevChildNode->GetChildCount() > 0 )
530 : {
531 : // move children
532 685 : pPrevChildNode->MoveGreaterChildren( *pChild, *pDestNode );
533 :
534 : // prepare next loop:
535 : // - search of last child of <pPrevChildNode
536 : // - If found, determine destination node
537 685 : if ( pPrevChildNode->GetChildCount() > 0 )
538 : {
539 : tSwNumberTreeChildren::reverse_iterator aIt =
540 569 : pPrevChildNode->mChildren.rbegin();
541 569 : pPrevChildNode = *aIt;
542 : // determine new destination node
543 569 : 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 569 : pDestNode = pDestNode->CreatePhantom();
554 : }
555 : }
556 : else
557 : {
558 : // ready -> break loop.
559 116 : break;
560 : }
561 : }
562 : // assure that unnessary created phantoms at <pChild> are deleted.
563 5275 : pChild->ClearObsoletePhantoms();
564 :
565 5275 : if ((*aPredIt)->IsValid())
566 83 : SetLastValid(aPredIt);
567 : }
568 : else
569 912 : SetLastValid(mChildren.end());
570 :
571 6187 : ClearObsoletePhantoms();
572 :
573 6187 : if( bNotification )
574 : {
575 : // invalidation of not counted parent
576 : // and notification of its siblings.
577 159 : if ( !IsCounted() )
578 : {
579 0 : InvalidateMe();
580 0 : NotifyInvalidSiblings();
581 : }
582 159 : 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 6187 : 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 6187 : if (pChild->IsPhantom())
607 : {
608 : OSL_FAIL("not applicable to phantoms!");
609 :
610 6187 : return;
611 : }
612 :
613 6187 : tSwNumberTreeChildren::const_iterator aRemoveIt = GetIterator(pChild);
614 :
615 6187 : if (aRemoveIt != mChildren.end())
616 : {
617 6187 : SwNumberTreeNode * pRemove = *aRemoveIt;
618 :
619 6187 : pRemove->mpParent = NULL;
620 :
621 6187 : tSwNumberTreeChildren::const_iterator aItPred = mChildren.end();
622 :
623 6187 : if (aRemoveIt == mChildren.begin())
624 : {
625 4090 : if (! pRemove->mChildren.empty())
626 : {
627 306 : CreatePhantom();
628 :
629 306 : aItPred = mChildren.begin();
630 : }
631 : }
632 : else
633 : {
634 2097 : aItPred = aRemoveIt;
635 2097 : --aItPred;
636 : }
637 :
638 6187 : if (! pRemove->mChildren.empty())
639 : {
640 307 : pRemove->MoveChildren(*aItPred);
641 307 : (*aItPred)->InvalidateTree();
642 307 : (*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 6187 : if (aItPred != mChildren.end() && (*aItPred)->IsPhantom())
650 479 : SetLastValid(mChildren.end());
651 : else
652 5708 : SetLastValid(aItPred);
653 :
654 6187 : mChildren.erase(aRemoveIt);
655 :
656 6187 : NotifyInvalidChildren();
657 : }
658 : else
659 : {
660 : OSL_FAIL("RemoveChild: failed!");
661 : }
662 :
663 6187 : pChild->PostRemove();
664 : }
665 :
666 6187 : void SwNumberTreeNode::RemoveMe()
667 : {
668 6187 : if (mpParent)
669 : {
670 6187 : SwNumberTreeNode * pSavedParent = mpParent;
671 :
672 6187 : pSavedParent->RemoveChild(this);
673 :
674 14356 : while (pSavedParent && pSavedParent->IsPhantom() &&
675 1541 : pSavedParent->HasOnlyPhantoms())
676 441 : pSavedParent = pSavedParent->GetParent();
677 :
678 6187 : if (pSavedParent)
679 6187 : pSavedParent->ClearObsoletePhantoms();
680 :
681 : #ifdef __SW_NUMBER_TREE_SANITY_CHECK
682 : if (! IsSane(false))
683 : clog << __FUNCTION__ << ": insanity!" << endl;
684 : #endif
685 : }
686 6187 : }
687 :
688 5308 : bool SwNumberTreeNode::IsValid() const
689 : {
690 5308 : return mpParent && mpParent->IsValid(this);
691 : }
692 :
693 16943 : SwNumberTree::tSwNumTreeNumber SwNumberTreeNode::GetNumber(bool bValidate)
694 : const
695 : {
696 16943 : if (bValidate && mpParent)
697 16595 : mpParent->Validate(this);
698 :
699 16943 : return mnNumber;
700 : }
701 :
702 :
703 10085 : vector<SwNumberTree::tSwNumTreeNumber> SwNumberTreeNode::GetNumberVector() const
704 : {
705 10085 : vector<SwNumberTree::tSwNumTreeNumber> aResult;
706 :
707 10085 : _GetNumberVector(aResult);
708 :
709 10085 : return aResult;
710 : }
711 :
712 24789 : bool SwNumberTreeNode::IsValid(const SwNumberTreeNode * pChild) const
713 : {
714 24789 : bool bResult = false;
715 :
716 24789 : if (mItLastValid != mChildren.end())
717 : {
718 18972 : if (pChild && pChild->mpParent == this)
719 : {
720 18972 : bResult = ! (*mItLastValid)->LessThan(*pChild);
721 : }
722 : }
723 :
724 24789 : return bResult;
725 : }
726 :
727 :
728 1215 : void SwNumberTreeNode::SetPhantom(bool _bPhantom)
729 : {
730 1215 : mbPhantom = _bPhantom;
731 1215 : }
732 :
733 1980 : bool SwNumberTreeNode::HasOnlyPhantoms() const
734 : {
735 1980 : bool bResult = false;
736 :
737 1980 : if (GetChildCount() == 1)
738 : {
739 1003 : tSwNumberTreeChildren::const_iterator aIt = mChildren.begin();
740 :
741 1003 : bResult = (*aIt)->IsPhantom() && (*aIt)->HasOnlyPhantoms();
742 : }
743 977 : else if (GetChildCount() == 0)
744 441 : bResult = true;
745 :
746 1980 : return bResult;
747 : }
748 :
749 824 : bool SwNumberTreeNode::IsCounted() const
750 : {
751 1736 : return !IsPhantom() ||
752 1546 : ( IsCountPhantoms() && HasCountedChildren() );
753 : }
754 :
755 61 : bool SwNumberTreeNode::HasPhantomCountedParent() const
756 : {
757 61 : bool bRet( false );
758 :
759 : OSL_ENSURE( IsPhantom(),
760 : "<SwNumberTreeNode::HasPhantomCountedParent()> - wrong usage of method - it's only for phantoms" );
761 61 : if ( IsPhantom() && mpParent )
762 : {
763 61 : if ( mpParent == GetRoot() )
764 : {
765 46 : bRet = true;
766 : }
767 15 : else if ( !mpParent->IsPhantom() )
768 : {
769 1 : bRet = mpParent->IsCounted();
770 : }
771 : else
772 : {
773 14 : bRet = mpParent->IsCounted() && mpParent->HasPhantomCountedParent();
774 : }
775 : }
776 :
777 61 : 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 756 : void SwNumberTreeNode::SetLevelInListTree( const int nLevel )
829 : {
830 756 : if ( nLevel < 0 )
831 : {
832 : OSL_FAIL( "<SwNumberTreeNode::SetLevelInListTree(..)> - parameter <nLevel> out of valid range. Serious defect -> please inform OD." );
833 756 : return;
834 : }
835 :
836 : OSL_ENSURE( GetParent(),
837 : "<SwNumberTreeNode::SetLevelInListTree(..)> - can only be called for number tree nodes in a list tree" );
838 756 : if ( GetParent() )
839 : {
840 756 : if ( nLevel != GetLevelInListTree() )
841 : {
842 567 : SwNumberTreeNode* pRootTreeNode = GetRoot();
843 : OSL_ENSURE( pRootTreeNode,
844 : "<SwNumberTreeNode::SetLevelInListTree(..)> - no root tree node found. Serious defect -> please inform OD." );
845 :
846 567 : RemoveMe();
847 567 : pRootTreeNode->AddChild( this, nLevel );
848 : }
849 : }
850 : }
851 :
852 509208 : int SwNumberTreeNode::GetLevelInListTree() const
853 : {
854 509208 : if (mpParent)
855 289922 : return mpParent->GetLevelInListTree() + 1;
856 :
857 219286 : return -1;
858 : }
859 :
860 : SwNumberTreeNode::tSwNumberTreeChildren::size_type
861 251433 : SwNumberTreeNode::GetChildCount() const
862 : {
863 251433 : 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 14304 : SwNumberTreeNode::GetIterator(const SwNumberTreeNode * pChild) const
953 : {
954 : tSwNumberTreeChildren::const_iterator aItResult =
955 14304 : 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 14304 : return aItResult;
961 : }
962 :
963 85700 : bool SwNumberTreeNodeLessThan(const SwNumberTreeNode * pA,
964 : const SwNumberTreeNode * pB)
965 : {
966 85700 : bool bResult = false;
967 :
968 85700 : if (pA == NULL && pB != NULL)
969 0 : bResult = true;
970 85700 : else if (pA != NULL && pB != NULL)
971 85700 : bResult = pA->LessThan(*pB);
972 :
973 85700 : return bResult;
974 : }
975 :
976 348 : SwNumberTreeNode * SwNumberTreeNode::GetLastDescendant() const
977 : {
978 348 : SwNumberTreeNode * pResult = NULL;
979 348 : tSwNumberTreeChildren::const_reverse_iterator aIt = mChildren.rbegin();
980 :
981 348 : if (aIt != mChildren.rend())
982 : {
983 0 : pResult = (*aIt)->GetLastDescendant();
984 :
985 0 : if (! pResult)
986 0 : pResult = *aIt;
987 : }
988 :
989 348 : return pResult;
990 : }
991 :
992 0 : bool SwNumberTreeNode::LessThan(const SwNumberTreeNode & rTreeNode) const
993 : {
994 0 : return this < &rTreeNode;
995 : }
996 :
997 373 : SwNumberTreeNode * SwNumberTreeNode::GetPred(bool bSibling) const
998 : {
999 373 : SwNumberTreeNode * pResult = NULL;
1000 :
1001 373 : if (mpParent)
1002 : {
1003 : tSwNumberTreeChildren::const_iterator aIt =
1004 373 : mpParent->GetIterator(this);
1005 :
1006 373 : if ( aIt == mpParent->mChildren.begin() )
1007 : {
1008 : // #i64311#
1009 : // root node is no valid predecessor
1010 25 : pResult = mpParent->GetParent() ? mpParent : NULL;
1011 : }
1012 : else
1013 : {
1014 348 : --aIt;
1015 :
1016 348 : if ( !bSibling )
1017 348 : pResult = (*aIt)->GetLastDescendant();
1018 : else
1019 0 : pResult = (*aIt);
1020 :
1021 348 : if (! pResult)
1022 348 : pResult = (*aIt);
1023 : }
1024 : }
1025 :
1026 373 : return pResult;
1027 : }
1028 :
1029 12202 : 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 27521 : if (
1037 18170 : bValidating ||
1038 56833 : aItValid == mChildren.end() ||
1039 16344 : (mItLastValid != mChildren.end() &&
1040 120 : (*aItValid)->LessThan(**mItLastValid))
1041 : )
1042 : {
1043 10237 : mItLastValid = aItValid;
1044 : // invalidation of children of next not counted is needed
1045 10237 : if ( GetParent() )
1046 : {
1047 : tSwNumberTreeChildren::const_iterator aParentChildIt =
1048 3246 : GetParent()->GetIterator( this );
1049 3246 : ++aParentChildIt;
1050 3246 : if ( aParentChildIt != GetParent()->mChildren.end() )
1051 : {
1052 648 : SwNumberTreeNode* pNextNode( *aParentChildIt );
1053 648 : if ( !pNextNode->IsCounted() )
1054 : {
1055 0 : pNextNode->InvalidateChildren();
1056 : }
1057 : }
1058 : }
1059 : }
1060 :
1061 : {
1062 12202 : if (IsContinuous())
1063 : {
1064 1715 : tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
1065 :
1066 1715 : if (aIt != mChildren.end())
1067 373 : ++aIt;
1068 : else
1069 1342 : aIt = mChildren.begin();
1070 :
1071 23420 : while (aIt != mChildren.end())
1072 : {
1073 19990 : (*aIt)->InvalidateTree();
1074 :
1075 19990 : ++aIt;
1076 : }
1077 :
1078 1715 : SetLastValid(bValidating);
1079 : }
1080 : }
1081 12202 : }
1082 :
1083 1715 : void SwNumberTreeNode::SetLastValid(bool bValidating) const
1084 : {
1085 1715 : if (mpParent)
1086 : {
1087 0 : tSwNumberTreeChildren::const_iterator aIt = mpParent->GetIterator(this);
1088 :
1089 0 : mpParent->SetLastValid(aIt, bValidating);
1090 : }
1091 1715 : }
1092 :
1093 26816 : void SwNumberTreeNode::InvalidateTree() const
1094 : {
1095 : // do not call SetInvalid, would cause loop !!!
1096 26816 : mItLastValid = mChildren.end();
1097 :
1098 26816 : tSwNumberTreeChildren::const_iterator aIt;
1099 :
1100 31545 : for (aIt = mChildren.begin(); aIt != mChildren.end(); ++aIt)
1101 4729 : (*aIt)->InvalidateTree();
1102 26816 : }
1103 :
1104 33 : void SwNumberTreeNode::Invalidate(SwNumberTreeNode * pChild)
1105 : {
1106 33 : if (pChild->IsValid())
1107 : {
1108 14 : tSwNumberTreeChildren::const_iterator aIt = GetIterator(pChild);
1109 :
1110 14 : if (aIt != mChildren.begin())
1111 4 : --aIt;
1112 : else
1113 10 : aIt = mChildren.end();
1114 :
1115 14 : SetLastValid(aIt);
1116 :
1117 : }
1118 33 : }
1119 :
1120 33 : void SwNumberTreeNode::InvalidateMe()
1121 : {
1122 33 : if (mpParent)
1123 33 : mpParent->Invalidate(this);
1124 33 : }
1125 :
1126 2916 : void SwNumberTreeNode::ValidateMe()
1127 : {
1128 2916 : if (mpParent)
1129 2886 : mpParent->Validate(this);
1130 2916 : }
1131 :
1132 78049 : void SwNumberTreeNode::Notify()
1133 : {
1134 78049 : if (IsNotifiable())
1135 : {
1136 3898 : if (! IsPhantom())
1137 2916 : NotifyNode();
1138 :
1139 3898 : tSwNumberTreeChildren::iterator aIt;
1140 :
1141 6439 : for (aIt = mChildren.begin(); aIt != mChildren.end(); ++aIt)
1142 2541 : (*aIt)->Notify();
1143 : }
1144 78049 : }
1145 :
1146 8002 : void SwNumberTreeNode::NotifyInvalidChildren()
1147 : {
1148 8002 : if (IsNotifiable())
1149 : {
1150 7810 : tSwNumberTreeChildren::const_iterator aIt = mItLastValid;
1151 :
1152 7810 : if (aIt == mChildren.end())
1153 7670 : aIt = mChildren.begin();
1154 : else
1155 140 : ++aIt;
1156 :
1157 91098 : while (aIt != mChildren.end())
1158 : {
1159 75478 : (*aIt)->Notify();
1160 :
1161 75478 : ++aIt;
1162 : }
1163 : // notification of next not counted node is also needed.
1164 7810 : if ( GetParent() )
1165 : {
1166 : tSwNumberTreeChildren::const_iterator aParentChildIt =
1167 1675 : GetParent()->GetIterator( this );
1168 1675 : ++aParentChildIt;
1169 1675 : if ( aParentChildIt != GetParent()->mChildren.end() )
1170 : {
1171 556 : SwNumberTreeNode* pNextNode( *aParentChildIt );
1172 556 : if ( !pNextNode->IsCounted() )
1173 : {
1174 1 : pNextNode->NotifyInvalidChildren();
1175 : }
1176 : }
1177 : }
1178 :
1179 : }
1180 :
1181 8002 : if (IsContinuous() && mpParent)
1182 0 : mpParent->NotifyInvalidChildren();
1183 8002 : }
1184 :
1185 33 : void SwNumberTreeNode::NotifyInvalidSiblings()
1186 : {
1187 33 : if (mpParent != NULL)
1188 33 : mpParent->NotifyInvalidChildren();
1189 33 : }
1190 :
1191 : // #i81002#
1192 146 : const SwNumberTreeNode* SwNumberTreeNode::GetPrecedingNodeOf(
1193 : const SwNumberTreeNode& rNode ) const
1194 : {
1195 146 : const SwNumberTreeNode* pPrecedingNode( 0 );
1196 :
1197 146 : if ( GetChildCount() > 0 )
1198 : {
1199 : tSwNumberTreeChildren::const_iterator aUpperBoundIt =
1200 144 : mChildren.upper_bound( const_cast<SwNumberTreeNode*>(&rNode) );
1201 144 : if ( aUpperBoundIt != mChildren.begin() )
1202 : {
1203 90 : --aUpperBoundIt;
1204 90 : pPrecedingNode = (*aUpperBoundIt)->GetPrecedingNodeOf( rNode );
1205 : }
1206 : }
1207 :
1208 146 : 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 56 : if ( !(rNode.LessThan( *this )) )
1215 : {
1216 56 : pPrecedingNode = this;
1217 : }
1218 : }
1219 :
1220 146 : 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: */
|
