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