sw/source/core/SwNumberTree/SwNumberTree.cxx

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