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