C++

Forum

 
make_indices (composition)

prestokeys (357)
Suppose:

•make_pack_indices<START, END>::type is the type pack_indices<START, START+1, START+2, ..., END-1>

•make_reverse_indices<std::size_t SIZE>::type is the type pack_indices<SIZE-1, SIZE-2, ..., 2, 1, 0>

•make_rotated_indices<SIZE, SHIFT>::type is the type pack_indices<SHIFT, SHIFT+1, ..., SIZE-1, 0, 1, 2, ..., SHIFT-1>

•make_alternating_indices<SIZE, START, INTERVAL>::type is the type pack_indices<START, START + INTERVAL, START + 2 * INTERVAL, ...> until the largest index less than START is reached.


How do I compose these (using indices directly, and not resorting to conversion to tuples)? For example, suppose
A = make_reverse_indices<5>
B = make_rotated_indices<5,2>
C = make_pack_indices<1,4>

Then the composition of these, in the order A,B,C, should result in

pack_indices<4,3,2,1,0> -> pack_indices<2,1,0,4,3> -> pack_indices<1,0,4>,

thus giving pack_indices<1,0,4> as the final output.

The composition, of course, must use A,B,C (or some sort of functional conversions of these) as parameters.

Here is an application. Suppose we have the argument pack

('a', 3.14 , 5, "home", '!', 4.5, "car", 20, 0.5, 'b'). We can reverse this using make_reverse_indices<10>, and we can rotate it to the left by 3 using make_rotated_indices<10,3>. But suppose I want to reverse the pack followed by rotating to the left by 3. Instead of manually doing one followed by the other, I want to define a compose struct that will take make_reverse_indices<10> and make_rotated_indices<10,3> (or something related to them) as parameters and give the desired result all in one go, which would be

("car", 4.5, '!', "home", 5, 3.14, 'a', 'b', 0.5, 20)

Here is the code I already have, in case anyone needs it for testing (the structs themselves have already been tested thoroughly):

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
 
#include <iostream>
#include <string>
#include <tuple>

template<std::size_t...>
struct pack_indices
{
    using type = pack_indices;
};

constexpr int positiveModulo(int i, int n)
{
    return (i % n + n) % n;
}

template<std::size_t START, std::size_t END, std::size_t... INDICES>
struct make_indices : make_indices<START + 1, END, INDICES..., START>
{};

template<std::size_t END, std::size_t... INDICES>
struct make_indices<END, END, INDICES...> : pack_indices <INDICES...>
{};


template<std::size_t SIZE, std::size_t... INDICES>
struct make_reverse_indices : make_reverse_indices<SIZE - 1, INDICES..., SIZE - 1>
{};

template<std::size_t... INDICES>
struct make_reverse_indices<0, INDICES...> : pack_indices<INDICES...>
{};


template<std::size_t SIZE, std::size_t SHIFT, std::size_t SHIFT_, std::size_t... INDICES> 
struct make_rotated_indices_helper
    : make_rotated_indices_helper<SIZE, SHIFT, SHIFT_ + 1, INDICES..., positiveModulo(SHIFT + SHIFT_, SIZE)>
{};

template<std::size_t SIZE, std::size_t SHIFT, std::size_t...INDICES>
struct make_rotated_indices_helper<SIZE, SHIFT, SIZE, INDICES...> : pack_indices<INDICES...>
{};

template<std::size_t SIZE, std::size_t SHIFT, std::size_t... INDICES>
struct make_rotated_indices
{
    using type = make_rotated_indices_helper<SIZE, SHIFT, 0, INDICES...>;
};

template<std::size_t SIZE, std::size_t START, std::size_t INTERVAL, std::size_t NUM_LEFT, std::size_t... INDICES>
    struct make_alternating_indices_helper
        : make_alternating_indices_helper<SIZE, START + INTERVAL, INTERVAL, NUM_LEFT - 1, INDICES..., positiveModulo(START, SIZE)>
    {};

template<std::size_t SIZE, std::size_t START, std::size_t INTERVAL, std::size_t... INDICES>
struct make_alternating_indices_helper<SIZE, START, INTERVAL, 0, INDICES...>
    : pack_indices<INDICES...>
{};

template<std::size_t SIZE, std::size_t START, std::size_t INTERVAL, std::size_t... INDICES>
struct make_alternating_indices 
{
    using type = make_alternating_indices_helper<SIZE, START, INTERVAL, (SIZE - 1) / INTERVAL + 1>;
};

// Testing
namespace Pack 
{
    template<typename LAST>
    void print(LAST && last)
    {
        std::cout << std::forward<LAST>(last) << std::endl;
    }

    template<typename FIRST, typename... REST>
    void print(FIRST && first, REST&&... rest)
    {
        std::cout << std::forward<FIRST>(first) << ", ";
        print<REST...>(std::forward<REST>(rest)...);
    }
}

template<typename TUPLE, std::size_t... INDICES>
void showValuesHelper(TUPLE&& tuple, const pack_indices<INDICES...>&)
{
    Pack::print(std::get<INDICES>(std::forward<TUPLE>(tuple))...);
}

template<std::size_t START, std::size_t END, typename... TYPES>
void showMiddleValues(TYPES && ...types)
{
    const auto tuple = std::forward_as_tuple(std::forward<TYPES>(types)...);
    const typename make_indices<START, END>::type indices;
    showValuesHelper (tuple, indices);
}

int main()
{
    std::cout << "original argument pack: ";
    Pack::print('a', 3.14, 5, "home", '!', 4.5, "car", 20, 0.5, 'b');

    std::cout << "showMiddleValues<2,7> = ";
    showMiddleValues<2, 7>('a', 3.14, 5, "home", '!', 4.5, "car", 20, 0.5, 'b'); // 5, home, !, 4.5, car
}


btw, at least 10 programmers in stackoverflow thought about this, with one very interested in it and went on chat with me to discuss ideas. Not one successful solution resulted, with one person even saying that it is not possible (which I refuse to believe). The last idea tried by these programmers was "making reverse versions of those respective classes and using template specializations to select the correct one.", but then they gave up.
Last edited on
helios (17574)
I could suggest an alternative implementation:
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
 
#include <iostream>
#include <string>
#include <tuple>

struct TypeNil{
	template <typename T3>
	T3 operator+(const T3 &) const{
		return T3();
	}
	template <typename OriginalType, typename F>
	void iterate(F &f) const{}
};

template <int N>
struct TypeIntNode{
	static const int value = N;
};

template <int N>
struct TypeUnsignedNode{
	static const unsigned value = N;
};

template <typename T1, typename T2>
struct TypeCons;

template <typename T1, typename T2>
struct TypeAppend{
};

template <typename T1, typename T2, typename T3>
struct TypeAppend<TypeCons<T1, T2>, T3>{
	typedef TypeCons<typename TypeAppend<T1, T3>::type, T2> type;
};

template <typename T3>
struct TypeAppend<TypeNil, T3>{
	typedef TypeCons<TypeNil, T3> type;
	template <typename OriginalType, typename F>
	void iterate(F &) const{}
};

template <typename T1, typename T2>
struct TypeCons{
	template <typename T3>
	typename TypeAppend<TypeCons<T1, T2>, T3>::type operator+(const TypeCons<TypeNil, T3> &) const{
		return typename TypeAppend<TypeCons<T1, T2>, T3>::type();
	}
	template <typename OriginalType, typename F>
	void iterate(F &f) const{
		if (f(T2(), OriginalType()))
			T1().iterate<OriginalType>(f);
	}
};

template <typename ListType, typename F>
void iterate_type_list(const ListType &lt, F &f){
	lt.template iterate<ListType>(f);
}

template <size_t N>
struct SizeType{
	static const size_t value = N;
};

template <size_t begin, size_t end>
struct BuildList{
	typedef TypeCons<typename BuildList<begin + 1, end>::type, SizeType<begin> > type;
};

template <size_t begin>
struct BuildList<begin, begin>{
	typedef TypeNil type;
};

template <typename T1>
struct ReverseList{
	template <typename List, typename Accum>
	struct Iter{
	};
	
	template <typename Accum>
	struct Iter<TypeNil, Accum>{
		typedef Accum type;
	};
	
	template <typename Y1, typename Y2, typename Accum>
	struct Iter<TypeCons<Y1, Y2>, Accum>{
		typedef typename Iter<Y1, TypeCons<Accum, Y2> >::type type;
	};
	
	typedef typename Iter<T1, TypeNil>::type type;
};

template <typename T1, size_t N>
struct GetNth{
	template <typename List, size_t I>
	struct Iter{
	};
	
	template <typename Y1, typename Y2, size_t I>
	struct Iter<TypeCons<Y1, Y2>, I>{
		typedef typename Iter<Y1, I + 1>::type type;
	};
	
	template <typename Y1, typename Y2>
	struct Iter<TypeCons<Y1, Y2>, N>{
		typedef Y2 type;
	};
	
	typedef typename Iter<T1, 0>::type type;
};

template <typename List, size_t Size, size_t Shift>
struct MakeRotated{
	template <size_t I, typename Accum>
	struct Iter{
		typedef typename GetNth<List, (I + Shift - 1) % Size>::type nth;
		typedef TypeCons<Accum, nth> cons;
		typedef typename Iter<I - 1, cons>::type type;
	};
	
	template <typename Accum>
	struct Iter<0, Accum>{
		typedef Accum type;
	};
	
	typedef typename Iter<Size, TypeNil>::type type;
};

struct PrintF{
	template <typename T1, typename T2>
	bool operator()(const T1 &, const T2 &){
		std::cout <<T1::value<<std::endl;
		return true;
	}
};

int main(){
	PrintF f;
	MakeRotated<ReverseList<BuildList<0, 5>::type>::type, 5, 2>::type l;
	iterate_type_list(l, f);
}


PS: I've found it really helps to first write the transformations in pseudo-Haskell:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
reverse x = iter x []
    where
        iter [] accum = accum
        iter y:ys accum = iter ys (y:accum)

get_nth list n = iter list 0
    where
        iter [] _ = undefined
        iter x:xs n = x
        iter x:xs i = iter xs (i + 1)

make_rotated list size shift = iter size []
    where
        iter 0 accum = accum
        iter i accum = iter (i - 1) ((get_nth list (mod (i + shift - 1) size)) : accum)
Last edited on
prestokeys (357)
Thanks helios, for your alternate approach (always a good thing to learn other methods). I haven't studied your method fully yet, but a quick glance says that you are avoiding indices (the "indices trick") and variadic template arguments altogether?
Last edited on
helios (17574)
I couldn't figure out how to manipulate variadic template arguments, so I recycled a solution I'm using in a project of mine. It's simply a functional programming-style list of types, where TypeNil is an empty list, and TypeCons<T1, T2> is a (cons T2 T1). Don't ask why I reversed the order; I have no idea.
Manipulating these lists is IMO a whole lot easier because it's just like manipulating lists in functional languages, particularly Haskell.

I wanted to implement showMiddleValues() for the example, but I'm not really familiar with std::forward and tuples. Still, I think you should be able to figure it out.
prestokeys (357)
->I wanted to implement showMiddleValues() for the example, but I'm not really familiar with std::forward and tuples.

Actually, the use of tuples and perfect forwarding was totally unnecessary in my code. They were just used to print out the packs for testing purposes. I already have my own way of printing without resorting to tuples (much like you have your own way above), but that involved more code which I didn't want to congest with. The ideal solution I seek uses no tuples at all (except for just printing perhaps) and stick directly with the indices.
JLBorges (13770)
You might want to have a lok at Boost mpl
http://www.boost.org/doc/libs/1_55_0/libs/mpl/doc/refmanual/refmanual_toc.html

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
 
#include <iostream>
#include <boost/mpl/vector_c.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/reverse.hpp>
#include <boost/mpl/copy.hpp>
#include <boost/mpl/copy_if.hpp>
#include <boost/mpl/modulus.hpp>

namespace mpl = boost::mpl ;

template < std::size_t... INDICES >
using index_pack = mpl::vector_c< std::size_t, INDICES... > ;

namespace detail
{
    struct print_
    {
        template < typename T > void operator() ( T v ) const { stm << v << ' ' ; }
        std::ostream& stm ;
    };
}

template < typename INT_SEQ_WRAPPER > std::ostream& print( std::ostream& stm = std::cout )
{
    stm << "[ " ;
    mpl::for_each<INT_SEQ_WRAPPER>( detail::print_{stm} ) ;
    return stm << ']' ;
}

template < typename INT_SEQ_WRAPPER > struct reverse
{
    using type = typename mpl::copy< typename mpl::reverse<INT_SEQ_WRAPPER>::type,
                                     mpl::back_inserter< index_pack<> > >::type ;
};

template < typename INT_SEQ_WRAPPER > struct select_odds
{
    using type = typename mpl::copy_if< INT_SEQ_WRAPPER,
                                        mpl::modulus< mpl::_1, mpl::int_<2> >,
                                        mpl::back_inserter< index_pack<> > >::type ;
};

template < typename INT_SEQ_WRAPPER_A, typename INT_SEQ_WRAPPER_B > struct cat
{
    using type = typename mpl::copy< INT_SEQ_WRAPPER_B,
                                     mpl::back_inserter<INT_SEQ_WRAPPER_A> >::type ;
};

int main()
{
    using pack = index_pack<0,1,2,3,4,5,6,7,8,9> ;
    print<pack>() << '\n' ;

    using rpack = reverse<pack>::type ;
    print<rpack>() << '\n' ;

    using opack = select_odds<rpack>::type ;
    print<opack>() << '\n' ;

    using pack2 = index_pack<51,53,55,57> ;
    print<pack2>() << '\n' ;
    using cpack = cat< pack2, opack >::type ;
    print<cpack>() << '\n' ;

    using rcpack = reverse<cpack>::type ;
    print<rcpack>() << '\n' ;

    // compose inline reverse( cat<>, ( select_odds<>, reverse<> ) )
    print< reverse<
                     cat<
                          index_pack<51,53,55,57>,
                          select_odds< reverse< index_pack<0,1,2,3,4,5,6,7,8,9> >::type >::type
                        >::type
                   >::type >( std::cout << "\ncomposed inline:\n" ) << '\n' ;
}

http://coliru.stacked-crooked.com/a/8f374e8e1cdae8e6
prestokeys (357)
Thanks, JLBorges for coming up with the closest solution. I will have to install Visual Studio to get boost working, to study this properly. 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? Anyway to do it by defining a class much simpler than what Boost mpl would involve? If not, then I guess this is why the other programmers gave up.

Last edited on
JLBorges (13770)
> I will have to install Visual Studio to get boost working

Boost mpl is 'header only'. Just download Boost source, put the directory in the include path, and use mpl with any mainstream compiler.


> 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. Boost is mainstream C++; get familiar with it.
JLBorges (13770)
> Is there anyway using c++11 only?

Something along these lines:

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
 
#include <iostream>

template < std::size_t... INDICES > struct index_list ;

template < std::size_t N > struct index_list<N>
{
    static std::ostream& print( std::ostream& stm = std::cout )
    { return stm << N << ' ' ; }
};

template < std::size_t FIRST, std::size_t... REST > struct index_list< FIRST, REST... >
{
    static std::ostream& print( std::ostream& stm = std::cout )
    { index_list<FIRST>::print(stm) ; return index_list<REST...>::print(stm) ; }
};

template < std::size_t, typename, std::size_t... > struct push_back ;
template < std::size_t N > struct push_back< N, index_list<> >
{ using type = index_list<N> ; } ;
template < std::size_t N, std::size_t... I > struct push_back< N, index_list<I...> >
{ using type = index_list<I...,N> ; } ;

template < typename, std::size_t... > struct pop_front ;
template < std::size_t N > struct pop_front< index_list<N> >
{ using type = index_list<> ; } ;
template < std::size_t FIRST, std::size_t... REST >
struct pop_front< index_list<FIRST,REST...> > { using type = index_list<REST...> ; } ;

template < typename, std::size_t... > struct rotate ;
template <> struct rotate< index_list<> > { using type = index_list<> ; } ;
template < std::size_t FIRST, std::size_t... REST >
struct rotate< index_list<FIRST,REST...> > { using type = index_list<REST...,FIRST> ; } ;

template < std::size_t, typename, std::size_t... > struct fold ;
template < std::size_t N> struct fold< N, index_list<> > { using type = index_list<> ; } ;
template < std::size_t N, std::size_t FIRST, std::size_t... REST >
struct fold< N, index_list<FIRST,REST...> >
{
    using type = typename push_back< FIRST,
                             typename fold< N-1, index_list<REST...> >::type >::type ;
} ;
template < typename std::size_t FIRST, std::size_t... REST >
struct fold< 0, index_list<FIRST,REST...> > { using type = index_list<FIRST,REST...> ; };

template < typename, std::size_t... > struct reverse ;
template <> struct reverse< index_list<> > { using type = index_list<> ; } ;
template < std::size_t FIRST, size_t... REST > struct reverse< index_list<FIRST,REST...> >
{ using type = typename push_back< FIRST,
                     typename reverse< index_list<REST...> >::type >::type ;
} ;

int main()
{
    using ilist = index_list<0,1,2,3,4,5,6,7,8,9> ;
    ilist::print() << '\n' ;

    using ilist2 = push_back<10,ilist>::type ;
    ilist2::print() << '\n' ;

    using ilist3 = pop_front<ilist2>::type ;
    ilist3::print() << '\n' ;

    using ilist4 = fold< 5, ilist3 >::type ;
    ilist4::print() << '\n' ;

    using ilist5 = reverse<ilist4>::type ;
    ilist5::print() << '\n' ;

    reverse<
               fold<
                      5,
                      pop_front<
                                   push_back<
                                                10,
                                                index_list<0,1,2,3,4,5,6,7,8,9>
                                            >::type
                                >::type
                    >::type
            >::type::print( std::cout << "\ncomposed inline:\n" ) << '\n' ;
}

http://coliru.stacked-crooked.com/a/973bb5cb533396a1
Topic archived. No new replies allowed.