// Tree_PLR.h    (c) 2009 walter_wabe@yahoo.com

#ifdef English_dox
/// \file   Tree_PLR.h
/// \brief  Process-Left-Right iterator.
/// \author Walter Wabe Acuña <walter_wabe@yahoo.com>
/// \author Adolfo Di Mare <adolfo@di-mare.com>
/// \date   2009
///
#endif
#ifdef Spanish_dox
/// \file   Tree_PLR.h
/// \brief  Iterador Proceso-Izquierda-Derecha.
/// \author Walter Wabe Acuña <walter_wabe@yahoo.com>
/// \author Adolfo Di Mare <adolfo@di-mare.com>
/// \date   2009
///
#endif

#ifndef Tree_PLR_h
#define Tree_PLR_h

#ifdef English_dox
    /// Doxygen English documentation.
    #define English_dox   "Doxygen English documentation"
   /// \def English_dox  ///< Marks English documentation blocks.
   /// \def Tree_PLR_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_PLR_h   ///< Evita la inclusión múltiple.
#endif

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

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

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

template <typename E>
class Tree_PLR {
    std::list< TL::Tree<E> > m_Q; ///< std::queue<>.
public:
    /// \c init().
    Tree_PLR( const TL::Tree<E>& T = TL::Tree<E>() )
     :   m_Q() { 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().
};

template <typename E>
void Tree_PLR<E>::set( const TL::Tree<E>& T ) {
    m_Q.clear(); // erase whatever was left
    if ( T.Empty() ) {
        return;
    }
    m_Q.push_back( T.Root() );                        // Push the first element of the Tree
    TL::Tree<E> Child = m_Q.begin()->Leftmost();      // Creates a Tree
    while ( ! Child.Empty() ) {                       // While the processed child is not empty..
        m_Q.push_back( Child );                       // Push the child into the list
        if ( ! Child.Leftmost().Empty() ) {           // If the processed child have a child
            Child = Child.Leftmost();                 // Its child becomes the new child
        }
        else {                                        // If the precessed child doesn`t have a child
            if ( ! Child.Right_Sibling().Empty() ) {  // If the processed child have a sibling to the right
                Child = Child.Right_Sibling();        // That sibling becomes the new child
            }
            else {                                    // No sibling to the right
                TL::Tree<E> Temp = Child;             // Use a temporary Tree
                while ( Temp.Father().Right_Sibling().Empty()
                          &&
                        Temp.Father() != T.Root()
                ) {
                    Temp = Temp.Father();             // The temporal Tree becomes it`s own father
                }
                if ( Temp.Father()==T.Root() ) {      // If the temporal Tree equals T.Root()
                    return;                           // Its the end of the process
                }
                else {
                    Child = Temp.Father().Right_Sibling();  // This right Sibling becomes the Child
                }
            }
        }
    }
}

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

/* Moves the iterator to it`s next element */
template <typename E>
const TL::Tree<E> Tree_PLR<E>::next() {
    TL::Tree<E> first = m_Q.front();
    m_Q.pop_front();
    return first;
}

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