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

vigra/type_lists.hxx |

    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)