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