C++

Forum

 
Returning a template pack nested N-dimensionally in another pack

prestokeys (357)
To explain this question, let me jump straight to main() and my current output:
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
 
struct Base {};
struct A : Base { A() {std::cout << "A";} };
struct B : Base { B() {std::cout << "B";} };
struct C : Base { C() {std::cout << "C";} };
struct D : Base { D() {std::cout << "D";} };
struct E : Base { E() {std::cout << "E";} };
struct F : Base { F() {std::cout << "F";} };
struct G : Base { G() {std::cout << "G";} };

template <int KEY, typename... RANGE> struct Map {};  // one-to-many map (mapping KEY to RANGE...)
template <typename...> struct Data {};

using Database1 = Data<  Map<0, A,B,C>,  Map<1, D,E,F,G>  >;

using Database2 = Data<
	Map<0,
		Map<0, A,B,C,D,E>,
		Map<1, F,G>
	>,
	Map<1,
		Map<0, A,B>,
		Map<1, C,D,E,F,G>
	>,
	Map<2,
		Map<0, A,B,C,D>,
		Map<1, E,F,G>
	>
>;

int main() {
	std::cout << "From Database1:" << std::endl;
	executeOneDimension<0>();
	executeOneDimension<1>();
	
	std::cout << "\nFrom Database2:" << std::endl;
	executeTwoDimension<0,0>();
	executeTwoDimension<0,1>();
	executeTwoDimension<1,0>();
	executeTwoDimension<1,1>();
	executeTwoDimension<2,0>();
	executeTwoDimension<2,1>();
	
//	How to generalize to higher dimensions???
}


Output:
1
2
3
4
5
6
7
8
9
10
11
 
From Database1:
ABC
DEFG

From Database2:
ABCDE
FG
AB
CDEFG
ABCD
EFG
prestokeys (357)
Here is my code for one-dimension:
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
 
#include <iostream>
#include <tuple>

template <std::size_t...> struct index_sequence {};

template <std::size_t N, std::size_t... Is>
struct make_index_sequence_helper : make_index_sequence_helper<N-1, N-1, Is...> {};

template <std::size_t... Is>
struct make_index_sequence_helper<0, Is...> {
    using type = index_sequence<Is...>;
};

template <std::size_t N>
using make_index_sequence = typename make_index_sequence_helper<N>::type;

struct Base {};
struct A : Base { A() {std::cout << "A";} };
struct B : Base { B() {std::cout << "B";} };
struct C : Base { C() {std::cout << "C";} };
struct D : Base { D() {std::cout << "D";} };
struct E : Base { E() {std::cout << "E";} };
struct F : Base { F() {std::cout << "F";} };
struct G : Base { G() {std::cout << "G";} };

template <int KEY, typename... RANGE> struct Map {};  // one-to-many map (mapping KEY to RANGE...)
template <typename...> struct Data {};
template <typename...> struct Foo {};

using Database1 = Data<  Map<0, A,B,C>,  Map<1, D,E,F,G>  >;

template <typename FIRST, typename... REST>
struct Foo<FIRST, REST...> {
	void operator()() {
		FIRST* x = new FIRST;
		// Do whatever with x.
		delete x;
		Foo<REST...>()();
	}
};

template <>
struct Foo<> {
	void operator()() {std::cout << "\n";}
};

template <typename D, int N>
struct RangeOneDimension;

template <template <typename...> class DATABASE
        , template <int, typename...> class MAP
        , typename... TYPES, typename... MAPS, int N>
struct RangeOneDimension<DATABASE<MAP<N, TYPES...>, MAPS...>, N> {
    using type = std::tuple<TYPES...>;
};

template <template <typename...> class DATABASE
        , template <int, typename...> class MAP
        , typename... RANGE, typename... MAPS, int KEY, int N>
struct RangeOneDimension<DATABASE<MAP<KEY, RANGE...>, MAPS...>, N> : RangeOneDimension<DATABASE<MAPS...>, N> {};

template <typename Tuple, std::size_t... Is>
void executeOneDimension (index_sequence<Is...>) {  // If using C++14, can use simply std::index_sequence instead of index_sequence.
	Foo<typename std::tuple_element<Is, Tuple>::type...>()();
}

template <int N>
void executeOneDimension() {
	using Tuple = typename RangeOneDimension<Database1, N>::type;
	return executeOneDimension<Tuple>(make_index_sequence<std::tuple_size<Tuple>::value>{});
}

int main() {
	std::cout << "From Database1:" << std::endl;
	executeOneDimension<0>();
	executeOneDimension<1>();
}


Output:
1
2
3
 
From Database1:
ABC
DEFG
Last edited on
prestokeys (357)
Here is my code for 2 dimensions:
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
 
#include <iostream>
#include <tuple>

template <std::size_t...> struct index_sequence {};

template <std::size_t N, std::size_t... Is>
struct make_index_sequence_helper : make_index_sequence_helper<N-1, N-1, Is...> {};

template <std::size_t... Is>
struct make_index_sequence_helper<0, Is...> {
    using type = index_sequence<Is...>;
};

template <std::size_t N>
using make_index_sequence = typename make_index_sequence_helper<N>::type;

struct Base {};
struct A : Base { A() {std::cout << "A";} };
struct B : Base { B() {std::cout << "B";} };
struct C : Base { C() {std::cout << "C";} };
struct D : Base { D() {std::cout << "D";} };
struct E : Base { E() {std::cout << "E";} };
struct F : Base { F() {std::cout << "F";} };
struct G : Base { G() {std::cout << "G";} };

template <int KEY, typename... RANGE> struct Map {};
template <typename...> struct Data {};
template <typename...> struct Foo {};

using Database2 = Data<
	Map<0,
		Map<0, A,B,C,D,E>,
		Map<1, F,G>
	>,
	Map<1,
		Map<0, A,B>,
		Map<1, C,D,E,F,G>
	>,
	Map<2,
		Map<0, A,B,C,D>,
		Map<1, E,F,G>
	>
>;

template <typename FIRST, typename... REST>
struct Foo<FIRST, REST...> {
	void operator()() {
		FIRST* x = new FIRST;
		// Do whatever with x.
		delete x;
		Foo<REST...>()();
	}
};

template <>
struct Foo<> {
	void operator()() {std::cout << "\n";}
};

template <typename D, int S, int N>
struct RangeTwoDimension;

template <template <typename...> class DATABASE, 
		  template <int, typename...> class MAP2,
		  template <int, typename...> class MAP1,
		  int S, int N, typename... TYPES, typename... MAPS1, typename... MAPS2>
struct RangeTwoDimension<DATABASE<MAP2<S, MAP1<N, TYPES...>, MAPS1...>, MAPS2...>, S, N> {
    using type = std::tuple<TYPES...>;
};

template <template <typename...> class DATABASE, 
		  template <int, typename...> class MAP2,
		  template <int, typename...> class MAP1,
		  int S, int N, int KEY, typename... RANGE, typename... MAPS1, typename... MAPS2>
struct RangeTwoDimension<DATABASE<MAP2<S, MAP1<KEY, RANGE...>, MAPS1...>, MAPS2...>, S, N> : RangeTwoDimension<DATABASE<MAP2<S, MAPS1...>, MAPS2...>, S, N> {};

template <template <typename...> class DATABASE, 
		  template <int, typename...> class MAP2,
		  template <int, typename...> class MAP1,
	      int S, int SS, int N, int KEY, typename... RANGE, typename... MAPS1, typename... MAPS2>
struct RangeTwoDimension<DATABASE<MAP2<S, MAP1<KEY, RANGE...>, MAPS1...>, MAPS2...>, SS, N> : RangeTwoDimension<DATABASE<MAPS2...>, SS, N> {};

template <int S, int N, typename Tuple, std::size_t... Is>
void executeTwoDimension (index_sequence<Is...>) {
	Foo<typename std::tuple_element<Is, Tuple>::type...>()();
}

template <int S, int N>
void executeTwoDimension() {
	using Tuple = typename RangeTwoDimension<Database2, S, N>::type;
	executeTwoDimension<S, N, Tuple>(make_index_sequence<std::tuple_size<Tuple>::value>{});
}

int main() {
	std::cout << "From Database2:" << std::endl;
	executeTwoDimension<0,0>();
	executeTwoDimension<0,1>();
	executeTwoDimension<1,0>();
	executeTwoDimension<1,1>();
	executeTwoDimension<2,0>();
	executeTwoDimension<2,1>();
}


Ouput:
1
2
3
4
5
6
7
 
From Database2:
ABCDE
FG
AB
CDEFG
ABCD
EFG

Everything compile-time constructs by the way. I could do the same thing for 3-dimensional, and 4-dimensional maps, but the effort grows fast as n gets larger. How to generalize all this to n-dimensions so that using any value for n will be effortless???

The magical function I'm seeking should probably look something like:
1
2
3
4
5
 
template <int... I>
void executeNDimension() {
	using Tuple = typename RangeNDimension<DatabaseN, I...>::type;
	return executeNDimension<Tuple>(make_index_sequence<std::tuple_size<Tuple>::value>{});
}

with the elusive RangeNDimension being defined recursively somehow.
Last edited on
prestokeys (357)
Anyone? Your solution does not have to follow the pattern I followed above. They are there just to demonstrate my method, which I obviously cannot find a generalization to. Perhaps someone has their own (shorter) recursive method that follows a different method altogether?
JLBorges (13770)
boost::mpl has the functionality. (Wrap it if you want a custom interface.) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
#include <boost/mpl/map.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/at.hpp>

struct A {}; struct B {}; struct C {}; struct D {}; struct E {};
struct F { F() { std::cout << "F::constructor\n"; } };
struct G {}; struct H {};

int main()
{
    using namespace boost::mpl ;
    using my_map = map< pair< A, map< pair< B, map< pair< C, vector<E,G,H,F> > > > > >,
                        pair< int_<32>, map< pair< C, vector<E,F,G>   > > >
                      >;
    at< at< at< at< my_map, A >::type, B >::type, C >::type, int_<3> >::type{} ;
    at< at< at< my_map, int_<32> >::type, C >::type, int_<1> >::type{} ;
}

http://coliru.stacked-crooked.com/a/3f045a5709b9a197
prestokeys (357)
Thanks JLBorges. So I take it that finding a C++11 solution is too difficult? One would end up having to define a class similar to boost::mpl to solve using C++11? I thought that recursion could do it. I guess I'm wrong.
JLBorges (13770)
> So I take it that finding a C++11 solution is too difficult?
> One would end up having to define a class similar to boost::mpl to solve using C++11?

> Is there anyway using c++11 only?
> Or would that require defining a class that will simply end up doing the same thing as Boost mpl?

Yes. Boost mpl is written in C++.
This particular problem would require just a minuscule subset of what mpl has to offer.

The problem with that approach is that we would have to keep writing more and more code as the program evolves and additional requirements surface.
http://www.cplusplus.com/forum/general/136138/#msg725178
prestokeys (357)
Sorry for not being versed in Boost yet. I'm still trying to learn C++11 (and now C++14), after only a year and a half of starting C++. For sure Boost::mpl will be the first Boost class I will study when I'm ready for Boost.
JLBorges (13770)
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
 
#include <iostream>
#include <tuple>

template< typename... > struct typelist {};

template< unsigned int, typename... > struct atl {} ;
template< unsigned int N, typename... T > struct atl< N, typelist<T...> >
{ using type = typename std::tuple_element< N, std::tuple<T...> >::type ; };

template < typename, unsigned int...> struct at {};
template < typename T, unsigned int N > struct at<T,N> { using type = typename atl<N,T>::type ; };
template < typename T, unsigned int FIRST, unsigned int... REST > struct at<T,FIRST,REST...>
{ using type = typename at< typename at<T,FIRST>::type, REST... >::type ; };

struct A {}; struct B {}; struct C {}; struct D {}; struct E {};
struct F { F() { std::cout << "F::constructor\n"; } };
struct G {}; struct H {};

int main()
{

    using my_db = typelist<
                                typelist<A,C,D,F,H>,

                                typelist<
                                            typelist<A,B,C>,
                                            typelist<D,E,F,G,H>,
                                            typelist<B,D,F>
                                        >,

                                typelist<
                                            typelist< A, B, typelist<C,D,E,F,G,H>, G, H, int >,
                                            typelist<>
                                        >
                           > ;

    at< my_db, 0, 3 >::type() ; // F::constructor
    at< my_db, 1, 1, 2 >::type() ; // F::constructor
    at< my_db, 2, 0, 2, 3 >::type() ; // F::constructor
}

http://coliru.stacked-crooked.com/a/a9f49b5eae035159
prestokeys (357)
Thanks for translating to the more familiar C++11. All seems good!

I noticed that you changed my database structure from the form
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
using Database2 = Data<
	Map<0,
		Map<0, A,B,C,D,E>,
		Map<1, F,G>
	>,
	Map<1,
		Map<0, A,B>,
		Map<1, C,D,E,F,G>
	>,
	Map<2,
		Map<0, A,B,C,D>,
		Map<1, E,F,G>
	>
>;

to having each "range", e.g. A,B,C,D,E, wrapped in typelist. Which means that my original problem (with my apparently questionable database design) is still unsolved, with or without boost::mpl. But that is fine. Often solving a problem usually means coming up with a different design to begin with, as I've learned over the months.

But as a fun exercise, I will try to adapt your solution to handle my database design as in Database2 above, with nothing to lose if I fail.
Last edited on
prestokeys (357)
Inspired by JLBorges' method with his design, I've solved my original problem with my chosen design, and without using tuple or make_index_sequence even. Here it is for those who want to apply this technique to a similar n-dimensional problem:
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
#include <iostream>

struct A { A() {std::cout << "A";} };
struct B { B() {std::cout << "B";} };
struct C { C() {std::cout << "C";} };
struct D { D() {std::cout << "D";} };
struct E { E() {std::cout << "E";} };
struct F { F() {std::cout << "F";} };
struct G { G() {std::cout << "G";} };
struct H { H() {std::cout << "H";} };

template <int KEY, typename... RANGE> struct Map {};  // one-to-many map (mapping KEY to RANGE...)
template <typename...> struct Data {};

using Database1 = Data<  Map<0, A,B,C>,  Map<1, D,E,F,G>  >;

using Database2 = Data<
	Map<0,
		Map<0, A,B,C,D,E>,
		Map<1, F,G>
	>,
	Map<1,
		Map<0, A,B>,
		Map<1, C,D,E,F,G>
	>,
	Map<2,
		Map<0, A,B,C,D>,
		Map<1, E,F,G>
	>
>;

using Database3 = Data<
	Map<0,
		Map<0,
			Map<0, A,B,C,D>,
			Map<1, G,F,E>
		>,
		Map<1,
			Map<0, A,B,C>,
			Map<1, F,D>,
			Map<2, E,G>
		>,
		Map<2,
			Map<0, A,B,D>,
			Map<1, C,E,F,G>
		>
	>,
	Map<1,
		Map<0,
			Map<0, B,C,D,E>,
			Map<1, A,F,G>
		>,
		Map<1,
			Map<0, A,C>,
			Map<1, D,G>,
			Map<2, B,E>,
			Map<3, F,A,B>			
		>
	>,
	Map<2,
		Map<0,
			Map<0, A,B,C,D,E,F,G>,
			Map<1>
		>,
		Map<1>
	>
>;

template <typename, int...>
struct GetRange;

template <template <typename...> class DATA, template <int, typename...> class MAP, int N, int KEY, int... REST, typename... NESTED_MAPS, typename... MAPS>
struct GetRange<DATA<MAP<KEY, NESTED_MAPS...>, MAPS...>, N, REST...> : GetRange<DATA<MAPS...>, N, REST...> {};  
// If KEY != N, check the next map in MAPS... until KEY equals N.

template <template <typename...> class DATA, template <int, typename...> class MAP, int N, int... REST, typename... NESTED_MAPS, typename... MAPS>
struct GetRange<DATA<MAP<N, NESTED_MAPS...>, MAPS...>, N, REST...> : GetRange<MAP<N, NESTED_MAPS...>, N, REST...> {};  
// Here the key matches with N, so move into the first map in DATA.

template <template <int, typename...> class MAP, int N, int S, int KEY, int... REST, typename... NESTED_MAPS, typename... MAPS>
struct GetRange<MAP<N, MAP<KEY, NESTED_MAPS...>, MAPS...>, N, S, REST...> : GetRange<MAP<N, MAPS...>, N, S, REST...> {};  
// Search in MAPS... until KEY equals S.

template <template <int, typename...> class MAP, int N, int KEY, int... REST, typename... NESTED_MAPS, typename... MAPS>
struct GetRange<MAP<N, MAP<KEY, NESTED_MAPS...>, MAPS...>, N, KEY, REST...> : GetRange<MAP<KEY, NESTED_MAPS...>, KEY, REST...> {};  
// Outer and inner keys match, so move into the inner map.

template <template <int, typename...> class MAP, int N, typename... TYPES>
struct GetRange<MAP<N, TYPES...>, N> {  // End of recursion.
	using type = Data<TYPES...>;
};

template <typename...> struct DoWhatever {};  // Function object for testing only.

template <typename FIRST, typename... REST>
struct DoWhatever<FIRST, REST...> {
	void operator()() {
		FIRST* x = new FIRST;
		// Do whatever with x.
		delete x;
		DoWhatever<REST...>()();
	}
};

template <>
struct DoWhatever<> {
	void operator()() {std::cout << "\n";}
};

template <typename... TYPES>
void extractTemplatePackHelper (Data<TYPES...>&&) {
	DoWhatever<TYPES...>()();
}

template <typename DATABASE, int... I>
void extractTemplatePack() {
	extractTemplatePackHelper (typename GetRange<DATABASE, I...>::type{});
}

int main() {
	std::cout << "Database1:" << std::endl;
	extractTemplatePack<Database1, 0>();
	extractTemplatePack<Database1, 1>();
	std::cout << "-------------------\nDatabase2:" << std::endl;
	extractTemplatePack<Database2, 0,0>();
	extractTemplatePack<Database2, 0,1>();
	extractTemplatePack<Database2, 1,0>();
	extractTemplatePack<Database2, 1,1>();
	extractTemplatePack<Database2, 2,0>();
	extractTemplatePack<Database2, 2,1>();
	std::cout << "-------------------\nDatabase3:" << std::endl;
	extractTemplatePack<Database3, 0,0,0>();
	extractTemplatePack<Database3, 0,0,1>();
	extractTemplatePack<Database3, 0,1,0>();
	extractTemplatePack<Database3, 0,1,1>();
	extractTemplatePack<Database3, 0,1,2>();
	extractTemplatePack<Database3, 0,2,0>();
	extractTemplatePack<Database3, 0,2,1>();
	extractTemplatePack<Database3, 1,0,0>();
	extractTemplatePack<Database3, 1,0,1>();
	extractTemplatePack<Database3, 1,1,0>();
	extractTemplatePack<Database3, 1,1,1>();
	extractTemplatePack<Database3, 1,1,2>();
	extractTemplatePack<Database3, 1,1,3>();
	extractTemplatePack<Database3, 2,0,0>();
	extractTemplatePack<Database3, 2,0,1>();
	extractTemplatePack<Database3, 2,1>();
	std::cin.get();
}

Output:

Database1:
ABC
DEFG
-------------------
Database2:
ABCDE
FG
AB
CDEFG
ABCD
EFG
-------------------
Database3:
ABCD
GFE
ABC
FD
EG
ABD
CEFG
BCDE
AFG
AC
DG
BE
FAB
Last edited on
Topic archived. No new replies allowed.