subset.h

Go to the documentation of this file.

// subset.h   (c) 2010 adolfo@di-mare.com

#ifdef English_dox
/// \file   subset.h
/// \brief  Generates all subsets form a \c N element number set.
/// \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   subset.h
/// \brief  Generat todos los subconjunto para un conjunto de \c N números.
/// \author Adolfo Di Mare <adolfo@di-mare.com>
/// \date   2009
///
/// - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
#endif

template <int N>
class subset {
private:
    bool * m_mask; // pointer to subset mask
    int    m_cont; // number of subsets that remain to be generated
public:
    subset(); ///< Constructor. <code> DIM() == N </code>
    ~subset() { delete [] m_mask; } ///< Destructor
    bool hasNext() const {
        return (this->m_cont>0);
    }
    const bool* next();
    int DIM() const { return N; }
};

template <int N>
const bool* subset<N>::next() {
    // basado en http://compprog.wordpress.com/2007/10/10/generating-subsets/
    this->m_cont--;
    int i,n = N;
    for ( i=0; (i<n) && (m_mask[i]); ++i ) {
        this->m_mask[i] = false;
    }

    if ( i<n ) {
        this->m_mask[i] = true;
    }

    return this->m_mask;
}

/// Constructor. Set has \n elements.
template <int N>
subset<N>::subset() {
    m_mask = new bool[N];

    int mult = 1;
    for ( int i=0; i<N; ++i ) {
        mult *= 2; // 2^n
        m_mask[i] = true;
    }
    m_cont = mult;
}

/*************\
|*  Doxygen  *| ==> http://www.doxygen.org
\*************/

#ifdef English_dox
    /// Doxygen English documentation.
    #define English_dox   "Doxygen English documentation"
   /// \def English_dox  ///< Marks English documentation blocks.
#endif
#ifdef Spanish_dox
    /// Documentación en español.
    #define Spanish_dox "Documentación Doxygen en español"
   /// \def Spanish_dox  ///< Marca los bloques de documentación en español.
#endif

#ifdef English_dox
/**
    \brief Marks which elements are in the current set.
    \var   subset::m_mask;

    \brief Goes from \c 2^n down to \c 0.
    \var   subset::m_cont;
*/
#endif
#ifdef Spanish_dox
/**
    \brief Marca cuáles elementos están en el conjunto actual.
    \var   subset::m_mask;

    \brief Va desde \c 2^n hasta \c 0.
    \var   subset::m_cont;
*/
#endif

#ifdef English_dox
/**
    \fn    subset::hasNext() const;
    \brief Returns \c true while there are more subsets to generate.

    \fn    subset::next();
    \brief Generate next subset.

    \fn    subset::DIM() const;
    \brief Returns the size of the complete set.
*/
#endif
#ifdef Spanish_dox
/**
    \fn    subset::hasNext() const;
    \brief Returns \c true while there are more subsets to generate.

    \fn    subset::next();
    \brief Generate next subset.

    \fn    subset::DIM() const;
    \brief Returns the size of the complete set.
*/
#endif


#ifdef SUBSET_EXAMPLE
#include <iostream>

/* class subset: program example.
    {  }
    { 0 }
    { 1 }
    { 0 , 1 }
    { 2 }
    { 0 , 2 }
    { 1 , 2 }
    { 0 , 1 , 2 }
*/
int main() {{
    subset<3> iter; // iter.DIM() == 3
    while ( iter.hasNext() ) {
        const bool *SS = iter.next();
        bool didOne = false;
        std::cout << "{ ";
        for ( int i=0; i<iter.DIM(); ++i ) {
            if ( SS[i] ) {
                if ( didOne ) {
                    std::cout << " , ";
                }
                std::cout << i;
                didOne = true;
            }
        }
        std::cout << " }" << std::endl;
    }
}}

#endif

#ifdef English_dox
/** \class subset;
    \brief Iterator/generator that returns all subsets for an \c N element set.
 */
#endif
#ifdef Spanish_dox
/** \class subset;
    \brief Iterador/generador que retorna todos los subconjuntos de un conjunto de \c N elementos.
 */
#endif
/** \class subset;
    \dontinclude subset.h
    \skipline    class subset: program example.
    \until       }}

    \see  http://compprog.wordpress.com/2007/10/10/generating-subsets/
*/

// EOF: subset.h