sw/inc/SwNumberTree.hxx

   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 #ifndef INCLUDED_SW_INC_SWNUMBERTREE_HXX
  21 #define INCLUDED_SW_INC_SWNUMBERTREE_HXX
  22
  23 #include <set>
  24 #include <vector>
  25 #include "swdllapi.h"
  26 #include "SwNumberTreeTypes.hxx"
  27
  28 class SwNumberTreeNode;
  29
  30 bool SwNumberTreeNodeLessThan (const SwNumberTreeNode * pA,
  31                                const SwNumberTreeNode * pB);
  32
  33 struct compSwNumberTreeNodeLessThan
  34 {
  35     bool operator()(const SwNumberTreeNode * pA,
  36                     const SwNumberTreeNode * pB) const
  37     { return SwNumberTreeNodeLessThan(pA, pB); }
  38 };
  39
  40 /**
  41    A tree of numbered nodes.
  42
  43    Simple example:
  44
  45    <pre>
  46    1. kshdkjfs
  47      1.1. lskjf
  48    2. sdfjlksaf
  49    3. fkaoslk
  50      3.1. lfjlaskf
  51      3.2. jaslkjflsf
  52        3.2.1. hkljhkjhk
  53
  54    + R
  55      + 1 kshdkjfs
  56      | + 1 lskjf
  57      + 2 sdfjlksaf
  58      + 3 fkaoslk
  59        + 1 lfjlaskf
  60        + 2 jaslkjflsf
  61          + 1 hkljhkjhk
  62    </pre>
  63
  64    The root contains the nodes of the first level. Each node A of the
  65    first level contains those nodes of the second level that have the
  66    same first level number as A and so on for the subsidiary levels.
  67
  68    The numbering label of a node A is resolved by concatenating the
  69    numbers of the nodes on the path from the root to A.
  70
  71     ------------------------------------------
  72
  73     Phantoms
  74
  75     A phantom is an auxiliary node that is used to emulate numberings
  76     starting with nodes not at top level. The phantom contains the
  77     number for the level but is not considered part of the numbering.
  78
  79      Constraint 1: A phantom is always the first child node.
  80      Constraint 2: At each node there is at most one child that is a phantom.
  81      Constraint 3: A phantom is the smallest of all numbering nodes.
  82
  83     Uncounted Phantoms
  84
  85       0.1. dljflskjlasf
  86     5. abcdagaha
  87       5.1.
  88
  89     + R (nStart = 5)
  90       + 0 (phantom, not counted)
  91       | + 1 dljflskjlasf
  92       + 5 abcdagaha
  93         + 1
  94
  95      The phantom gets numbered with 0. The first non-phantom node gets
  96      numbered with the start value.
  97
  98      -----------------------------------------
  99
 100      Counted Phantoms
 101
 102        5.1. lgkjjgklg
 103      6. lkjfalskjflsaf
 104        6.1. ljdflaksjflkjasflkjsf
 105
 106      + R (nStart = 5)
 107        + 5 (phantom, counted)
 108        | + 1 lgkjjgklg
 109        + 6 lkjfalskjflsaf
 110          + 1 ljdflaksjflkjasflkjsf
 111
 112      The phantom gets numbered with the start value.
 113 */
 114 class SAL_DLLPUBLIC_RTTI SwNumberTreeNode
 115 {
 116 protected:
 117     typedef std::set<SwNumberTreeNode *, compSwNumberTreeNodeLessThan>
 118     tSwNumberTreeChildren;
 119
 120 public:
 121     SwNumberTreeNode();
 122
 123     virtual ~SwNumberTreeNode();
 124
 125     /**
 126        Add a child.
 127
 128        @param pChild   child to add
 129        @param nDepth   depth in which to add the child
 130      */
 131     void AddChild( SwNumberTreeNode* pChild,
 132                    const int nDepth );
 133
 134     /**
 135        Remove a child.
 136
 137        @param pChild     child to be removed
 138      */
 139     void RemoveChild( SwNumberTreeNode* pChild );
 140
 141     /**
 142        Remove this child from the tree.
 143      */
 144     void RemoveMe();
 145
 146     /**
 147        Returns the parent of this node.
 148
 149        @return the parent
 150     */
 151     SwNumberTreeNode* GetParent() const
 152     {
 153         return mpParent;
 154     }
 155
 156     /**
 157        Returns number of this node.
 158
 159        @param bValidate     validate the number?
 160
 161        @return number of this node
 162      */
 163     SwNumberTree::tSwNumTreeNumber GetNumber( bool bValidate = true ) const;
 164
 165     bool IsContinueingPreviousSubTree() const { return mbContinueingPreviousSubTree;}
 166
 167     /**
 168        Returns level numbers of this node.
 169
 170        @return level numbers of this node
 171      */
 172     SwNumberTree::tNumberVector GetNumberVector() const;
 173
 174     /**
 175        Return if numbering is restarted at this node.
 176      */
 177     virtual bool IsRestart() const = 0;
 178
 179     /**
 180        Return start value.
 181
 182        @return start value
 183      */
 184     virtual SwNumberTree::tSwNumTreeNumber GetStartValue() const = 0;
 185
 186     /**
 187        Return if this node is counted.
 188
 189        @retval true this node is counted
 190        @retval false this node is NOT counted
 191      */
 192     virtual bool IsCounted() const;
 193
 194     /**
 195        Return if this node is counted continuous.
 196
 197        @retval true    This node is counted continuous.
 198        @retval false   else
 199      */
 200     virtual bool IsContinuous() const = 0;
 201
 202     /**
 203        Return if a node is first non-phantom child of this node.
 204
 205        @param pNode     the node to check
 206
 207        @retval true     pNode is first child of this node
 208        @retval false    else
 209      */
 210     bool IsFirst(const SwNumberTreeNode * pNode) const;
 211
 212     /**
 213        Return if this node if the first non-phantom node in the tree.
 214
 215        @retval true     this node is the first non-phantom node in the tree
 216        @retval false    else
 217      */
 218     bool IsFirst() const;
 219
 220     /**
 221        Return if this node is a phantom.
 222
 223        @retval true this node is a phantom
 224        @retval false this node is NOT a phantom
 225      */
 226     bool IsPhantom() const { return mbPhantom;}
 227
 228     /** set level of this node
 229
 230         precondition: node is already member of a list tree
 231     */
 232     void SetLevelInListTree( const int nLevel );
 233
 234     /**
 235        Return level of this node.
 236
 237        The level of this node is the length of the path from the root
 238        to this node.
 239
 240        @return the level of this node
 241      */
 242     int GetLevelInListTree() const;
 243
 244     /**
 245        Returns if this node is less than another node.
 246
 247        @param rTreeNode   node to compare with
 248
 249        @attention A phantom node is considered the least element with
 250        respect to lessThan.
 251
 252        @retval true this node is less than rTreeNode
 253        @retval false else
 254     */
 255     virtual bool LessThan(const SwNumberTreeNode & rTreeNode) const;
 256
 257     /**
 258        Invalidate this node and all its descendants.
 259
 260        All iterators holding the last valid node in the according list
 261        of children are set to the end of this list, thereby stating all
 262        children in the list are invalid.
 263        #i83479# - made public
 264      */
 265     void InvalidateTree() const;
 266
 267     /**
 268        Notifies all invalid children of this node.
 269        #i83479# - made public
 270      */
 271     void NotifyInvalidChildren();
 272
 273     /**
 274        Notifies the node.
 275
 276        Calls Invalidate(this) on parent.
 277      */
 278     void InvalidateMe();
 279
 280     /**
 281        Validates this node.
 282
 283        Calls Validate(this) on parent.
 284     */
 285     void ValidateMe();
 286
 287     /** Notifies all invalid siblings of this node. */
 288     void NotifyInvalidSiblings();
 289
 290     /** notification of all nodes in the list tree on certain list level */
 291     void NotifyNodesOnListLevel( const int nListLevel );
 292
 293     /** Invalidation and notification of complete numbering tree
 294
 295         #i64010#
 296         Usage: on <IsCounted()> state change it's needed to invalidate the
 297                complete numbering tree due to wide influence of this change.
 298     */
 299     void InvalidateAndNotifyTree()
 300     {
 301         if ( GetRoot() )
 302         {
 303             GetRoot()->InvalidateTree();
 304             GetRoot()->Notify();
 305         }
 306     }
 307
 308     /**
 309        Returns the greatest descendant of the root that is smaller than
 310        this node, aka the predecessor of this node.
 311
 312        @return the predecessor
 313      */
 314     SwNumberTreeNode* GetPred( bool bSibling = false ) const;
 315
 316     /** determines the node, which is preceding the node
 317
 318         #i81002#
 319         The search for the preceding node is performed for the tree below the
 320         <this> node. To search the complete tree, the method has been called for
 321         the root of the tree.
 322     */
 323     const SwNumberTreeNode* GetPrecedingNodeOf( const SwNumberTreeNode& rNode ) const;
 324
 325 #ifdef DBG_UTIL
 326     /**
 327        Sanity check.
 328
 329        @param bRecursive    descend to children
 330
 331        @retval true   the structure of this node is sane
 332        @retval false  else
 333      */
 334     void IsSane(bool bRecursive) const;
 335 #endif // DBG_UTIL
 336
 337 protected:
 338     /** the children */
 339     tSwNumberTreeChildren mChildren;
 340
 341     /**
 342        Returns the root node of the tree this node is part of.
 343
 344        Important note: method call <GetRoot()->GetRoot()> returns NULL.
 345
 346        @return the root
 347      */
 348     SwNumberTreeNode* GetRoot() const;
 349
 350      /**
 351        Return if the notification is not disabled on global conditions
 352
 353        @retval true   Notification enabled in general.
 354        @retval false  else
 355      */
 356     virtual bool IsNotificationEnabled() const = 0;
 357
 358     /**
 359        Returns how many children this node has got.
 360
 361        @return number of children
 362      */
 363     tSwNumberTreeChildren::size_type GetChildCount() const;
 364
 365     // #i64010# - made pure virtual
 366     virtual bool HasCountedChildren() const = 0;
 367
 368     // #i64010#
 369     virtual bool IsCountedForNumbering() const = 0;
 370
 371     // method called before this tree node has been added to the list tree
 372     virtual void PreAdd() = 0;
 373     // method called after this tree node has been removed from the list tree
 374     virtual void PostRemove() = 0;
 375
 376 #ifdef DBG_UTIL
 377     /** Sanity check with loop detection.
 378
 379        @param bRecursive   descend to children
 380        @param rParents     vector for recording path
 381      */
 382     void IsSane(bool bRecursive, std::vector<const SwNumberTreeNode *> rParents) const;
 383 #endif // DBG_UTIL
 384
 385     /** he parent node */
 386     SwNumberTreeNode * mpParent;
 387
 388     /** the number of the node */
 389     mutable SwNumberTree::tSwNumTreeNumber mnNumber;
 390
 391     // boolean indicating, that a node of a not counted parent node is continuing
 392     // the numbering of parent's previous node sub tree.
 393     // Example:
 394     //   1. kshdkjfs
 395     //     1.1. lskjf
 396     //      sdfjlksaf <-- not counted parent node
 397     //     1.2. lfjlaskf <-- <mbContinueingPreviousSubTree = true>
 398     mutable bool mbContinueingPreviousSubTree;
 399
 400     /**
 401        true     this node is a phantom
 402        false    this node is NOT a phantom
 403      */
 404     bool mbPhantom;
 405
 406     /**
 407        Iterator to the last valid element. All children that are less
 408        than or equal to the referenced child are valid. All children
 409        greater than the referenced child are invalid.
 410      */
 411     mutable tSwNumberTreeChildren::const_iterator mItLastValid;
 412
 413     SwNumberTreeNode(const SwNumberTreeNode& );
 414     SwNumberTreeNode& operator=( const SwNumberTreeNode& );
 415
 416     /**
 417        Calls GetNumberVector_ on parent and adds number of this node
 418        at the end.
 419
 420        @param rVector     return value
 421        @param bValidate   validate the number?
 422      */
 423     void GetNumberVector_( SwNumberTree::tNumberVector& rVector,
 424                            bool bValidate = true ) const;
 425
 426     /**
 427        Invalidates a child.
 428
 429        Calls SetLastValid for the preceding sibling of the child and
 430        notifies all invalid children.
 431
 432        @param pChild      the child to invalidate
 433      */
 434     void Invalidate( SwNumberTreeNode const * pChild );
 435
 436     /** Invalidation of all children
 437
 438         Usage: on <IsCounted()> state change the children have to be invalidated
 439     */
 440     void InvalidateChildren()
 441     {
 442         SetLastValid( mChildren.end() );
 443     }
 444
 445     /**
 446        Set the last valid child of this node.
 447
 448        @param aItLastValid    iterator pointing to the new last valid child
 449        @param bValidating     - true    always set the last valid node to
 450                                         aItLastValid
 451                               - false   only set if aItLastValid is preceding
 452                                         the current last valid node
 453      */
 454     void SetLastValid(const tSwNumberTreeChildren::const_iterator& aItLastValid,
 455                       bool bValidating = false) const;
 456
 457     /**
 458        Return if this node is notifiable.
 459
 460        @attention If a not is not notifiable a notify request is *not*
 461        forwarded to its descendants.
 462
 463        @retval true   This node is notifiable.
 464        @retval false  else
 465      */
 466     virtual bool IsNotifiable() const = 0;
 467
 468     /**
 469        Notifies the node.
 470
 471        Called when the number of the node got invalid.
 472      */
 473     virtual void NotifyNode() = 0;
 474
 475     /** Notifies this node (NotifyNode) and all descendants.*/
 476     void Notify();
 477
 478     /** notification of children nodes on certain depth */
 479     void NotifyChildrenOnDepth( const int nDepth );
 480
 481     /**
 482        Returns if a child A this node is valid.
 483
 484        A is valid if aItLastValid in parent refers to a node
 485        greater than of equal to A.
 486
 487        @param pChild    child to be tested
 488
 489        @retval true this node is valid
 490        @retval false this node is NOT valid
 491      */
 492     bool IsValid(const SwNumberTreeNode * pChild) const;
 493
 494     /**
 495        Returns if this node is valid.
 496
 497        @retval true    this node is valid
 498        @retval false   else
 499      */
 500     bool IsValid() const;
 501
 502     /**
 503        Validates a child.
 504
 505        @param pNode     child to be validated
 506
 507        @attention All invalid children preceding pNode are validated, too.
 508      */
 509     void Validate(const SwNumberTreeNode * pNode) const;
 510
 511     /**
 512        Validates a child using hierarchical numbering.
 513
 514        @param pNode      child to be validated
 515
 516        @attention All invalid children preceding pNode are validated, too.
 517      */
 518     void ValidateHierarchical(const SwNumberTreeNode * pNode) const;
 519
 520     /**
 521        Validates a child using continuous numbering.
 522
 523        @param pNode      child to be validated
 524
 525        @attention All invalid children preceding pNode are validated, too.
 526      */
 527     void ValidateContinuous(const SwNumberTreeNode * pNode) const;
 528
 529     /**
 530        Creates a new node of the same class.
 531
 532        @return the new node
 533     */
 534     virtual SwNumberTreeNode * Create() const = 0;
 535
 536     /**
 537        Creates a phantom.
 538
 539        @return the created phantom
 540      */
 541     SwNumberTreeNode * CreatePhantom();
 542
 543     /**
 544        Return if phantoms are counted.
 545      */
 546     virtual bool IsCountPhantoms() const = 0;
 547
 548     /** Return if all descendants of this node are phantoms. */
 549     bool HasOnlyPhantoms() const;
 550
 551     bool HasPhantomCountedParent() const;
 552
 553     /**
 554         HB, OD : return node, if it isn't a phantom, otherwise return first
 555                  non-phantom descendant.
 556         Returns the first child of this node that is NOT a phantom.
 557
 558         @return  the first non phantom child
 559     */
 560     SwNumberTreeNode* GetFirstNonPhantomChild();
 561
 562     /**
 563        Removes recursively phantoms that have no children.
 564
 565        The resulting tree has no phantoms that either have no children or
 566        whose descendancy consist entirely of phantoms.
 567      */
 568     void ClearObsoletePhantoms();
 569
 570     tSwNumberTreeChildren::const_iterator GetIterator(const SwNumberTreeNode * pChild) const;
 571
 572     /**
 573        Moves all children to a given destination node.
 574
 575        @param pDest    the destination node
 576      */
 577     void MoveChildren(SwNumberTreeNode * pDest);
 578
 579     /** Moves all children of this node that are greater than a given node
 580         to the destination node.
 581
 582         distinguish between node for comparing, whose children are greater,
 583         and the destination node.
 584
 585         @param _rCompareNode
 586         input parameter - reference to the node, which is used to determine
 587         the greater children
 588
 589         @param _rDestNode
 590         input parameter - reference to the node, which is the destination for
 591         the greater children
 592     */
 593     void MoveGreaterChildren( SwNumberTreeNode& _rCompareNode,
 594                               SwNumberTreeNode& _rDestNode );
 595
 596     /**
 597        Returns the last descendant of a node, if it has children.
 598
 599        @return last descendant of the node
 600     */
 601     SwNumberTreeNode* GetLastDescendant() const;
 602
 603 };
 604
 605 #endif // INCLUDED_SW_INC_SWNUMBERTREE_HXX
 606
 607 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */