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