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