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