Java iterators for C++:
 All Classes Namespaces Files Functions Variables Typedefs Friends Macros Pages
Tree_LPR.h
Go to the documentation of this file.
1 // Tree_LPR.h (c) 2009 adolfo@di-mare.com
2 
3 #ifdef English_dox
4 /// \file Tree_LPR.h
5 /// \brief Left-Process-Right iterator.
6 /// \author Adolfo Di Mare <adolfo@di-mare.com>
7 /// This implementation uses a Stack to store the path that remains
8 /// to traverse for the tree. This path is not exactly the path
9 /// to the root, as oftentimes it contains references to the rigth
10 /// siblings for the sub-tree.
11 /// \date 2009
12 #endif
13 #ifdef Spanish_dox
14 /// \file Tree_LPR.h
15 /// \brief Iterador Izquierda-Proceso-Derecha.
16 /// Esta implementacíon usa una Pila para almacenar el camino que falta
17 /// de recorer del árbol. Este camino no es exactamente el camino hasta
18 /// la raíz, pues muchas veces referencias a los hermanos derechos de
19 /// un sub-árbol.
20 /// \author Adolfo Di Mare <adolfo@di-mare.com>
21 /// \date 2009
22 #endif
23 
24 #ifndef Tree_LPR_h
25 #define Tree_LPR_h
26 
27 #ifdef English_dox
28  /// Doxygen English documentation.
29  #define English_dox "Doxygen English documentation"
30  /// \def English_dox ///< Marks English documentation blocks.
31  /// \def Tree_LPR_h ///< Avoids multiple inclusion.
32 #endif
33 #ifdef Spanish_dox
34  /// Documentaci¢n en espa¤ol.
35  #define Spanish_dox "Documentaci¢n Doxygen en espa¤ol"
36  /// \def Spanish_dox ///< Macro usado para que Doxygen genere documentación.
37  /// \def Tree_LPR_h ///< Evita la inclusión múltiple.
38 #endif
39 
40 #include <vector>
41 #include "Tree_L.h"
42 #include <iostream>
43 
44 #ifdef English_dox
45 /// Left-Process-Right iterator.
46 #endif
47 #ifdef Spanish_dox
48 /// Iterador Izquierda-Proceso-Derecha.
49 #endif
50 /**
51  \dontinclude test_iterJava.cpp
52  \skipline test::Tree_LPR()
53  \until }}
54  \see test_iterJava::test_Tree_LPR()
55 
56  \see make_a_o(TL::Tree<char> & T)
57  \dontinclude test_iterJava.cpp
58  \skipline T = a
59  \until +--k
60 */
61 
62 template <typename E>
63 class Tree_LPR {
64  std::vector< TL::Tree<E> > m_S; ///< std::stack<>.
65 public:
66  /// \c init().
67  Tree_LPR( const TL::Tree<E>& T = TL::Tree<E>() )
68  : m_S(32) { set(T); }
69  void set( const TL::Tree<E>& T ); ///< \c Iterator::set().
70 
71  bool hasNext() const; ///< \c Iterator::hasNext().
72  const TL::Tree<E> next(); ///< \c Iterator::next().
73 
74  void push_left_descendants( const TL::Tree<E>& T );
75 };
76 
77 template <typename E>
78 void Tree_LPR<E>::set( const TL::Tree<E>& T ) {
79  m_S.clear(); // erase whatever was left
80  m_S.push_back( T );
81  push_left_descendants( T );
82 }
83 
84 #ifdef English_dox
85  /// Push every \c Child(0) [left] descendant of \c T in the stack.
86 #endif
87 #ifdef Spanish_dox
88  /// Empuje cada descendiente \c Child(0) [izquierdo] de \c T en la pila.
89 #endif
90 template <typename E>
92  TL::Tree<E> D = T.Child(0);
93  while ( ! D.Empty() ) {
94  m_S.push_back( D );
95  D = D.Child(0);
96  }
97 }
98 
99 /* Indicates if the iterator have a next element */
100 template <typename E>
101 bool Tree_LPR<E>::hasNext() const {
102  return ( ! m_S.empty() );
103 }
104 
105 #if 0
106 template <typename C>
107 inline void printC( const C& L ) {
108  typename C::const_reverse_iterator it;
109  std::cout << '[' << L.size() << "] ";
110  for ( it = L.rbegin() ; it != L.rend() ; ++it ) {
111  std::cout << **it << ' ';
112  }
113  std::cout << std::endl;
114 }
115 #endif
116 
117 /* Moves the iterator to it`s next element */
118 template <typename E>
120 // printC( m_S );
121  TL::Tree<E> Res = m_S.back();
122  m_S.pop_back(); // stack top will be returned by next()
123 
124  TL::Tree<E> Child = Res.Rightmost();
125  TL::Tree<E> Stop = Res.Leftmost();
126  TL::Tree<E> Left;
127  if( ! Child.Empty() ) {
128  for (;;) {
129  Left = Child.Left_Sibling();
130  if ( Left.Empty() ) {
131  if ( ! Child.Same( Res.Child(0) ) ) {
132  m_S.push_back( Child );
133  if ( ! Child.Child(0).Empty() ) {
134  push_left_descendants( Child );
135  }
136  }
137  break;
138  }
139  else if ( Stop.Same( Left ) ) {
140  m_S.push_back( Child );
141  push_left_descendants( Child );
142  break;
143  }
144  else {
145  m_S.push_back( Child );
146  if ( ! Child.Child(0).Empty() ) {
147  push_left_descendants( Child );
148  }
149  }
150  Child = Left;
151  }
152  }
153  return Res;
154 }
155 
156 #endif // Tree_LPR_h
157 // EOF: Tree_PLR.h
Left-Process-Right iterator.
Definition: Tree_LPR.h:63
void push_left_descendants(const TL::Tree< E > &T)
Push every Child(0) [left] descendant of T in the stack.
Definition: Tree_LPR.h:91
const TL::Tree< E > next()
Iterator::next().
Definition: Tree_LPR.h:119
bool Same(const Tree &o) const
Retorna true si &quot;o&quot; comparte la raíz con &quot;*this&quot;.
Definition: Tree_L.h:148
void set(const TL::Tree< E > &T)
Iterator::set().
Definition: Tree_LPR.h:78
std::vector< TL::Tree< E > > m_S
std::stack&lt;&gt;.
Definition: Tree_LPR.h:64
Tree Leftmost() const
Obtiene el hijo más izquierdo del árbol.
Definition: Tree_L.h:698
Declaraciones y definiciones para la clase Tree.
bool Empty() const
Retorna &quot;true&quot; si el sub-árbol está vacío.
Definition: Tree_L.h:91
Tree Left_Sibling() const
Obtiene el hermano no vacío anterior, que está hacia la izquierda.
Definition: Tree_L.h:474
Los métodos para trabajar con árboles regresan &quot;referencias&quot; que son sub-árboles. ...
Definition: Tree_L.h:25
Tree Rightmost() const
Obtiene el hijo más derecho del árbol.
Definition: Tree_L.h:721
bool hasNext() const
Iterator::hasNext().
Definition: Tree_LPR.h:101
Tree Child(unsigned n) const
Acceso al &quot;n&quot;-ésimo hijo.
Definition: Tree_L.h:375