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 INCLUDED_SVX_SOURCE_INC_TREEVISITOR_HXX
21 #define INCLUDED_SVX_SOURCE_INC_TREEVISITOR_HXX
22
23 #include <stack>
24
25 template< class ELEMENT, class NODEINFO, class PROCESSOR >
26 class TreeVisitor
27 {
28 public:
TreeVisitor(NODEINFO _nodeInfo)29 TreeVisitor( NODEINFO _nodeInfo )
30 :m_visitedRoot( false )
31 ,m_root()
32 ,m_current()
33 ,m_nodeInfo( _nodeInfo )
34 {
35 }
36
process(const ELEMENT & _root,PROCESSOR & _processor)37 void process( const ELEMENT& _root, PROCESSOR& _processor )
38 {
39 m_root = _root;
40 m_visitedRoot = false;
41
42 while ( do_step() )
43 _processor.process( m_current );
44 }
45
46 private:
47 bool do_step();
48
49 private:
50 bool m_visitedRoot;
51 ELEMENT m_root;
52 ELEMENT m_current;
53 const NODEINFO m_nodeInfo;
54
55 ::std::stack< size_t > m_pathToCurrent;
56 ::std::stack< ELEMENT > m_currentAncestors;
57 };
58
59 template< class ELEMENT, class NODEINFO, class PROCESSOR >
do_step()60 bool TreeVisitor< ELEMENT, NODEINFO, PROCESSOR >::do_step()
61 {
62 if ( !m_visitedRoot )
63 {
64 m_current = m_root;
65 m_visitedRoot = true;
66 return true;
67 }
68
69 // can we step down from the current node?
70 size_t childCount = m_nodeInfo.childCount( m_current );
71 if ( childCount )
72 {
73 m_currentAncestors.push( m_current );
74 m_current = m_nodeInfo.getChild( m_current, 0 );
75 m_pathToCurrent.push( 0 );
76 return true;
77 }
78
79 // is there a right sibling of the current node?
80 while ( !m_pathToCurrent.empty() )
81 {
82 const ELEMENT& currentParent = m_currentAncestors.top();
83 childCount = m_nodeInfo.childCount( currentParent );
84
85 size_t currentChildPos = m_pathToCurrent.top();
86 if ( ++currentChildPos < childCount )
87 {
88 // yes there is
89 m_pathToCurrent.top() = currentChildPos;
90 m_current = m_nodeInfo.getChild( currentParent, currentChildPos );
91 return true;
92 }
93
94 // no there isn't => step up
95 m_currentAncestors.pop();
96 m_pathToCurrent.pop();
97 }
98
99 return false;
100 }
101
102 #endif // INCLUDED_SVX_SOURCE_INC_TREEVISITOR_HXX
103
104 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
105