Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : : /*************************************************************************
3 : : *
4 : : * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 : : *
6 : : * Copyright 2000, 2010 Oracle and/or its affiliates.
7 : : *
8 : : * OpenOffice.org - a multi-platform office productivity suite
9 : : *
10 : : * This file is part of OpenOffice.org.
11 : : *
12 : : * OpenOffice.org is free software: you can redistribute it and/or modify
13 : : * it under the terms of the GNU Lesser General Public License version 3
14 : : * only, as published by the Free Software Foundation.
15 : : *
16 : : * OpenOffice.org is distributed in the hope that it will be useful,
17 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 : : * GNU Lesser General Public License version 3 for more details
20 : : * (a copy is included in the LICENSE file that accompanied this code).
21 : : *
22 : : * You should have received a copy of the GNU Lesser General Public License
23 : : * version 3 along with OpenOffice.org. If not, see
24 : : * <http://www.openoffice.org/license.html>
25 : : * for a copy of the LGPLv3 License.
26 : : *
27 : : ************************************************************************/
28 : :
29 : : #ifndef _SW_NUMBER_TREE_HXX
30 : : #define _SW_NUMBER_TREE_HXX
31 : :
32 : : #include <set>
33 : : #include <vector>
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 : 96386 : bool operator()(const SwNumberTreeNode * pA,
45 : : const SwNumberTreeNode * pB) const
46 : 96386 : { 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. abcdagaha
96 : : 5.1.
97 : :
98 : : + R (nStart = 5)
99 : : + 0 (phantom, not counted)
100 : : | + 1 dljflskjlasf
101 : : + 5 abcdagaha
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 : : @param pChild child to be removed
147 : : */
148 : : void RemoveChild( SwNumberTreeNode* pChild );
149 : :
150 : : /**
151 : : Remove this child from the tree.
152 : : */
153 : : void RemoveMe();
154 : :
155 : : /**
156 : : Returns the parent of this node.
157 : :
158 : : @return the parent
159 : : */
160 : 63871 : inline SwNumberTreeNode* GetParent() const
161 : : {
162 : 63871 : return mpParent;
163 : : }
164 : :
165 : : /**
166 : : Returns number of this node.
167 : :
168 : : @param bValidate validate the number?
169 : :
170 : : @return number of this node
171 : : */
172 : : SwNumberTree::tSwNumTreeNumber GetNumber( bool bValidate = true ) const;
173 : :
174 : : bool IsContinueingPreviousSubTree() const;
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 : : precondition: node is already member of a list tree
240 : :
241 : : @author OD
242 : : */
243 : : void SetLevelInListTree( const int nLevel );
244 : :
245 : : /**
246 : : Return level of this node.
247 : :
248 : : The level of this node is the length of the path from the root
249 : : to this node.
250 : :
251 : : @return the level of this node
252 : : */
253 : : int GetLevelInListTree() const;
254 : :
255 : : /**
256 : : Returns if this node is less than another node.
257 : :
258 : : @param rTreeNode node to compare with
259 : :
260 : : @attention A phantom node is considered the least element with
261 : : respect to lessThan.
262 : :
263 : : @retval true this node is less than rTreeNode
264 : : @retval false else
265 : : */
266 : : virtual bool LessThan(const SwNumberTreeNode & rTreeNode) const;
267 : :
268 : : /**
269 : : Invalidate this node and all its descendants.
270 : :
271 : : All iterators holding the last valid node in the according list
272 : : of children are set to the end of this list, thereby stating all
273 : : children in the list are invalid.
274 : : #i83479# - made public
275 : : */
276 : : void InvalidateTree() const;
277 : :
278 : : /**
279 : : Notifies all invalid children of this node.
280 : : #i83479# - made public
281 : : */
282 : : void NotifyInvalidChildren();
283 : :
284 : : /**
285 : : Notifies the node.
286 : :
287 : : Calls Invalidate(this) on parent.
288 : : */
289 : : void InvalidateMe();
290 : :
291 : : /**
292 : : Validate the tree.
293 : :
294 : : Validates all nodes in this subtree.
295 : : */
296 : : void ValidateTree();
297 : :
298 : : /**
299 : : Validates this node.
300 : :
301 : : Calls Validate(this) on parent.
302 : : */
303 : : void ValidateMe();
304 : :
305 : : /**
306 : : Notifies all invalid siblings of this node.
307 : : */
308 : : void NotifyInvalidSiblings();
309 : :
310 : : /**
311 : : notification of all nodes in the list tree on certain list level
312 : : */
313 : : void NotifyNodesOnListLevel( const int nListLevel );
314 : :
315 : : /** Invalidation and notification of complete numbering tree
316 : :
317 : : #i64010#
318 : : Usage: on <IsCounted()> state change its needed to invalidate the
319 : : complete numbering tree due to wide influence of this change.
320 : : */
321 : 147 : inline void InvalidateAndNotifyTree()
322 : : {
323 [ + - ]: 147 : if ( GetRoot() )
324 : : {
325 : 147 : GetRoot()->InvalidateTree();
326 : 147 : GetRoot()->Notify();
327 : : }
328 : 147 : }
329 : :
330 : : /**
331 : : Returns the greatest descendant of the root that is smaller than
332 : : this node, aka the predecessor of this node.
333 : :
334 : : @return the predecessor
335 : : */
336 : : SwNumberTreeNode* GetPred( bool bSibling = false ) const;
337 : :
338 : : /** determines the node, which is preceding the node
339 : :
340 : : #i81002#
341 : : The search for the preceding node is performed for the tree below the
342 : : <this> node. To search the complete tree, the method has been called for
343 : : the root of the tree.
344 : :
345 : : @author OD
346 : : */
347 : : const SwNumberTreeNode* GetPrecedingNodeOf( const SwNumberTreeNode& rNode ) const;
348 : :
349 : : #ifdef __SW_NUMBER_TREE_SANITY_CHECK
350 : : /**
351 : : Sanity check.
352 : :
353 : : @param bRecursive descend to children
354 : :
355 : : @retval true the structure of this node is sane
356 : : @retval false else
357 : : */
358 : : bool IsSane(bool bRecursive) const;
359 : : #endif // __SW_NUMBER_TREE_SANITY_CHECK
360 : :
361 : : protected:
362 : : /**
363 : : the children
364 : : */
365 : : tSwNumberTreeChildren mChildren;
366 : :
367 : : /**
368 : : Returns the root node of the tree this node is part of.
369 : :
370 : : Important note: method call <GetRoot()->GetRoot()> returns NULL.
371 : :
372 : : @return the root
373 : : */
374 : : SwNumberTreeNode* GetRoot() const;
375 : :
376 : : /**
377 : : Return if the notification is not disabled on global conditions
378 : :
379 : : @retval true Notification enabled in general.
380 : : @retval false else
381 : : */
382 : : virtual bool IsNotificationEnabled() const = 0;
383 : :
384 : : /**
385 : : Returns how many children this node has got.
386 : :
387 : : @return number of children
388 : : */
389 : : tSwNumberTreeChildren::size_type GetChildCount() const;
390 : :
391 : : // #i64010# - made pure virtual
392 : : virtual bool HasCountedChildren() const = 0;
393 : :
394 : : // #i64010#
395 : : virtual bool IsCountedForNumbering() const = 0;
396 : :
397 : : // method called before this tree node has been added to the list tree
398 : : virtual void PreAdd() = 0;
399 : : // method called after this tree node has been removed from the list tree
400 : : virtual void PostRemove() = 0;
401 : :
402 : : #ifdef __SW_NUMBER_TREE_SANITY_CHECK
403 : : /**
404 : : Sanity check with loop detection.
405 : :
406 : : @param bRecursive descend to children
407 : : @param rParents vector for recording path
408 : :
409 : : @retval true this node is sane
410 : : @retval false else */
411 : : virtual bool IsSane
412 : : (bool bRecursive, std::vector<const SwNumberTreeNode *> rParents) const;
413 : : #endif // __SW_NUMBER_TREE_SANITY_CHECK
414 : :
415 : : /**
416 : : the parent node
417 : : */
418 : : SwNumberTreeNode * mpParent;
419 : :
420 : : /**
421 : : the number of the node
422 : : */
423 : : mutable SwNumberTree::tSwNumTreeNumber mnNumber;
424 : :
425 : : // boolean indicating, that a node of a not counted parent node is continueing
426 : : // the numbering of parent's previous node sub tree.
427 : : // Example:
428 : : // 1. kshdkjfs
429 : : // 1.1. lskjf
430 : : // sdfjlksaf <-- not counted parent node
431 : : // 1.2. lfjlaskf <-- <mbContinueingPreviousSubTree = true>
432 : : mutable bool mbContinueingPreviousSubTree;
433 : :
434 : : /**
435 : : true this node is a phantom
436 : : false this node is NOT a phantom
437 : : */
438 : : bool mbPhantom;
439 : :
440 : : /**
441 : : Iterator to the last valid element. All children that are less
442 : : than or equal to the referenced child are valid. All children
443 : : greater than the referenced child are invalid.
444 : : */
445 : : mutable tSwNumberTreeChildren::const_iterator mItLastValid;
446 : :
447 : : SwNumberTreeNode(const SwNumberTreeNode& );
448 : : SwNumberTreeNode& operator=( const SwNumberTreeNode& );
449 : :
450 : : /**
451 : : Calls _GetNumberVector on parent and adds number of this node
452 : : at the end.
453 : :
454 : : @param rVector return value
455 : : @param bValidate validate the number?
456 : : */
457 : : void _GetNumberVector( SwNumberTree::tNumberVector& rVector,
458 : : bool bValidate = true ) const;
459 : :
460 : : /**
461 : : Invalidates a child.
462 : :
463 : : Calls SetLastValid for the preceeding sibling of the child and
464 : : notifies all invalid children.
465 : :
466 : : @param pChild the child to invalidate
467 : : */
468 : : void Invalidate( SwNumberTreeNode * pChild );
469 : :
470 : : /** Invalidation of all children
471 : :
472 : : Usage: on <IsCounted()> state change the children have to be invalidated
473 : : */
474 : 0 : inline void InvalidateChildren()
475 : : {
476 : 0 : SetLastValid( mChildren.end() );
477 : 0 : }
478 : :
479 : : /** Invalidation of parent node, if its not counted.
480 : :
481 : : Usage: on <IsCounted()> state change the parent have to be invalidated
482 : : */
483 : : inline void InvalidateNotCountedParent()
484 : : {
485 : : if ( GetParent() && !GetParent()->IsCountedForNumbering() )
486 : : {
487 : : GetParent()->InvalidateMe();
488 : : }
489 : : }
490 : :
491 : : /**
492 : : Set the last valid child of this node.
493 : :
494 : : @param aItLastValid iterator pointing to the new last valid child
495 : : @param bValidating - true always set the last valid node to
496 : : aItLastValid
497 : : - false only set if aItLastValid is preceeding
498 : : the current last valid node
499 : : */
500 : : void SetLastValid(tSwNumberTreeChildren::const_iterator aItLastValid,
501 : : bool bValidating = false) const;
502 : :
503 : : /**
504 : : Set this node as last valid child of its parent.
505 : :
506 : : @param bValidation see aboce
507 : : */
508 : : void SetLastValid(bool bValidating) const;
509 : :
510 : : /**
511 : : Return if this node is notifiable.
512 : :
513 : : @attention If a not is not notifiable a notify request is *not*
514 : : forwarded to its descendants.
515 : :
516 : : @retval true This node is notifiable.
517 : : @retval false else
518 : : */
519 : : virtual bool IsNotifiable() const = 0;
520 : :
521 : : /**
522 : : Notifies the node.
523 : :
524 : : Called when the number of the node got invalid.
525 : : */
526 : : virtual void NotifyNode() = 0;
527 : :
528 : : /**
529 : : Notifies this node (NotifyNode) and all descendants.
530 : : */
531 : : void Notify();
532 : :
533 : : /** Notification of parent node siblings, if its not counted.
534 : :
535 : : Usage: on <IsCounted()> state change the parent node and its siblings
536 : : have to be notified.
537 : : */
538 : : inline void NotifyNotCountedParentSiblings()
539 : : {
540 : : if ( GetParent() && !GetParent()->IsCountedForNumbering() )
541 : : {
542 : : GetParent()->NotifyInvalidSiblings();
543 : : }
544 : : }
545 : :
546 : : /** notification of children nodes on certain depth
547 : :
548 : : @author OD
549 : : */
550 : : void NotifyChildrenOnDepth( const int nDepth );
551 : :
552 : : /**
553 : : Returns if a child A this node is valid.
554 : :
555 : : A is valid if aItLastValid in parent refers to a node
556 : : greater than of equal to A.
557 : :
558 : : @param pChild child to be tested
559 : :
560 : : @retval true this node is valid
561 : : @retval false this node is NOT valid
562 : : */
563 : : bool IsValid(const SwNumberTreeNode * pChild) const;
564 : :
565 : : /**
566 : : Returns if this node is valid.
567 : :
568 : : @retval true this node is valid
569 : : @retval false else
570 : : */
571 : : bool IsValid() const;
572 : :
573 : : /**
574 : : Validates a child.
575 : :
576 : : @param pNode child to be validated
577 : :
578 : : @attention All invalid children preceding pNode are validated, too.
579 : : */
580 : : void Validate(const SwNumberTreeNode * pNode) const;
581 : :
582 : : /**
583 : : Validates a child using hierarchical numbering.
584 : :
585 : : @param pNode child to be validated
586 : :
587 : : @attention All invalid children preceding pNode are validated, too.
588 : : */
589 : : void ValidateHierarchical(const SwNumberTreeNode * pNode) const;
590 : :
591 : : /**
592 : : Validates a child using continuous numbering.
593 : :
594 : : @param pNode child to be validated
595 : :
596 : : @attention All invalid children preceding pNode are validated, too.
597 : : */
598 : : void ValidateContinuous(const SwNumberTreeNode * pNode) const;
599 : :
600 : : /**
601 : : Creates a new node of the same class.
602 : :
603 : : @return the new node
604 : : */
605 : : virtual SwNumberTreeNode * Create() const = 0;
606 : :
607 : : /**
608 : : Creates a phantom.
609 : :
610 : : @return the created phantom
611 : : */
612 : : SwNumberTreeNode * CreatePhantom();
613 : :
614 : : /**
615 : : Set if this node is a phantom.
616 : :
617 : : @param bPhantom - true this node is a phantom
618 : : - false this node is a phantom
619 : : */
620 : : void SetPhantom(bool bPhantom = true);
621 : :
622 : : /**
623 : : Return if phantoms are counted.
624 : :
625 : : @retval true phantoms are counted
626 : : @retval false else
627 : : */
628 : : virtual bool IsCountPhantoms() const = 0;
629 : :
630 : : /**
631 : : Return if all descendants of this node are phantoms.
632 : :
633 : : @retval true all descendants are phantoms
634 : : @retval false else
635 : : */
636 : : bool HasOnlyPhantoms() const;
637 : :
638 : : bool HasPhantomCountedParent() const;
639 : :
640 : : /**
641 : : HB, OD : return node, if it isn't a phantom, otherwise return first
642 : : non-phantom descendant.
643 : : Returns the first child of this node that is NOT a phantom.
644 : :
645 : : @return the first non phantom child
646 : : */
647 : : SwNumberTreeNode* GetFirstNonPhantomChild();
648 : :
649 : : /**
650 : : Removes recursively phantoms that have no children.
651 : :
652 : : The resulting tree has no phantoms that either have no children or
653 : : whose descendancy consist entirely of phantoms.
654 : : */
655 : : void ClearObsoletePhantoms();
656 : :
657 : : tSwNumberTreeChildren::const_iterator GetIterator(const SwNumberTreeNode * pChild) const;
658 : :
659 : : /**
660 : : Moves all children to a given destination node.
661 : :
662 : : @param pDest the destination node
663 : : */
664 : : void MoveChildren(SwNumberTreeNode * pDest);
665 : :
666 : : /** Moves all children of this node that are greater than a given node
667 : : to the destination node.
668 : :
669 : : distinguish between node for comparing, whose children are greater,
670 : : and the destination node.
671 : :
672 : : @param _rCompareNode
673 : : input parameter - reference to the node, which is used to determine
674 : : the greater children
675 : :
676 : : @param _rDestNode
677 : : input parameter - reference to the node, which is the destination for
678 : : the greater children
679 : : */
680 : : void MoveGreaterChildren( SwNumberTreeNode& _rCompareNode,
681 : : SwNumberTreeNode& _rDestNode );
682 : :
683 : : /**
684 : : Returns the last descendant of a node, if it has children.
685 : :
686 : : @return last descendant of the node
687 : : */
688 : : SwNumberTreeNode* GetLastDescendant() const;
689 : :
690 : : };
691 : :
692 : : /**
693 : : Functor. Checks if a certain node is less than the functor's member.
694 : : */
695 : : struct SwNumberTreeNodeIsLessThan
696 : : {
697 : : const SwNumberTreeNode * pNode;
698 : :
699 : : SwNumberTreeNodeIsLessThan(const SwNumberTreeNode * _pNode)
700 : : : pNode(_pNode) {}
701 : :
702 : : bool operator()(const SwNumberTreeNode * _pNode) const
703 : : { return SwNumberTreeNodeLessThan(_pNode, pNode); }
704 : : };
705 : : #endif // _SW_NUMBER_TREE_HXX
706 : :
707 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
