Tree_LPR.h

Go to the documentation of this file.

// Tree_LPR.h     (c) 2009 adolfo@di-mare.com

#ifdef English_dox
/// \file   Tree_LPR.h
/// \brief  Left-Process-Right iterator.
/// \author Adolfo Di Mare <adolfo@di-mare.com>
/// This implementation uses a Stack to store the path that remains
/// to traverse for the tree. This path is not exactly the path
/// to the root, as oftentimes it contains references to the rigth
/// siblings for the sub-tree.
/// \date   2009
#endif
#ifdef Spanish_dox
/// \file   Tree_LPR.h
/// \brief  Iterador Izquierda-Proceso-Derecha.
/// Esta implementacíon usa una Pila para almacenar el camino que falta
/// de recorer del árbol. Este camino no es exactamente el camino hasta
/// la raíz, pues muchas veces referencias a los hermanos derechos de
/// un sub-árbol.
/// \author Adolfo Di Mare <adolfo@di-mare.com>
/// \date   2009
#endif

#ifndef Tree_LPR_h
#define Tree_LPR_h

#ifdef English_dox
    /// Doxygen English documentation.
    #define English_dox   "Doxygen English documentation"
   /// \def English_dox  ///< Marks English documentation blocks.
   /// \def Tree_LPR_h   ///< Avoids multiple inclusion.
#endif
#ifdef Spanish_dox
    /// Documentaci¢n en espa¤ol.
    #define Spanish_dox "Documentaci¢n Doxygen en espa¤ol"
   /// \def Spanish_dox  ///< Macro usado para que Doxygen genere documentación.
   /// \def Tree_LPR_h   ///< Evita la inclusión múltiple.
#endif

#include <vector>
#include "Tree_L.h"
#include <iostream>

#ifdef English_dox
/// Left-Process-Right iterator.
#endif
#ifdef Spanish_dox
/// Iterador Izquierda-Proceso-Derecha.
#endif
/**
    \dontinclude test_iterJava.cpp
    \skipline    test::Tree_LPR()
    \until       }}
    \see         test_iterJava::test_Tree_LPR()

    \see         make_a_o(TL::Tree<char> & T)
    \dontinclude test_iterJava.cpp
    \skipline    T = a
    \until       +--k
*/

template <typename E>
class Tree_LPR {
    std::vector< TL::Tree<E> > m_S; ///< std::stack<>.
public:
    /// \c init().
    Tree_LPR( const TL::Tree<E>& T = TL::Tree<E>() )
     :   m_S(32) { set(T); }
     void set( const TL::Tree<E>& T ); ///< \c Iterator::set().

    bool  hasNext() const;    ///< \c Iterator::hasNext().
    const TL::Tree<E> next(); ///< \c Iterator::next().

    void push_left_descendants( const TL::Tree<E>& T );
};

template <typename E>
void Tree_LPR<E>::set( const TL::Tree<E>& T ) {
    m_S.clear(); //  erase whatever was left
    m_S.push_back( T );
    push_left_descendants( T );
}

#ifdef English_dox
    /// Push every \c Child(0) [left] descendant of \c T in the stack.
#endif
#ifdef Spanish_dox
    /// Empuje cada descendiente \c Child(0) [izquierdo] de  \c T en la pila.
#endif
template <typename E>
void Tree_LPR<E>::push_left_descendants( const TL::Tree<E>& T ) {
    TL::Tree<E> D = T.Child(0);
    while ( ! D.Empty() ) {
        m_S.push_back( D );
        D = D.Child(0);
    }
}

/* Indicates if the iterator have a next element */
template <typename E>
bool Tree_LPR<E>::hasNext() const {
    return ( ! m_S.empty() );
}

#if 0
template <typename C>
inline void printC( const C& L ) {
    typename C::const_reverse_iterator it;
    std::cout << '[' << L.size() << "] ";
    for ( it = L.rbegin() ; it != L.rend() ; ++it ) {
        std::cout << **it << ' ';
    }
    std::cout << std::endl;
}
#endif

/* Moves the iterator to it`s next element */
template <typename E>
const TL::Tree<E> Tree_LPR<E>::next() {
//  printC( m_S );
    TL::Tree<E> Res = m_S.back();
    m_S.pop_back();  // stack top will be returned by next()

    TL::Tree<E> Child = Res.Rightmost();
    TL::Tree<E> Stop  = Res.Leftmost();
    TL::Tree<E> Left;
    if( ! Child.Empty() ) {
        for (;;) {
            Left = Child.Left_Sibling();
            if ( Left.Empty() ) {
                if ( ! Child.Same( Res.Child(0) ) ) {
                    m_S.push_back( Child );
                    if ( ! Child.Child(0).Empty() ) {
                        push_left_descendants( Child );
                    }
                }
                break;
            }
            else if ( Stop.Same( Left ) ) {
                m_S.push_back( Child );
                push_left_descendants( Child );
                break;
            }
            else {
                m_S.push_back( Child );
                if ( ! Child.Child(0).Empty() ) {
                    push_left_descendants( Child );
                }
            }
            Child = Left;
        }
    }
    return Res;
}

#endif //  Tree_LPR_h
//  EOF: Tree_PLR.h