INTEGRATION: CWS swnumtree (1.1.2); FILE ADDED

2005/11/02 10:37:04 od 1.1.2.14: #126009# class <SwNumberTree> - new method <HasPhantomCountedParent()>
2005/10/20 08:31:09 od 1.1.2.13: #126009# class <SwNumberTreeNode>
	 - add public methods <InvalidateChildren()>, <InvalidateNotCountedParent()>
	   and <NotifyNotCountedParentSiblings()>
2005/10/18 14:08:01 od 1.1.2.12: #125991# class <SwNumberTreeNode> - adjust method <MoveGreaterChildren(..)>
2005/09/28 07:54:35 hbrinkm 1.1.2.11: #i54903# license changed
2005/09/19 15:43:53 hbrinkm 1.1.2.10: #i51089# NotifyInvalidSiblings
2005/09/14 13:16:37 hbrinkm 1.1.2.9: #i51089# -m[nb]Level{Valid}, -const on Notify...
2005/09/12 14:18:12 hbrinkm 1.1.2.8: #i51089# SetValid: new parameter: bValidating
2005/08/26 13:37:55 hbrinkm 1.1.2.7: #i51089# GetStart has to be virtual
2005/08/19 15:17:32 hbrinkm 1.1.2.6: #i51089# place SW_DLLPUBLIC correctly, only compile IsSane if __SW_NUMBER_TREE_SANITY_CHECK is set
2005/08/09 12:34:06 hbrinkm 1.1.2.5: #i51089# IsFirst
2005/07/08 14:34:46 hbrinkm 1.1.2.4: #i51089# Solaris compiler does not like sDefaultIndent
2005/07/07 12:39:54 hbrinkm 1.1.2.3: #i51089# HasCountedChildren
2005/06/23 09:17:08 hbrinkm 1.1.2.2: #i51089# replace ifdef DEBUG by ifndef PRODUCT
2005/06/22 09:23:17 hbrinkm 1.1.2.1: #i51089# a numbering tree

1 files changed, 725 insertions, 0 deletions

diff --git a/sw/inc/SwNumberTree.hxx b/sw/inc/SwNumberTree.hxx
new file mode 100644
index 0000000000..fc31fcd995
--- /dev/null
+++ b/sw/inc/SwNumberTree.hxx
@@ -0,0 +1,725 @@
+/*************************************************************************
+ *
+ *  OpenOffice.org - a multi-platform office productivity suite
+ *
+ *  $RCSfile: SwNumberTree.hxx,v $
+ *
+ *  $Revision: 1.2 $
+ *
+ *  last change: $Author: rt $ $Date: 2005-11-08 17:11:18 $
+ *
+ *  The Contents of this file are made available subject to
+ *  the terms of GNU Lesser General Public License Version 2.1.
+ *
+ *
+ *    GNU Lesser General Public License Version 2.1
+ *    =============================================
+ *    Copyright 2005 by Sun Microsystems, Inc.
+ *    901 San Antonio Road, Palo Alto, CA 94303, USA
+ *
+ *    This library is free software; you can redistribute it and/or
+ *    modify it under the terms of the GNU Lesser General Public
+ *    License version 2.1, as published by the Free Software Foundation.
+ *
+ *    This library is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *    Lesser General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Lesser General Public
+ *    License along with this library; if not, write to the Free Software
+ *    Foundation, Inc., 59 Temple Place, Suite 330, Boston,
+ *    MA  02111-1307  USA
+ *
+ ************************************************************************/
+
+#ifndef _SW_NUMBER_TREE_HXX
+#define _SW_NUMBER_TREE_HXX
+
+#include <set>
+#include <vector>
+#include <tools/string.hxx>
+#include <swdllapi.h>
+
+class SwNumberTreeNode;
+
+bool SwNumberTreeNodeLessThan (const SwNumberTreeNode * pA,
+                               const SwNumberTreeNode * pB);
+
+bool SwNumberTreeNodeGreaterEqual (const SwNumberTreeNode * pA,
+                                   const SwNumberTreeNode * pB);
+
+struct compSwNumberTreeNodeLessThan
+{
+    bool operator()(const SwNumberTreeNode * pA,
+                    const SwNumberTreeNode * pB) const
+    { return SwNumberTreeNodeLessThan(pA, pB); }
+};
+
+/**
+   A tree of numbered nodes.
+
+   Simple example:
+
+   <pre>
+   1. kshdkjfs
+     1.1. lskjf
+   2. sdfjlksaf
+   3. fkaöslk
+     3.1. lfjlaskf
+     3.2. jaslkjflsf
+       3.2.1. hkljhkjhk
+
+   + R
+     + 1 kshdkjfs
+     | + 1 lskjf
+     + 2 sdfjlksaf
+     + 3 fkaöslk
+       + 1 lfjlaskf
+       + 2 jaslkjflsf
+         + 1 hkljhkjhk
+   </pre>
+
+   The root contains the nodes of the first level. Each node A of the
+   first level contains those nodes of the second level that have the
+   same first level number as A and so on for the subsidiary levels.
+
+   The numbering label of a node A is resolved by concatenating the
+   numbers of the nodes on the path from the root to A.
+
+    ------------------------------------------
+
+    Phantoms
+
+    A phantom is an auxiliary node that is used to emulate numberings
+    starting with nodes not at top level. The phantom contains the
+    number for the level but is not considered part of the numbering.
+
+     Constraint 1: A phantom is always the first child node.
+     Constraint 2: At each node there is at most one child that is a phantom.
+     Constraint 3: A phantom is the smallest of all numbering nodes.
+
+    Uncounted Phantoms
+
+      0.1. dljflskjlasf
+    5. ödsöfkaös
+      5.1.
+
+    + R (nStart = 5)
+      + 0 (phantom, not counted)
+      | + 1 dljflskjlasf
+      + 5 ödsöfkaös
+        + 1
+
+     The phantom gets numbered with 0. The first non-phantom node gets
+     numbered with the start value.
+
+     -----------------------------------------
+
+     Counted Phantoms
+
+       5.1. lgkjjgklg
+     6. lkjfalskjflsaf
+       6.1. ljdflaksjflkjasflkjsf
+
+     + R (nStart = 5)
+       + 5 (phantom, counted)
+       | + 1 lgkjjgklg
+       + 6 lkjfalskjflsaf
+         + 1 ljdflaksjflkjasflkjsf
+
+     The phantom gets numbered with the start value.
+*/
+class SW_DLLPUBLIC SwNumberTreeNode
+{
+    /**
+       Default indent for printing a tree.
+
+       If a level has level n this indent is printed n times before
+       the actual node is printed.
+     */
+    //String sDefaultIndent;
+
+#ifndef PRODUCT
+    /**
+       Counter for the number of created instances.
+     */
+    static unsigned long nInstances;
+
+    /**
+       Serial number.
+    */
+    unsigned long mnSerial;
+#endif
+
+protected:
+    typedef std::set<SwNumberTreeNode *, compSwNumberTreeNodeLessThan>
+    tSwNumberTreeChildren;
+
+public:
+    typedef long tSwNumTreeNumber;
+    typedef std::vector<tSwNumTreeNumber> tNumberVector;
+
+protected:
+    /**
+       the parent node
+    */
+    SwNumberTreeNode * mpParent;
+
+    /**
+       the number of the node
+    */
+    mutable tSwNumTreeNumber mnNumber;
+
+    /**
+       true     this node is a phantom
+       false    this node is NOT a phantom
+     */
+    bool mbPhantom;
+
+    /**
+       the children
+    */
+    tSwNumberTreeChildren mChildren;
+
+    /**
+       Iterator to the last valid element. All children that are less
+       than or equal to the referenced child are valid. All children
+       greater than the referenced child are invalid.
+     */
+    mutable tSwNumberTreeChildren::iterator mItLastValid;
+
+    /**
+       Validates a child.
+
+       @param pNode     child to be validated
+
+       @attention All invalid children preceding pNode are validated, too.
+     */
+    void Validate(const SwNumberTreeNode * pNode) const;
+
+    /**
+       Validates a child using hierarchical numbering.
+
+       @param pNode      child to be validated
+
+       @attention All invalid children preceding pNode are validated, too.
+     */
+    void ValidateHierarchical(const SwNumberTreeNode * pNode) const;
+
+    /**
+       Validates a child using continuous numbering.
+
+       @param pNode      child to be validated
+
+       @attention All invalid children preceding pNode are validated, too.
+     */
+    void ValidateContinuous(const SwNumberTreeNode * pNode) const;
+
+    /**
+        HB, OD : return node, if it isn't a phantom, otherwise return first
+                 non-phantom descendant.
+        Returns the first child of this node that is NOT a phantom.
+
+        @return  the first non phantom child
+    */
+    SwNumberTreeNode * GetFirstNonPhantomChild();
+
+    /**
+       Returns the last descendant of a node, if it has children.
+
+       @return last descendant of the node
+    */
+    SwNumberTreeNode * GetLastDescendant() const;
+
+    /**
+       Returns the greatest descendant of the root that is smaller than
+       this node, aka the predecessor of this node.
+
+       @return the predecessor
+     */
+    SwNumberTreeNode * GetPred() const;
+
+    /**
+       Set the last valid child of this node.
+
+       @param aItLastValid    iterator pointing to the new last valid child
+       @param bValidating     - true    always set the last valid node to
+                                        aItLastValid
+                              - false   only set if aItLastValid is preceeding
+                                        the current last valid node
+     */
+    void SetLastValid(tSwNumberTreeChildren::iterator aItLastValid,
+                      bool bValidating = false) const;
+
+    /**
+       Set this node as last valid child of its parent.
+
+       @param bValidation    see aboce
+     */
+    void SetLastValid(bool bValidating) const;
+
+    /**
+       Invalidate this node and all its descendants.
+
+       All iterators holding the last valid node in the according list
+       of childs are set to the end of this list, thereby stating all
+       children in the list are invalid.
+     */
+    void InvalidateTree() const;
+
+    /**
+       Notifies the node.
+
+       Called when the number of the node got invalid.
+     */
+    virtual void NotifyNode();
+
+    /**
+       Notifies this node (NotifyNode) and all descendants.
+     */
+    void Notify();
+
+    /**
+       Notifies a child and its descendants.
+
+       @param pNode    the child to be notifed
+     */
+    void Notify(SwNumberTreeNode * pNode);
+
+    /**
+       Notifies all invalid children of this node.
+     */
+    void NotifyInvalidChildren();
+
+    /**
+       Notifies all invalid siblings of this node.
+    */
+    void NotifyInvalidSiblings();
+
+    /**
+       Calls _GetNumberVector on parent and adds number of this node
+       at the end.
+
+       @param rVector     return value
+       @param bValidate   validate the number?
+     */
+    void _GetNumberVector(tNumberVector & rVector, bool bValidate = true) const;
+
+    /** Moves all children of this node that are greater than a given node
+        to the destination node.
+
+        OD 2005-10-14 #125991#
+        distinguish between node for comparing, whose children are greater,
+        and the destination node.
+
+        @param _rCompareNode
+        input parameter - reference to the node, which is used to determine
+        the greater children
+
+        @param _rDestNode
+        input parameter - reference to the node, which is the destination for
+        the greater children
+    */
+    void MoveGreaterChildren( SwNumberTreeNode& _rCompareNode,
+                              SwNumberTreeNode& _rDestNode );
+
+    /**
+       Moves all children to a given destination node.
+
+       @param pDest    the destination node
+     */
+    void MoveChildren(SwNumberTreeNode * pDest);
+
+    /**
+       Creates a phantom.
+
+       @return the created phantom
+     */
+    SwNumberTreeNode * CreatePhantom();
+
+    /**
+       Removes recursively phantoms that have no children.
+
+       The resulting tree has no phantoms that either have no children or
+       whose descendancy consist entirely of phantoms.
+     */
+    void ClearObsoletePhantoms();
+
+    /**
+       Return if all descendants of this node are phantoms.
+
+       @retval true   all descendants are phantoms
+       @retval false  else
+     */
+    bool HasOnlyPhantoms() const;
+
+#ifdef __SW_NUMBER_TREE_SANITY_CHECK
+    /**
+       Sanity check with loop detection.
+
+       @param bRecursive   descend to children
+       @param rParents     vector for recording path
+
+       @retval true     this node is sane
+       @retval false    else     */
+    virtual bool IsSane
+    (bool bRecursive, std::vector<const SwNumberTreeNode *> rParents) const;
+#endif // __SW_NUMBER_TREE_SANITY_CHECK
+
+    tSwNumberTreeChildren::iterator
+    GetIterator(const SwNumberTreeNode * pChild) const;
+
+    bool HasCountedChildren() const;
+
+    // --> OD 2005-10-27 #126009#
+    bool HasPhantomCountedParent() const;
+    // <--
+
+public:
+    SwNumberTreeNode();
+    SwNumberTreeNode(const SwNumberTreeNode & rNode);
+
+    virtual ~SwNumberTreeNode();
+
+#ifndef PRODUCT
+    static unsigned long GetInstances();
+    unsigned long GetSerial();
+#endif
+
+    /**
+       Creates a new node of the same class.
+
+       @return the new node
+    */
+    virtual SwNumberTreeNode * Create() const = 0;
+
+    /**
+       Creates a copy of this node.
+
+       @return the copy
+     */
+    virtual SwNumberTreeNode * Copy() const = 0;
+
+    /**
+       Returns the parent of this node.
+
+       @return the parent
+    */
+    SwNumberTreeNode * GetParent() const { return mpParent; }
+
+    /**
+       Returns the root node of the tree this node is part of.
+
+       @return the root
+     */
+    SwNumberTreeNode * GetRoot() const;
+
+    /**
+       Add a child.
+
+       @param pChild   child to add
+       @param nDepth   depth in whuch to add the child
+     */
+    void AddChild(SwNumberTreeNode * pChild, unsigned int nDepth = 0);
+
+    /**
+       Remove a child.
+
+       @param pChild     child to be removed
+     */
+    virtual void RemoveChild(SwNumberTreeNode * pChild);
+
+    /**
+       Remove this child from the tree.
+     */
+    void RemoveMe();
+
+    /**
+       Returns number of this node.
+
+       @param bValidate     validate the number?
+
+       @return number of this node
+     */
+    tSwNumTreeNumber GetNumber(bool bValidate = true) const;
+
+    /**
+       Returns level numbers of this node.
+
+       @return level numbers of this node
+     */
+    tNumberVector GetNumberVector() const;
+
+    /**
+       Return start value.
+
+       @return start value
+     */
+    virtual tSwNumTreeNumber GetStart() const;
+
+    /**
+       Return if numbering is restartet at this node.
+     */
+    virtual bool IsRestart() const;
+
+    /**
+       Return if phantoms are counted.
+
+       @retval true phantoms are counted
+       @retval false else
+     */
+    virtual bool IsCountPhantoms() const;
+
+    /**
+       Returns if a child A this node is valid.
+
+       A is valid if aItLastValid in parent refers to a node
+       greater than of equal to A.
+
+       @param pChild    child to be tested
+
+       @retval true this node is valid
+       @retval false this node is NOT valid
+     */
+    bool IsValid(const SwNumberTreeNode * pChild) const;
+
+    /**
+       Returns if this node is valid.
+
+       @retval true    this node is valid
+       @retval false   else
+     */
+    bool IsValid() const;
+
+    /**
+       Return if this node is a phantom.
+
+       @retval true this node is a phantom
+       @retval false this node is NOT a phantom
+     */
+    bool IsPhantom() const;
+
+    /**
+       Set if this node is a phantom.
+
+       @param bPhantom   - true this node is a phantom
+                         - false this node is a phantom
+     */
+    void SetPhantom(bool bPhantom = true);
+
+    /**
+       Return if this node is counted.
+
+       @retval true this node is counted
+       @retval false this node is NOT counted
+     */
+    virtual bool IsCounted() const;
+
+    /**
+       Return if this node is counted continuous.
+
+       @retval true    This node is counted continuous.
+       @retval false   else
+     */
+    virtual bool IsContinuous() const;
+
+    /**
+       Return if this node is notifiable.
+
+       @attention If a not is not notifiable a notify request is *not*
+       forwarded to its descendants.
+
+       @retval true   This node is notifiable.
+       @retval false  else
+     */
+    virtual bool IsNotifiable() const;
+
+    /**
+       Return if a node is first non-phantom child of this node.
+
+       @param pNode     the node to check
+
+       @retval true     pNode is first child of this node
+       @retval false    else
+     */
+    virtual bool IsFirst(const SwNumberTreeNode * pNode) const;
+
+    /**
+       Return if this node if the first non-phantom node in the tree.
+
+       @retval true     this node is the first non-phantom node in the tree
+       @retval false    else
+     */
+    virtual bool IsFirst() const;
+
+    /**
+       Return level of this node.
+
+       The level of this node is the length of the path from the root
+       to this node.
+
+       @return the level of this node
+     */
+    int GetLevel() const;
+
+    /**
+       Returns how many children this node has got.
+
+       @return number of children
+     */
+    tSwNumberTreeChildren::size_type GetChildCount() const;
+
+    /**
+       Returns if this node is less than another node.
+
+       @param rTreeNode   node to compare with
+
+       @attention A phantom node is considered the least element with
+       respect to lessThan.
+
+       @retval true this node is less than rTreeNode
+       @retval false else
+    */
+    virtual bool LessThan(const SwNumberTreeNode & rTreeNode) const
+    { return this < &rTreeNode; }
+
+    /**
+       Validate the tree.
+
+       Validates all nodes in this subtree.
+    */
+    void ValidateTree();
+
+    /**
+       Invalidates a child.
+
+       Calls SetLastValid for the preceeding sibling of the child and
+       notifies all invalid children.
+
+       @param pChild      the child to invalidate
+     */
+    void Invalidate(SwNumberTreeNode * pChild);
+
+    /**
+       Invalidates this node.
+
+       Calls Invalidate(this) on parent.
+     */
+    void InvalidateMe();
+
+    /**
+       Validates this node.
+
+       Calls Validate(this) on parent.
+    */
+    void ValidateMe();
+
+#ifdef __SW_NUMBER_TREE_SANITY_CHECK
+    /**
+       Sanity check.
+
+       @param bRecursive    descend to children
+
+       @retval true   the structure of this node is sane
+       @retval false  else
+     */
+    bool IsSane(bool bRecursive) const;
+#endif // __SW_NUMBER_TREE_SANITY_CHECK
+
+    /**
+       Returns if this node contains a node as a child.
+
+       @param pChild      node to search
+
+       @retval true    pChild is a child of this node
+       @retval false   else
+     */
+    bool Contains(const SwNumberTreeNode * pChild) const;
+
+    /**
+       Returns a string representation of this node.
+
+       @return the string representation of this node
+     */
+    virtual String ToString() const = 0;
+
+    /**
+       Returns the number of nodes in this subtree.
+
+       @param bCountPhantoms     - true  count phantoms
+                                 - false else
+
+       @return number of nodes counted in this subtree
+     */
+    unsigned long GetCount(bool bCountPhantoms = false) const;
+
+    /** Invalidation of all children
+
+        OD 2005-10-19 #126009#
+        Usage: on <IsCounted()> state change the children have to be invalidated
+    */
+    inline void InvalidateChildren()
+    {
+        SetLastValid( mChildren.end() );
+    }
+
+    /** Invalidation of parent node, if its not counted.
+
+        OD 2005-10-19 #126009#
+        Usage: on <IsCounted()> state change the parent have to be invalidated
+    */
+    inline void InvalidateNotCountedParent()
+    {
+        if ( GetParent() && !GetParent()->IsCounted() )
+        {
+            GetParent()->InvalidateMe();
+        }
+    }
+
+    /** Notification of parent node siblings, if its not counted.
+
+        OD 2005-10-19 #126009#
+        Usage: on <IsCounted()> state change the parent node and its siblings
+               have to be notified.
+    */
+    inline void NotifyNotCountedParentSiblings()
+    {
+        if ( GetParent() && !GetParent()->IsCounted() )
+        {
+            GetParent()->NotifyInvalidSiblings();
+        }
+    }
+
+    /**
+       Print this subtree.
+
+       @param o              output stream to direct output to
+       @param rIndent        additional indent for the children of this node
+       @param rMyIndent      indent to use for this node
+       @param nDepth         number of levels to print (-1 means all levels)
+
+       @return output stream after output of this subtree
+     */
+    String print(const String & rIndent = String("  ",
+                                                 RTL_TEXTENCODING_ASCII_US),
+                 const String & rMyIndent = String("  ",
+                                                   RTL_TEXTENCODING_ASCII_US),
+                 int nDepth = -1) const;
+
+};
+
+/**
+   Functor. Checks if a certain node is less than the functor's member.
+ */
+struct SwNumberTreeNodeIsLessThan
+{
+    const SwNumberTreeNode * pNode;
+
+    SwNumberTreeNodeIsLessThan(const SwNumberTreeNode * _pNode)
+        : pNode(_pNode) {}
+
+    bool operator()(const SwNumberTreeNode * _pNode) const
+    { return SwNumberTreeNodeLessThan(_pNode, pNode); }
+};
+#endif // _SW_NUMBER_TREE_HXX