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: 33 TreeVisitor( NODEINFO _nodeInfo ) 34 :m_visitedRoot( false ) 35 ,m_root() 36 ,m_current() 37 ,m_nodeInfo( _nodeInfo ) 38 { 39 } 40 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 > 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