1 // -*- C++ -*-
2 /***************************************************************************
3 * blitz/array/cartesian.h Cartesian product of indirection containers
4 *
5 * $Id$
6 *
7 * Copyright (C) 1997-2011 Todd Veldhuizen <tveldhui@acm.org>
8 *
9 * This file is a part of Blitz.
10 *
11 * Blitz is free software: you can redistribute it and/or modify
12 * it under the terms of the GNU Lesser General Public License
13 * as published by the Free Software Foundation, either version 3
14 * of the License, or (at your option) any later version.
15 *
16 * Blitz is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU Lesser General Public License for more details.
20 *
21 * You should have received a copy of the GNU Lesser General Public
22 * License along with Blitz. If not, see <http://www.gnu.org/licenses/>.
23 *
24 * Suggestions: blitz-devel@lists.sourceforge.net
25 * Bugs: blitz-support@lists.sourceforge.net
26 *
27 * For more information, please see the Blitz++ Home Page:
28 * https://sourceforge.net/projects/blitz/
29 *
30 ****************************************************************************/
31 #ifndef BZ_ARRAY_CARTESIAN_H
32 #define BZ_ARRAY_CARTESIAN_H
33
34 namespace blitz {
35
36 /*
37 * CartesianProduct<T_tuple,T_container> is an adaptor which represents
38 * the cartesian product of several containers.
39 */
40
41 // forward declaration of iterator
42 template<typename T_tuple, typename T_container, int N_containers>
43 class CartesianProductIterator;
44
45 struct _cp_end_tag { };
46
47 template<typename T_tuple, typename T_container, int N_containers>
48 class CartesianProduct {
49 public:
50 typedef T_tuple value_type;
51 typedef T_tuple& reference;
52 typedef const T_tuple& const_reference;
53 typedef CartesianProductIterator<T_tuple,T_container,N_containers> iterator;
54
begin()55 iterator begin()
56 { return iterator(*this); }
57
end()58 iterator end()
59 { return iterator(_cp_end_tag()); }
60
CartesianProduct(const T_container & container0,const T_container & container1)61 CartesianProduct(const T_container& container0,
62 const T_container& container1)
63 {
64 BZPRECONDITION(N_containers == 2);
65 containers_[0] = &container0;
66 containers_[1] = &container1;
67 }
68
CartesianProduct(const T_container & container0,const T_container & container1,const T_container & container2)69 CartesianProduct(const T_container& container0,
70 const T_container& container1,
71 const T_container& container2)
72 {
73 BZPRECONDITION(N_containers == 3);
74 containers_[0] = &container0;
75 containers_[1] = &container1;
76 containers_[2] = &container2;
77 }
78
CartesianProduct(const T_container & container0,const T_container & container1,const T_container & container2,const T_container & container3)79 CartesianProduct(const T_container& container0,
80 const T_container& container1,
81 const T_container& container2,
82 const T_container& container3)
83 {
84 BZPRECONDITION(N_containers == 4);
85 containers_[0] = &container0;
86 containers_[1] = &container1;
87 containers_[2] = &container2;
88 containers_[3] = &container3;
89 }
90
CartesianProduct(const T_container & container0,const T_container & container1,const T_container & container2,const T_container & container3,const T_container & container4)91 CartesianProduct(const T_container& container0,
92 const T_container& container1,
93 const T_container& container2,
94 const T_container& container3,
95 const T_container& container4)
96 {
97 BZPRECONDITION(N_containers == 5);
98 containers_[0] = &container0;
99 containers_[1] = &container1;
100 containers_[2] = &container2;
101 containers_[3] = &container3;
102 containers_[4] = &container4;
103 }
104
CartesianProduct(const T_container & container0,const T_container & container1,const T_container & container2,const T_container & container3,const T_container & container4,const T_container & container5)105 CartesianProduct(const T_container& container0,
106 const T_container& container1,
107 const T_container& container2,
108 const T_container& container3,
109 const T_container& container4,
110 const T_container& container5)
111 {
112 BZPRECONDITION(N_containers == 6);
113 containers_[0] = &container0;
114 containers_[1] = &container1;
115 containers_[2] = &container2;
116 containers_[3] = &container3;
117 containers_[4] = &container4;
118 containers_[5] = &container5;
119 }
120
CartesianProduct(const T_container & container0,const T_container & container1,const T_container & container2,const T_container & container3,const T_container & container4,const T_container & container5,const T_container & container6)121 CartesianProduct(const T_container& container0,
122 const T_container& container1,
123 const T_container& container2,
124 const T_container& container3,
125 const T_container& container4,
126 const T_container& container5,
127 const T_container& container6)
128 {
129 BZPRECONDITION(N_containers == 7);
130 containers_[0] = &container0;
131 containers_[1] = &container1;
132 containers_[2] = &container2;
133 containers_[3] = &container3;
134 containers_[4] = &container4;
135 containers_[5] = &container5;
136 containers_[6] = &container6;
137 }
138
CartesianProduct(const T_container & container0,const T_container & container1,const T_container & container2,const T_container & container3,const T_container & container4,const T_container & container5,const T_container & container6,const T_container & container7)139 CartesianProduct(const T_container& container0,
140 const T_container& container1,
141 const T_container& container2,
142 const T_container& container3,
143 const T_container& container4,
144 const T_container& container5,
145 const T_container& container6,
146 const T_container& container7)
147 {
148 BZPRECONDITION(N_containers == 8);
149 containers_[0] = &container0;
150 containers_[1] = &container1;
151 containers_[2] = &container2;
152 containers_[3] = &container3;
153 containers_[4] = &container4;
154 containers_[5] = &container5;
155 containers_[6] = &container6;
156 containers_[7] = &container7;
157 }
158
CartesianProduct(const T_container & container0,const T_container & container1,const T_container & container2,const T_container & container3,const T_container & container4,const T_container & container5,const T_container & container6,const T_container & container7,const T_container & container8)159 CartesianProduct(const T_container& container0,
160 const T_container& container1,
161 const T_container& container2,
162 const T_container& container3,
163 const T_container& container4,
164 const T_container& container5,
165 const T_container& container6,
166 const T_container& container7,
167 const T_container& container8)
168 {
169 BZPRECONDITION(N_containers == 9);
170 containers_[0] = &container0;
171 containers_[1] = &container1;
172 containers_[2] = &container2;
173 containers_[3] = &container3;
174 containers_[4] = &container4;
175 containers_[5] = &container5;
176 containers_[6] = &container6;
177 containers_[7] = &container7;
178 containers_[8] = &container8;
179 }
180
CartesianProduct(const T_container & container0,const T_container & container1,const T_container & container2,const T_container & container3,const T_container & container4,const T_container & container5,const T_container & container6,const T_container & container7,const T_container & container8,const T_container & container9)181 CartesianProduct(const T_container& container0,
182 const T_container& container1,
183 const T_container& container2,
184 const T_container& container3,
185 const T_container& container4,
186 const T_container& container5,
187 const T_container& container6,
188 const T_container& container7,
189 const T_container& container8,
190 const T_container& container9)
191 {
192 BZPRECONDITION(N_containers == 10);
193 containers_[0] = &container0;
194 containers_[1] = &container1;
195 containers_[2] = &container2;
196 containers_[3] = &container3;
197 containers_[4] = &container4;
198 containers_[5] = &container5;
199 containers_[6] = &container6;
200 containers_[7] = &container7;
201 containers_[8] = &container8;
202 containers_[9] = &container9;
203 }
204
CartesianProduct(const T_container & container0,const T_container & container1,const T_container & container2,const T_container & container3,const T_container & container4,const T_container & container5,const T_container & container6,const T_container & container7,const T_container & container8,const T_container & container9,const T_container & container10)205 CartesianProduct(const T_container& container0,
206 const T_container& container1,
207 const T_container& container2,
208 const T_container& container3,
209 const T_container& container4,
210 const T_container& container5,
211 const T_container& container6,
212 const T_container& container7,
213 const T_container& container8,
214 const T_container& container9,
215 const T_container& container10)
216 {
217 BZPRECONDITION(N_containers == 11);
218 containers_[0] = &container0;
219 containers_[1] = &container1;
220 containers_[2] = &container2;
221 containers_[3] = &container3;
222 containers_[4] = &container4;
223 containers_[5] = &container5;
224 containers_[6] = &container6;
225 containers_[7] = &container7;
226 containers_[8] = &container8;
227 containers_[9] = &container9;
228 containers_[10] = &container10;
229 }
230
231 const T_container& operator[](int i)
232 { return *(containers_[i]); }
233
234 void debugDump();
235
236 protected:
237 const T_container* containers_[N_containers];
238 };
239
240 template<typename T_tuple, typename T_container, int N_containers>
debugDump()241 void CartesianProduct<T_tuple,T_container,N_containers>::debugDump()
242 {
243 cout << "Dump of CartesianProduct<..,..," << N_containers << ">" << endl;
244 for (int i=0; i < N_containers; ++i)
245 {
246 cout << "Container " << (i+1) << ": ";
247 _bz_typename T_container::const_iterator iter = containers_[i]->begin(),
248 end = containers_[i]->end();
249 for (; iter != end; ++iter)
250 cout << (*iter) << '\t';
251 }
252 }
253
254 template<typename T_tuple, typename T_container, int N_containers>
255 class CartesianProductIterator {
256 public:
257 typedef _bz_typename T_container::const_iterator citerator;
258 typedef CartesianProductIterator<T_tuple,T_container,N_containers> iterator;
259 typedef CartesianProduct<T_tuple,T_container,N_containers> T_cp;
260
CartesianProductIterator(T_cp & container)261 CartesianProductIterator(T_cp& container)
262 {
263 for (int i=0; i < N_containers; ++i)
264 {
265 firstiters_[i] = container[i].begin();
266 iters_[i] = firstiters_[i];
267 enditers_[i] = container[i].end();
268 tuple_[i] = *iters_[i];
269 }
270
271 endflag_ = false;
272 }
273
274 void operator++();
275
CartesianProductIterator(_cp_end_tag)276 CartesianProductIterator(_cp_end_tag)
277 {
278 endflag_ = true;
279 }
280
281 bool operator==(const iterator& x) const
282 {
283 return (endflag_ == x.endflag_);
284 }
285
286 bool operator!=(const iterator& x) const
287 {
288 return endflag_ != x.endflag_;
289 }
290
291 const T_tuple& operator*() const
292 { return tuple_; }
293
294 protected:
295 citerator iters_[N_containers];
296 citerator firstiters_[N_containers];
297 citerator enditers_[N_containers];
298 T_tuple tuple_;
299 bool endflag_;
300 };
301
302 template<typename T_tuple, typename T_container, int N_containers>
303 void CartesianProductIterator<T_tuple, T_container,
304 N_containers>::operator++()
305 {
306 // Usual stack-style increment
307 const int Nminus1 = N_containers - 1;
308
309 int i = Nminus1;
310
311 // Short-circuit for most common case
312 // (just increment the last iterator)
313
314 if((++iters_[i]) != enditers_[i])
315 {
316 tuple_[i] = *iters_[i];
317 return;
318 }
319
320 // Less common cases
321
322 for (--i; i >= 0; --i)
323 {
324 ++iters_[i];
325 if (iters_[i] != enditers_[i])
326 break;
327 }
328
329 if (i == -1)
330 {
331 endflag_ = true;
332 return;
333 }
334
335 tuple_[i] = *iters_[i];
336
337 for (++i; i < N_containers; ++i)
338 {
339 iters_[i] = firstiters_[i];
340 tuple_[i] = *iters_[i];
341 }
342 }
343
344 }
345
346 #endif // BZ_ARRAY_CARTESIAN_H
347
348