Awali
Another Weighted Automata library
tuple.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_TUPLE_HH
18 # define AWALI_TUPLE_HH
19 
20 # include <iostream>
21 # include <tuple>
22 
23 # include <awali/utils/hash.hh>
24 
25 namespace awali
26 {
27 
28  // These definitions come in handy every time we define variadic tuples.
29  namespace internal
30  {
31 
32  /*-----------------.
33  | index_sequence. |
34  `-----------------*/
35 
36  // See "Pretty-print std::tuple"
37  // <http://stackoverflow.com/questions/6245735>.
38 
39  // See O(log N) implementation of integer sequence
40  // <http://stackoverflow.com/questions/17424477>
41 
42  template<std::size_t...> struct index_sequence
43  { using type = index_sequence; };
44 
45  template<class S1, class S2> struct concat;
46 
47  template<std::size_t... I1, std::size_t... I2>
48  struct concat<index_sequence<I1...>, index_sequence<I2...>>
49  : index_sequence<I1..., (sizeof...(I1)+I2)...>{};
50 
51  template<class S1, class S2>
52  using Concat = typename concat<S1, S2>::type;
53 
54  template<std::size_t N> struct make_index_sequence;
55  template<std::size_t N> using GenSeq =
57 
58  template<std::size_t N>
59  struct make_index_sequence : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};
60 
61  template<> struct make_index_sequence<0> : index_sequence<>{};
62  template<> struct make_index_sequence<1> : index_sequence<0>{};
63 
64  template<class S1, class S2> struct seqconcat;
65 
66  template<std::size_t... I1, std::size_t... I2>
67  struct seqconcat<index_sequence<I1...>, index_sequence<I2...>>
68  : index_sequence<I1..., I2...>{};
69 
70  template<typename S> struct reverseseq;
71  template<size_t I1, size_t... I2>
72  struct reverseseq<index_sequence<I1, I2...>> {
73  using type = typename seqconcat<typename reverseseq<index_sequence<I2...>>::type,
75  };
76  template<size_t I1>
77  struct reverseseq<index_sequence<I1>> {
79  };
80 
81  template<std::size_t off, class S2> struct int_range;
82 
83  template<std::size_t off, std::size_t... I>
84  struct int_range<off, index_sequence<I...>>
85  : index_sequence<I + off...>{};
86 
87  template<std::size_t S, std::size_t L>
89  : int_range<S, typename make_index_sequence<L>::type>{};
90 
91  template<std::size_t S>
92  struct make_index_range<S, 0> : index_sequence<>{};
93  template<std::size_t S>
94  struct make_index_range<S, -1U> : index_sequence<>{};
95 
96  template<typename S1, typename S2>
98 
99  template<std::size_t... I1, std::size_t... I2>
101  : index_sequence<I1..., I2...>{};
102 
103  template <typename S1, typename S2>
105 
106  // There is a bug in clang making this one useless...
107  // The index sequence generated is always <0>
108  // Bug report:
109  // http://llvm.org/bugs/show_bug.cgi?id=14858
110  //template<class... T>
111  //using index_sequence_for = make_index_sequence<sizeof...(T)>;
112 
113 
114  template <typename Fun, typename... Ts>
115  inline void
116  for_(const std::tuple<Ts...>& ts, Fun f)
117  {
118  for_(f, ts, make_index_sequence<sizeof...(Ts)>());
119  }
120 
121  template <typename Fun, typename... Ts, size_t... I>
122  inline void
123  for_(Fun f,
124  const std::tuple<Ts...>& ts,
126  {
127  using swallow = int[];
128  (void) swallow{ (f(std::get<I>(ts)), 0)... };
129  }
130 
132  template <typename Fun, typename... Ts>
133  inline auto
134  map(const std::tuple<Ts...>& ts, Fun f)
135  -> decltype(map_tuple_(f, ts, make_index_sequence<sizeof...(Ts)>()))
136  {
137  return map_tuple_(f, ts, make_index_sequence<sizeof...(Ts)>());
138  }
139 
140  template <typename Fun, typename... Ts, size_t... I>
141  inline auto
142  map_tuple_(Fun f,
143  const std::tuple<Ts...>& ts,
145  -> decltype(map_variadic_(f, std::get<I>(ts)...))
146  {
147  return map_variadic_(f, std::get<I>(ts)...);
148  }
149 
150  template<typename Fun>
151  inline auto
153  -> decltype(std::make_tuple())
154  {
155  return std::make_tuple();
156  }
157 
158  template <typename Fun, typename T, typename... Ts>
159  inline auto
160  map_variadic_(Fun f, T t, Ts&&... ts)
161  -> decltype(std::tuple_cat(std::make_tuple(f(t)), map_variadic_(f, ts...)))
162  {
163  // Enforce evaluation order from left to right.
164  auto r = f(t);
165  return std::tuple_cat(std::make_tuple(r), map_variadic_(f, ts...));
166  }
167 
168 
169 
170  //#if 0
171 
172  /*-----------------.
173  | make_inv_tuple. |
174  `-----------------*/
175 
176  // This does not work, I don't understand why. If you know, please
177  // let me (AD) know.
178  inline auto
180  -> std::tuple<>
181  {
182  return {};
183  }
184 
185  template <typename T, typename... Ts>
186  inline auto
187  make_inv_tuple(T t, Ts&&... ts)
188  -> decltype(std::tuple_cat(make_inv_tuple(std::forward<Ts>(ts)...), std::make_tuple(t)));
189 
190  template <typename T, typename... Ts>
191  inline auto
192  make_inv_tuple(T t, Ts&&... ts)
193  -> decltype(std::tuple_cat(make_inv_tuple(std::forward<Ts>(ts)...), std::make_tuple(t)))
194  {
195  return std::tuple_cat(make_inv_tuple(std::forward<Ts>(ts)...), std::make_tuple(t));
196  }
197 
198  //#endif
199 
200 
201  /*----------------.
202  | reverse_tuple. |
203  `----------------*/
204 
205  template <typename... Ts>
206  inline auto
207  reverse_tuple(const std::tuple<Ts...>& t)
208  -> decltype(reverse_tuple(t, make_index_sequence<sizeof...(Ts)>()))
209  {
210  return reverse_tuple(t, make_index_sequence<sizeof...(Ts)>());
211  }
212 
213  template <typename... Ts, std::size_t... I>
214  inline auto
215  reverse_tuple(const std::tuple<Ts...>& t, index_sequence<I...>)
216  -> decltype(std::make_tuple(std::get<sizeof...(Ts) - 1 - I>(t)...))
217  {
218  return std::make_tuple(std::get<sizeof...(Ts) - 1 - I>(t)...);
219  }
220 
221  template <typename... Ts>
222  inline auto
223  make_inv_tuple(Ts&&... ts)
224  -> decltype(reverse_tuple(std::make_tuple(std::forward<Ts>(ts)...)))
225  {
226  return reverse_tuple(std::make_tuple(std::forward<Ts>(ts)...));
227  }
228 
229 
230  /*------------------------.
231  | print(tuple, ostream). |
232  `------------------------*/
233 
234  template<class Tuple, std::size_t N>
236  {
237  static void print(const Tuple& t, std::ostream& o)
238  {
240  o << ", " << std::get<N-1>(t);
241  }
242  };
243 
244  template<class Tuple>
245  struct tuple_printer<Tuple, 1>
246  {
247  static void print(const Tuple& t, std::ostream& o)
248  {
249  o << std::get<0>(t);
250  }
251  };
252 
253  template <typename... Args>
254  std::ostream& print(const std::tuple<Args...>& args, std::ostream& o)
255  {
256  o << '(';
257  tuple_printer<decltype(args), sizeof...(Args)>::print(args, o);
258  return o << ')';
259  }
260 
261  // Compile-time logic
262  // See:
263  // http://stillmoreperfect.blogspot.fr/2010/03/template-metaprogramming-compile-time.html
264 
265  // Test if (c) then T1 else T2
266  template<bool c, class T1, class T2>
267  struct if_c { typedef T1 type; };
268 
269  template<class T1, class T2>
270  struct if_c<false, T1, T2> { typedef T2 type; };
271 
272  template<class C, class T1, class T2>
273  struct if_ : if_c<C::value, T1, T2> {};
274 
275  // Test if (c) then F1 else F2 and get the value
276  template<bool c, class F1, class F2>
277  struct eval_if_c : if_c<c, F1, F2>::type {};
278 
279  template<class C, class F1, class F2>
280  struct eval_if : if_<C, F1, F2>::type {};
281 
282  // And condition on several classes
283  template<class... F>
284  struct and_;
285 
286  template<class F1, class... F>
287  struct and_<F1, F...> : eval_if<F1, and_<F...>, std::false_type>::type {};
288 
289  template<class F1>
290  struct and_<F1> : eval_if<F1, std::true_type, std::false_type>::type {};
291 
292  template<>
293  struct and_<> : std::true_type::type {};
294 
295  // Or condition on several classes
296  template<class... F>
297  struct or_;
298 
299  template<class F1, class... F>
300  struct or_<F1, F...> : eval_if<F1, std::true_type, or_<F...>>::type { };
301 
302  template<class F1>
303  struct or_<F1> : eval_if<F1, std::true_type, std::false_type>::type { };
304 
305  template<>
306  struct or_<> : std::true_type::type {};
307  }
308 
310  template<bool... B>
311  constexpr bool any_()
312  {
314  }
315 
316  // Static evaluation of the 'and' of the template parameters
317  template<bool... B>
318  constexpr bool all_()
319  {
321  }
322 
323 
324 }
325 
326 namespace std
327 {
328 
329  /*-------------------------.
330  | std::hash(tuple<T...>). |
331  `-------------------------*/
332 
333  template <typename... Elements>
334  struct hash<std::tuple<Elements...>>
335  {
336  using value_t = std::tuple<Elements...>;
337  using indices_t = awali::internal::make_index_sequence<sizeof...(Elements)>;
338 
339  std::size_t operator()(const value_t& v) const
340  {
341  return hash_(v, indices_t{});
342  }
343 
344  private:
345  template <std::size_t... I>
346  static std::size_t
347  hash_(const value_t& v, awali::internal::index_sequence<I...>)
348  {
349  std::size_t res = 0;
350  using swallow = int[];
351  (void) swallow
352  {
353  (std::hash_combine(res, std::get<I>(v)), 0)...
354  };
355  return res;
356  }
357  };
358 
359  template<typename T1, typename T2> struct cons_tuple;
360  template<typename T1, typename... T2>
361  struct cons_tuple<T1,std::tuple<T2...>> {
362  using type = std::tuple<T1,T2...>;
363  };
364 
365  template<typename T1, typename T2> struct concat_tuple;
366  template<typename... T1, typename... T2>
367  struct concat_tuple<std::tuple<T1...>,std::tuple<T2...>> {
368  using type = std::tuple<T1...,T2...>;
369  };
370 
371  template<typename T, unsigned N>
372  struct cst_tuple {
373  using type = typename cons_tuple<T, typename cst_tuple<T, N-1>::type>::type;
374  };
375 
376  template<typename T>
377  struct cst_tuple<T,1u> {
378  using type = std::tuple<T>;
379  };
380 
381 
382 }
383 
384 namespace std {
385  template <typename... Args>
386  std::ostream& operator<<(std::ostream& o, const std::tuple<Args...>& args)
387  {
388  return awali::internal::print(args, o);
389  }
390 }
391 
392 #endif // !AWALI_MISC_TUPLE_HH
auto map(const std::tuple< Ts... > &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
Definition: tuple.hh:134
typename seqconcat< typename reverseseq< index_sequence< I2... > >::type, index_sequence< I1 > >::type type
Definition: tuple.hh:74
typename concat_index_sequence< S1, S2 >::type concat_sequence
Definition: tuple.hh:104
auto map_variadic_(Fun) -> decltype(std::make_tuple())
Definition: tuple.hh:152
typename concat< S1, S2 >::type Concat
Definition: tuple.hh:52
T1 type
Definition: tuple.hh:267
auto map_tuple_(Fun f, const std::tuple< Ts... > &ts, index_sequence< I... >) -> decltype(map_variadic_(f, std::get< I >(ts)...))
Definition: tuple.hh:142
auto reverse_tuple(const std::tuple< Ts... > &t) -> decltype(reverse_tuple(t, make_index_sequence< sizeof...(Ts)>()))
Definition: tuple.hh:207
auto make_inv_tuple() -> std::tuple<>
Definition: tuple.hh:179
void for_(const std::tuple< Ts... > &ts, Fun f)
Definition: tuple.hh:116
typename make_index_sequence< N >::type GenSeq
Definition: tuple.hh:56
T2 type
Definition: tuple.hh:270
std::ostream & print(const std::tuple< Args... > &args, std::ostream &o)
Definition: tuple.hh:254
Definition: tuple.hh:284
Definition: tuple.hh:45
Definition: tuple.hh:267
Definition: tuple.hh:43
Definition: tuple.hh:81
Definition: tuple.hh:297
Definition: tuple.hh:70
Definition: tuple.hh:64
static constexpr TOP< void > value
Definition: priority.hh:93
Main namespace of Awali.
Definition: ato.hh:22
constexpr bool any_()
Static evaluation of the 'or' of the template parameters.
Definition: tuple.hh:311
constexpr bool all_()
Definition: tuple.hh:318
Definition: tuple.hh:277
Definition: tuple.hh:280
Definition: tuple.hh:273
Definition: tuple.hh:89
static void print(const Tuple &t, std::ostream &o)
Definition: tuple.hh:247
Definition: tuple.hh:236
static void print(const Tuple &t, std::ostream &o)
Definition: tuple.hh:237
std::tuple< T1..., T2... > type
Definition: tuple.hh:368
Definition: tuple.hh:365
std::tuple< T1, T2... > type
Definition: tuple.hh:362
Definition: tuple.hh:359
std::tuple< T > type
Definition: tuple.hh:378
Definition: tuple.hh:372
typename cons_tuple< T, typename cst_tuple< T, N-1 >::type >::type type
Definition: tuple.hh:373
std::size_t operator()(const value_t &v) const
Definition: tuple.hh:339
std::tuple< Elements... > value_t
Definition: tuple.hh:336
void hash_combine(std::size_t &seed, const T &v)
Definition: hash.hh:27