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

vigra/type_lists.hxx VIGRA

00001 /************************************************************************/
00002 /*                                                                      */
00003 /*    Copyright 2011-2012 by Markus Nullmeier and Ullrich Koethe        */
00004 /*                                                                      */
00005 /*    This file is part of the VIGRA computer vision library.           */
00006 /*    The VIGRA Website is                                              */
00007 /*        http://hci.iwr.uni-heidelberg.de/vigra/                       */
00008 /*    Please direct questions, bug reports, and contributions to        */
00009 /*        ullrich.koethe@iwr.uni-heidelberg.de    or                    */
00010 /*        vigra@informatik.uni-hamburg.de                               */
00011 /*                                                                      */
00012 /*    Permission is hereby granted, free of charge, to any person       */
00013 /*    obtaining a copy of this software and associated documentation    */
00014 /*    files (the "Software"), to deal in the Software without           */
00015 /*    restriction, including without limitation the rights to use,      */
00016 /*    copy, modify, merge, publish, distribute, sublicense, and/or      */
00017 /*    sell copies of the Software, and to permit persons to whom the    */
00018 /*    Software is furnished to do so, subject to the following          */
00019 /*    conditions:                                                       */
00020 /*                                                                      */
00021 /*    The above copyright notice and this permission notice shall be    */
00022 /*    included in all copies or substantial portions of the             */
00023 /*    Software.                                                         */
00024 /*                                                                      */
00025 /*    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND    */
00026 /*    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES   */
00027 /*    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND          */
00028 /*    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT       */
00029 /*    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,      */
00030 /*    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      */
00031 /*    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR     */
00032 /*    OTHER DEALINGS IN THE SOFTWARE.                                   */
00033 /*                                                                      */
00034 /************************************************************************/
00035 
00036 #ifndef VIGRA_TYPE_LISTS_HXX
00037 #define VIGRA_TYPE_LISTS_HXX
00038 
00039 #include <iostream>
00040 #include <typeinfo>
00041 #include <utility>
00042 #include <algorithm>
00043 #include "metaprogramming.hxx"
00044 #include "bit_array.hxx"
00045 #include "error.hxx"
00046 
00047 namespace vigra {
00048 
00049 // mask cl.exe shortcomings [begin]
00050 #if defined(_MSC_VER)
00051 #pragma warning( push )
00052 #pragma warning( disable : 4503 )
00053 #endif
00054 
00055 namespace type_lists {
00056 
00057     struct nil; // end-of-list marker.
00058     template <class T>
00059     struct nil_t;
00060     
00061     // type lists of size >= 1.
00062 
00063     template <class A, class B = nil> struct cons
00064     {
00065         typedef A first;
00066         typedef B rest;
00067     };
00068 
00069     template <class X, class A, class B> struct if_nil
00070     {
00071         typedef B type;
00072     };
00073     template <class A, class B> struct if_nil <nil, A, B>
00074     {
00075         typedef A type;
00076     };
00077 
00078     // truncate type list L (using class NIL as ending marker)
00079     // at the first occurence of type X
00080     template <class X, class L, class NIL = nil> struct truncate
00081     {
00082         typedef cons<typename L::first,
00083                      typename truncate<X, typename L::rest, NIL>::type> type;
00084     };
00085     template <class L, class NIL> struct truncate<typename L::first, L, NIL>
00086     {
00087         typedef nil type; // do the actual truncation
00088     };
00089     template <class X, class NIL> struct truncate<X, NIL, NIL>
00090     {
00091         typedef nil type;
00092     };
00093 
00094     template <class NIL, class A = NIL, class B = NIL, class C = NIL,
00095                          class D = NIL, class E = NIL, class F = NIL,
00096                          class G = NIL, class H = NIL, class I = NIL,
00097                          class J = NIL, class K = NIL, class L = NIL,
00098                          class M = NIL, class N = NIL, class O = NIL,
00099                          class P = NIL, class Q = NIL, class R = NIL,
00100                          class S = NIL, class T = NIL, class U = NIL,
00101                          class V = NIL, class W = NIL, class X = NIL,
00102                          class Y = NIL, class Z = NIL>
00103     struct make_list_nil {
00104         typedef typename truncate<NIL, cons<A, cons<B, cons<C, cons<D, cons<E,
00105                                        cons<F, cons<G, cons<H, cons<I, cons<J,
00106                                        cons<K, cons<L, cons<M, cons<N, cons<O,
00107                                        cons<P, cons<Q, cons<R, cons<S, cons<T,
00108                                        cons<U, cons<V, cons<W, cons<X, cons<Y,
00109                                        cons<Z, NIL> > > > > > > > > > > > > > >
00110                                        > > > > > > > > > > >, NIL>::type type;
00111     };
00112 
00113     template <class A = nil, class B = nil, class C = nil, class D = nil,
00114               class E = nil, class F = nil, class G = nil, class H = nil,
00115               class I = nil, class J = nil, class K = nil, class L = nil,
00116               class M = nil, class N = nil, class O = nil, class P = nil,
00117               class Q = nil, class R = nil, class S = nil, class T = nil,
00118               class U = nil, class V = nil, class W = nil, class X = nil,
00119               class Y = nil, class Z = nil>
00120 
00121     struct make_list {
00122         typedef typename make_list_nil<nil, A, B, C, D, E, F, G, H, I,
00123                                             J, K, L, M, N, O, P, Q, R,
00124                                             S, T, U, V, W, X, Y, Z
00125                                       >::type type;
00126     };
00127 
00128     template <class T_, template<class> class A = nil_t,
00129                         template<class> class B = nil_t,
00130                         template<class> class C = nil_t,
00131                         template<class> class D = nil_t,
00132                         template<class> class E = nil_t,
00133                         template<class> class F = nil_t,
00134                         template<class> class G = nil_t,
00135                         template<class> class H = nil_t,
00136                         template<class> class I = nil_t,
00137                         template<class> class J = nil_t,
00138                         template<class> class K = nil_t,
00139                         template<class> class L = nil_t,
00140                         template<class> class M = nil_t,
00141                         template<class> class N = nil_t,
00142                         template<class> class O = nil_t,
00143                         template<class> class P = nil_t,
00144                         template<class> class Q = nil_t,
00145                         template<class> class R = nil_t,
00146                         template<class> class S = nil_t,
00147                         template<class> class T = nil_t,
00148                         template<class> class U = nil_t,
00149                         template<class> class V = nil_t,
00150                         template<class> class W = nil_t,
00151                         template<class> class X = nil_t,
00152                         template<class> class Y = nil_t,
00153                         template<class> class Z = nil_t>
00154     struct make_list_template {
00155         typedef typename make_list_nil<nil_t<T_>,
00156                                        A<T_>, B<T_>, C<T_>, D<T_>, E<T_>,
00157                                        F<T_>, G<T_>, H<T_>, I<T_>, J<T_>,
00158                                        K<T_>, L<T_>, M<T_>, N<T_>, O<T_>,
00159                                        P<T_>, Q<T_>, R<T_>, S<T_>, T<T_>,
00160                                        U<T_>, V<T_>, W<T_>, X<T_>, Y<T_>,
00161                                        Z<T_> >::type type;
00162     };
00163 
00164     // a means to partially compensate for the lack of templated typedefs.
00165     template <template<class, class> class BASE, class T_,
00166                                                 template<class> class A = nil_t,
00167                                                 template<class> class B = nil_t,
00168                                                 template<class> class C = nil_t,
00169                                                 template<class> class D = nil_t,
00170                                                 template<class> class E = nil_t,
00171                                                 template<class> class F = nil_t,
00172                                                 template<class> class G = nil_t,
00173                                                 template<class> class H = nil_t,
00174                                                 template<class> class I = nil_t,
00175                                                 template<class> class J = nil_t,
00176                                                 template<class> class K = nil_t,
00177                                                 template<class> class L = nil_t,
00178                                                 template<class> class M = nil_t,
00179                                                 template<class> class N = nil_t,
00180                                                 template<class> class O = nil_t,
00181                                                 template<class> class P = nil_t,
00182                                                 template<class> class Q = nil_t,
00183                                                 template<class> class R = nil_t,
00184                                                 template<class> class S = nil_t,
00185                                                 template<class> class T = nil_t,
00186                                                 template<class> class U = nil_t,
00187                                                 template<class> class V = nil_t,
00188                                                 template<class> class W = nil_t,
00189                                                 template<class> class X = nil_t,
00190                                                 template<class> class Y = nil_t,
00191                                                 template<class> class Z = nil_t>
00192     struct use_template_list
00193         : public BASE<T_, typename make_list_template<T_, A, B, C, D, E, F, G,
00194                                                           H, I, J, K, L, M, N,
00195                                                           O, P, Q, R, S, T, U,
00196                                                           V, W, X, Y, Z>::type>
00197     {};
00198 
00199     // use first and rest only when possible:
00200     template <class T>
00201     struct has_first_rest : public sfinae_test<T, has_first_rest>
00202     {
00203         template <class U>
00204         has_first_rest(U*, typename U::first* = 0, typename U::rest* = 0);
00205     };
00206     template <bool P, class A>
00207     struct cond_cons_rest;
00208     template <class A>
00209     struct cond_cons_rest<false, A>
00210     {
00211         typedef void* type;
00212     };
00213     template <class A>
00214     struct cond_cons_rest<true, A>
00215     {
00216         typedef typename A::rest type;
00217     };
00218     // test if a type is a list in the above sense.
00219     template <class A> struct is_list
00220     {
00221         static const bool value = is_list<typename
00222                       cond_cons_rest<has_first_rest<A>::value, A>::type>::value;
00223     };
00224     template <> struct is_list<nil>
00225     {
00226         static const bool value = true;
00227     };
00228     template <> struct is_list<void*>
00229     {
00230         static const bool value = false;
00231     };
00232 
00233     template <class A> struct list_guard
00234     {
00235         typedef typename IfBool<is_list<A>::value, A, nil>::type type;
00236     };
00237 
00238     template <class A> struct size
00239     {
00240         static const unsigned of = size<typename A::rest>::of + 1;
00241     };
00242     template <> struct size<nil>
00243     {
00244         static const unsigned of = 0;
00245     };
00246 
00247     template <class X, class L> struct append
00248     {
00249         typedef cons<typename L::first,
00250                      typename append<X, typename L::rest>::type> type;
00251     };
00252     template <class X> struct append<X, nil>
00253     {
00254         typedef cons<X, nil> type;
00255     };
00256     template <> struct append<nil, nil>
00257     {
00258         typedef nil type;
00259     };
00260 
00261     template <class L, class R = nil> struct reverse
00262     {
00263         typedef typename reverse<typename L::rest,
00264                                  cons<typename L::first, R> >::type type;
00265     };
00266     template <class R> struct reverse<nil, R>
00267     {
00268         typedef R type;
00269     };
00270 
00271     template <template<class> class P, class Q, class L>
00272     struct max_value
00273     {
00274         static const bool is_nil = false;
00275         static const Q first_value = P<typename L::first>::value;
00276         typedef max_value<P, Q, typename L::rest> rest_type;
00277         static const Q rest_value = rest_type::value;
00278         static const bool gt = first_value > rest_value || rest_type::is_nil;
00279         static const Q value = gt * first_value + !gt * rest_value;
00280     };
00281     template <template<class> class P, class Q>
00282     struct max_value<P, Q, nil>
00283     {
00284         static const Q value = 0;
00285         static const bool is_nil = true;
00286     };
00287 
00288     // remove the all occurences of type X in type list L
00289     template <class X, class L> struct remove // recursion
00290     {
00291         typedef cons<typename L::first,
00292                      typename remove<X, typename L::rest>::type> type;
00293     };
00294     template <class L> struct remove<typename L::first, L> // actual removal
00295     {
00296         typedef typename remove<typename L::first, typename L::rest>::type type;
00297     };
00298     template <class X> struct remove<X, nil> // list end
00299     {
00300         typedef nil type;
00301     };
00302 
00303     // remove the all occurences of type list L where predicate P equals value
00304     template <template<class> class P, class L, bool value = true>
00305     struct remove_if
00306     {
00307         typedef typename
00308             IfBool<
00309                 value == P<typename L::first>::value, typename
00310                 remove_if<P, typename L::rest, value>::type,
00311                 cons<typename
00312                     L::first, typename
00313                     remove_if<P, typename L::rest, value>::type
00314                 >
00315             >::type type;
00316     };
00317     template <template<class> class P, bool value>
00318     struct remove_if<P, nil, value>
00319     {
00320         typedef nil type;
00321     };
00322 
00323     template <template<class> class P, class L>
00324     struct remove_if_not
00325     {
00326         typedef typename remove_if<P, L, false>::type type;
00327     };
00328 
00329     template <class X, class L> struct contains
00330     {
00331         static const bool value = contains<X, typename L::rest>::value;
00332     };
00333     template <class L> struct contains<typename L::first, L>
00334     {
00335         static const bool value = true;
00336     };
00337     template <class X> struct contains<X, nil>
00338     {
00339         static const bool value = false;
00340     };
00341 
00342     // simple, unstable merge
00343     template <class X, class L> struct merge
00344     {
00345         typedef typename L::first first;
00346         typedef typename
00347             merge<
00348                     typename IfBool<contains<first, X>::value,
00349                                X,
00350                                cons<first, X>
00351                           >::type,
00352                     typename L::rest
00353                  >::type type;
00354     };
00355     template <class X> struct merge<X, nil>
00356     {
00357         typedef X type;
00358     };
00359 
00360     // simple, unstable unique
00361     template <class L> struct unique
00362     {
00363         typedef typename merge<nil, L>::type type;
00364     };
00365 
00366     template <class T_, template<class> class A = nil_t,
00367                         template<class> class B = nil_t,
00368                         template<class> class C = nil_t,
00369                         template<class> class D = nil_t,
00370                         template<class> class E = nil_t,
00371                         template<class> class F = nil_t,
00372                         template<class> class G = nil_t,
00373                         template<class> class H = nil_t,
00374                         template<class> class I = nil_t,
00375                         template<class> class J = nil_t,
00376                         template<class> class K = nil_t,
00377                         template<class> class L = nil_t,
00378                         template<class> class M = nil_t,
00379                         template<class> class N = nil_t,
00380                         template<class> class O = nil_t,
00381                         template<class> class P = nil_t,
00382                         template<class> class Q = nil_t,
00383                         template<class> class R = nil_t,
00384                         template<class> class S = nil_t,
00385                         template<class> class T = nil_t,
00386                         template<class> class U = nil_t,
00387                         template<class> class V = nil_t,
00388                         template<class> class W = nil_t,
00389                         template<class> class X = nil_t,
00390                         template<class> class Y = nil_t,
00391                         template<class> class Z = nil_t>
00392     struct implies_template
00393     {
00394         typedef typename make_list_template<T_, A, B, C, D, E, F, G, H, I, J, K,
00395                                                 L, M, N, O, P, Q, R, S, T, U, V,
00396                                                 W, X, Y, Z>::type implies_types;
00397     };
00398 
00399     template <class T_, template<class> class A = nil_t,
00400                         template<class> class B = nil_t,
00401                         template<class> class C = nil_t,
00402                         template<class> class D = nil_t,
00403                         template<class> class E = nil_t,
00404                         template<class> class F = nil_t,
00405                         template<class> class G = nil_t,
00406                         template<class> class H = nil_t,
00407                         template<class> class I = nil_t,
00408                         template<class> class J = nil_t,
00409                         template<class> class K = nil_t,
00410                         template<class> class L = nil_t,
00411                         template<class> class M = nil_t,
00412                         template<class> class N = nil_t,
00413                         template<class> class O = nil_t,
00414                         template<class> class P = nil_t,
00415                         template<class> class Q = nil_t,
00416                         template<class> class R = nil_t,
00417                         template<class> class S = nil_t,
00418                         template<class> class T = nil_t,
00419                         template<class> class U = nil_t,
00420                         template<class> class V = nil_t,
00421                         template<class> class W = nil_t,
00422                         template<class> class X = nil_t,
00423                         template<class> class Y = nil_t,
00424                         template<class> class Z = nil_t>
00425     struct follows_template
00426     {
00427         typedef typename make_list_template<T_, A, B, C, D, E, F, G, H, I, J, K,
00428                                                 L, M, N, O, P, Q, R, S, T, U, V,
00429                                                 W, X, Y, Z>::type follows_types;
00430     };
00431 
00432     template <class T_, template<class> class A = nil_t,
00433                         template<class> class B = nil_t,
00434                         template<class> class C = nil_t,
00435                         template<class> class D = nil_t,
00436                         template<class> class E = nil_t,
00437                         template<class> class F = nil_t,
00438                         template<class> class G = nil_t,
00439                         template<class> class H = nil_t,
00440                         template<class> class I = nil_t,
00441                         template<class> class J = nil_t,
00442                         template<class> class K = nil_t,
00443                         template<class> class L = nil_t,
00444                         template<class> class M = nil_t,
00445                         template<class> class N = nil_t,
00446                         template<class> class O = nil_t,
00447                         template<class> class P = nil_t,
00448                         template<class> class Q = nil_t,
00449                         template<class> class R = nil_t,
00450                         template<class> class S = nil_t,
00451                         template<class> class T = nil_t,
00452                         template<class> class U = nil_t,
00453                         template<class> class V = nil_t,
00454                         template<class> class W = nil_t,
00455                         template<class> class X = nil_t,
00456                         template<class> class Y = nil_t,
00457                         template<class> class Z = nil_t>
00458     struct depends_on_template
00459     {
00460         typedef typename make_list_template<T_, A, B, C, D, E, F, G, H, I, J, K,
00461                                                 L, M, N, O, P, Q, R, S, T, U, V,
00462                                                 W, X, Y, Z>::type depends_on;
00463     };
00464 
00465     template <class T_u, template<class> class A = nil_t,
00466                          template<class> class B = nil_t,
00467                          template<class> class C = nil_t,
00468                          template<class> class D = nil_t,
00469                          template<class> class E = nil_t,
00470                          template<class> class F = nil_t,
00471                          template<class> class G = nil_t,
00472                          template<class> class H = nil_t,
00473                          template<class> class I = nil_t,
00474                          template<class> class J = nil_t,
00475                          template<class> class K = nil_t,
00476                          template<class> class L = nil_t,
00477                          template<class> class M = nil_t,
00478                          template<class> class N = nil_t,
00479                          template<class> class O = nil_t,
00480                          template<class> class P = nil_t,
00481                          template<class> class Q = nil_t,
00482                          template<class> class R = nil_t,
00483                          template<class> class S = nil_t,
00484                          template<class> class T = nil_t,
00485                          template<class> class U = nil_t,
00486                          template<class> class V = nil_t,
00487                          template<class> class W = nil_t,
00488                          template<class> class X = nil_t,
00489                          template<class> class Y = nil_t,
00490                          template<class> class Z = nil_t>
00491     struct uses_template
00492         : public implies_template<T_u, A, B, C, D, E, F, G, H, I, J, K, L, M,
00493                                        N, O, P, Q, R, S, T, U, V, W, X, Y, Z>,
00494           public depends_on_template<T_u, A, B, C, D, E, F, G, H, I, J, K, L, M,
00495                                        N, O, P, Q, R, S, T, U, V, W, X, Y, Z>
00496     {
00497         template <template<class> class A_ = nil_t,
00498                   template<class> class B_ = nil_t,
00499                   template<class> class C_ = nil_t,
00500                   template<class> class D_ = nil_t,
00501                   template<class> class E_ = nil_t,
00502                   template<class> class F_ = nil_t,
00503                   template<class> class G_ = nil_t,
00504                   template<class> class H_ = nil_t,
00505                   template<class> class I_ = nil_t,
00506                   template<class> class J_ = nil_t,
00507                   template<class> class K_ = nil_t,
00508                   template<class> class L_ = nil_t,
00509                   template<class> class M_ = nil_t,
00510                   template<class> class N_ = nil_t,
00511                   template<class> class O_ = nil_t,
00512                   template<class> class P_ = nil_t,
00513                   template<class> class Q_ = nil_t,
00514                   template<class> class R_ = nil_t,
00515                   template<class> class S_ = nil_t,
00516                   template<class> class T_ = nil_t,
00517                   template<class> class U_ = nil_t,
00518                   template<class> class V_ = nil_t,
00519                   template<class> class W_ = nil_t,
00520                   template<class> class X_ = nil_t,
00521                   template<class> class Y_ = nil_t,
00522                   template<class> class Z_ = nil_t>
00523         struct follows
00524             : public uses_template
00525             , public follows_template<T_u, A_, B_, C_, D_, E_, F_, G_, H_, I_,
00526                                            J_, K_, L_, M_, N_, O_, P_, Q_, R_,
00527                                            S_, T_, U_, V_, W_, X_, Y_, Z_> {};
00528 
00529         template <template<class> class A_ = nil_t,
00530                   template<class> class B_ = nil_t,
00531                   template<class> class C_ = nil_t,
00532                   template<class> class D_ = nil_t,
00533                   template<class> class E_ = nil_t,
00534                   template<class> class F_ = nil_t,
00535                   template<class> class G_ = nil_t,
00536                   template<class> class H_ = nil_t,
00537                   template<class> class I_ = nil_t,
00538                   template<class> class J_ = nil_t,
00539                   template<class> class K_ = nil_t,
00540                   template<class> class L_ = nil_t,
00541                   template<class> class M_ = nil_t,
00542                   template<class> class N_ = nil_t,
00543                   template<class> class O_ = nil_t,
00544                   template<class> class P_ = nil_t,
00545                   template<class> class Q_ = nil_t,
00546                   template<class> class R_ = nil_t,
00547                   template<class> class S_ = nil_t,
00548                   template<class> class T_ = nil_t,
00549                   template<class> class U_ = nil_t,
00550                   template<class> class V_ = nil_t,
00551                   template<class> class W_ = nil_t,
00552                   template<class> class X_ = nil_t,
00553                   template<class> class Y_ = nil_t,
00554                   template<class> class Z_ = nil_t>
00555         struct implies
00556             : public uses_template
00557         {
00558             typedef typename
00559                 merge<typename
00560                     uses_template::implies_types, typename
00561                     implies_template<T_u, A_, B_, C_, D_, E_, F_, G_, H_, I_,
00562                                           J_, K_, L_, M_, N_, O_, P_, Q_, R_,
00563                                           S_, T_, U_, V_, W_, X_, Y_, Z_>
00564                         ::implies_types
00565                 >::type
00566             implies_types;
00567         };
00568     };
00569 
00570     // for_all() helper class.
00571     template <template<class> class EXEC, class L> struct for_exec
00572     {
00573         template <class TX>
00574         static void all(TX & tx)
00575         {
00576             EXEC<typename L::first>::exec(tx);
00577             for_exec<EXEC, typename L::rest>::all(tx);
00578         }
00579     };
00580     template <template<class> class EXEC> struct for_exec<EXEC, nil>
00581     {
00582         template <class TX> static void all(TX &) {}
00583     };
00584     // for_all on type lists.
00585     // for all types T in the list L,
00586     // calls the static member function EXEC<T>::exec(TX & tx).
00587     template <class L, template<class> class EXEC, class TX>
00588     inline void for_all(TX & tx)
00589     {
00590         for_exec<EXEC, L>::all(tx);
00591     }
00592 
00593     template <class T>
00594     struct has_depends_on : public sfinae_test<T, has_depends_on>
00595     {
00596         template <class U> has_depends_on(U*, typename U::depends_on* = 0);
00597     };
00598     template <class T>
00599     struct has_implies : public sfinae_test<T, has_implies>
00600     {
00601         template <class U> has_implies(U*, typename U::implies_types* = 0);
00602     };
00603     template <class T>
00604     struct has_follows : public sfinae_test<T, has_follows>
00605     {
00606         template <class U> has_follows(U*, typename U::follows_types* = 0);
00607     };
00608 
00609     // use empty list in case of lacking / faulty depends_on or implies_types:
00610     template <bool P, class T>
00611     struct depends_on_guard;
00612     template <class T>
00613     struct depends_on_guard<false, T>
00614     {
00615         typedef nil type;
00616     };
00617     template <class T>
00618     struct depends_on_guard<true, T>
00619     {
00620         typedef typename list_guard<typename T::depends_on>::type type;
00621     };
00622     template <class T>
00623     struct get_pure_depends_on
00624     {
00625         typedef typename depends_on_guard<has_depends_on<T>::value, T>::type
00626             type;
00627     };
00628 
00629     template <bool P, class T>
00630     struct follows_guard;
00631     template <class T>
00632     struct follows_guard<false, T>
00633     {
00634         typedef nil type;
00635     };
00636     template <class T>
00637     struct follows_guard<true, T>
00638     {
00639         typedef typename list_guard<typename T::follows_types>::type type;
00640     };
00641     template <class T>
00642     struct get_follows
00643     {
00644         typedef typename follows_guard<has_follows<T>::value, T>::type
00645             type;
00646     };
00647 
00648     template <class T>
00649     struct get_depends_on
00650     {
00651         typedef typename merge<typename get_pure_depends_on<T>::type,
00652                                typename get_follows<T>::type       >::type type;
00653     };
00654 
00655     template <bool P, class T>
00656     struct implies_guard;
00657     template <class T>
00658     struct implies_guard<false, T>
00659     {
00660         typedef nil type;
00661     };
00662     template <class T>
00663     struct implies_guard<true, T>
00664     {
00665         typedef typename list_guard<typename T::implies_types>::type type;
00666     };
00667     template <class T>
00668     struct get_implies
00669     {
00670         typedef typename implies_guard<has_implies<T>::value, T>::type
00671             type;
00672     };
00673 
00674     template <class L> struct implies_expand
00675     {
00676         typedef typename L::first first;
00677         typedef typename L::rest  rest;
00678         typedef
00679             cons<first, typename
00680                         merge<typename
00681                               implies_expand<rest>::type, typename
00682                               implies_expand<typename
00683                                   get_implies<first>
00684         ::type>::type>::type> type;
00685     };
00686     template <> struct implies_expand<nil>
00687     {
00688         typedef nil type;
00689     };
00690 
00691     // for_all with type list == T::depends_on (if any.)
00692     template <class T, template<class> class EXEC, class TX>
00693     inline void for_all_used(TX & tx)
00694     {
00695         for_all<typename get_pure_depends_on<T>::type, EXEC>(tx);
00696     }
00697 
00698     template <class X, class T>
00699     struct contains_dependent
00700     {
00701         static const bool value
00702             = contains<X, typename get_depends_on<T>::type>::value;
00703     };
00704 
00705     template <class X, class XL> struct is_independent_on
00706     {
00707         static const bool value
00708             = ChooseBool<contains_dependent<X, typename XL::first>,
00709                             VigraFalseType,
00710                             is_independent_on<X, typename XL::rest>
00711                         >::value;
00712     };
00713     template <class X> struct is_independent_on<X, nil>
00714     {
00715         static const bool value = true;
00716     };
00717 
00718     template <class XL, class YL = XL> struct get_independent
00719     {
00720         typedef typename YL::first YL_first;
00721         typedef typename
00722         IfBool<is_independent_on<YL_first, XL>::value,
00723                           YL_first,
00724                           typename get_independent<XL, typename YL::rest>::type
00725               >::type type;
00726     };
00727     template <class XL> struct get_independent<XL, nil>
00728     {
00729         typedef nil type;
00730     };
00731 
00732     // the output is a list of types in reverse order, starting with the
00733     // most depedent types.
00734     template <class L> struct topo_sort
00735     {
00736         typedef typename get_independent<L>::type indep;
00737         typedef typename
00738         if_nil<indep,
00739                   nil,
00740                   cons<indep,
00741                       typename topo_sort<typename remove<indep, L>::type>::type
00742                       >
00743               >::type type;
00744     };
00745     template <> struct topo_sort<nil>
00746     {
00747         typedef nil type;
00748     };
00749 
00750     // Topological sort -- the input is a list of types (see below),
00751     // each of which may, optionally, have an embedded typedef 'depends_on'
00752     // set to a singly-linked-list of types declared
00753     // using vigra::type_lists::cons, such as
00754     // cons<type_a, cons<type_b, cons<type_c> > >
00755     // (a one-parameter cons will add the trailing nil automatically),
00756     // -- the output is a list of types with increasing dependence,
00757     // starting with the indepedent types.
00758     // Types that should be said lists -- but are in fact not -- are silently
00759     // replaced by empty lists.
00760 
00761     template <class L> struct topological_sort
00762     {
00763         typedef typename
00764             reverse<typename
00765                 topo_sort<typename
00766                     unique<typename
00767                         list_guard<L>
00768         ::type>::type>::type>::type type;
00769     };
00770 
00771     template <class L> struct topological_sort_expanded
00772     {
00773         typedef typename
00774             topological_sort<typename
00775                 implies_expand<L>
00776         ::type>::type type;
00777     };
00778 
00779     template <class V, unsigned pos = 0>
00780     class cond_val : public V
00781     {
00782         typedef V load_type;
00783     protected:
00784         bool is_set_;
00785     public:
00786         cond_val() : is_set_(false) {}
00787         const V & val() const { return *this; }
00788               V & val()       { return *this; }
00789 
00790         template <class TUPLE>
00791         bool is_set(const TUPLE &) const
00792         {
00793             return is_set_;
00794         }
00795 
00796         template <class TUPLE>
00797         void set(TUPLE &)
00798         {
00799             is_set_ = true;
00800         }
00801         template <class TUPLE>
00802         void set(const V & v, TUPLE & tuple)
00803         {
00804             set(tuple);
00805             val() = v;
00806         }
00807         friend std::ostream & operator<<(std::ostream & os, const cond_val & x)
00808         {
00809             if (x.is_set_)
00810                 os << x.val(x);
00811             else
00812                 os << "<nil>";
00813             return os;
00814         }
00815     };
00816 
00817     template <class V, unsigned pos>
00818     class bit_cond_val : public V
00819     {
00820         typedef V load_type;
00821     public:
00822         const V & val() const { return *this; }
00823               V & val()       { return *this; }
00824 
00825         template <class TUPLE>
00826         bool is_set(const TUPLE & tuple) const
00827         {
00828             return tuple.template is_bit_set<pos>();
00829         }
00830 
00831         template <class TUPLE>
00832         void set(TUPLE & tuple)
00833         {
00834             tuple.template set_bit<pos>();
00835         }
00836         template <class TUPLE>
00837         void set(const V & v, TUPLE & tuple)
00838         {
00839             set(tuple);
00840             val() = v;
00841         }
00842     };
00843 
00844     // no templated virtual functions in C++ ...
00845     //
00846     // simple_member_dispatch: sample base and polymorphic adapter classes
00847     // for cond_virtual_tuple / etc.
00848     // -- the names 'member_base_type' and 'load_type' of the templates,
00849     // and also their parameter types, are fixed.
00850     // -- note that the member_base_type template of any "member_dispatch"
00851     // class can not directly serve as a base class for any member type that
00852     // is used within the tuple, since the signatures of most of the
00853     // virtual functions that are usually needed necessarily require the
00854     // type of the tuple itself.
00855     //
00856     struct simple_member_dispatch
00857     {
00858         template <class ACX, class T>
00859         struct member_base_type
00860         {
00861             virtual void operator()() {}
00862             virtual void operator()(ACX &, const T &) {}
00863             virtual void operator()(const ACX &, const ACX &, const ACX &) {}
00864             virtual void call(ACX &, const T &, unsigned) {}
00865             virtual ~member_base_type() {}
00866         };
00867         template <class ACX, class T, class V>
00868         struct load_type : public member_base_type<ACX, T>, public V
00869         {
00870             load_type() {}
00871             load_type(const V & v) : V(v) {}
00872             void operator()()
00873             {
00874                 V::operator()();
00875             }
00876             void operator()(ACX & x, const T & v)
00877             {
00878                 V::operator()(x, v);
00879             }
00880             void operator()(const ACX & z, const ACX & x, const ACX & y)
00881             {
00882                 V::operator()(z, x, y);
00883             }
00884             void call(ACX & x, const T & v, unsigned n)
00885             {
00886                 V::call(x, v, n);
00887             }
00888         };
00889     };
00890 
00891     // polymorphic (conditional) tuple entry, modelled after cond_val
00892     template <class ACX, class T,  class Z, class V>
00893     class tuple_entry
00894     {
00895         typedef typename Z::template load_type<ACX, T, V> load_type;
00896         typedef load_type*                                ptr_type;
00897 
00898     protected:
00899         ptr_type p;
00900         
00901     public:
00902         tuple_entry() : p(0) {}
00903         template <class TUPLE>
00904         bool is_set(const TUPLE &) const { return p != 0; }
00905 
00906     protected:
00907         void make_load()
00908         {
00909             if (!p)
00910                 p = new load_type;
00911         }
00912         void assign(const V & v)
00913         {
00914             ptr_type tmp = new load_type(v);
00915             delete p;
00916             p = tmp;
00917         }
00918         void check_pointer() const
00919         {
00920             if (!p)
00921                 vigra_fail("tuple_entry::operator V &: unused tuple entry "
00922                            "type V = [" + std::string(typeid(V).name()) + "], "
00923                            "use set() to create an entry.");
00924         }
00925     public:
00926         operator const V & () const
00927         {
00928             check_pointer();
00929             return *p;
00930         }
00931         operator V & ()
00932         {
00933             check_pointer();
00934             return *p;
00935         }
00936 
00937         template <class TUPLE> // not neccearily identical to ACX
00938         void set(TUPLE & tuple)
00939         {
00940             make_load();
00941         }
00942         template <class TUPLE>
00943         void set(const V & v, TUPLE & tuple)
00944         {
00945             set(tuple);
00946             assign(v);
00947         }
00948 
00949         tuple_entry & operator=(tuple_entry const & e)
00950         {
00951             ptr_type tmp = new load_type(*e.p);
00952             delete p;
00953             p = tmp;
00954             return *this;
00955         }
00956         tuple_entry(tuple_entry const & e)
00957             : p(0)
00958         {
00959             if (e.p) // properly care for empty original
00960                 p = new load_type(*e.p);
00961         }
00962         ~tuple_entry()
00963         {
00964             delete p;
00965         }
00966         friend std::ostream & operator<<(std::ostream & os,
00967                                                           const tuple_entry & x)
00968         {
00969             if (x.p)
00970                 os << x.val(x);
00971             else
00972                 os << "<nil>";
00973             return os;
00974         }
00975     };
00976 
00977     // pos is the position of type V in the type list of the tuple
00978     template <class ACX, class T, class Z, class V, unsigned pos>
00979     struct cond_tuple_entry : public tuple_entry<ACX, T, Z, V>
00980     {
00981         template <class TUPLE> // not quite identical to ACX
00982         void set(TUPLE & tuple)
00983         {
00984             this->make_load();
00985             tuple.template add<V>(this->p, pos);
00986         }
00987         template <class TUPLE>
00988         void reassign(TUPLE & tuple)
00989         {
00990             if (this->p)
00991                 tuple.reassign(this->p, pos);
00992         }
00993         template <class TUPLE>
00994         void set(const V & v, TUPLE & tuple)
00995         {
00996             set(tuple);
00997             this->assign(v);
00998         }
00999     };
01000    
01001     // helper classes for tuples
01002     
01003     template <unsigned pos, class X>
01004     struct at_finder
01005     {
01006         typedef at_finder<pos - 1, typename X::rest_type> next_type;
01007         typedef typename next_type::type type;
01008         static
01009         type & at(X & x)
01010         {
01011             return next_type::at(x.rest);
01012         }
01013     };
01014     template <class X>
01015     struct at_finder<0, X>
01016     {
01017         typedef typename X::first_type type;
01018         static
01019         type & at(X & x) {
01020             return x.first;
01021         }
01022     };
01023 
01024     template <class T, class X>
01025     struct sub_finder
01026     {
01027         typedef typename X::rest_type rest_type;
01028         typedef sub_finder<T, rest_type>
01029                 next_type;
01030         typedef typename next_type::type type;
01031         static type & object(X & x)
01032         {
01033             return next_type::object(x.rest);
01034         }
01035         static const type & const_object(const X & x)
01036         {
01037             return next_type::const_object(x.rest);
01038         }
01039     };
01040     template <class X>
01041     struct sub_finder<typename X::finder_type, X>
01042     {
01043         typedef X type;
01044         static type & object(X & x)
01045         {
01046             return x;
01047         }
01048         static const type & const_object(const X & x)
01049         {
01050             return x;
01051         }
01052     };
01053 
01054     template <class T, class X>
01055     struct ref_finder
01056     {
01057         typedef          sub_finder<T, X>         finder;
01058         typedef typename finder::type::first_type type;
01059         static
01060         type & ref(X & x)
01061         {
01062             return finder::object(x).first;
01063         }
01064         static
01065         const type & ref(const X & x)
01066         {
01067             return finder::const_object(x).first;
01068         }
01069     };
01070 
01071     struct binder_0
01072     {
01073         template <class F>
01074         void operator()(F & first)
01075         {
01076             first();
01077         }
01078         template <class F>
01079         void call(F & first)
01080         {
01081             first.call();
01082         }
01083     };
01084     template <class A>
01085     struct binder_1
01086     {
01087         A v;
01088         binder_1(A v_) : v(v_) {}
01089         template <class F>
01090         void operator()(F & first)
01091         {
01092             first(v);
01093         }
01094         template <class F>
01095         void call(F & first)
01096         {
01097             first.call(v);
01098         }
01099     };
01100     template <class A, class B>
01101     struct binder_2
01102     {
01103         A v;
01104         B w;
01105         binder_2(A v_, B w_) : v(v_), w(w_) {}
01106         template <class F>
01107         void operator()(F & first)
01108         {
01109             first(v, w);
01110         }
01111         template <class F>
01112         void call(F & first)
01113         {
01114             first.call(v, w);
01115         }
01116     };
01117     template <class A, class B, class C>
01118     struct binder_3
01119     {
01120         A v;
01121         B w;
01122         C x;
01123         binder_3(A v_, B w_, C x_) : v(v_), w(w_), x(x_) {}
01124         template <class F>
01125         void operator()(F & first)
01126         {
01127             first(v, w, x);
01128         }
01129         template <class F>
01130         void call(F & first)
01131         {
01132             first.call(v, w, x);
01133         }
01134     };
01135 
01136     // mechanism for iterative application of operator() to a tuple
01137     template <template <class> class TEST>
01138     struct exec_op_plain
01139     {
01140         template <class TUPLE, class B, class TBASE>
01141         static void exec(TUPLE & tuple, B & binder, const TBASE & z)
01142         {
01143             binder(tuple.first);
01144             tuple.rest.exec_bound_op(binder, z);
01145         }
01146         template <class TUPLE, class B, class TBASE>
01147         static void call(TUPLE & tuple, B & binder, const TBASE & z)
01148         {
01149             typedef typename TUPLE::ref_finder_type ref_finder_type;
01150             if (TEST<ref_finder_type>::value)
01151                 binder.call(static_cast<ref_finder_type &> (tuple.first));
01152             tuple.rest.call_bound_op(binder, z);
01153         }
01154     };
01155 
01156     // policy classes for tuples
01157     struct plain_global_data
01158     {
01159         void reassign() {}
01160     };
01161     
01162     struct plain_chooser // this policy does effectively nothing.
01163     {
01164         template <class V, unsigned pos = 0>
01165         struct use
01166         {
01167              typedef V type;
01168         };
01169 
01170         template <class, template <class> class TEST>
01171         struct exec_op : public exec_op_plain<TEST> {};
01172 
01173         // "M" & "S" -> bug in cl.exe's parser.
01174         template <template<class, class, template<class> class M, unsigned>
01175                   class, class, template<class> class S, unsigned>
01176         struct global_data : public plain_global_data
01177         {
01178             typedef global_data global_data_type;
01179         };
01180         template <class QV, class TUPLE>
01181         static bool is_set(const QV &, const TUPLE &) { return true; }
01182         template <class QV, class TUPLE>
01183         static void set(QV &, TUPLE &) {}
01184     };
01185 
01186                         // this policy uses the cond_val template to annotate
01187                         // each tuple member with a bool that steers conditional
01188                         // execution of each member's operator(), if called via
01189                         // the tuple's operator().
01190     struct cond_chooser_plain : public plain_chooser
01191     {
01192         template <class V, unsigned pos = 0>
01193         struct use
01194         {
01195             typedef cond_val<V, pos> type;
01196         };
01197 
01198         template <class, template <class> class TEST>
01199         struct exec_op
01200         {
01201             template <class TUPLE, class B, class TBASE>
01202             static void exec(TUPLE & tuple, B & binder, const TBASE & z)
01203             {
01204                 typedef typename TUPLE::ref_finder_type ref_finder_type;
01205                 if (tuple.first.is_set(z))
01206                     binder(static_cast<ref_finder_type &>(tuple.first));
01207                 tuple.rest.exec_bound_op(binder, z);
01208             }
01209             template <class TUPLE, class B, class TBASE>
01210             static void call(TUPLE & tuple, B & binder, const TBASE & z)
01211             {
01212                 typedef typename TUPLE::ref_finder_type ref_finder_type;
01213                 if (TEST<ref_finder_type>::value)
01214                     if (tuple.first.is_set(z))
01215                         binder.call(static_cast<ref_finder_type &>
01216                                                                  (tuple.first));
01217                 tuple.rest.call_bound_op(binder, z);
01218             }
01219         };
01220 
01221         template <class QV, class TUPLE>
01222         static bool is_set(const QV & qv, const TUPLE & t)
01223         {
01224             return qv.is_set(t);
01225         }
01226         template <class QV, class TUPLE>
01227         static void set(QV & qv, TUPLE & t)
01228         {
01229             qv.set(t);
01230         }
01231     };
01232     
01233     // start the machinery for cond_chooser that produces nested 'if's
01234 
01235     template <class X, class T, class L = typename get_pure_depends_on<T>::type>
01236     struct depends_on_deep
01237     {
01238         static const bool value =
01239             depends_on_deep<X, T, typename L::rest>::value   // iterate list
01240             || depends_on_deep<X, typename L::first>::value; // indirect dep.
01241     };
01242     template <class T, class L>
01243     struct depends_on_deep<typename L::first, T, L>
01244     {
01245         static const bool value = true;
01246     };
01247     template <class X, class T>
01248     struct depends_on_deep<X, T, nil>
01249     {
01250         static const bool value = false;
01251     };
01252 
01253     template <class T, class R>
01254     struct first_depends_on
01255     {
01256         static const bool value
01257             =  depends_on_deep<typename R::first, T>::value;
01258     };
01259     template <class T>
01260     struct first_depends_on<T, nil>
01261     {
01262         static const bool value = false;
01263     };
01264 
01265     template <class RRL, class R>
01266     struct first_depends_on_all_of
01267     {
01268         static const bool value
01269             = ChooseBool<
01270                   first_depends_on<typename
01271                       RRL::first,
01272                       R
01273                   >,
01274                   first_depends_on_all_of<typename RRL::rest, R>,
01275                   VigraFalseType
01276               >::value;
01277     };
01278     template <class R> // end of list RRL: 'success'
01279     struct first_depends_on_all_of<nil, R>
01280     {
01281         static const bool value = true;
01282     };
01283     template <class RRL> // 'invalid' input (e.g., at end of cond_op recursion)
01284     struct first_depends_on_all_of<RRL, nil>
01285     {
01286         static const bool value = false;
01287     };
01288     template <> // 'invalid' input (e.g., at end of cond_op recursion)
01289     struct first_depends_on_all_of<nil, nil>
01290     {
01291         static const bool value = false;
01292     };
01293 
01294     // helper structs for cond_op:
01295     struct null_exec
01296     {
01297         template <class TUPLE, class B, class TBASE>
01298         static void exec(TUPLE &, B &, const TBASE &) {}
01299         template <class TUPLE, class B, class TBASE>
01300         static void call(TUPLE &, B &, const TBASE &) {}
01301         typedef nil iter_leftover_type;
01302     };
01303     template <bool cond, class EX>
01304     struct if_then
01305     {
01306         template <class TUPLE, class B, class TBASE>
01307         static void exec(TUPLE & t, B & b, const TBASE & z)
01308         {
01309             IfBool<cond, EX, null_exec>::type::exec(t, b, z);
01310         }
01311         template <class TUPLE, class B, class TBASE>
01312         static void call(TUPLE & t, B & b, const TBASE & z)
01313         {
01314             IfBool<cond, EX, null_exec>::type::call(t, b, z);
01315         }
01316     };
01317     template <class ZL, template <class> class TEST, class RRL>
01318     struct cond_op_inner;
01319     
01320     template <class ZL, template <class> class TEST, class RRL = nil>
01321     struct cond_op
01322     {
01323         typedef typename ZL::first             first_type;
01324         typedef typename ZL::rest              rest_type;
01325         typedef          cons<first_type, RRL> next_rr_list;
01326 
01327         static const bool recurse_deep
01328             = first_depends_on<first_type, rest_type>::value;
01329         typedef cond_op<rest_type, TEST, next_rr_list>
01330             deep_type;
01331 
01332         typedef typename IfBool<recurse_deep, typename
01333                                 deep_type::iter_leftover_type,
01334                                 rest_type
01335                                >::type
01336             deep_leftover_type;
01337 
01338         static const bool iterate
01339             = first_depends_on_all_of<RRL, deep_leftover_type>::value;
01340 
01341         typedef cond_op_inner<deep_leftover_type, TEST, RRL>
01342             iter_type;
01343 
01344         // the type list left over from the deep first recursion of exec()
01345         // and the iteration step: the recursion patterns of both the type
01346         // 'iter_leftover_type' and the function 'exec()' must match.
01347         typedef typename IfBool<iterate, typename
01348                                 iter_type::iter_leftover_type,
01349                                 deep_leftover_type
01350                                >::type
01351             iter_leftover_type;
01352 
01353         // the code generation templates
01354         template <class TUPLE, class B, class TBASE>
01355         static void exec(TUPLE & tuple, B & binder, const TBASE & z)
01356         {
01357             if (tuple.first.is_set(z))
01358             {
01359                 binder(tuple.first);
01360                 if_then<recurse_deep, deep_type>::exec(tuple.rest, binder, z);
01361             }
01362             if_then<iterate, iter_type>::exec(tuple, binder, z);
01363         }
01364         template <class TUPLE, class B, class TBASE>
01365         static void call(TUPLE & tuple, B & binder, const TBASE & z)
01366         {
01367             if (tuple.first.is_set(z))
01368             {
01369                 typedef typename TUPLE::ref_finder_type ref_finder_type;
01370                 if (TEST<ref_finder_type>::value)
01371                     binder.call(static_cast<ref_finder_type &> (tuple.first));
01372                     
01373                 if_then<recurse_deep, deep_type>::call(tuple.rest, binder, z);
01374             }
01375             if_then<iterate, iter_type>::call(tuple, binder, z);
01376         }
01377     };
01378     template <template <class> class TEST, class RRL> // end of type list ZL
01379     struct cond_op<nil, TEST, RRL> : public null_exec {};
01380 
01381     template <template <class> class TEST, class RRL> // end of type list ZL
01382     struct cond_op_inner<nil, TEST, RRL> : public null_exec {};
01383 
01384     template <class ZL, template <class> class TEST, class RRL>
01385     struct cond_op_inner
01386     {
01387         typedef cond_op<ZL, TEST, RRL> exec_type;
01388         typedef typename exec_type::iter_leftover_type iter_leftover_type;
01389 
01390         template <class TUPLE, class B, class TBASE>
01391         static void exec(TUPLE & tuple, B & binder, const TBASE & z)
01392         {
01393             exec_type::
01394                 exec(sub_finder<typename ZL::first, TUPLE>::object(tuple),
01395                      binder,
01396                      z);
01397         }
01398         template <class TUPLE, class B, class TBASE>
01399         static void call(TUPLE & tuple, B & binder, const TBASE & z)
01400         {
01401             exec_type::
01402                 call(sub_finder<typename ZL::first, TUPLE>::object(tuple),
01403                      binder,
01404                      z);
01405         }
01406     };
01407 
01408     struct cond_chooser : public cond_chooser_plain
01409     {
01410         template <class ZL, template <class> class TEST>
01411         struct exec_op : public cond_op<ZL, TEST> {};
01412     };
01413 
01414     struct bit_cond_chooser : public cond_chooser
01415     {
01416         template <class V, unsigned pos>
01417         struct use
01418         {
01419             typedef bit_cond_val<V, pos> type;
01420         };
01421 
01422         // cl.exe wants this -- maybe it is right.
01423         template <template<class, class, template<class> class M, unsigned>
01424                   class, class, template<class> class S, unsigned>
01425         struct global_data : public plain_global_data
01426         {
01427             typedef global_data global_data_type;
01428         };
01429         template <template<class, class, template<class> class M, unsigned>
01430                   class TBASE, class ITL, template<class> class TEST>
01431         struct global_data<TBASE, ITL, TEST, 0> : public plain_global_data
01432         {
01433             // typedef to catch our copy constructor and assignment operator:
01434             typedef global_data global_data_type;
01435 
01436             BitArray<size<ITL>::of> bit_set;
01437 
01438             void clear() { bit_set.clear(); }
01439             template <unsigned pos>
01440             void set_bit() { bit_set.template set<pos>(); }
01441             template <unsigned pos>
01442             bool is_bit_set() const { return bit_set.template test<pos>(); }
01443         };
01444     };
01445 
01446     template <class ACX, class T, class Z>
01447     struct virtual_chooser: public cond_chooser_plain
01448     {
01449         template <class V, unsigned pos = 0>
01450         struct use
01451         {
01452             typedef tuple_entry<ACX, T, Z, V> type;
01453         };
01454     };
01455 
01456     template <class T> struct set_exec
01457     {
01458         template <class ACX>
01459         static void exec(ACX & x)
01460         {
01461             x.template set<T>();
01462         }
01463     };
01464 
01465     template <class ACX, class T, class Z>
01466     struct cond_virtual_chooser: public cond_chooser_plain
01467     {
01468         template <class V, unsigned pos = 0>
01469         struct use
01470         {
01471             typedef cond_tuple_entry<ACX, T, Z, V, pos> type;
01472         };
01473 
01474         template <class, template <class> class TEST>
01475         struct exec_op
01476         {
01477             template <class TUPLE, class B, class TBASE>
01478             static void exec(TUPLE & tuple, B & binder, const TBASE &)
01479             {
01480                 for (unsigned i = 0; i != tuple.execs.size; ++i)
01481                     binder(*tuple.execs.pointers[i]);
01482             }
01483             template <class TUPLE, class B, class TBASE>
01484             static void call(TUPLE & tuple, B & binder, const TBASE &)
01485             {
01486                 for (unsigned i = 0; i != tuple.callers.size; ++i)
01487                     binder.call(*tuple.callers.pointers[i]);
01488             }
01489         };
01490         // cl.exe wants this -- maybe it is right.
01491         template <template<class, class, template<class> class M, unsigned>
01492                   class, class, template<class> class S, unsigned>
01493         struct global_data : public plain_global_data
01494         {
01495             typedef global_data global_data_type;
01496         };
01497 
01498         template <class ITL>
01499         struct global_data_pointers // weak pointers
01500         {
01501             typedef typename Z::template member_base_type<ACX, T>* pointer_type;
01502             static const unsigned array_len = size<ITL>::of;
01503 
01504             unsigned     orders  [array_len]; // consciously use two arrays
01505             unsigned     size;
01506             pointer_type pointers[array_len];
01507 
01508             void clear()
01509             {
01510                 size = 0;
01511             }
01512             global_data_pointers()
01513             {
01514                 clear();
01515             }
01516             unsigned* end(unsigned* = 0)
01517             {
01518                 return orders + size;
01519             }
01520             pointer_type* end(pointer_type*)
01521             {
01522                 return pointers + size;
01523             }
01524             template <class E>
01525             void make_room(E* i)
01526             {
01527                 std::copy_backward(i, end(i), end(i) + 1);
01528             }
01529             typedef std::pair<unsigned*, pointer_type*> finder;
01530             bool find(unsigned pos, finder & found)
01531             {
01532                 found.first  = std::lower_bound(orders, end(), pos);
01533                 found.second = pointers + (found.first - orders);
01534                 return found.first != end() && *found.first == pos;
01535             }
01536             void add(pointer_type p, unsigned pos)
01537             {
01538                 // merge pointer according to its topological sort order
01539                 finder found;
01540                 if (find(pos, found))
01541                     return;
01542                 make_room(found.first);
01543                 make_room(found.second);
01544                 ++size;
01545                 *found.first  = pos;
01546                 *found.second = p;
01547             }
01548             void reassign(pointer_type p, unsigned pos)
01549             {
01550                 // replace pointers -- the present values still belong to
01551                 // the old tuple object that was copied from
01552                 finder found;
01553                 if (find(pos, found))
01554                     *found.second = p;
01555             }
01556         };
01557         template <template<class, class, template<class> class M, unsigned>
01558                   class TBASE, class ITL, template<class> class TEST>
01559         struct global_data<TBASE, ITL, TEST, 0>
01560         {
01561             // typedef to catch our copy constructor and assignment operator:
01562             typedef global_data global_data_type;
01563             // the derived class:
01564             typedef TBASE<ITL, cond_virtual_chooser, TEST, 0> crtp_type;
01565 
01566             typedef global_data_pointers<ITL>        ptrs_type;
01567             typedef typename ptrs_type::pointer_type pointer_type;
01568             ptrs_type callers;
01569             ptrs_type execs;
01570 
01571             template <class V>
01572             void add(pointer_type p, unsigned pos)
01573             {
01574                 execs.add(p, pos);
01575                 if (TEST<V>::value)
01576                     callers.add(p, pos);
01577             }
01578             void reassign(pointer_type p, unsigned pos)
01579             {
01580                 execs.  reassign(p, pos);
01581                 callers.reassign(p, pos);
01582             }
01583 
01584             template <class V>
01585             struct reassign_op
01586             {
01587                 static void exec(crtp_type & tuple)
01588                 {
01589                     tuple.template ref<V>().reassign(tuple);
01590                 }
01591             };
01592 
01593             void reassign()
01594             {
01595                 for_all<ITL, reassign_op>(static_cast<crtp_type &>(*this));
01596             }
01597         };
01598     };
01599 
01600 
01601     template <class ITL, class Q = plain_chooser,
01602               template<class> class TEST = true_test, unsigned index = 0>
01603     struct tuple_base
01604         : public Q::template global_data<tuple_base, ITL, TEST, index>
01605     {
01606         typedef typename tuple_base::global_data_type global_data_base_type;
01607         typedef nil derived_type; // dummy declaration for static_cast_2<>
01608         typedef tuple_base tuple_type;
01609         typedef ITL        list_type;
01610 
01611         // use the original types from the list to find tuple members via ref():
01612         typedef typename ITL::first                            finder_type;
01613         typedef typename ITL::rest                             rest_list_type;
01614 
01615         typedef tuple_base<rest_list_type, Q, TEST, index + 1> rest_type;
01616 
01617         // use policy class Q to annotate the types of the type list ITL
01618         // for use as members of the tuple:
01619         // -- the actually stored type
01620         typedef typename ITL::first                            ref_finder_type;
01621         typedef typename Q::template use<ref_finder_type,
01622                                          index>::type          first_type;
01623         first_type first;
01624         rest_type  rest;
01625 
01626         template <class T>
01627         struct has_element
01628         {
01629             static const bool value = contains<T, ITL>::value;
01630         };
01631 
01632         template <unsigned pos>
01633         typename at_finder<pos, tuple_base>::type & at()
01634         {
01635             return at_finder<pos, tuple_base>::at(*this);
01636         }
01637 
01638         template <class T>
01639         struct ref_returns
01640         {
01641             typedef ref_finder<T, tuple_base>     finder;
01642             typedef typename finder::type         ref_finder_type;
01643             typedef       ref_finder_type &       type;
01644             typedef const ref_finder_type & const_type;
01645         };
01646         template <class T>
01647         typename ref_returns<T>::type
01648         ref()
01649         {
01650             return ref_returns<T>::finder::ref(*this);
01651         }
01652         template <class T>
01653         typename ref_returns<T>::const_type
01654         ref() const
01655         {
01656             return ref_returns<T>::finder::ref(*this);
01657         }
01658 
01659         template <class V>
01660         bool is_set() const
01661         {
01662             return Q::template is_set(this->template ref<V>(), *this);
01663         }
01664         template <class RV>
01665         void set_if_not(RV & rv)
01666         {
01667             if (! Q::template is_set(rv, *this))
01668                 Q::template set(rv, *this);
01669         }
01670         // recursively set all the cond_val::is_set bits of the depended-on
01671         // types, or, respectively, take equivalent action.
01672         template <class V>
01673         void set()
01674         {
01675             set_if_not(this->template ref<V>());
01676             for_all_used<V, set_exec>(*this);
01677         }
01678         // transfer the set bits of *this to another tuple t2:
01679         // (ITL must be a subset of ITL2.)
01680         template <class ITL2, class Q2, template<class> class TEST2>
01681         void transfer_set_to(tuple_base<ITL2, Q2, TEST2> & t2) const
01682         {
01683             if (is_set<ref_finder_type>())
01684                 t2.template set<ref_finder_type>();
01685             rest.transfer_set_to(t2);
01686         }
01687 
01688         // policy-based application of operator()
01689         template <class B, class TBASE>
01690         void exec_bound_op(B & binder, const TBASE & z)
01691         {
01692             Q::template exec_op<list_type, true_test>::exec(*this, binder, z);
01693         }
01694         template <class B>
01695         void exec_bound(B & binder)
01696         {
01697             exec_bound_op(binder, *this);
01698         }
01699 
01700         void operator()()
01701         {
01702             binder_0 binder;
01703             exec_bound(binder);
01704         }
01705 
01706         template <class A>
01707         void operator()(const A & v)
01708         {
01709             binder_1<const A &> binder(v);
01710             exec_bound(binder);
01711         }
01712         template <class A>
01713         void operator()(A & v)
01714         {
01715             binder_1<A &> binder(v);
01716             exec_bound(binder);
01717         }
01718         template <class A>
01719         void operator()(A & v) const
01720         {
01721             binder_1<A &> binder(v);
01722             exec_bound(binder);
01723         }
01724 
01725         template <class A, class B>
01726         void operator()(const A & v, const B & w)
01727         {
01728             binder_2<const A &, const B &> binder(v, w);
01729             exec_bound(binder);
01730         }
01731         template <class A, class B>
01732         void operator()(A & v, const B & w)
01733         {
01734             binder_2<A &, const B &> binder(v, w);
01735             exec_bound(binder);
01736         }
01737         template <class A, class B>
01738         void operator()(A & v, const B & w) const
01739         {
01740             binder_2<A &, const B &> binder(v, w);
01741             exec_bound(binder);
01742         }
01743 
01744         template <class A, class B, class C>
01745         void operator()(const A & v, const B & w, const C & x)
01746         {
01747             binder_3<const A &, const B &, const C &> binder(v, w, x);
01748             exec_bound(binder);
01749         }
01750         template <class A, class B, class C>
01751         void operator()(A & v, const B & w, const C & x)
01752         {
01753             binder_3<A &, const B &, const C &> binder(v, w, x);
01754             exec_bound(binder);
01755         }
01756         template <class A, class B, class C>
01757         void operator()(A & v, const B & w, const C & x) const
01758         {
01759             binder_3<A &, const B &, const C &> binder(v, w, x);
01760             exec_bound(binder);
01761         }
01762 
01763         // policy-based application of call()
01764         template <class B, class TBASE>
01765         void call_bound_op(B & binder, const TBASE & z)
01766         {
01767             Q::template exec_op<list_type, TEST>::call(*this, binder, z);
01768         }
01769         template <class B>
01770         void call_bound(B & binder)
01771         {
01772             call_bound_op(binder, *this);
01773         }
01774 
01775         template <class A, class B>
01776         void call(const A & v, const B & w)
01777         {
01778             binder_2<const A &, const B &> binder(v, w);
01779             call_bound(binder);
01780         }
01781         template <class A, class B>
01782         void call(A & v, const B & w)
01783         {
01784             binder_2<A &, const B &> binder(v, w);
01785             call_bound(binder);
01786         }
01787         template <class A, class B>
01788         void call(A & v, const B & w) const
01789         {
01790             binder_2<A &, const B &> binder(v, w);
01791             call_bound(binder);
01792         }
01793 
01794         template <class A, class B, class C>
01795         void call(const A & v, const B & w, const C & x)
01796         {
01797             binder_3<const A &, const B &, const C &> binder(v, w, x);
01798             call_bound(binder);
01799         }
01800         template <class A, class B, class C>
01801         void call(A & v, const B & w, const C & x)
01802         {
01803             binder_3<A &, const B &, const C &> binder(v, w, x);
01804             call_bound(binder);
01805         }
01806         template <class A, class B, class C>
01807         void call(A & v, const B & w, const C & x) const
01808         {
01809             binder_3<A &, const B &, const C &> binder(v, w, x);
01810             call_bound(binder);
01811         }
01812 
01813         // the possible reassign() of global data requires handmade copies here
01814         tuple_base() {}
01815         tuple_base(const tuple_base & x)
01816             : global_data_base_type(x), first(x.first), rest(x.rest)
01817         {
01818             this->reassign();
01819         }
01820         tuple_base & operator=(const tuple_base & x)
01821         {
01822             global_data_base_type::operator=(x);
01823             first = x.first;
01824             rest  = x.rest;
01825             this->reassign();
01826             return *this;
01827         }
01828     };
01829     template <class Q, template <class> class TEST, unsigned index>
01830     struct tuple_base<nil, Q, TEST, index>
01831     {
01832         template <class>
01833         struct has_element
01834         {
01835             static const bool value = false;
01836         };
01837         template <class B, class TBASE>
01838         void exec_bound_op(B &, const TBASE &) {}
01839         template <class B, class TBASE>
01840         void call_bound_op(B &, const TBASE &) {}
01841         template <class ITL2, class Q2, template<class> class TEST2>
01842         void transfer_set_to(tuple_base<ITL2, Q2, TEST2> &) const {}
01843     };
01844 
01845     template <class V, class L, class A, class B>
01846     struct choose_tuple
01847     {
01848         static const bool value = contains<V, L>::value;
01849         typedef typename IfBool<value, A, B>::type type;
01850         static type & at(A & a, B & b)
01851         {
01852             return choose_type<value>::at(a, b);
01853         }
01854         static const type & at(const A & a, const B & b)
01855         {
01856             return choose_type<value>::at(a, b);
01857         }
01858 
01859         typedef typename type::template ref_returns<V>::      type
01860             ref_type;
01861         typedef typename type::template ref_returns<V>::const_type
01862             const_ref_type;
01863 
01864         ref_type
01865         static ref(A & a, B & b)
01866         {
01867             return at(a, b).template ref<V>();
01868         }
01869         const_ref_type
01870         static ref(const A & a, const B & b)
01871         {
01872             return at(a, b).template ref<V>();
01873         }
01874     };
01875 
01876     template <class ITL, template<class> class TEST = true_test>
01877     struct tuple : public tuple_base<ITL, plain_chooser, TEST> {};
01878 
01879     template <class ITL, template<class> class TEST = true_test>
01880     struct cond_tuple_plain
01881         : public tuple_base<ITL, cond_chooser_plain, TEST> {};
01882 
01883     template <class ITL, template<class> class TEST = true_test>
01884     struct cond_tuple : public tuple_base<ITL, cond_chooser, TEST> {};
01885 
01886     template <class ITL, template<class> class TEST = true_test>
01887     struct bit_cond_tuple : public tuple_base<ITL, bit_cond_chooser, TEST> {};
01888 
01889     template <class ITL, class ACX, class T, class Z,
01890               template<class> class TEST = true_test>
01891     struct virtual_tuple_base
01892         : public tuple_base<ITL, virtual_chooser<ACX, T, Z>, TEST> {};
01893 
01894     template <template <class, class> class ACXTT, class T,
01895               class Z = simple_member_dispatch>
01896     struct virtual_tuple
01897     {
01898         template <class ITL, template<class> class TEST = true_test>
01899         struct type
01900             : public virtual_tuple_base<ITL, ACXTT<T, ITL>, T, Z, TEST> {};
01901     };
01902 
01903     template <class ITL, class ACX, class T, class Z,
01904               template<class> class TEST = true_test>
01905     struct cond_virtual_tuple_base
01906         : public tuple_base<ITL, cond_virtual_chooser<ACX, T, Z>, TEST>
01907     {
01908         typedef ACX derived_type;
01909     };
01910 
01911     template <template <class, class> class ACXTT, class T,
01912               class Z = simple_member_dispatch>
01913     struct cond_virtual_tuple
01914     {
01915         template <class ITL, template<class> class TEST = true_test>
01916         struct type
01917             : public cond_virtual_tuple_base<ITL, ACXTT<T, ITL>, T, Z, TEST> {};
01918     };
01919 
01920 } // namespace type_lists
01921 
01922 // mask cl.exe shortcomings [end]
01923 #if defined(_MSC_VER)
01924 #pragma warning( pop )
01925 #endif
01926 
01927 } // namespace vigra
01928 
01929 #endif // VIGRA_TYPE_LISTS_HXX

© 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.9.0 (Tue Nov 6 2012)