xref: /aoo42x/main/sw/inc/SwNumberTree.hxx (revision 3e9d8370)
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 IsContinuingPreviousSubTree() 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 restarted 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 is 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 above
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