sw/inc/SwNumberTree.hxx

   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.hxx,v $
  10  * $Revision: 1.11 $
  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 #ifndef _SW_NUMBER_TREE_HXX
  32 #define _SW_NUMBER_TREE_HXX
  33
  34 #include <set>
  35 #include <vector>
  36 #include <tools/string.hxx>
  37 #include <swdllapi.h>
  38 #include <SwNumberTreeTypes.hxx>
  39
  40 class SwNumberTreeNode;
  41
  42 bool SwNumberTreeNodeLessThan (const SwNumberTreeNode * pA,
  43                                const SwNumberTreeNode * pB);
  44
  45 struct compSwNumberTreeNodeLessThan
  46 {
  47     bool operator()(const SwNumberTreeNode * pA,
  48                     const SwNumberTreeNode * pB) const
  49     { return SwNumberTreeNodeLessThan(pA, pB); }
  50 };
  51
  52 /**
  53    A tree of numbered nodes.
  54
  55    Simple example:
  56
  57    <pre>
  58    1. kshdkjfs
  59      1.1. lskjf
  60    2. sdfjlksaf
  61    3. fkaöslk
  62      3.1. lfjlaskf
  63      3.2. jaslkjflsf
  64        3.2.1. hkljhkjhk
  65
  66    + R
  67      + 1 kshdkjfs
  68      | + 1 lskjf
  69      + 2 sdfjlksaf
  70      + 3 fkaöslk
  71        + 1 lfjlaskf
  72        + 2 jaslkjflsf
  73          + 1 hkljhkjhk
  74    </pre>
  75
  76    The root contains the nodes of the first level. Each node A of the
  77    first level contains those nodes of the second level that have the
  78    same first level number as A and so on for the subsidiary levels.
  79
  80    The numbering label of a node A is resolved by concatenating the
  81    numbers of the nodes on the path from the root to A.
  82
  83     ------------------------------------------
  84
  85     Phantoms
  86
  87     A phantom is an auxiliary node that is used to emulate numberings
  88     starting with nodes not at top level. The phantom contains the
  89     number for the level but is not considered part of the numbering.
  90
  91      Constraint 1: A phantom is always the first child node.
  92      Constraint 2: At each node there is at most one child that is a phantom.
  93      Constraint 3: A phantom is the smallest of all numbering nodes.
  94
  95     Uncounted Phantoms
  96
  97       0.1. dljflskjlasf
  98     5. ödsöfkaös
  99       5.1.
 100
 101     + R (nStart = 5)
 102       + 0 (phantom, not counted)
 103       | + 1 dljflskjlasf
 104       + 5 ödsöfkaös
 105         + 1
 106
 107      The phantom gets numbered with 0. The first non-phantom node gets
 108      numbered with the start value.
 109
 110      -----------------------------------------
 111
 112      Counted Phantoms
 113
 114        5.1. lgkjjgklg
 115      6. lkjfalskjflsaf
 116        6.1. ljdflaksjflkjasflkjsf
 117
 118      + R (nStart = 5)
 119        + 5 (phantom, counted)
 120        | + 1 lgkjjgklg
 121        + 6 lkjfalskjflsaf
 122          + 1 ljdflaksjflkjasflkjsf
 123
 124      The phantom gets numbered with the start value.
 125 */
 126 class SW_DLLPUBLIC SwNumberTreeNode
 127 {
 128 protected:
 129     typedef std::set<SwNumberTreeNode *, compSwNumberTreeNodeLessThan>
 130     tSwNumberTreeChildren;
 131
 132 public:
 133     SwNumberTreeNode();
 134
 135     virtual ~SwNumberTreeNode();
 136
 137     /**
 138        Add a child.
 139
 140        @param pChild   child to add
 141        @param nDepth   depth in which to add the child
 142      */
 143     void AddChild( SwNumberTreeNode* pChild,
 144                    const int nDepth = 0 );
 145
 146     /**
 147        Remove a child.
 148
 149        OD 2008-02-19 #refactorlists# - no longer virtual
 150
 151        @param pChild     child to be removed
 152      */
 153     void RemoveChild( SwNumberTreeNode* pChild );
 154
 155     /**
 156        Remove this child from the tree.
 157      */
 158     void RemoveMe();
 159
 160     /**
 161        Returns the parent of this node.
 162
 163        @return the parent
 164     */
 165     inline SwNumberTreeNode* GetParent() const
 166     {
 167         return mpParent;
 168     }
 169
 170     /**
 171        Returns the first child of this node.
 172
 173        @return the child
 174     */
 175     SwNumberTreeNode* GetFirstChild() const;
 176
 177     /**
 178        Returns number of this node.
 179
 180        @param bValidate     validate the number?
 181
 182        @return number of this node
 183      */
 184     SwNumberTree::tSwNumTreeNumber GetNumber( bool bValidate = true ) const;
 185
 186     // --> OD 2008-11-26 #158694#
 187     bool IsContinueingPreviousSubTree() const;
 188     // <--
 189
 190     /**
 191        Returns level numbers of this node.
 192
 193        @return level numbers of this node
 194      */
 195     SwNumberTree::tNumberVector GetNumberVector() const;
 196
 197     /**
 198        Return if numbering is restartet at this node.
 199      */
 200     virtual bool IsRestart() const = 0;
 201
 202     /**
 203        Return start value.
 204
 205        @return start value
 206      */
 207     virtual SwNumberTree::tSwNumTreeNumber GetStartValue() const = 0;
 208
 209     /**
 210        Return if this node is counted.
 211
 212        @retval true this node is counted
 213        @retval false this node is NOT counted
 214      */
 215     virtual bool IsCounted() const;
 216
 217     /**
 218        Return if this node is counted continuous.
 219
 220        @retval true    This node is counted continuous.
 221        @retval false   else
 222      */
 223     virtual bool IsContinuous() const = 0;
 224
 225     /**
 226        Return if a node is first non-phantom child of this node.
 227
 228        @param pNode     the node to check
 229
 230        @retval true     pNode is first child of this node
 231        @retval false    else
 232      */
 233     virtual bool IsFirst(const SwNumberTreeNode * pNode) const;
 234
 235     /**
 236        Return if this node if the first non-phantom node in the tree.
 237
 238        @retval true     this node is the first non-phantom node in the tree
 239        @retval false    else
 240      */
 241     virtual bool IsFirst() const;
 242
 243     /**
 244        Return if this node is a phantom.
 245
 246        @retval true this node is a phantom
 247        @retval false this node is NOT a phantom
 248      */
 249     bool IsPhantom() const;
 250
 251     /** set level of this node
 252
 253         OD 2008-03-13 #refactorlists#
 254         precondition: node is already member of a list tree
 255
 256         @author OD
 257     */
 258     void SetLevelInListTree( const int nLevel );
 259
 260     /**
 261        Return level of this node.
 262
 263        The level of this node is the length of the path from the root
 264        to this node.
 265
 266        @return the level of this node
 267      */
 268     int GetLevelInListTree() const;
 269
 270     /**
 271        Returns if this node is less than another node.
 272
 273        @param rTreeNode   node to compare with
 274
 275        @attention A phantom node is considered the least element with
 276        respect to lessThan.
 277
 278        @retval true this node is less than rTreeNode
 279        @retval false else
 280     */
 281     virtual bool LessThan(const SwNumberTreeNode & rTreeNode) const;
 282
 283     /**
 284        Invalidate this node and all its descendants.
 285
 286        All iterators holding the last valid node in the according list
 287        of childs are set to the end of this list, thereby stating all
 288        children in the list are invalid.
 289        OD 2007-10-26 #i83479# - made public
 290      */
 291     void InvalidateTree() const;
 292
 293     /**
 294        Notifies all invalid children of this node.
 295        OD 2007-10-26 #i83479# - made public
 296      */
 297     void NotifyInvalidChildren();
 298
 299     /**
 300        Notifies the node.
 301
 302        Calls Invalidate(this) on parent.
 303      */
 304     void InvalidateMe();
 305
 306     /**
 307        Validate the tree.
 308
 309        Validates all nodes in this subtree.
 310     */
 311     void ValidateTree();
 312
 313     /**
 314        Validates this node.
 315
 316        Calls Validate(this) on parent.
 317     */
 318     void ValidateMe();
 319
 320     /**
 321        Notifies all invalid siblings of this node.
 322     */
 323     void NotifyInvalidSiblings();
 324
 325     /** notification of all nodes in the list tree on certain list level
 326
 327         OD 2008-04-17 #refactorlists#
 328     */
 329     void NotifyNodesOnListLevel( const int nListLevel );
 330
 331     /** Invalidation and notification of complete numbering tree
 332
 333         OD 2006-04-26 #i64010#
 334         Usage: on <IsCounted()> state change its needed to invalidate the
 335                complete numbering tree due to wide influence of this change.
 336     */
 337     inline void InvalidateAndNotifyTree()
 338     {
 339         if ( GetRoot() )
 340         {
 341             GetRoot()->InvalidateTree();
 342             GetRoot()->Notify();
 343         }
 344     }
 345
 346     /**
 347        Returns the greatest descendant of the root that is smaller than
 348        this node, aka the predecessor of this node.
 349
 350        @return the predecessor
 351      */
 352     SwNumberTreeNode* GetPred( bool bSibling = false ) const;
 353
 354     /** determines the node, which is preceding the node
 355
 356         OD 2007-09-06 #i81002#
 357         The search for the preceding node is performed for the tree below the
 358         <this> node. To search the complete tree, the method has been called for
 359         the root of the tree.
 360
 361         @author OD
 362     */
 363     const SwNumberTreeNode* GetPrecedingNodeOf( const SwNumberTreeNode& rNode ) const;
 364
 365 //    /**
 366 //       Returns a string representation of this node.
 367
 368 //       @return the string representation of this node
 369 //     */
 370 //    virtual String ToString() const = 0;
 371
 372 //    /**
 373 //       Print this subtree.
 374
 375 //       @param o              output stream to direct output to
 376 //       @param rIndent        additional indent for the children of this node
 377 //       @param rMyIndent      indent to use for this node
 378 //       @param nDepth         number of levels to print (-1 means all levels)
 379
 380 //       @return output stream after output of this subtree
 381 //     */
 382 //    String print(const String & rIndent = String("  ",
 383 //                                                 RTL_TEXTENCODING_ASCII_US),
 384 //                 const String & rMyIndent = String("  ",
 385 //                                                   RTL_TEXTENCODING_ASCII_US),
 386 //                 int nDepth = -1) const;
 387
 388 #ifndef PRODUCT
 389     static unsigned long GetInstances();
 390     unsigned long GetSerial();
 391 #endif
 392
 393 #ifdef __SW_NUMBER_TREE_SANITY_CHECK
 394     /**
 395        Sanity check.
 396
 397        @param bRecursive    descend to children
 398
 399        @retval true   the structure of this node is sane
 400        @retval false  else
 401      */
 402     bool IsSane(bool bRecursive) const;
 403 #endif // __SW_NUMBER_TREE_SANITY_CHECK
 404
 405 protected:
 406     /**
 407        the children
 408     */
 409     tSwNumberTreeChildren mChildren;
 410
 411     /**
 412        Returns the root node of the tree this node is part of.
 413
 414        Important note: method call <GetRoot()->GetRoot()> returns NULL.
 415
 416        @return the root
 417      */
 418     SwNumberTreeNode* GetRoot() const;
 419
 420      /**
 421        Return if the notification is not disabled on global conditions
 422
 423        @retval true   Notification enabled in general.
 424        @retval false  else
 425      */
 426     virtual bool IsNotificationEnabled() const = 0;
 427
 428     /**
 429        Returns how many children this node has got.
 430
 431        @return number of children
 432      */
 433     tSwNumberTreeChildren::size_type GetChildCount() const;
 434
 435     // --> OD 2006-04-26 #i64010# - made pure virtual
 436     virtual bool HasCountedChildren() const = 0;
 437     // <--
 438
 439     // --> OD 2006-04-26 #i64010#
 440     virtual bool IsCountedForNumbering() const = 0;
 441     // <--
 442
 443     // --> OD 2008-02-19 #refactorlists#
 444     // method called before this tree node has been added to the list tree
 445     virtual void PreAdd() = 0;
 446     // method called after this tree node has been removed from the list tree
 447     virtual void PostRemove() = 0;
 448     // <--
 449
 450 #ifdef __SW_NUMBER_TREE_SANITY_CHECK
 451     /**
 452        Sanity check with loop detection.
 453
 454        @param bRecursive   descend to children
 455        @param rParents     vector for recording path
 456
 457        @retval true     this node is sane
 458        @retval false    else     */
 459     virtual bool IsSane
 460     (bool bRecursive, std::vector<const SwNumberTreeNode *> rParents) const;
 461 #endif // __SW_NUMBER_TREE_SANITY_CHECK
 462
 463     /**
 464        the parent node
 465     */
 466     SwNumberTreeNode * mpParent;
 467
 468     /**
 469        the number of the node
 470     */
 471     mutable SwNumberTree::tSwNumTreeNumber mnNumber;
 472
 473     // --> OD 2008-11-26 #158694#
 474     // boolean indicating, that a node of a not counted parent node is continueing
 475     // the numbering of parent's previous node sub tree.
 476     // Example:
 477     //   1. kshdkjfs
 478     //     1.1. lskjf
 479     //      sdfjlksaf <-- not counted parent node
 480     //     1.2. lfjlaskf <-- <mbContinueingPreviousSubTree = true>
 481     mutable bool mbContinueingPreviousSubTree;
 482     // <--
 483
 484     /**
 485        true     this node is a phantom
 486        false    this node is NOT a phantom
 487      */
 488     bool mbPhantom;
 489
 490     /**
 491        Iterator to the last valid element. All children that are less
 492        than or equal to the referenced child are valid. All children
 493        greater than the referenced child are invalid.
 494      */
 495     mutable tSwNumberTreeChildren::iterator mItLastValid;
 496
 497 #ifndef PRODUCT
 498     /**
 499        Counter for the number of created instances.
 500      */
 501     static unsigned long nInstances;
 502
 503     /**
 504        Serial number.
 505     */
 506     unsigned long mnSerial;
 507 #endif
 508
 509     SwNumberTreeNode(const SwNumberTreeNode& );
 510     SwNumberTreeNode& operator=( const SwNumberTreeNode& );
 511
 512     /**
 513        Calls _GetNumberVector on parent and adds number of this node
 514        at the end.
 515
 516        @param rVector     return value
 517        @param bValidate   validate the number?
 518      */
 519     void _GetNumberVector( SwNumberTree::tNumberVector& rVector,
 520                            bool bValidate = true ) const;
 521
 522     /**
 523        Invalidates a child.
 524
 525        Calls SetLastValid for the preceeding sibling of the child and
 526        notifies all invalid children.
 527
 528        @param pChild      the child to invalidate
 529      */
 530     void Invalidate( SwNumberTreeNode * pChild );
 531
 532     /** Invalidation of all children
 533
 534         OD 2005-10-19 #126009#
 535         Usage: on <IsCounted()> state change the children have to be invalidated
 536     */
 537     inline void InvalidateChildren()
 538     {
 539         SetLastValid( mChildren.end() );
 540     }
 541
 542     /** Invalidation of parent node, if its not counted.
 543
 544         OD 2005-10-19 #126009#
 545         Usage: on <IsCounted()> state change the parent have to be invalidated
 546     */
 547     inline void InvalidateNotCountedParent()
 548     {
 549         if ( GetParent() && !GetParent()->IsCountedForNumbering() )
 550         {
 551             GetParent()->InvalidateMe();
 552         }
 553     }
 554
 555     /**
 556        Set the last valid child of this node.
 557
 558        @param aItLastValid    iterator pointing to the new last valid child
 559        @param bValidating     - true    always set the last valid node to
 560                                         aItLastValid
 561                               - false   only set if aItLastValid is preceeding
 562                                         the current last valid node
 563      */
 564     void SetLastValid(tSwNumberTreeChildren::iterator aItLastValid,
 565                       bool bValidating = false) const;
 566
 567     /**
 568        Set this node as last valid child of its parent.
 569
 570        @param bValidation    see aboce
 571      */
 572     void SetLastValid(bool bValidating) const;
 573
 574     /**
 575        Return if this node is notifiable.
 576
 577        @attention If a not is not notifiable a notify request is *not*
 578        forwarded to its descendants.
 579
 580        @retval true   This node is notifiable.
 581        @retval false  else
 582      */
 583     virtual bool IsNotifiable() const = 0;
 584
 585     /**
 586        Notifies the node.
 587
 588        Called when the number of the node got invalid.
 589      */
 590     virtual void NotifyNode() = 0;
 591
 592     /**
 593        Notifies this node (NotifyNode) and all descendants.
 594      */
 595     void Notify();
 596
 597     /** Notification of parent node siblings, if its not counted.
 598
 599         OD 2005-10-19 #126009#
 600         Usage: on <IsCounted()> state change the parent node and its siblings
 601                have to be notified.
 602     */
 603     inline void NotifyNotCountedParentSiblings()
 604     {
 605         if ( GetParent() && !GetParent()->IsCountedForNumbering() )
 606         {
 607             GetParent()->NotifyInvalidSiblings();
 608         }
 609     }
 610
 611     /** notification of children nodes on certain depth
 612
 613         OD 2008-04-17 #refactorlists#
 614
 615         @author OD
 616     */
 617     void NotifyChildrenOnDepth( const int nDepth );
 618
 619     /**
 620        Returns if a child A this node is valid.
 621
 622        A is valid if aItLastValid in parent refers to a node
 623        greater than of equal to A.
 624
 625        @param pChild    child to be tested
 626
 627        @retval true this node is valid
 628        @retval false this node is NOT valid
 629      */
 630     bool IsValid(const SwNumberTreeNode * pChild) const;
 631
 632     /**
 633        Returns if this node is valid.
 634
 635        @retval true    this node is valid
 636        @retval false   else
 637      */
 638     bool IsValid() const;
 639
 640     /**
 641        Validates a child.
 642
 643        @param pNode     child to be validated
 644
 645        @attention All invalid children preceding pNode are validated, too.
 646      */
 647     void Validate(const SwNumberTreeNode * pNode) const;
 648
 649     /**
 650        Validates a child using hierarchical numbering.
 651
 652        @param pNode      child to be validated
 653
 654        @attention All invalid children preceding pNode are validated, too.
 655      */
 656     void ValidateHierarchical(const SwNumberTreeNode * pNode) const;
 657
 658     /**
 659        Validates a child using continuous numbering.
 660
 661        @param pNode      child to be validated
 662
 663        @attention All invalid children preceding pNode are validated, too.
 664      */
 665     void ValidateContinuous(const SwNumberTreeNode * pNode) const;
 666
 667     /**
 668        Creates a new node of the same class.
 669
 670        @return the new node
 671     */
 672     virtual SwNumberTreeNode * Create() const = 0;
 673
 674     /**
 675        Creates a phantom.
 676
 677        @return the created phantom
 678      */
 679     SwNumberTreeNode * CreatePhantom();
 680
 681     /**
 682        Set if this node is a phantom.
 683
 684        @param bPhantom   - true this node is a phantom
 685                          - false this node is a phantom
 686      */
 687     void SetPhantom(bool bPhantom = true);
 688
 689     /**
 690        Return if phantoms are counted.
 691
 692        OD 2008-02-19 #refactorlists# - pure virtual now
 693
 694        @retval true phantoms are counted
 695        @retval false else
 696      */
 697     virtual bool IsCountPhantoms() const = 0;
 698
 699     /**
 700        Return if all descendants of this node are phantoms.
 701
 702        @retval true   all descendants are phantoms
 703        @retval false  else
 704      */
 705     bool HasOnlyPhantoms() const;
 706
 707     // --> OD 2005-10-27 #126009#
 708     bool HasPhantomCountedParent() const;
 709     // <--
 710
 711     /**
 712         HB, OD : return node, if it isn't a phantom, otherwise return first
 713                  non-phantom descendant.
 714         Returns the first child of this node that is NOT a phantom.
 715
 716         @return  the first non phantom child
 717     */
 718     SwNumberTreeNode* GetFirstNonPhantomChild();
 719
 720     /**
 721        Removes recursively phantoms that have no children.
 722
 723        The resulting tree has no phantoms that either have no children or
 724        whose descendancy consist entirely of phantoms.
 725      */
 726     void ClearObsoletePhantoms();
 727
 728     tSwNumberTreeChildren::iterator GetIterator(const SwNumberTreeNode * pChild) const;
 729
 730     /**
 731        Moves all children to a given destination node.
 732
 733        @param pDest    the destination node
 734      */
 735     void MoveChildren(SwNumberTreeNode * pDest);
 736
 737     /** Moves all children of this node that are greater than a given node
 738         to the destination node.
 739
 740         OD 2005-10-14 #125991#
 741         distinguish between node for comparing, whose children are greater,
 742         and the destination node.
 743
 744         @param _rCompareNode
 745         input parameter - reference to the node, which is used to determine
 746         the greater children
 747
 748         @param _rDestNode
 749         input parameter - reference to the node, which is the destination for
 750         the greater children
 751     */
 752     void MoveGreaterChildren( SwNumberTreeNode& _rCompareNode,
 753                               SwNumberTreeNode& _rDestNode );
 754
 755     /**
 756        Returns the last descendant of a node, if it has children.
 757
 758        @return last descendant of the node
 759     */
 760     SwNumberTreeNode* GetLastDescendant() const;
 761
 762 };
 763
 764 /**
 765    Functor. Checks if a certain node is less than the functor's member.
 766  */
 767 struct SwNumberTreeNodeIsLessThan
 768 {
 769     const SwNumberTreeNode * pNode;
 770
 771     SwNumberTreeNodeIsLessThan(const SwNumberTreeNode * _pNode)
 772         : pNode(_pNode) {}
 773
 774     bool operator()(const SwNumberTreeNode * _pNode) const
 775     { return SwNumberTreeNodeLessThan(_pNode, pNode); }
 776 };
 777 #endif // _SW_NUMBER_TREE_HXX