cartesian_product.h 3.7 KB
Newer Older
1
2
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#ifndef _MCQTL_CACHE_CARTESIAN_PRODUCT_H_
#define _MCQTL_CACHE_CARTESIAN_PRODUCT_H_

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

template <typename... ITEMS>
    struct cartesian_product {
        typedef typename make_sequence<sizeof...(ITEMS)>::type indices;
        template <typename X> struct to_bool { typedef bool type; };
        std::tuple<iterator_context<ITEMS>...> iter;
        bool at_end;
        cartesian_product() : iter(), at_end(true) {}
        cartesian_product(const ITEMS&... x)
            : iter(x...), at_end(false)
        {}
        cartesian_product(const std::tuple<ITEMS...>& x)
            : iter(x), at_end(false)
        {}
        cartesian_product(const cartesian_product<ITEMS...>& cp)
            : iter(cp.iter), at_end(cp.at_end)
        {}

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

        std::tuple<typename item_iterator<ITEMS>::value_type...> operator * () const
        {
            if (!at_end) {
                return getter::process(iter);
            }
            throw 0;
        }

        struct iterator {
            typedef std::tuple<typename item_iterator<ITEMS>::value_type...> value_type;
            cartesian_product<ITEMS...> cp;

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

            iterator& operator ++ () { cp.next(); }
            iterator& operator ++ (int) { cp.next(); }
            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;
        }

        iterator begin() { std::cout << "BEGIN" << std::endl; return {*this}; }
        iterator end() { std::cout << "END" << std::endl; return {{}}; }
    };

}

#endif