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