cartesian_product.h 6.65 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
#ifndef _SPEL_CACHE_CARTESIAN_PRODUCT_H_
#define _SPEL_CACHE_CARTESIAN_PRODUCT_H_
20
21
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

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;
        }
    };

65
66
struct cartesian_product_at_end_exception : std::exception {};

67
68
69
70
template <typename... ITEMS>
    struct cartesian_product {
        typedef typename make_sequence<sizeof...(ITEMS)>::type indices;
        template <typename X> struct to_bool { typedef bool type; };
71
72
        typedef std::tuple<iterator_context<ITEMS>...> iter_type;
        iter_type iter;
73
74
75
76
        bool at_end;
        cartesian_product() : iter(), at_end(true) {}
        cartesian_product(const ITEMS&... x)
            : iter(x...), at_end(false)
77
        { _debug_types(); }
78
79
        cartesian_product(const std::tuple<ITEMS...>& x)
            : iter(x), at_end(false)
80
        { _debug_types(); }
81
82
        cartesian_product(const cartesian_product<ITEMS...>& cp)
            : iter(cp.iter), at_end(cp.at_end)
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
        { _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)>()();
        }
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

        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;
        }

123
124
125
126
127
128
129
130
131
        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
132
133
134
135
136
137
138

                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)...);
                    }
139
140
            };

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

Damien Leroux's avatar
Damien Leroux committed
150
151
152
153
154
155
156
157
158
        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();
            }

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

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

165
166
            iterator& operator ++ () { cp.next(); return *this; }
            iterator& operator ++ (int) { cp.next(); return *this; }
167
168
169
170
171
172
173
174
175
176
177
178
            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;
        }

179
180
        iterator begin() { return {*this}; }
        iterator end() { return {{}}; }
181
182
    };

183
184
185
186
187
188
189
190
191
192
193
194
/*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};
    }

195
196
197
198
}

#endif