Tree_BF.h

Go to the documentation of this file.

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

#ifdef English_dox
/// \file   Tree_BF.h
/// \brief  Breadth first tree iterator.
/// \author Adolfo Di Mare <adolfo@di-mare.com>
/// \date   2009
/// - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
#endif
#ifdef Spanish_dox
/// \file   Tree_BF.h
/// \brief  Iterador por niveles para el árbol.
/// \author Adolfo Di Mare <adolfo@di-mare.com>
/// \date   2009
/// - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
#endif

#ifndef Tree_BF_h
#define Tree_BF_h

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

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

#ifdef English_dox
/// Breadth first tree iterator.
#endif
#ifdef Spanish_dox
/// Iterador por niveles para el árbol.
#endif
/**
    \dontinclude test_iterJava.cpp
    \skipline    test::Tree_BF()
    \until       }}
    \see         test_iterJava::test_Tree_BF()

    \see         make_a_o(TL::Tree<char> & T)
    \dontinclude test_iterJava.cpp
    \skipline    T = a
    \until       +--k
*/
template <typename E>
class Tree_BF {
    std::list< TL::Tree<E> > m_Q; ///< std::queue<>.
public:
    /// \c init().
    Tree_BF( 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_BF<E>::set( const TL::Tree<E>& T ) {
    m_Q.clear(); // erase whatever was left
    if ( T.Empty() ) {
        return;
    }
    m_Q.push_back( T.Root() );
    typename std::list< TL::Tree<E> >::const_iterator iQ;
    iQ = m_Q.begin();
    while ( iQ != m_Q.end() ) {
        TL::Tree<E> Child = iQ->Leftmost();
        while ( ! Child.Empty() ) {
            m_Q.push_back( Child );
            Child = Child.Right_Sibling();
        }
        ++iQ;
    }
    // Algorithm: push_back() children until no one is left.
    // - This implementation relies on the queue m_Q being able to
    //   push_back() without affecting iteraror iQ.
}

template <typename E>
bool Tree_BF<E>::hasNext() const {
    return ( ! m_Q.empty() );
}

template <typename E>
const TL::Tree<E> Tree_BF<E>::next() {
    TL::Tree<E> first = m_Q.front();
    m_Q.pop_front();
    return first;
}

#endif  // Tree_BF_h
// EOF: Tree_BF.h