LCOV - code coverage report
Current view: top level - usr/local/src/libreoffice/sw/inc - SwNumberTree.hxx (source / functions) Hit Total Coverage
Test: libreoffice_filtered.info Lines: 4 12 33.3 %
Date: 2013-07-09 Functions: 2 4 50.0 %
Legend: Lines: hit not hit

          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: */

Generated by: LCOV version 1.10