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