[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

type_lists.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 2011-2012 by Markus Nullmeier and Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35 
36 #ifndef VIGRA_TYPE_LISTS_HXX
37 #define VIGRA_TYPE_LISTS_HXX
38 
39 #include <iostream>
40 #include <typeinfo>
41 #include <utility>
42 #include <algorithm>
43 #include "metaprogramming.hxx"
44 #include "bit_array.hxx"
45 #include "error.hxx"
46 
47 namespace vigra {
48 
49 // mask cl.exe shortcomings [begin]
50 #if defined(_MSC_VER)
51 #pragma warning( push )
52 #pragma warning( disable : 4503 )
53 #endif
54 
55 namespace type_lists {
56 
57  struct nil; // end-of-list marker.
58  template <class T>
59  struct nil_t;
60 
61  // type lists of size >= 1.
62 
63  template <class A, class B = nil> struct cons
64  {
65  typedef A first;
66  typedef B rest;
67  };
68 
69  template <class X, class A, class B> struct if_nil
70  {
71  typedef B type;
72  };
73  template <class A, class B> struct if_nil <nil, A, B>
74  {
75  typedef A type;
76  };
77 
78  // truncate type list L (using class NIL as ending marker)
79  // at the first occurence of type X
80  template <class X, class L, class NIL = nil> struct truncate
81  {
82  typedef cons<typename L::first,
83  typename truncate<X, typename L::rest, NIL>::type> type;
84  };
85  template <class L, class NIL> struct truncate<typename L::first, L, NIL>
86  {
87  typedef nil type; // do the actual truncation
88  };
89  template <class X, class NIL> struct truncate<X, NIL, NIL>
90  {
91  typedef nil type;
92  };
93 
94  template <class NIL, class A = NIL, class B = NIL, class C = NIL,
95  class D = NIL, class E = NIL, class F = NIL,
96  class G = NIL, class H = NIL, class I = NIL,
97  class J = NIL, class K = NIL, class L = NIL,
98  class M = NIL, class N = NIL, class O = NIL,
99  class P = NIL, class Q = NIL, class R = NIL,
100  class S = NIL, class T = NIL, class U = NIL,
101  class V = NIL, class W = NIL, class X = NIL,
102  class Y = NIL, class Z = NIL>
103  struct make_list_nil {
104  typedef typename truncate<NIL, cons<A, cons<B, cons<C, cons<D, cons<E,
105  cons<F, cons<G, cons<H, cons<I, cons<J,
106  cons<K, cons<L, cons<M, cons<N, cons<O,
107  cons<P, cons<Q, cons<R, cons<S, cons<T,
108  cons<U, cons<V, cons<W, cons<X, cons<Y,
109  cons<Z, NIL> > > > > > > > > > > > > > >
110  > > > > > > > > > > >, NIL>::type type;
111  };
112 
113  template <class A = nil, class B = nil, class C = nil, class D = nil,
114  class E = nil, class F = nil, class G = nil, class H = nil,
115  class I = nil, class J = nil, class K = nil, class L = nil,
116  class M = nil, class N = nil, class O = nil, class P = nil,
117  class Q = nil, class R = nil, class S = nil, class T = nil,
118  class U = nil, class V = nil, class W = nil, class X = nil,
119  class Y = nil, class Z = nil>
120 
121  struct make_list {
122  typedef typename make_list_nil<nil, A, B, C, D, E, F, G, H, I,
123  J, K, L, M, N, O, P, Q, R,
124  S, T, U, V, W, X, Y, Z
125  >::type type;
126  };
127 
128  template <class T_, template<class> class A = nil_t,
129  template<class> class B = nil_t,
130  template<class> class C = nil_t,
131  template<class> class D = nil_t,
132  template<class> class E = nil_t,
133  template<class> class F = nil_t,
134  template<class> class G = nil_t,
135  template<class> class H = nil_t,
136  template<class> class I = nil_t,
137  template<class> class J = nil_t,
138  template<class> class K = nil_t,
139  template<class> class L = nil_t,
140  template<class> class M = nil_t,
141  template<class> class N = nil_t,
142  template<class> class O = nil_t,
143  template<class> class P = nil_t,
144  template<class> class Q = nil_t,
145  template<class> class R = nil_t,
146  template<class> class S = nil_t,
147  template<class> class T = nil_t,
148  template<class> class U = nil_t,
149  template<class> class V = nil_t,
150  template<class> class W = nil_t,
151  template<class> class X = nil_t,
152  template<class> class Y = nil_t,
153  template<class> class Z = nil_t>
154  struct make_list_template {
155  typedef typename make_list_nil<nil_t<T_>,
156  A<T_>, B<T_>, C<T_>, D<T_>, E<T_>,
157  F<T_>, G<T_>, H<T_>, I<T_>, J<T_>,
158  K<T_>, L<T_>, M<T_>, N<T_>, O<T_>,
159  P<T_>, Q<T_>, R<T_>, S<T_>, T<T_>,
160  U<T_>, V<T_>, W<T_>, X<T_>, Y<T_>,
161  Z<T_> >::type type;
162  };
163 
164  // a means to partially compensate for the lack of templated typedefs.
165  template <template<class, class> class BASE, class T_,
166  template<class> class A = nil_t,
167  template<class> class B = nil_t,
168  template<class> class C = nil_t,
169  template<class> class D = nil_t,
170  template<class> class E = nil_t,
171  template<class> class F = nil_t,
172  template<class> class G = nil_t,
173  template<class> class H = nil_t,
174  template<class> class I = nil_t,
175  template<class> class J = nil_t,
176  template<class> class K = nil_t,
177  template<class> class L = nil_t,
178  template<class> class M = nil_t,
179  template<class> class N = nil_t,
180  template<class> class O = nil_t,
181  template<class> class P = nil_t,
182  template<class> class Q = nil_t,
183  template<class> class R = nil_t,
184  template<class> class S = nil_t,
185  template<class> class T = nil_t,
186  template<class> class U = nil_t,
187  template<class> class V = nil_t,
188  template<class> class W = nil_t,
189  template<class> class X = nil_t,
190  template<class> class Y = nil_t,
191  template<class> class Z = nil_t>
192  struct use_template_list
193  : public BASE<T_, typename make_list_template<T_, A, B, C, D, E, F, G,
194  H, I, J, K, L, M, N,
195  O, P, Q, R, S, T, U,
196  V, W, X, Y, Z>::type>
197  {};
198 
199  // use first and rest only when possible:
200  template <class T>
201  struct has_first_rest : public sfinae_test<T, has_first_rest>
202  {
203  template <class U>
204  has_first_rest(U*, typename U::first* = 0, typename U::rest* = 0);
205  };
206  template <bool P, class A>
207  struct cond_cons_rest;
208  template <class A>
209  struct cond_cons_rest<false, A>
210  {
211  typedef void* type;
212  };
213  template <class A>
214  struct cond_cons_rest<true, A>
215  {
216  typedef typename A::rest type;
217  };
218  // test if a type is a list in the above sense.
219  template <class A> struct is_list
220  {
221  static const bool value = is_list<typename
222  cond_cons_rest<has_first_rest<A>::value, A>::type>::value;
223  };
224  template <> struct is_list<nil>
225  {
226  static const bool value = true;
227  };
228  template <> struct is_list<void*>
229  {
230  static const bool value = false;
231  };
232 
233  template <class A> struct list_guard
234  {
235  typedef typename IfBool<is_list<A>::value, A, nil>::type type;
236  };
237 
238  template <class A> struct size
239  {
240  static const unsigned of = size<typename A::rest>::of + 1;
241  };
242  template <> struct size<nil>
243  {
244  static const unsigned of = 0;
245  };
246 
247  template <class X, class L> struct append
248  {
249  typedef cons<typename L::first,
250  typename append<X, typename L::rest>::type> type;
251  };
252  template <class X> struct append<X, nil>
253  {
254  typedef cons<X, nil> type;
255  };
256  template <> struct append<nil, nil>
257  {
258  typedef nil type;
259  };
260 
261  template <class L, class R = nil> struct reverse
262  {
263  typedef typename reverse<typename L::rest,
264  cons<typename L::first, R> >::type type;
265  };
266  template <class R> struct reverse<nil, R>
267  {
268  typedef R type;
269  };
270 
271  template <template<class> class P, class Q, class L>
272  struct max_value
273  {
274  static const bool is_nil = false;
275  static const Q first_value = P<typename L::first>::value;
276  typedef max_value<P, Q, typename L::rest> rest_type;
277  static const Q rest_value = rest_type::value;
278  static const bool gt = first_value > rest_value || rest_type::is_nil;
279  static const Q value = gt * first_value + !gt * rest_value;
280  };
281  template <template<class> class P, class Q>
282  struct max_value<P, Q, nil>
283  {
284  static const Q value = 0;
285  static const bool is_nil = true;
286  };
287 
288  // remove the all occurences of type X in type list L
289  template <class X, class L> struct remove // recursion
290  {
291  typedef cons<typename L::first,
292  typename remove<X, typename L::rest>::type> type;
293  };
294  template <class L> struct remove<typename L::first, L> // actual removal
295  {
296  typedef typename remove<typename L::first, typename L::rest>::type type;
297  };
298  template <class X> struct remove<X, nil> // list end
299  {
300  typedef nil type;
301  };
302 
303  // remove the all occurences of type list L where predicate P equals value
304  template <template<class> class P, class L, bool value = true>
305  struct remove_if
306  {
307  typedef typename
308  IfBool<
309  value == P<typename L::first>::value, typename
310  remove_if<P, typename L::rest, value>::type,
311  cons<typename
312  L::first, typename
313  remove_if<P, typename L::rest, value>::type
314  >
315  >::type type;
316  };
317  template <template<class> class P, bool value>
318  struct remove_if<P, nil, value>
319  {
320  typedef nil type;
321  };
322 
323  template <template<class> class P, class L>
324  struct remove_if_not
325  {
326  typedef typename remove_if<P, L, false>::type type;
327  };
328 
329  template <class X, class L> struct contains
330  {
331  static const bool value = contains<X, typename L::rest>::value;
332  };
333  template <class L> struct contains<typename L::first, L>
334  {
335  static const bool value = true;
336  };
337  template <class X> struct contains<X, nil>
338  {
339  static const bool value = false;
340  };
341 
342  // simple, unstable merge
343  template <class X, class L> struct merge
344  {
345  typedef typename L::first first;
346  typedef typename
347  merge<
348  typename IfBool<contains<first, X>::value,
349  X,
350  cons<first, X>
351  >::type,
352  typename L::rest
353  >::type type;
354  };
355  template <class X> struct merge<X, nil>
356  {
357  typedef X type;
358  };
359 
360  // simple, unstable unique
361  template <class L> struct unique
362  {
363  typedef typename merge<nil, L>::type type;
364  };
365 
366  template <class T_, template<class> class A = nil_t,
367  template<class> class B = nil_t,
368  template<class> class C = nil_t,
369  template<class> class D = nil_t,
370  template<class> class E = nil_t,
371  template<class> class F = nil_t,
372  template<class> class G = nil_t,
373  template<class> class H = nil_t,
374  template<class> class I = nil_t,
375  template<class> class J = nil_t,
376  template<class> class K = nil_t,
377  template<class> class L = nil_t,
378  template<class> class M = nil_t,
379  template<class> class N = nil_t,
380  template<class> class O = nil_t,
381  template<class> class P = nil_t,
382  template<class> class Q = nil_t,
383  template<class> class R = nil_t,
384  template<class> class S = nil_t,
385  template<class> class T = nil_t,
386  template<class> class U = nil_t,
387  template<class> class V = nil_t,
388  template<class> class W = nil_t,
389  template<class> class X = nil_t,
390  template<class> class Y = nil_t,
391  template<class> class Z = nil_t>
392  struct implies_template
393  {
394  typedef typename make_list_template<T_, A, B, C, D, E, F, G, H, I, J, K,
395  L, M, N, O, P, Q, R, S, T, U, V,
396  W, X, Y, Z>::type implies_types;
397  };
398 
399  template <class T_, template<class> class A = nil_t,
400  template<class> class B = nil_t,
401  template<class> class C = nil_t,
402  template<class> class D = nil_t,
403  template<class> class E = nil_t,
404  template<class> class F = nil_t,
405  template<class> class G = nil_t,
406  template<class> class H = nil_t,
407  template<class> class I = nil_t,
408  template<class> class J = nil_t,
409  template<class> class K = nil_t,
410  template<class> class L = nil_t,
411  template<class> class M = nil_t,
412  template<class> class N = nil_t,
413  template<class> class O = nil_t,
414  template<class> class P = nil_t,
415  template<class> class Q = nil_t,
416  template<class> class R = nil_t,
417  template<class> class S = nil_t,
418  template<class> class T = nil_t,
419  template<class> class U = nil_t,
420  template<class> class V = nil_t,
421  template<class> class W = nil_t,
422  template<class> class X = nil_t,
423  template<class> class Y = nil_t,
424  template<class> class Z = nil_t>
425  struct follows_template
426  {
427  typedef typename make_list_template<T_, A, B, C, D, E, F, G, H, I, J, K,
428  L, M, N, O, P, Q, R, S, T, U, V,
429  W, X, Y, Z>::type follows_types;
430  };
431 
432  template <class T_, template<class> class A = nil_t,
433  template<class> class B = nil_t,
434  template<class> class C = nil_t,
435  template<class> class D = nil_t,
436  template<class> class E = nil_t,
437  template<class> class F = nil_t,
438  template<class> class G = nil_t,
439  template<class> class H = nil_t,
440  template<class> class I = nil_t,
441  template<class> class J = nil_t,
442  template<class> class K = nil_t,
443  template<class> class L = nil_t,
444  template<class> class M = nil_t,
445  template<class> class N = nil_t,
446  template<class> class O = nil_t,
447  template<class> class P = nil_t,
448  template<class> class Q = nil_t,
449  template<class> class R = nil_t,
450  template<class> class S = nil_t,
451  template<class> class T = nil_t,
452  template<class> class U = nil_t,
453  template<class> class V = nil_t,
454  template<class> class W = nil_t,
455  template<class> class X = nil_t,
456  template<class> class Y = nil_t,
457  template<class> class Z = nil_t>
458  struct depends_on_template
459  {
460  typedef typename make_list_template<T_, A, B, C, D, E, F, G, H, I, J, K,
461  L, M, N, O, P, Q, R, S, T, U, V,
462  W, X, Y, Z>::type depends_on;
463  };
464 
465  template <class T_u, template<class> class A = nil_t,
466  template<class> class B = nil_t,
467  template<class> class C = nil_t,
468  template<class> class D = nil_t,
469  template<class> class E = nil_t,
470  template<class> class F = nil_t,
471  template<class> class G = nil_t,
472  template<class> class H = nil_t,
473  template<class> class I = nil_t,
474  template<class> class J = nil_t,
475  template<class> class K = nil_t,
476  template<class> class L = nil_t,
477  template<class> class M = nil_t,
478  template<class> class N = nil_t,
479  template<class> class O = nil_t,
480  template<class> class P = nil_t,
481  template<class> class Q = nil_t,
482  template<class> class R = nil_t,
483  template<class> class S = nil_t,
484  template<class> class T = nil_t,
485  template<class> class U = nil_t,
486  template<class> class V = nil_t,
487  template<class> class W = nil_t,
488  template<class> class X = nil_t,
489  template<class> class Y = nil_t,
490  template<class> class Z = nil_t>
491  struct uses_template
492  : public implies_template<T_u, A, B, C, D, E, F, G, H, I, J, K, L, M,
493  N, O, P, Q, R, S, T, U, V, W, X, Y, Z>,
494  public depends_on_template<T_u, A, B, C, D, E, F, G, H, I, J, K, L, M,
495  N, O, P, Q, R, S, T, U, V, W, X, Y, Z>
496  {
497  template <template<class> class A_ = nil_t,
498  template<class> class B_ = nil_t,
499  template<class> class C_ = nil_t,
500  template<class> class D_ = nil_t,
501  template<class> class E_ = nil_t,
502  template<class> class F_ = nil_t,
503  template<class> class G_ = nil_t,
504  template<class> class H_ = nil_t,
505  template<class> class I_ = nil_t,
506  template<class> class J_ = nil_t,
507  template<class> class K_ = nil_t,
508  template<class> class L_ = nil_t,
509  template<class> class M_ = nil_t,
510  template<class> class N_ = nil_t,
511  template<class> class O_ = nil_t,
512  template<class> class P_ = nil_t,
513  template<class> class Q_ = nil_t,
514  template<class> class R_ = nil_t,
515  template<class> class S_ = nil_t,
516  template<class> class T_ = nil_t,
517  template<class> class U_ = nil_t,
518  template<class> class V_ = nil_t,
519  template<class> class W_ = nil_t,
520  template<class> class X_ = nil_t,
521  template<class> class Y_ = nil_t,
522  template<class> class Z_ = nil_t>
523  struct follows
524  : public uses_template
525  , public follows_template<T_u, A_, B_, C_, D_, E_, F_, G_, H_, I_,
526  J_, K_, L_, M_, N_, O_, P_, Q_, R_,
527  S_, T_, U_, V_, W_, X_, Y_, Z_> {};
528 
529  template <template<class> class A_ = nil_t,
530  template<class> class B_ = nil_t,
531  template<class> class C_ = nil_t,
532  template<class> class D_ = nil_t,
533  template<class> class E_ = nil_t,
534  template<class> class F_ = nil_t,
535  template<class> class G_ = nil_t,
536  template<class> class H_ = nil_t,
537  template<class> class I_ = nil_t,
538  template<class> class J_ = nil_t,
539  template<class> class K_ = nil_t,
540  template<class> class L_ = nil_t,
541  template<class> class M_ = nil_t,
542  template<class> class N_ = nil_t,
543  template<class> class O_ = nil_t,
544  template<class> class P_ = nil_t,
545  template<class> class Q_ = nil_t,
546  template<class> class R_ = nil_t,
547  template<class> class S_ = nil_t,
548  template<class> class T_ = nil_t,
549  template<class> class U_ = nil_t,
550  template<class> class V_ = nil_t,
551  template<class> class W_ = nil_t,
552  template<class> class X_ = nil_t,
553  template<class> class Y_ = nil_t,
554  template<class> class Z_ = nil_t>
555  struct implies
556  : public uses_template
557  {
558  typedef typename
559  merge<typename
560  uses_template::implies_types, typename
561  implies_template<T_u, A_, B_, C_, D_, E_, F_, G_, H_, I_,
562  J_, K_, L_, M_, N_, O_, P_, Q_, R_,
563  S_, T_, U_, V_, W_, X_, Y_, Z_>
564  ::implies_types
565  >::type
566  implies_types;
567  };
568  };
569 
570  // for_all() helper class.
571  template <template<class> class EXEC, class L> struct for_exec
572  {
573  template <class TX>
574  static void all(TX & tx)
575  {
576  EXEC<typename L::first>::exec(tx);
577  for_exec<EXEC, typename L::rest>::all(tx);
578  }
579  };
580  template <template<class> class EXEC> struct for_exec<EXEC, nil>
581  {
582  template <class TX> static void all(TX &) {}
583  };
584  // for_all on type lists.
585  // for all types T in the list L,
586  // calls the static member function EXEC<T>::exec(TX & tx).
587  template <class L, template<class> class EXEC, class TX>
588  inline void for_all(TX & tx)
589  {
590  for_exec<EXEC, L>::all(tx);
591  }
592 
593  template <class T>
594  struct has_depends_on : public sfinae_test<T, has_depends_on>
595  {
596  template <class U> has_depends_on(U*, typename U::depends_on* = 0);
597  };
598  template <class T>
599  struct has_implies : public sfinae_test<T, has_implies>
600  {
601  template <class U> has_implies(U*, typename U::implies_types* = 0);
602  };
603  template <class T>
604  struct has_follows : public sfinae_test<T, has_follows>
605  {
606  template <class U> has_follows(U*, typename U::follows_types* = 0);
607  };
608 
609  // use empty list in case of lacking / faulty depends_on or implies_types:
610  template <bool P, class T>
611  struct depends_on_guard;
612  template <class T>
613  struct depends_on_guard<false, T>
614  {
615  typedef nil type;
616  };
617  template <class T>
618  struct depends_on_guard<true, T>
619  {
620  typedef typename list_guard<typename T::depends_on>::type type;
621  };
622  template <class T>
623  struct get_pure_depends_on
624  {
625  typedef typename depends_on_guard<has_depends_on<T>::value, T>::type
626  type;
627  };
628 
629  template <bool P, class T>
630  struct follows_guard;
631  template <class T>
632  struct follows_guard<false, T>
633  {
634  typedef nil type;
635  };
636  template <class T>
637  struct follows_guard<true, T>
638  {
639  typedef typename list_guard<typename T::follows_types>::type type;
640  };
641  template <class T>
642  struct get_follows
643  {
644  typedef typename follows_guard<has_follows<T>::value, T>::type
645  type;
646  };
647 
648  template <class T>
649  struct get_depends_on
650  {
651  typedef typename merge<typename get_pure_depends_on<T>::type,
652  typename get_follows<T>::type >::type type;
653  };
654 
655  template <bool P, class T>
656  struct implies_guard;
657  template <class T>
658  struct implies_guard<false, T>
659  {
660  typedef nil type;
661  };
662  template <class T>
663  struct implies_guard<true, T>
664  {
665  typedef typename list_guard<typename T::implies_types>::type type;
666  };
667  template <class T>
668  struct get_implies
669  {
670  typedef typename implies_guard<has_implies<T>::value, T>::type
671  type;
672  };
673 
674  template <class L> struct implies_expand
675  {
676  typedef typename L::first first;
677  typedef typename L::rest rest;
678  typedef
679  cons<first, typename
680  merge<typename
681  implies_expand<rest>::type, typename
682  implies_expand<typename
683  get_implies<first>
684  ::type>::type>::type> type;
685  };
686  template <> struct implies_expand<nil>
687  {
688  typedef nil type;
689  };
690 
691  // for_all with type list == T::depends_on (if any.)
692  template <class T, template<class> class EXEC, class TX>
693  inline void for_all_used(TX & tx)
694  {
695  for_all<typename get_pure_depends_on<T>::type, EXEC>(tx);
696  }
697 
698  template <class X, class T>
699  struct contains_dependent
700  {
701  static const bool value
702  = contains<X, typename get_depends_on<T>::type>::value;
703  };
704 
705  template <class X, class XL> struct is_independent_on
706  {
707  static const bool value
708  = ChooseBool<contains_dependent<X, typename XL::first>,
709  VigraFalseType,
710  is_independent_on<X, typename XL::rest>
711  >::value;
712  };
713  template <class X> struct is_independent_on<X, nil>
714  {
715  static const bool value = true;
716  };
717 
718  template <class XL, class YL = XL> struct get_independent
719  {
720  typedef typename YL::first YL_first;
721  typedef typename
722  IfBool<is_independent_on<YL_first, XL>::value,
723  YL_first,
724  typename get_independent<XL, typename YL::rest>::type
725  >::type type;
726  };
727  template <class XL> struct get_independent<XL, nil>
728  {
729  typedef nil type;
730  };
731 
732  // the output is a list of types in reverse order, starting with the
733  // most depedent types.
734  template <class L> struct topo_sort
735  {
736  typedef typename get_independent<L>::type indep;
737  typedef typename
738  if_nil<indep,
739  nil,
740  cons<indep,
741  typename topo_sort<typename remove<indep, L>::type>::type
742  >
743  >::type type;
744  };
745  template <> struct topo_sort<nil>
746  {
747  typedef nil type;
748  };
749 
750  // Topological sort -- the input is a list of types (see below),
751  // each of which may, optionally, have an embedded typedef 'depends_on'
752  // set to a singly-linked-list of types declared
753  // using vigra::type_lists::cons, such as
754  // cons<type_a, cons<type_b, cons<type_c> > >
755  // (a one-parameter cons will add the trailing nil automatically),
756  // -- the output is a list of types with increasing dependence,
757  // starting with the indepedent types.
758  // Types that should be said lists -- but are in fact not -- are silently
759  // replaced by empty lists.
760 
761  template <class L> struct topological_sort
762  {
763  typedef typename
764  reverse<typename
765  topo_sort<typename
766  unique<typename
767  list_guard<L>
768  ::type>::type>::type>::type type;
769  };
770 
771  template <class L> struct topological_sort_expanded
772  {
773  typedef typename
774  topological_sort<typename
775  implies_expand<L>
776  ::type>::type type;
777  };
778 
779  template <class V, unsigned pos = 0>
780  class cond_val : public V
781  {
782  typedef V load_type;
783  protected:
784  bool is_set_;
785  public:
786  cond_val() : is_set_(false) {}
787  const V & val() const { return *this; }
788  V & val() { return *this; }
789 
790  template <class TUPLE>
791  bool is_set(const TUPLE &) const
792  {
793  return is_set_;
794  }
795 
796  template <class TUPLE>
797  void set(TUPLE &)
798  {
799  is_set_ = true;
800  }
801  template <class TUPLE>
802  void set(const V & v, TUPLE & tuple)
803  {
804  set(tuple);
805  val() = v;
806  }
807  friend std::ostream & operator<<(std::ostream & os, const cond_val & x)
808  {
809  if (x.is_set_)
810  os << x.val(x);
811  else
812  os << "<nil>";
813  return os;
814  }
815  };
816 
817  template <class V, unsigned pos>
818  class bit_cond_val : public V
819  {
820  typedef V load_type;
821  public:
822  const V & val() const { return *this; }
823  V & val() { return *this; }
824 
825  template <class TUPLE>
826  bool is_set(const TUPLE & tuple) const
827  {
828  return tuple.template is_bit_set<pos>();
829  }
830 
831  template <class TUPLE>
832  void set(TUPLE & tuple)
833  {
834  tuple.template set_bit<pos>();
835  }
836  template <class TUPLE>
837  void set(const V & v, TUPLE & tuple)
838  {
839  set(tuple);
840  val() = v;
841  }
842  };
843 
844  // no templated virtual functions in C++ ...
845  //
846  // simple_member_dispatch: sample base and polymorphic adapter classes
847  // for cond_virtual_tuple / etc.
848  // -- the names 'member_base_type' and 'load_type' of the templates,
849  // and also their parameter types, are fixed.
850  // -- note that the member_base_type template of any "member_dispatch"
851  // class can not directly serve as a base class for any member type that
852  // is used within the tuple, since the signatures of most of the
853  // virtual functions that are usually needed necessarily require the
854  // type of the tuple itself.
855  //
856  struct simple_member_dispatch
857  {
858  template <class ACX, class T>
859  struct member_base_type
860  {
861  virtual void operator()() {}
862  virtual void operator()(ACX &, const T &) {}
863  virtual void operator()(const ACX &, const ACX &, const ACX &) {}
864  virtual void call(ACX &, const T &, unsigned) {}
865  virtual ~member_base_type() {}
866  };
867  template <class ACX, class T, class V>
868  struct load_type : public member_base_type<ACX, T>, public V
869  {
870  load_type() {}
871  load_type(const V & v) : V(v) {}
872  void operator()()
873  {
874  V::operator()();
875  }
876  void operator()(ACX & x, const T & v)
877  {
878  V::operator()(x, v);
879  }
880  void operator()(const ACX & z, const ACX & x, const ACX & y)
881  {
882  V::operator()(z, x, y);
883  }
884  void call(ACX & x, const T & v, unsigned n)
885  {
886  V::call(x, v, n);
887  }
888  };
889  };
890 
891  // polymorphic (conditional) tuple entry, modelled after cond_val
892  template <class ACX, class T, class Z, class V>
893  class tuple_entry
894  {
895  typedef typename Z::template load_type<ACX, T, V> load_type;
896  typedef load_type* ptr_type;
897 
898  protected:
899  ptr_type p;
900 
901  public:
902  tuple_entry() : p(0) {}
903  template <class TUPLE>
904  bool is_set(const TUPLE &) const { return p != 0; }
905 
906  protected:
907  void make_load()
908  {
909  if (!p)
910  p = new load_type;
911  }
912  void assign(const V & v)
913  {
914  ptr_type tmp = new load_type(v);
915  delete p;
916  p = tmp;
917  }
918  void check_pointer() const
919  {
920  if (!p)
921  vigra_fail("tuple_entry::operator V &: unused tuple entry "
922  "type V = [" + std::string(typeid(V).name()) + "], "
923  "use set() to create an entry.");
924  }
925  public:
926  operator const V & () const
927  {
928  check_pointer();
929  return *p;
930  }
931  operator V & ()
932  {
933  check_pointer();
934  return *p;
935  }
936 
937  template <class TUPLE> // not neccearily identical to ACX
938  void set(TUPLE & tuple)
939  {
940  make_load();
941  }
942  template <class TUPLE>
943  void set(const V & v, TUPLE & tuple)
944  {
945  set(tuple);
946  assign(v);
947  }
948 
949  tuple_entry & operator=(tuple_entry const & e)
950  {
951  ptr_type tmp = new load_type(*e.p);
952  delete p;
953  p = tmp;
954  return *this;
955  }
956  tuple_entry(tuple_entry const & e)
957  : p(0)
958  {
959  if (e.p) // properly care for empty original
960  p = new load_type(*e.p);
961  }
962  ~tuple_entry()
963  {
964  delete p;
965  }
966  friend std::ostream & operator<<(std::ostream & os,
967  const tuple_entry & x)
968  {
969  if (x.p)
970  os << x.val(x);
971  else
972  os << "<nil>";
973  return os;
974  }
975  };
976 
977  // pos is the position of type V in the type list of the tuple
978  template <class ACX, class T, class Z, class V, unsigned pos>
979  struct cond_tuple_entry : public tuple_entry<ACX, T, Z, V>
980  {
981  template <class TUPLE> // not quite identical to ACX
982  void set(TUPLE & tuple)
983  {
984  this->make_load();
985  tuple.template add<V>(this->p, pos);
986  }
987  template <class TUPLE>
988  void reassign(TUPLE & tuple)
989  {
990  if (this->p)
991  tuple.reassign(this->p, pos);
992  }
993  template <class TUPLE>
994  void set(const V & v, TUPLE & tuple)
995  {
996  set(tuple);
997  this->assign(v);
998  }
999  };
1000 
1001  // helper classes for tuples
1002 
1003  template <unsigned pos, class X>
1004  struct at_finder
1005  {
1006  typedef at_finder<pos - 1, typename X::rest_type> next_type;
1007  typedef typename next_type::type type;
1008  static
1009  type & at(X & x)
1010  {
1011  return next_type::at(x.rest);
1012  }
1013  };
1014  template <class X>
1015  struct at_finder<0, X>
1016  {
1017  typedef typename X::first_type type;
1018  static
1019  type & at(X & x) {
1020  return x.first;
1021  }
1022  };
1023 
1024  template <class T, class X>
1025  struct sub_finder
1026  {
1027  typedef typename X::rest_type rest_type;
1028  typedef sub_finder<T, rest_type>
1029  next_type;
1030  typedef typename next_type::type type;
1031  static type & object(X & x)
1032  {
1033  return next_type::object(x.rest);
1034  }
1035  static const type & const_object(const X & x)
1036  {
1037  return next_type::const_object(x.rest);
1038  }
1039  };
1040  template <class X>
1041  struct sub_finder<typename X::finder_type, X>
1042  {
1043  typedef X type;
1044  static type & object(X & x)
1045  {
1046  return x;
1047  }
1048  static const type & const_object(const X & x)
1049  {
1050  return x;
1051  }
1052  };
1053 
1054  template <class T, class X>
1055  struct ref_finder
1056  {
1057  typedef sub_finder<T, X> finder;
1058  typedef typename finder::type::first_type type;
1059  static
1060  type & ref(X & x)
1061  {
1062  return finder::object(x).first;
1063  }
1064  static
1065  const type & ref(const X & x)
1066  {
1067  return finder::const_object(x).first;
1068  }
1069  };
1070 
1071  struct binder_0
1072  {
1073  template <class F>
1074  void operator()(F & first)
1075  {
1076  first();
1077  }
1078  template <class F>
1079  void call(F & first)
1080  {
1081  first.call();
1082  }
1083  };
1084  template <class A>
1085  struct binder_1
1086  {
1087  A v;
1088  binder_1(A v_) : v(v_) {}
1089  template <class F>
1090  void operator()(F & first)
1091  {
1092  first(v);
1093  }
1094  template <class F>
1095  void call(F & first)
1096  {
1097  first.call(v);
1098  }
1099  };
1100  template <class A, class B>
1101  struct binder_2
1102  {
1103  A v;
1104  B w;
1105  binder_2(A v_, B w_) : v(v_), w(w_) {}
1106  template <class F>
1107  void operator()(F & first)
1108  {
1109  first(v, w);
1110  }
1111  template <class F>
1112  void call(F & first)
1113  {
1114  first.call(v, w);
1115  }
1116  };
1117  template <class A, class B, class C>
1118  struct binder_3
1119  {
1120  A v;
1121  B w;
1122  C x;
1123  binder_3(A v_, B w_, C x_) : v(v_), w(w_), x(x_) {}
1124  template <class F>
1125  void operator()(F & first)
1126  {
1127  first(v, w, x);
1128  }
1129  template <class F>
1130  void call(F & first)
1131  {
1132  first.call(v, w, x);
1133  }
1134  };
1135 
1136  // mechanism for iterative application of operator() to a tuple
1137  template <template <class> class TEST>
1138  struct exec_op_plain
1139  {
1140  template <class TUPLE, class B, class TBASE>
1141  static void exec(TUPLE & tuple, B & binder, const TBASE & z)
1142  {
1143  binder(tuple.first);
1144  tuple.rest.exec_bound_op(binder, z);
1145  }
1146  template <class TUPLE, class B, class TBASE>
1147  static void call(TUPLE & tuple, B & binder, const TBASE & z)
1148  {
1149  typedef typename TUPLE::ref_finder_type ref_finder_type;
1150  if (TEST<ref_finder_type>::value)
1151  binder.call(static_cast<ref_finder_type &> (tuple.first));
1152  tuple.rest.call_bound_op(binder, z);
1153  }
1154  };
1155 
1156  // policy classes for tuples
1157  struct plain_global_data
1158  {
1159  void reassign() {}
1160  };
1161 
1162  struct plain_chooser // this policy does effectively nothing.
1163  {
1164  template <class V, unsigned pos = 0>
1165  struct use
1166  {
1167  typedef V type;
1168  };
1169 
1170  template <class, template <class> class TEST>
1171  struct exec_op : public exec_op_plain<TEST> {};
1172 
1173  // "M" & "S" -> bug in cl.exe's parser.
1174  template <template<class, class, template<class> class M, unsigned>
1175  class, class, template<class> class S, unsigned>
1176  struct global_data : public plain_global_data
1177  {
1178  typedef global_data global_data_type;
1179  };
1180  template <class QV, class TUPLE>
1181  static bool is_set(const QV &, const TUPLE &) { return true; }
1182  template <class QV, class TUPLE>
1183  static void set(QV &, TUPLE &) {}
1184  };
1185 
1186  // this policy uses the cond_val template to annotate
1187  // each tuple member with a bool that steers conditional
1188  // execution of each member's operator(), if called via
1189  // the tuple's operator().
1190  struct cond_chooser_plain : public plain_chooser
1191  {
1192  template <class V, unsigned pos = 0>
1193  struct use
1194  {
1195  typedef cond_val<V, pos> type;
1196  };
1197 
1198  template <class, template <class> class TEST>
1199  struct exec_op
1200  {
1201  template <class TUPLE, class B, class TBASE>
1202  static void exec(TUPLE & tuple, B & binder, const TBASE & z)
1203  {
1204  typedef typename TUPLE::ref_finder_type ref_finder_type;
1205  if (tuple.first.is_set(z))
1206  binder(static_cast<ref_finder_type &>(tuple.first));
1207  tuple.rest.exec_bound_op(binder, z);
1208  }
1209  template <class TUPLE, class B, class TBASE>
1210  static void call(TUPLE & tuple, B & binder, const TBASE & z)
1211  {
1212  typedef typename TUPLE::ref_finder_type ref_finder_type;
1213  if (TEST<ref_finder_type>::value)
1214  if (tuple.first.is_set(z))
1215  binder.call(static_cast<ref_finder_type &>
1216  (tuple.first));
1217  tuple.rest.call_bound_op(binder, z);
1218  }
1219  };
1220 
1221  template <class QV, class TUPLE>
1222  static bool is_set(const QV & qv, const TUPLE & t)
1223  {
1224  return qv.is_set(t);
1225  }
1226  template <class QV, class TUPLE>
1227  static void set(QV & qv, TUPLE & t)
1228  {
1229  qv.set(t);
1230  }
1231  };
1232 
1233  // start the machinery for cond_chooser that produces nested 'if's
1234 
1235  template <class X, class T, class L = typename get_pure_depends_on<T>::type>
1236  struct depends_on_deep
1237  {
1238  static const bool value =
1239  depends_on_deep<X, T, typename L::rest>::value // iterate list
1240  || depends_on_deep<X, typename L::first>::value; // indirect dep.
1241  };
1242  template <class T, class L>
1243  struct depends_on_deep<typename L::first, T, L>
1244  {
1245  static const bool value = true;
1246  };
1247  template <class X, class T>
1248  struct depends_on_deep<X, T, nil>
1249  {
1250  static const bool value = false;
1251  };
1252 
1253  template <class T, class R>
1254  struct first_depends_on
1255  {
1256  static const bool value
1257  = depends_on_deep<typename R::first, T>::value;
1258  };
1259  template <class T>
1260  struct first_depends_on<T, nil>
1261  {
1262  static const bool value = false;
1263  };
1264 
1265  template <class RRL, class R>
1266  struct first_depends_on_all_of
1267  {
1268  static const bool value
1269  = ChooseBool<
1270  first_depends_on<typename
1271  RRL::first,
1272  R
1273  >,
1274  first_depends_on_all_of<typename RRL::rest, R>,
1275  VigraFalseType
1276  >::value;
1277  };
1278  template <class R> // end of list RRL: 'success'
1279  struct first_depends_on_all_of<nil, R>
1280  {
1281  static const bool value = true;
1282  };
1283  template <class RRL> // 'invalid' input (e.g., at end of cond_op recursion)
1284  struct first_depends_on_all_of<RRL, nil>
1285  {
1286  static const bool value = false;
1287  };
1288  template <> // 'invalid' input (e.g., at end of cond_op recursion)
1289  struct first_depends_on_all_of<nil, nil>
1290  {
1291  static const bool value = false;
1292  };
1293 
1294  // helper structs for cond_op:
1295  struct null_exec
1296  {
1297  template <class TUPLE, class B, class TBASE>
1298  static void exec(TUPLE &, B &, const TBASE &) {}
1299  template <class TUPLE, class B, class TBASE>
1300  static void call(TUPLE &, B &, const TBASE &) {}
1301  typedef nil iter_leftover_type;
1302  };
1303  template <bool cond, class EX>
1304  struct if_then
1305  {
1306  template <class TUPLE, class B, class TBASE>
1307  static void exec(TUPLE & t, B & b, const TBASE & z)
1308  {
1309  IfBool<cond, EX, null_exec>::type::exec(t, b, z);
1310  }
1311  template <class TUPLE, class B, class TBASE>
1312  static void call(TUPLE & t, B & b, const TBASE & z)
1313  {
1314  IfBool<cond, EX, null_exec>::type::call(t, b, z);
1315  }
1316  };
1317  template <class ZL, template <class> class TEST, class RRL>
1318  struct cond_op_inner;
1319 
1320  template <class ZL, template <class> class TEST, class RRL = nil>
1321  struct cond_op
1322  {
1323  typedef typename ZL::first first_type;
1324  typedef typename ZL::rest rest_type;
1325  typedef cons<first_type, RRL> next_rr_list;
1326 
1327  static const bool recurse_deep
1328  = first_depends_on<first_type, rest_type>::value;
1329  typedef cond_op<rest_type, TEST, next_rr_list>
1330  deep_type;
1331 
1332  typedef typename IfBool<recurse_deep, typename
1333  deep_type::iter_leftover_type,
1334  rest_type
1335  >::type
1336  deep_leftover_type;
1337 
1338  static const bool iterate
1339  = first_depends_on_all_of<RRL, deep_leftover_type>::value;
1340 
1341  typedef cond_op_inner<deep_leftover_type, TEST, RRL>
1342  iter_type;
1343 
1344  // the type list left over from the deep first recursion of exec()
1345  // and the iteration step: the recursion patterns of both the type
1346  // 'iter_leftover_type' and the function 'exec()' must match.
1347  typedef typename IfBool<iterate, typename
1348  iter_type::iter_leftover_type,
1349  deep_leftover_type
1350  >::type
1351  iter_leftover_type;
1352 
1353  // the code generation templates
1354  template <class TUPLE, class B, class TBASE>
1355  static void exec(TUPLE & tuple, B & binder, const TBASE & z)
1356  {
1357  if (tuple.first.is_set(z))
1358  {
1359  binder(tuple.first);
1360  if_then<recurse_deep, deep_type>::exec(tuple.rest, binder, z);
1361  }
1362  if_then<iterate, iter_type>::exec(tuple, binder, z);
1363  }
1364  template <class TUPLE, class B, class TBASE>
1365  static void call(TUPLE & tuple, B & binder, const TBASE & z)
1366  {
1367  if (tuple.first.is_set(z))
1368  {
1369  typedef typename TUPLE::ref_finder_type ref_finder_type;
1370  if (TEST<ref_finder_type>::value)
1371  binder.call(static_cast<ref_finder_type &> (tuple.first));
1372 
1373  if_then<recurse_deep, deep_type>::call(tuple.rest, binder, z);
1374  }
1375  if_then<iterate, iter_type>::call(tuple, binder, z);
1376  }
1377  };
1378  template <template <class> class TEST, class RRL> // end of type list ZL
1379  struct cond_op<nil, TEST, RRL> : public null_exec {};
1380 
1381  template <template <class> class TEST, class RRL> // end of type list ZL
1382  struct cond_op_inner<nil, TEST, RRL> : public null_exec {};
1383 
1384  template <class ZL, template <class> class TEST, class RRL>
1385  struct cond_op_inner
1386  {
1387  typedef cond_op<ZL, TEST, RRL> exec_type;
1388  typedef typename exec_type::iter_leftover_type iter_leftover_type;
1389 
1390  template <class TUPLE, class B, class TBASE>
1391  static void exec(TUPLE & tuple, B & binder, const TBASE & z)
1392  {
1393  exec_type::
1394  exec(sub_finder<typename ZL::first, TUPLE>::object(tuple),
1395  binder,
1396  z);
1397  }
1398  template <class TUPLE, class B, class TBASE>
1399  static void call(TUPLE & tuple, B & binder, const TBASE & z)
1400  {
1401  exec_type::
1402  call(sub_finder<typename ZL::first, TUPLE>::object(tuple),
1403  binder,
1404  z);
1405  }
1406  };
1407 
1408  struct cond_chooser : public cond_chooser_plain
1409  {
1410  template <class ZL, template <class> class TEST>
1411  struct exec_op : public cond_op<ZL, TEST> {};
1412  };
1413 
1414  struct bit_cond_chooser : public cond_chooser
1415  {
1416  template <class V, unsigned pos>
1417  struct use
1418  {
1419  typedef bit_cond_val<V, pos> type;
1420  };
1421 
1422  // cl.exe wants this -- maybe it is right.
1423  template <template<class, class, template<class> class M, unsigned>
1424  class, class, template<class> class S, unsigned>
1425  struct global_data : public plain_global_data
1426  {
1427  typedef global_data global_data_type;
1428  };
1429  template <template<class, class, template<class> class M, unsigned>
1430  class TBASE, class ITL, template<class> class TEST>
1431  struct global_data<TBASE, ITL, TEST, 0> : public plain_global_data
1432  {
1433  // typedef to catch our copy constructor and assignment operator:
1434  typedef global_data global_data_type;
1435 
1436  BitArray<size<ITL>::of> bit_set;
1437 
1438  void clear() { bit_set.clear(); }
1439  template <unsigned pos>
1440  void set_bit() { bit_set.template set<pos>(); }
1441  template <unsigned pos>
1442  bool is_bit_set() const { return bit_set.template test<pos>(); }
1443  };
1444  };
1445 
1446  template <class ACX, class T, class Z>
1447  struct virtual_chooser: public cond_chooser_plain
1448  {
1449  template <class V, unsigned pos = 0>
1450  struct use
1451  {
1452  typedef tuple_entry<ACX, T, Z, V> type;
1453  };
1454  };
1455 
1456  template <class T> struct set_exec
1457  {
1458  template <class ACX>
1459  static void exec(ACX & x)
1460  {
1461  x.template set<T>();
1462  }
1463  };
1464 
1465  template <class ACX, class T, class Z>
1466  struct cond_virtual_chooser: public cond_chooser_plain
1467  {
1468  template <class V, unsigned pos = 0>
1469  struct use
1470  {
1471  typedef cond_tuple_entry<ACX, T, Z, V, pos> type;
1472  };
1473 
1474  template <class, template <class> class TEST>
1475  struct exec_op
1476  {
1477  template <class TUPLE, class B, class TBASE>
1478  static void exec(TUPLE & tuple, B & binder, const TBASE &)
1479  {
1480  for (unsigned i = 0; i != tuple.execs.size; ++i)
1481  binder(*tuple.execs.pointers[i]);
1482  }
1483  template <class TUPLE, class B, class TBASE>
1484  static void call(TUPLE & tuple, B & binder, const TBASE &)
1485  {
1486  for (unsigned i = 0; i != tuple.callers.size; ++i)
1487  binder.call(*tuple.callers.pointers[i]);
1488  }
1489  };
1490  // cl.exe wants this -- maybe it is right.
1491  template <template<class, class, template<class> class M, unsigned>
1492  class, class, template<class> class S, unsigned>
1493  struct global_data : public plain_global_data
1494  {
1495  typedef global_data global_data_type;
1496  };
1497 
1498  template <class ITL>
1499  struct global_data_pointers // weak pointers
1500  {
1501  typedef typename Z::template member_base_type<ACX, T>* pointer_type;
1502  static const unsigned array_len = size<ITL>::of;
1503 
1504  unsigned orders [array_len]; // consciously use two arrays
1505  unsigned size;
1506  pointer_type pointers[array_len];
1507 
1508  void clear()
1509  {
1510  size = 0;
1511  }
1512  global_data_pointers()
1513  {
1514  clear();
1515  }
1516  unsigned* end(unsigned* = 0)
1517  {
1518  return orders + size;
1519  }
1520  pointer_type* end(pointer_type*)
1521  {
1522  return pointers + size;
1523  }
1524  template <class E>
1525  void make_room(E* i)
1526  {
1527  std::copy_backward(i, end(i), end(i) + 1);
1528  }
1529  typedef std::pair<unsigned*, pointer_type*> finder;
1530  bool find(unsigned pos, finder & found)
1531  {
1532  found.first = std::lower_bound(orders, end(), pos);
1533  found.second = pointers + (found.first - orders);
1534  return found.first != end() && *found.first == pos;
1535  }
1536  void add(pointer_type p, unsigned pos)
1537  {
1538  // merge pointer according to its topological sort order
1539  finder found;
1540  if (find(pos, found))
1541  return;
1542  make_room(found.first);
1543  make_room(found.second);
1544  ++size;
1545  *found.first = pos;
1546  *found.second = p;
1547  }
1548  void reassign(pointer_type p, unsigned pos)
1549  {
1550  // replace pointers -- the present values still belong to
1551  // the old tuple object that was copied from
1552  finder found;
1553  if (find(pos, found))
1554  *found.second = p;
1555  }
1556  };
1557  template <template<class, class, template<class> class M, unsigned>
1558  class TBASE, class ITL, template<class> class TEST>
1559  struct global_data<TBASE, ITL, TEST, 0>
1560  {
1561  // typedef to catch our copy constructor and assignment operator:
1562  typedef global_data global_data_type;
1563  // the derived class:
1564  typedef TBASE<ITL, cond_virtual_chooser, TEST, 0> crtp_type;
1565 
1566  typedef global_data_pointers<ITL> ptrs_type;
1567  typedef typename ptrs_type::pointer_type pointer_type;
1568  ptrs_type callers;
1569  ptrs_type execs;
1570 
1571  template <class V>
1572  void add(pointer_type p, unsigned pos)
1573  {
1574  execs.add(p, pos);
1575  if (TEST<V>::value)
1576  callers.add(p, pos);
1577  }
1578  void reassign(pointer_type p, unsigned pos)
1579  {
1580  execs. reassign(p, pos);
1581  callers.reassign(p, pos);
1582  }
1583 
1584  template <class V>
1585  struct reassign_op
1586  {
1587  static void exec(crtp_type & tuple)
1588  {
1589  tuple.template ref<V>().reassign(tuple);
1590  }
1591  };
1592 
1593  void reassign()
1594  {
1595  for_all<ITL, reassign_op>(static_cast<crtp_type &>(*this));
1596  }
1597  };
1598  };
1599 
1600 
1601  template <class ITL, class Q = plain_chooser,
1602  template<class> class TEST = true_test, unsigned index = 0>
1603  struct tuple_base
1604  : public Q::template global_data<tuple_base, ITL, TEST, index>
1605  {
1606  typedef typename tuple_base::global_data_type global_data_base_type;
1607  typedef nil derived_type; // dummy declaration for static_cast_2<>
1608  typedef tuple_base tuple_type;
1609  typedef ITL list_type;
1610 
1611  // use the original types from the list to find tuple members via ref():
1612  typedef typename ITL::first finder_type;
1613  typedef typename ITL::rest rest_list_type;
1614 
1615  typedef tuple_base<rest_list_type, Q, TEST, index + 1> rest_type;
1616 
1617  // use policy class Q to annotate the types of the type list ITL
1618  // for use as members of the tuple:
1619  // -- the actually stored type
1620  typedef typename ITL::first ref_finder_type;
1621  typedef typename Q::template use<ref_finder_type,
1622  index>::type first_type;
1623  first_type first;
1624  rest_type rest;
1625 
1626  template <class T>
1627  struct has_element
1628  {
1629  static const bool value = contains<T, ITL>::value;
1630  };
1631 
1632  template <unsigned pos>
1633  typename at_finder<pos, tuple_base>::type & at()
1634  {
1635  return at_finder<pos, tuple_base>::at(*this);
1636  }
1637 
1638  template <class T>
1639  struct ref_returns
1640  {
1641  typedef ref_finder<T, tuple_base> finder;
1642  typedef typename finder::type ref_finder_type;
1643  typedef ref_finder_type & type;
1644  typedef const ref_finder_type & const_type;
1645  };
1646  template <class T>
1647  typename ref_returns<T>::type
1648  ref()
1649  {
1650  return ref_returns<T>::finder::ref(*this);
1651  }
1652  template <class T>
1653  typename ref_returns<T>::const_type
1654  ref() const
1655  {
1656  return ref_returns<T>::finder::ref(*this);
1657  }
1658 
1659  template <class V>
1660  bool is_set() const
1661  {
1662  return Q::template is_set(this->template ref<V>(), *this);
1663  }
1664  template <class RV>
1665  void set_if_not(RV & rv)
1666  {
1667  if (! Q::template is_set(rv, *this))
1668  Q::template set(rv, *this);
1669  }
1670  // recursively set all the cond_val::is_set bits of the depended-on
1671  // types, or, respectively, take equivalent action.
1672  template <class V>
1673  void set()
1674  {
1675  set_if_not(this->template ref<V>());
1676  for_all_used<V, set_exec>(*this);
1677  }
1678  // transfer the set bits of *this to another tuple t2:
1679  // (ITL must be a subset of ITL2.)
1680  template <class ITL2, class Q2, template<class> class TEST2>
1681  void transfer_set_to(tuple_base<ITL2, Q2, TEST2> & t2) const
1682  {
1683  if (is_set<ref_finder_type>())
1684  t2.template set<ref_finder_type>();
1685  rest.transfer_set_to(t2);
1686  }
1687 
1688  // policy-based application of operator()
1689  template <class B, class TBASE>
1690  void exec_bound_op(B & binder, const TBASE & z)
1691  {
1692  Q::template exec_op<list_type, true_test>::exec(*this, binder, z);
1693  }
1694  template <class B>
1695  void exec_bound(B & binder)
1696  {
1697  exec_bound_op(binder, *this);
1698  }
1699 
1700  void operator()()
1701  {
1702  binder_0 binder;
1703  exec_bound(binder);
1704  }
1705 
1706  template <class A>
1707  void operator()(const A & v)
1708  {
1709  binder_1<const A &> binder(v);
1710  exec_bound(binder);
1711  }
1712  template <class A>
1713  void operator()(A & v)
1714  {
1715  binder_1<A &> binder(v);
1716  exec_bound(binder);
1717  }
1718  template <class A>
1719  void operator()(A & v) const
1720  {
1721  binder_1<A &> binder(v);
1722  exec_bound(binder);
1723  }
1724 
1725  template <class A, class B>
1726  void operator()(const A & v, const B & w)
1727  {
1728  binder_2<const A &, const B &> binder(v, w);
1729  exec_bound(binder);
1730  }
1731  template <class A, class B>
1732  void operator()(A & v, const B & w)
1733  {
1734  binder_2<A &, const B &> binder(v, w);
1735  exec_bound(binder);
1736  }
1737  template <class A, class B>
1738  void operator()(A & v, const B & w) const
1739  {
1740  binder_2<A &, const B &> binder(v, w);
1741  exec_bound(binder);
1742  }
1743 
1744  template <class A, class B, class C>
1745  void operator()(const A & v, const B & w, const C & x)
1746  {
1747  binder_3<const A &, const B &, const C &> binder(v, w, x);
1748  exec_bound(binder);
1749  }
1750  template <class A, class B, class C>
1751  void operator()(A & v, const B & w, const C & x)
1752  {
1753  binder_3<A &, const B &, const C &> binder(v, w, x);
1754  exec_bound(binder);
1755  }
1756  template <class A, class B, class C>
1757  void operator()(A & v, const B & w, const C & x) const
1758  {
1759  binder_3<A &, const B &, const C &> binder(v, w, x);
1760  exec_bound(binder);
1761  }
1762 
1763  // policy-based application of call()
1764  template <class B, class TBASE>
1765  void call_bound_op(B & binder, const TBASE & z)
1766  {
1767  Q::template exec_op<list_type, TEST>::call(*this, binder, z);
1768  }
1769  template <class B>
1770  void call_bound(B & binder)
1771  {
1772  call_bound_op(binder, *this);
1773  }
1774 
1775  template <class A, class B>
1776  void call(const A & v, const B & w)
1777  {
1778  binder_2<const A &, const B &> binder(v, w);
1779  call_bound(binder);
1780  }
1781  template <class A, class B>
1782  void call(A & v, const B & w)
1783  {
1784  binder_2<A &, const B &> binder(v, w);
1785  call_bound(binder);
1786  }
1787  template <class A, class B>
1788  void call(A & v, const B & w) const
1789  {
1790  binder_2<A &, const B &> binder(v, w);
1791  call_bound(binder);
1792  }
1793 
1794  template <class A, class B, class C>
1795  void call(const A & v, const B & w, const C & x)
1796  {
1797  binder_3<const A &, const B &, const C &> binder(v, w, x);
1798  call_bound(binder);
1799  }
1800  template <class A, class B, class C>
1801  void call(A & v, const B & w, const C & x)
1802  {
1803  binder_3<A &, const B &, const C &> binder(v, w, x);
1804  call_bound(binder);
1805  }
1806  template <class A, class B, class C>
1807  void call(A & v, const B & w, const C & x) const
1808  {
1809  binder_3<A &, const B &, const C &> binder(v, w, x);
1810  call_bound(binder);
1811  }
1812 
1813  // the possible reassign() of global data requires handmade copies here
1814  tuple_base() {}
1815  tuple_base(const tuple_base & x)
1816  : global_data_base_type(x), first(x.first), rest(x.rest)
1817  {
1818  this->reassign();
1819  }
1820  tuple_base & operator=(const tuple_base & x)
1821  {
1822  global_data_base_type::operator=(x);
1823  first = x.first;
1824  rest = x.rest;
1825  this->reassign();
1826  return *this;
1827  }
1828  };
1829  template <class Q, template <class> class TEST, unsigned index>
1830  struct tuple_base<nil, Q, TEST, index>
1831  {
1832  template <class>
1833  struct has_element
1834  {
1835  static const bool value = false;
1836  };
1837  template <class B, class TBASE>
1838  void exec_bound_op(B &, const TBASE &) {}
1839  template <class B, class TBASE>
1840  void call_bound_op(B &, const TBASE &) {}
1841  template <class ITL2, class Q2, template<class> class TEST2>
1842  void transfer_set_to(tuple_base<ITL2, Q2, TEST2> &) const {}
1843  };
1844 
1845  template <class V, class L, class A, class B>
1846  struct choose_tuple
1847  {
1848  static const bool value = contains<V, L>::value;
1849  typedef typename IfBool<value, A, B>::type type;
1850  static type & at(A & a, B & b)
1851  {
1852  return choose_type<value>::at(a, b);
1853  }
1854  static const type & at(const A & a, const B & b)
1855  {
1856  return choose_type<value>::at(a, b);
1857  }
1858 
1859  typedef typename type::template ref_returns<V>:: type
1860  ref_type;
1861  typedef typename type::template ref_returns<V>::const_type
1862  const_ref_type;
1863 
1864  ref_type
1865  static ref(A & a, B & b)
1866  {
1867  return at(a, b).template ref<V>();
1868  }
1869  const_ref_type
1870  static ref(const A & a, const B & b)
1871  {
1872  return at(a, b).template ref<V>();
1873  }
1874  };
1875 
1876  template <class ITL, template<class> class TEST = true_test>
1877  struct tuple : public tuple_base<ITL, plain_chooser, TEST> {};
1878 
1879  template <class ITL, template<class> class TEST = true_test>
1880  struct cond_tuple_plain
1881  : public tuple_base<ITL, cond_chooser_plain, TEST> {};
1882 
1883  template <class ITL, template<class> class TEST = true_test>
1884  struct cond_tuple : public tuple_base<ITL, cond_chooser, TEST> {};
1885 
1886  template <class ITL, template<class> class TEST = true_test>
1887  struct bit_cond_tuple : public tuple_base<ITL, bit_cond_chooser, TEST> {};
1888 
1889  template <class ITL, class ACX, class T, class Z,
1890  template<class> class TEST = true_test>
1891  struct virtual_tuple_base
1892  : public tuple_base<ITL, virtual_chooser<ACX, T, Z>, TEST> {};
1893 
1894  template <template <class, class> class ACXTT, class T,
1895  class Z = simple_member_dispatch>
1896  struct virtual_tuple
1897  {
1898  template <class ITL, template<class> class TEST = true_test>
1899  struct type
1900  : public virtual_tuple_base<ITL, ACXTT<T, ITL>, T, Z, TEST> {};
1901  };
1902 
1903  template <class ITL, class ACX, class T, class Z,
1904  template<class> class TEST = true_test>
1905  struct cond_virtual_tuple_base
1906  : public tuple_base<ITL, cond_virtual_chooser<ACX, T, Z>, TEST>
1907  {
1908  typedef ACX derived_type;
1909  };
1910 
1911  template <template <class, class> class ACXTT, class T,
1912  class Z = simple_member_dispatch>
1913  struct cond_virtual_tuple
1914  {
1915  template <class ITL, template<class> class TEST = true_test>
1916  struct type
1917  : public cond_virtual_tuple_base<ITL, ACXTT<T, ITL>, T, Z, TEST> {};
1918  };
1919 
1920 } // namespace type_lists
1921 
1922 // mask cl.exe shortcomings [end]
1923 #if defined(_MSC_VER)
1924 #pragma warning( pop )
1925 #endif
1926 
1927 } // namespace vigra
1928 
1929 #endif // VIGRA_TYPE_LISTS_HXX
vigra::add
void add(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r, FixedPoint< IntBits3, FracBits3 > &result)
addition with enforced result type.
Definition: fixedpoint.hxx:561

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.11.1 (Fri May 19 2017)