Java iterators for C++:
 All Classes Namespaces Files Functions Variables Typedefs Friends Macros Pages
subset.h
Go to the documentation of this file.
1 // subset.h (c) 2010 adolfo@di-mare.com
2 
3 #ifdef English_dox
4 /// \file subset.h
5 /// \brief Generates all subsets form a \c N element number set.
6 /// \author Adolfo Di Mare <adolfo@di-mare.com>
7 /// \date 2009
8 ///
9 /// - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
10 #endif
11 #ifdef Spanish_dox
12 /// \file subset.h
13 /// \brief Generat todos los subconjunto para un conjunto de \c N números.
14 /// \author Adolfo Di Mare <adolfo@di-mare.com>
15 /// \date 2009
16 ///
17 /// - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
18 #endif
19 
20 template <int N>
21 class subset {
22 private:
23  bool * m_mask; // pointer to subset mask
24  int m_cont; // number of subsets that remain to be generated
25 public:
26  subset(); ///< Constructor. <code> DIM() == N </code>
27  ~subset() { delete [] m_mask; } ///< Destructor
28  bool hasNext() const {
29  return (this->m_cont>0);
30  }
31  const bool* next();
32  int DIM() const { return N; }
33 };
34 
35 template <int N>
36 const bool* subset<N>::next() {
37  // basado en http://compprog.wordpress.com/2007/10/10/generating-subsets/
38  this->m_cont--;
39  int i,n = N;
40  for ( i=0; (i<n) && (m_mask[i]); ++i ) {
41  this->m_mask[i] = false;
42  }
43 
44  if ( i<n ) {
45  this->m_mask[i] = true;
46  }
47 
48  return this->m_mask;
49 }
50 
51 /// Constructor. Set has \n elements.
52 template <int N>
54  m_mask = new bool[N];
55 
56  int mult = 1;
57  for ( int i=0; i<N; ++i ) {
58  mult *= 2; // 2^n
59  m_mask[i] = true;
60  }
61  m_cont = mult;
62 }
63 
64 /*************\
65 |* Doxygen *| ==> http://www.doxygen.org
66 \*************/
67 
68 #ifdef English_dox
69  /// Doxygen English documentation.
70  #define English_dox "Doxygen English documentation"
71  /// \def English_dox ///< Marks English documentation blocks.
72 #endif
73 #ifdef Spanish_dox
74  /// Documentación en español.
75  #define Spanish_dox "Documentación Doxygen en español"
76  /// \def Spanish_dox ///< Marca los bloques de documentación en español.
77 #endif
78 
79 #ifdef English_dox
80 /**
81  \brief Marks which elements are in the current set.
82  \var subset::m_mask;
83 
84  \brief Goes from \c 2^n down to \c 0.
85  \var subset::m_cont;
86 */
87 #endif
88 #ifdef Spanish_dox
89 /**
90  \brief Marca cuáles elementos están en el conjunto actual.
91  \var subset::m_mask;
92 
93  \brief Va desde \c 2^n hasta \c 0.
94  \var subset::m_cont;
95 */
96 #endif
97 
98 #ifdef English_dox
99 /**
100  \fn subset::hasNext() const;
101  \brief Returns \c true while there are more subsets to generate.
102 
103  \fn subset::next();
104  \brief Generate next subset.
105 
106  \fn subset::DIM() const;
107  \brief Returns the size of the complete set.
108 */
109 #endif
110 #ifdef Spanish_dox
111 /**
112  \fn subset::hasNext() const;
113  \brief Returns \c true while there are more subsets to generate.
114 
115  \fn subset::next();
116  \brief Generate next subset.
117 
118  \fn subset::DIM() const;
119  \brief Returns the size of the complete set.
120 */
121 #endif
122 
123 
124 #ifdef SUBSET_EXAMPLE
125 #include <iostream>
126 
127 /* class subset: program example.
128  { }
129  { 0 }
130  { 1 }
131  { 0 , 1 }
132  { 2 }
133  { 0 , 2 }
134  { 1 , 2 }
135  { 0 , 1 , 2 }
136 */
137 int main() {{
138  subset<3> iter; // iter.DIM() == 3
139  while ( iter.hasNext() ) {
140  const bool *SS = iter.next();
141  bool didOne = false;
142  std::cout << "{ ";
143  for ( int i=0; i<iter.DIM(); ++i ) {
144  if ( SS[i] ) {
145  if ( didOne ) {
146  std::cout << " , ";
147  }
148  std::cout << i;
149  didOne = true;
150  }
151  }
152  std::cout << " }" << std::endl;
153  }
154 }}
155 
156 #endif
157 
158 #ifdef English_dox
159 /** \class subset;
160  \brief Iterator/generator that returns all subsets for an \c N element set.
161  */
162 #endif
163 #ifdef Spanish_dox
164 /** \class subset;
165  \brief Iterador/generador que retorna todos los subconjuntos de un conjunto de \c N elementos.
166  */
167 #endif
168 /** \class subset;
169  \dontinclude subset.h
170  \skipline class subset: program example.
171  \until }}
172 
173  \see http://compprog.wordpress.com/2007/10/10/generating-subsets/
174 */
175 
176 // EOF: subset.h
int DIM() const
Returns the size of the complete set.
Definition: subset.h:32
int main()
Test ==&gt; main() ==&gt; iterJava().
Iterator/generator that returns all subsets for an N element set.
Definition: subset.h:21
const bool * next()
Generate next subset.
Definition: subset.h:36
bool * m_mask
Marks which elements are in the current set.
Definition: subset.h:23
bool hasNext() const
Returns true while there are more subsets to generate.
Definition: subset.h:28
int m_cont
Definition: subset.h:24
subset()
Constructor. DIM() == N
Definition: subset.h:53
~subset()
Destructor.
Definition: subset.h:27