cartesian_product.h 6.71 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* Spell-QTL  Software suite for the QTL analysis of modern datasets.
 * Copyright (C) 2016,2017  Damien Leroux <damien.leroux@inra.fr>, Sylvain Jasson <sylvain.jasson@inra.fr>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

18
19
20
#ifdef _SPEL_CACHE_CARTESIAN_PRODUCT_H_
#error "_SPEL_CACHE_CARTESIAN_PRODUCT_H_ already defined!"
#else
21
#define _SPEL_CACHE_CARTESIAN_PRODUCT_H_
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

namespace cache {

template <typename ITEM>
    using item_iterator = typename ITEM::iterator;

template <typename ITEM>
    struct iterator_context {
        typedef item_iterator<ITEM> iterator;
        item_iterator<ITEM> begin, end, cursor;
        iterator_context() : begin(), end(), cursor() {}
        iterator_context(const ITEM& i)
            : begin(i.begin()), end(i.end()), cursor(i.begin())
        {}
        iterator_context(const iterator_context<ITEM>& ic)
            : begin(ic.begin), end(ic.end), cursor(ic.cursor)
        {}
        iterator_context<ITEM>& operator = (const iterator_context<ITEM>& i)
        {
            begin = i.begin;
            end = i.end;
            cursor = i.cursor;
        }
        bool next() { ++cursor; if (cursor == end) { cursor = begin; return true; } return false; }
        typename item_iterator<ITEM>::value_type operator * () const { return *cursor; } 
    };

template <typename Item>
    struct do_next {
        typedef bool return_type;
        bool operator () (Item& i) const
        {
            return i.next();
        }
    };

template <typename Item>
    struct do_get {
        typedef typename std::remove_const<typename std::remove_reference<typename item_iterator<Item>::value_type>::type>::type return_type;
        return_type operator () (const Item& i) const
        {
            return *i;
        }
    };

67
68
struct cartesian_product_at_end_exception : std::exception {};

69
70
71
72
template <typename... ITEMS>
    struct cartesian_product {
        typedef typename make_sequence<sizeof...(ITEMS)>::type indices;
        template <typename X> struct to_bool { typedef bool type; };
73
74
        typedef std::tuple<iterator_context<ITEMS>...> iter_type;
        iter_type iter;
75
76
77
78
        bool at_end;
        cartesian_product() : iter(), at_end(true) {}
        cartesian_product(const ITEMS&... x)
            : iter(x...), at_end(false)
79
        { _debug_types(); }
80
81
        cartesian_product(const std::tuple<ITEMS...>& x)
            : iter(x), at_end(false)
82
        { _debug_types(); }
83
84
        cartesian_product(const cartesian_product<ITEMS...>& cp)
            : iter(cp.iter), at_end(cp.at_end)
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
        { _debug_types(); }

        template <int I, int N>
            struct _debug_types_impl {
                typedef typename std::tuple_element<I, std::tuple<ITEMS...>>::type etype;
                typedef typename std::tuple_element<I, iter_type>::type::iterator::value_type itype;
                void operator () () {
                    /*MSG_DEBUG('#' << I << ": " << typeid(etype).name() << " / " << typeid(itype).name());*/
                    _debug_types_impl<I + 1, N>()();
                }
            };

        template <int N>
            struct _debug_types_impl<N, N> {
                void operator () () {}
            };

        void _debug_types() const
        {
            _debug_types_impl<0, sizeof...(ITEMS)>()();
        }
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

        cartesian_product<ITEMS...>& operator = (const cartesian_product& cp)
        {
            iter = cp.iter;
            at_end = cp.at_end;
            return *this;
        }

        typedef typename indices::template with_backward_recursion<do_next,  iterator_context<ITEMS>...> nexter;
        typedef typename indices::template with_processor<do_get, iterator_context<ITEMS>...> getter;

        bool next()
        {
            if (!at_end) {
                at_end = nexter::process(iter);
            }
            return !at_end;
        }

125
126
127
128
129
130
131
132
133
        template <typename I> struct _get;
        template <int... Indices>
            struct _get<sequence<Indices...>> {
                static
                std::tuple<typename item_iterator<ITEMS>::value_type...>
                get(const std::tuple<iterator_context<ITEMS>...>& iter)
                {
                    return std::make_tuple(*std::get<Indices>(iter)...);
                }
Damien Leroux's avatar
Damien Leroux committed
134
135
136
137
138
139
140

                template <typename T>
                    static
                    void push_to(std::vector<T>& vec, const std::tuple<iterator_context<ITEMS>...>& iter)
                    {
                        vec.emplace_back(*std::get<Indices>(iter)...);
                    }
141
142
            };

143
144
145
        std::tuple<typename item_iterator<ITEMS>::value_type...> operator * () const
        {
            if (!at_end) {
146
147
                /*return getter::process(iter);*/
                return _get<indices>::get(iter);
148
            }
149
            throw cartesian_product_at_end_exception();
150
151
        }

Damien Leroux's avatar
Damien Leroux committed
152
153
154
155
156
157
158
159
160
        template <typename T>
            void push_to(std::vector<T>& vec)
            {
                if (!at_end) {
                    return _get<indices>::push_to(vec, iter);
                }
                throw cartesian_product_at_end_exception();
            }

161
162
163
164
165
166
        struct iterator {
            typedef std::tuple<typename item_iterator<ITEMS>::value_type...> value_type;
            cartesian_product<ITEMS...> cp;

            value_type operator * () const { return *cp; }

167
168
            iterator& operator ++ () { cp.next(); return *this; }
            iterator& operator ++ (int) { cp.next(); return *this; }
169
170
171
172
173
174
175
176
177
178
179
180
            bool operator == (const iterator& i) { return i.cp.at_end && cp.at_end; }
            bool operator != (const iterator& i) { return !(*this == i); }
        };

        cartesian_product<ITEMS...> copy() const
        {
            cartesian_product<ITEMS...> ret;
            ret.iter = iter;
            ret.at_end = at_end;
            return ret;
        }

181
182
        iterator begin() { return {*this}; }
        iterator end() { return {{}}; }
183
184
    };

185
186
187
188
189
190
191
192
193
194
195
196
/*template <typename... E>*/
    /*cartesian_product<E...> make_cartesian_product(E&&... x)*/
    /*{*/
        /*return {x...};*/
    /*}*/

template <typename... E>
    cartesian_product<E...> make_cartesian_product(const std::tuple<E...>& x)
    {
        return {x};
    }

197
198
199
200
}

#endif