cartesian_product.h 5.83 KB
Newer Older
1
2
#ifndef _SPEL_CACHE_CARTESIAN_PRODUCT_H_
#define _SPEL_CACHE_CARTESIAN_PRODUCT_H_
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

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

48
49
struct cartesian_product_at_end_exception : std::exception {};

50
51
52
53
template <typename... ITEMS>
    struct cartesian_product {
        typedef typename make_sequence<sizeof...(ITEMS)>::type indices;
        template <typename X> struct to_bool { typedef bool type; };
54
55
        typedef std::tuple<iterator_context<ITEMS>...> iter_type;
        iter_type iter;
56
57
58
59
        bool at_end;
        cartesian_product() : iter(), at_end(true) {}
        cartesian_product(const ITEMS&... x)
            : iter(x...), at_end(false)
60
        { _debug_types(); }
61
62
        cartesian_product(const std::tuple<ITEMS...>& x)
            : iter(x), at_end(false)
63
        { _debug_types(); }
64
65
        cartesian_product(const cartesian_product<ITEMS...>& cp)
            : iter(cp.iter), at_end(cp.at_end)
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
        { _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)>()();
        }
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

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

106
107
108
109
110
111
112
113
114
        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
115
116
117
118
119
120
121

                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)...);
                    }
122
123
            };

124
125
126
        std::tuple<typename item_iterator<ITEMS>::value_type...> operator * () const
        {
            if (!at_end) {
127
128
                /*return getter::process(iter);*/
                return _get<indices>::get(iter);
129
            }
130
            throw cartesian_product_at_end_exception();
131
132
        }

Damien Leroux's avatar
Damien Leroux committed
133
134
135
136
137
138
139
140
141
        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();
            }

142
143
144
145
146
147
        struct iterator {
            typedef std::tuple<typename item_iterator<ITEMS>::value_type...> value_type;
            cartesian_product<ITEMS...> cp;

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

148
149
            iterator& operator ++ () { cp.next(); return *this; }
            iterator& operator ++ (int) { cp.next(); return *this; }
150
151
152
153
154
155
156
157
158
159
160
161
            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;
        }

162
163
        iterator begin() { return {*this}; }
        iterator end() { return {{}}; }
164
165
    };

166
167
168
169
170
171
172
173
174
175
176
177
/*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};
    }

178
179
180
181
}

#endif