sw/source/core/SwNumberTree/SwNumberTree.cxx

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