tuples.hh 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409
  1. // -*- mode: c++; coding: utf-8 -*-
  2. // ra-ra - Basic macros & tuple library.
  3. // (c) Daniel Llorens - 2005-2023
  4. // This library is free software; you can redistribute it and/or modify it under
  5. // the terms of the GNU Lesser General Public License as published by the Free
  6. // Software Foundation; either version 3 of the License, or (at your option) any
  7. // later version.
  8. #pragma once
  9. #include <tuple>
  10. #include <limits>
  11. #include <algorithm>
  12. #include <type_traits>
  13. #include <utility>
  14. #define STRINGIZE_( x ) #x
  15. #define STRINGIZE( x ) STRINGIZE_( x )
  16. #define JOIN_( x, y ) x##y
  17. #define JOIN( x, y ) JOIN_( x, y )
  18. // see http://stackoverflow.com/a/1872506
  19. #define FOR_EACH_1(what, x, ...) what(x)
  20. #define FOR_EACH_2(what, x, ...) what(x) FOR_EACH_1(what, __VA_ARGS__)
  21. #define FOR_EACH_3(what, x, ...) what(x) FOR_EACH_2(what, __VA_ARGS__)
  22. #define FOR_EACH_4(what, x, ...) what(x) FOR_EACH_3(what, __VA_ARGS__)
  23. #define FOR_EACH_5(what, x, ...) what(x) FOR_EACH_4(what, __VA_ARGS__)
  24. #define FOR_EACH_6(what, x, ...) what(x) FOR_EACH_5(what, __VA_ARGS__)
  25. #define FOR_EACH_7(what, x, ...) what(x) FOR_EACH_6(what, __VA_ARGS__)
  26. #define FOR_EACH_8(what, x, ...) what(x) FOR_EACH_7(what, __VA_ARGS__)
  27. #define FOR_EACH_9(what, x, ...) what(x) FOR_EACH_8(what, __VA_ARGS__)
  28. #define FOR_EACH_10(what, x, ...) what(x) FOR_EACH_9(what, __VA_ARGS__)
  29. #define FOR_EACH_11(what, x, ...) what(x) FOR_EACH_10(what, __VA_ARGS__)
  30. #define FOR_EACH_12(what, x, ...) what(x) FOR_EACH_11(what, __VA_ARGS__)
  31. #define FOR_EACH_NARG(...) FOR_EACH_NARG_(__VA_ARGS__, FOR_EACH_RSEQ_N())
  32. #define FOR_EACH_NARG_(...) FOR_EACH_ARG_N(__VA_ARGS__)
  33. #define FOR_EACH_ARG_N(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, N, ...) N
  34. #define FOR_EACH_RSEQ_N() 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
  35. #define FOR_EACH_(N, what, ...) JOIN(FOR_EACH_, N)(what, __VA_ARGS__)
  36. #define FOR_EACH(what, ...) FOR_EACH_(FOR_EACH_NARG(__VA_ARGS__), what, __VA_ARGS__)
  37. #define RA_FWD(a) std::forward<decltype(a)>(a)
  38. namespace ra {
  39. template <class T> constexpr bool is_constant = false;
  40. template <class T, T N> constexpr bool is_constant<std::integral_constant<T, N>> = true;
  41. template <int V> using int_c = std::integral_constant<int, V>;
  42. template <bool V> using bool_c = std::integral_constant<bool, V>;
  43. template <auto V> using ic_t = std::integral_constant<decltype(V), V>;
  44. template <auto V> constexpr std::integral_constant<decltype(V), V> ic {};
  45. template <class ... T> constexpr bool always_false = false; // p2593r0
  46. } // namespace ra
  47. namespace ra::mp {
  48. // xxx<...> is user facing and xxx_<...>::type (if needed) is implementation.
  49. using std::tuple;
  50. using nil = tuple<>;
  51. template <class T> constexpr bool nilp = std::is_same_v<nil, T>;
  52. template <class A> constexpr int len = std::tuple_size_v<A>;
  53. template <int ... I> using int_list = tuple<int_c<I> ...>;
  54. template <class T> constexpr bool is_tuple = false;
  55. template <class ... A> constexpr bool is_tuple<tuple<A ...>> = true;
  56. template <class A, class B> struct cons_ { static_assert(is_tuple<B>); };
  57. template <class A0, class ... A> struct cons_<A0, tuple<A ...>> { using type = tuple<A0, A ...>; };
  58. template <class A, class B> using cons = typename cons_<A, B>::type;
  59. template <class A, class B> struct append_ { static_assert(is_tuple<A> && is_tuple<B>); };
  60. template <class ... A, class ... B> struct append_<tuple<A ...>, tuple<B ...>> { using type = tuple<A ..., B ...>; };
  61. template <class A, class B> using append = typename append_<A, B>::type;
  62. template <class A, class B> struct zip_ { static_assert(is_tuple<A> && is_tuple<B>); };
  63. template <class ... A, class ... B> struct zip_<tuple<A ...>, tuple<B ...>> { using type = tuple<tuple<A, B> ...>; };
  64. template <class A, class B> using zip = typename zip_<A, B>::type;
  65. template <int n, int o=0, int s=1> struct iota_ { static_assert(n>0); using type = cons<int_c<o>, typename iota_<n-1, o+s, s>::type>; };
  66. template <int o, int s> struct iota_<0, o, s> { using type = nil; };
  67. template <int n, int o=0, int s=1> using iota = typename iota_<n, o, s>::type;
  68. template <int n, class T> struct makelist_ { static_assert(n>0); using type = cons<T, typename makelist_<n-1, T>::type>; };
  69. template <class T> struct makelist_<0, T> { using type = nil; };
  70. template <int n, class T> using makelist = typename makelist_<n, T>::type;
  71. // A is a nested list, I the indices at each level.
  72. template <class A, int ... I> struct ref_ { using type = A; };
  73. template <class A, int ... I> using ref = typename ref_<A, I ...>::type;
  74. template <class A, int I0, int ... I> struct ref_<A, I0, I ...> { using type = ref<std::tuple_element_t<I0, A>, I ...>; };
  75. template <class A> using first = ref<A, 0>;
  76. template <class A> using last = ref<A, (len<A> - 1)>;
  77. template <bool a> using when = bool_c<a>;
  78. template <bool a> using unless = bool_c<(!a)>;
  79. // Return the index of a type in a type list, or -1 if not found.
  80. template <class A, class T, int i=0> struct index_ { using type = int_c<-1>; };
  81. template <class A, class T, int i=0> using index = typename index_<A, T, i>::type;
  82. template <class ... A, class T, int i> struct index_<tuple<T, A ...>, T, i> { using type = int_c<i>; };
  83. template <class A0, class ... A, class T, int i> struct index_<tuple<A0, A ...>, T, i> { using type = index<tuple<A ...>, T, i+1>; };
  84. // Index (& type) of the 1st item for which Pred<> is true, or -1 (& nil).
  85. template <class A, template <class> class Pred, int i=0>
  86. struct IndexIf
  87. {
  88. constexpr static int value = -1;
  89. using type = nil;
  90. };
  91. template <class A0, class ... A, template <class> class Pred, int i>
  92. requires (Pred<A0>::value)
  93. struct IndexIf<tuple<A0, A ...>, Pred, i>
  94. {
  95. using type = A0;
  96. constexpr static int value = i;
  97. };
  98. template <class A0, class ... A, template <class> class Pred, int i>
  99. requires (!(Pred<A0>::value))
  100. struct IndexIf<tuple<A0, A ...>, Pred, i>
  101. {
  102. using next = IndexIf<tuple<A ...>, Pred, i+1>;
  103. using type = typename next::type;
  104. constexpr static int value = next::value;
  105. };
  106. // Index (& type) of pairwise winner. A variant of fold.
  107. template <template <class A, class B> class pick_i, class T, int k=1, int sel=0> struct indexof_;
  108. template <template <class A, class B> class pick_i, class T0, int k, int sel>
  109. struct indexof_<pick_i, tuple<T0>, k, sel>
  110. {
  111. constexpr static int value = sel;
  112. using type = T0;
  113. };
  114. template <template <class A, class B> class pick_i, class T0, class T1, class ... Ti, int k, int sel>
  115. struct indexof_<pick_i, tuple<T0, T1, Ti ...>, k, sel>
  116. {
  117. constexpr static int i = pick_i<std::decay_t<T0>, std::decay_t<T1>>::value;
  118. using next = indexof_<pick_i, tuple<std::conditional_t<i==0, T0, T1>, Ti ...>, k+1, i==0 ? sel : k>;
  119. using type = typename next::type;
  120. constexpr static int value = next::value;
  121. };
  122. template <template <class A, class B> class pick_i, class T>
  123. constexpr int indexof = indexof_<pick_i, T>::value;
  124. // Return the first tail of A headed by Val, like find-tail.
  125. template <class A, class Val> struct findtail_;
  126. template <class A, class Val> using findtail = typename findtail_<A, Val>::type;
  127. template <class Val> struct findtail_<nil, Val> { using type = nil; };
  128. template <class ... A, class Val> struct findtail_<tuple<Val, A ...>, Val> { using type = tuple<Val, A ...>; };
  129. template <class A0, class ... A, class Val> struct findtail_<tuple<A0, A ...>, Val> { using type = findtail<tuple<A ...>, Val>; };
  130. // Reverse list. See TSPL^3, p. 137.
  131. template <class A, class B=nil> struct reverse_ { using type = B; };
  132. template <class A, class B=nil> using reverse = typename reverse_<A, B>::type;
  133. template <class A0, class ... A, class B> struct reverse_<tuple<A0, A ...>, B> { using type = reverse<tuple<A ...>, cons<A0, B>>; };
  134. // drop1 is needed to avoid ambiguity in the declarations of drop, take.
  135. template <class A> struct drop1_;
  136. template <class A0, class ... A> struct drop1_<tuple<A0, A ...>> { using type = tuple<A ...>; };
  137. template <class A> using drop1 = typename drop1_<A>::type;
  138. template <class A, int n> struct drop_ { static_assert(n>0); using type = typename drop_<drop1<A>, n-1>::type; };
  139. template <class A> struct drop_<A, 0> { using type = A; };
  140. template <class A, int n> using drop = typename drop_<A, n>::type;
  141. template <class A, int n> struct take_ { static_assert(n>0); using type = cons<first<A>, typename take_<drop1<A>, n-1>::type>; };
  142. template <class A> struct take_<A, 0> { using type = nil; };
  143. template <class A, int n> using take = typename take_<A, n>::type;
  144. template <template <class ... A> class F, class L> struct apply_;
  145. template <template <class ... A> class F, class ... L> struct apply_<F, tuple<L ...>> { using type = F<L ...>; };
  146. template <template <class ... A> class F, class L> using apply = typename apply_<F, L>::type;
  147. // As map.
  148. template <template <class ... A> class F, class ... L>
  149. struct map_ { using type = cons<F<first<L> ...>, typename map_<F, drop1<L> ...>::type>; };
  150. template <template <class ... A> class F, class ... L>
  151. struct map_<F, nil, L ...> { using type = nil; };
  152. template <template <class ... A> class F>
  153. struct map_<F> { using type = nil; };
  154. template <template <class ... A> class F, class ... L> using map = typename map_<F, L ...>::type;
  155. template <class A, class B> struct Filter
  156. {
  157. using type = mp::append<std::conditional_t<mp::first<A>::value, mp::take<B, 1>, mp::nil>,
  158. typename Filter<mp::drop1<A>, mp::drop1<B>>::type>;
  159. };
  160. template <class B> struct Filter<mp::nil, B> { using type = B; };
  161. template <class A, class B> using Filter_ = typename Filter<A, B>::type;
  162. // As SRFI-1 fold (= fold-left).
  163. template <template <class ... A> class F, class Def, class ... L>
  164. struct fold_
  165. {
  166. using def = std::conditional_t<std::is_same_v<void, Def>, F<>, Def>;
  167. using type = typename fold_<F, F<def, first<L> ...>, drop1<L> ...>::type;
  168. };
  169. template <template <class ... A> class F, class Def, class ... L>
  170. struct fold_<F, Def, nil, L ...>
  171. {
  172. using type = std::conditional_t<std::is_same_v<void, Def>, F<>, Def>;
  173. };
  174. template <template <class ... A> class F, class Def>
  175. struct fold_<F, Def>
  176. {
  177. using type = std::conditional_t<std::is_same_v<void, Def>, F<>, Def>;
  178. };
  179. template <template <class ... A> class F, class Def, class ... L>
  180. using fold = typename fold_<F, Def, L ...>::type;
  181. template <class ... A> struct max_ { using type = int_c<std::numeric_limits<int>::min()>; };
  182. template <class ... A> using max = typename max_<A ...>::type;
  183. template <class A0, class ... A> struct max_<A0, A ...> { using type = int_c<std::max(A0::value, max<A ...>::value)>; };
  184. template <class ... A> struct min_ { using type = int_c<std::numeric_limits<int>::max()>; };
  185. template <class ... A> using min = typename min_<A ...>::type;
  186. template <class A0, class ... A> struct min_<A0, A ...> { using type = int_c<std::min(A0::value, min<A ...>::value)>; };
  187. // Operations on int_c arguments.
  188. template <class ... A> using sum = int_c<(A::value + ... + 0)>;
  189. template <class ... A> using prod = int_c<(A::value * ... * 1)>;
  190. template <class ... A> using andb = bool_c<(A::value && ...)>;
  191. template <class ... A> using orb = bool_c<(A::value || ...)>;
  192. // Remove from the second list the elements of the first list. None may have repeated elements, but they may be unsorted.
  193. template <class S, class T, class SS=S> struct complement_list_;
  194. template <class S, class T, class SS=S> using complement_list = typename complement_list_<S, T, SS>::type;
  195. // end of T.
  196. template <class S, class SS>
  197. struct complement_list_<S, nil, SS>
  198. {
  199. using type = nil;
  200. };
  201. // end search on S, did not find.
  202. template <class T0, class ... T, class SS>
  203. struct complement_list_<nil, tuple<T0, T ...>, SS>
  204. {
  205. using type = cons<T0, complement_list<SS, tuple<T ...>>>;
  206. };
  207. // end search on S, found.
  208. template <class F, class ... S, class ... T, class SS>
  209. struct complement_list_<tuple<F, S ...>, tuple<F, T ...>, SS>
  210. {
  211. using type = complement_list<SS, tuple<T ...>>;
  212. };
  213. // keep searching on S.
  214. template <class S0, class ... S, class T0, class ... T, class SS>
  215. struct complement_list_<tuple<S0, S ...>, tuple<T0, T ...>, SS>
  216. {
  217. using type = complement_list<tuple<S ...>, tuple<T0, T ...>, SS>;
  218. };
  219. // Like complement_list, but assume that both lists are sorted.
  220. template <class S, class T> struct complement_sorted_list_ { using type = nil; };
  221. template <class S, class T> using complement_sorted_list = typename complement_sorted_list_<S, T>::type;
  222. template <class T>
  223. struct complement_sorted_list_<nil, T>
  224. {
  225. using type = T;
  226. };
  227. template <class F, class ... S, class ... T>
  228. struct complement_sorted_list_<tuple<F, S ...>, tuple<F, T ...>>
  229. {
  230. using type = complement_sorted_list<tuple<S ...>, tuple<T ...>>;
  231. };
  232. template <class S0, class ... S, class T0, class ... T>
  233. struct complement_sorted_list_<tuple<S0, S ...>, tuple<T0, T ...>>
  234. {
  235. static_assert(T0::value<=S0::value, "bad lists for complement_sorted_list<>");
  236. using type = cons<T0, complement_sorted_list<tuple<S0, S ...>, tuple<T ...>>>;
  237. };
  238. // Variant of complement_list where the second argument is [0 .. end-1].
  239. template <class S, int end> using complement = complement_sorted_list<S, iota<end>>;
  240. // Prepend an element to each of a list of lists.
  241. template <class c, class A> struct MapCons;
  242. template <class c, class A> using MapCons_ = typename MapCons<c, A>::type;
  243. template <class c, class ... A> struct MapCons<c, tuple<A ...>> { using type = tuple<cons<c, A> ...>; };
  244. // Prepend a list to each list in a list of lists.
  245. template <class c, class A> struct MapPrepend;
  246. template <class c, class A> using MapPrepend_ = typename MapPrepend<c, A>::type;
  247. template <class c, class ... A> struct MapPrepend<c, tuple<A ...>> { using type = tuple<append<c, A> ...>; };
  248. // Form all possible lists by prepending an element of A to an element of B.
  249. template <class A, class B> struct ProductAppend { using type = nil; };
  250. template <class A, class B> using ProductAppend_ = typename ProductAppend<A, B>::type;
  251. template <class A0, class ... A, class B> struct ProductAppend<tuple<A0, A ...>, B> { using type = append<MapPrepend_<A0, B>, ProductAppend_<tuple<A ...>, B>>; };
  252. // Compute the K-combinations of the N elements of list A.
  253. template <class A, int K, int N=len<A>> struct combinations_;
  254. template <class A, int k, int N=len<A>> using combinations = typename combinations_<A, k, N>::type;
  255. // In this case, return a list with one element: the empty list.
  256. template <class A, int N> struct combinations_<A, 0, N> { using type = tuple<nil>; };
  257. // In this case, return a list with one element: the whole list.
  258. template <class A, int N> struct combinations_<A, N, N> { using type = tuple<A>; };
  259. // Special case for 0 over 0, to resolve ambiguity of 0/N and N/N when N=0.
  260. template <> struct combinations_<nil, 0> { using type = tuple<nil>; };
  261. template <class A, int K, int N>
  262. struct combinations_
  263. {
  264. static_assert(is_tuple<A>);
  265. static_assert(N>=0 && K>=0);
  266. static_assert(K<=N);
  267. using Rest = drop1<A>;
  268. using type = append<MapCons_<first<A>, combinations<Rest, K-1, N-1>>, combinations<Rest, K, N-1>>;
  269. };
  270. // Sign of permutations.
  271. template <class C, class R> struct PermutationSign;
  272. template <int w, class C, class R>
  273. constexpr int PermutationSignIfFound = PermutationSign<append<take<C, w>, drop<C, w+1>>, drop1<R>>::value
  274. * ((w & 1) ? -1 : +1);
  275. template <class C, class R>
  276. constexpr int PermutationSignIfFound<-1, C, R> = 0;
  277. template <> struct PermutationSign<nil, nil> { constexpr static int value = 1; };
  278. template <class C> struct PermutationSign<C, nil> { constexpr static int value = 0; };
  279. template <class R> struct PermutationSign<nil, R> { constexpr static int value = 0; };
  280. template <class C, class Org>
  281. struct PermutationSign
  282. {
  283. constexpr static int value = PermutationSignIfFound<index<C, first<Org>>::value, C, Org>;
  284. };
  285. // increment the w-th element of an int_list
  286. template <class L, int w> using inc = append<take<L, w>, cons<int_c<ref<L, w>::value+1>, drop<L, w+1>>>;
  287. template <class A> struct InvertIndex_;
  288. template <class ... A> struct InvertIndex_<tuple<A ...>>
  289. {
  290. using AT = tuple<A ...>;
  291. template <class T> using IndexA = int_c<index<AT, T>::value>;
  292. constexpr static int N = apply<max, AT>::value;
  293. using type = map<IndexA, iota<(N>=0 ? N+1 : 0)>>;
  294. };
  295. template <class A> using InvertIndex = typename InvertIndex_<A>::type;
  296. // Used in tests.
  297. template <class A, int ... I> struct check_idx { constexpr static bool value = false; };
  298. template <> struct check_idx<nil> { constexpr static bool value = true; };
  299. template <class A0, int I0, class ... A, int ... I>
  300. struct check_idx<tuple<A0, A ...>, I0, I ...>
  301. {
  302. constexpr static bool value = (A0::value==I0) && check_idx<tuple<A ...>, I ...>::value;
  303. };
  304. // -------------------------
  305. // Tuples in dynamic context
  306. // -------------------------
  307. // like std::make_trom_tuple, but use brace constructor (e.g. for std::array).
  308. template <class C, class T>
  309. constexpr C
  310. from_tuple(T && t)
  311. {
  312. return std::apply([](auto && ... x) { return C { RA_FWD(x) ... }; }, t);
  313. }
  314. template <class C, class T>
  315. consteval auto
  316. tuple_values()
  317. {
  318. return std::apply([](auto ... t) { return std::array<C, len<T>> { C(t) ... }; }, T {});
  319. }
  320. template <class C, class T, class I>
  321. constexpr C
  322. map_indices(I const & i)
  323. {
  324. return std::apply([&i](auto ... t) { return std::array<C, len<T>> { i[t] ... }; }, T {});
  325. };
  326. template <class T, int k=0>
  327. constexpr int
  328. int_list_index(int i)
  329. {
  330. if constexpr (k>=mp::len<T>) {
  331. return -1;
  332. } else {
  333. return (i==mp::ref<T, k>::value) ? k : int_list_index<T, k+1>(i);
  334. }
  335. }
  336. template <class K, class T, class F, class I = int_c<0>>
  337. constexpr auto
  338. fold_tuple(K && k, T && t, F && f, I && i = int_c<0> {})
  339. {
  340. if constexpr (I::value==len<std::decay_t<T>>) {
  341. return k;
  342. } else {
  343. return fold_tuple(f(k, std::get<I::value>(t)), t, f, int_c<I::value+1> {});
  344. }
  345. }
  346. } // namespace ra::mp