xref: /aoo42x/main/svx/source/inc/treevisitor.hxx (revision 3334a7e6)
1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 #ifndef SVX_TREE_VISITOR_HXX
25 #define SVX_TREE_VISITOR_HXX
26 
27 #include <stack>
28 
29 template< class ELEMENT, class NODEINFO, class PROCESSOR >
30 class TreeVisitor
31 {
32 public:
TreeVisitor(NODEINFO _nodeInfo)33     TreeVisitor( NODEINFO _nodeInfo )
34         :m_visitedRoot( false )
35         ,m_root()
36         ,m_current()
37         ,m_nodeInfo( _nodeInfo )
38     {
39     }
40 
process(const ELEMENT & _root,PROCESSOR & _processor)41     void    process( const ELEMENT& _root, PROCESSOR& _processor )
42     {
43         m_root = _root;
44         m_visitedRoot = false;
45 
46         while ( do_step() )
47             _processor.process( m_current );
48     }
49 
50 private:
51     bool    do_step();
52 
53 private:
54     bool            m_visitedRoot;
55     ELEMENT         m_root;
56     ELEMENT         m_current;
57     const NODEINFO  m_nodeInfo;
58 
59     ::std::stack< size_t >  m_pathToCurrent;
60     ::std::stack< ELEMENT > m_currentAncestors;
61 };
62 
63 template< class ELEMENT, class NODEINFO, class PROCESSOR >
do_step()64 bool TreeVisitor< ELEMENT, NODEINFO, PROCESSOR >::do_step()
65 {
66     if ( !m_visitedRoot )
67     {
68         m_current = m_root;
69         m_visitedRoot = true;
70         return true;
71     }
72 
73     // can we step down from the current node?
74     size_t childCount = m_nodeInfo.childCount( m_current );
75     if ( childCount )
76     {
77         m_currentAncestors.push( m_current );
78         m_current = m_nodeInfo.getChild( m_current, 0 );
79         m_pathToCurrent.push( 0 );
80         return true;
81     }
82 
83     // is there a right sibling of the current node?
84     while ( !m_pathToCurrent.empty() )
85     {
86         const ELEMENT& currentParent = m_currentAncestors.top();
87         childCount = m_nodeInfo.childCount( currentParent );
88 
89         size_t currentChildPos = m_pathToCurrent.top();
90         if ( ++currentChildPos < childCount )
91         {
92             // yes there is
93             m_pathToCurrent.top() = currentChildPos;
94             m_current = m_nodeInfo.getChild( currentParent, currentChildPos );
95             return true;
96         }
97 
98         // no there isn't => step up
99         m_currentAncestors.pop();
100         m_pathToCurrent.pop();
101     }
102 
103     return false;
104 }
105 
106 #endif // SVX_TREE_VISITOR_HXX
107