di 0.1.0
Loading...
Searching...
No Matches
algorithm.h
Go to the documentation of this file.
1#pragma once
2
3#include "di/meta/constexpr.h"
4#include "di/meta/core.h"
5#include "di/meta/function.h"
6#include "di/meta/list.h"
7#include "di/types/integers.h"
9
10namespace di::meta {
11namespace detail {
12 template<typename Pred, typename Type>
13 struct AllHelper {};
14
15 template<typename Pred, typename... Types>
16 struct AllHelper<Pred, List<Types...>> : Constexpr<(meta::Invoke<Pred, Types> {} && ...)> {};
17}
18
19template<concepts::TypeList List, concepts::MetaInvocable Pred>
20constexpr inline bool All = detail::AllHelper<Pred, List>::value;
21
22namespace detail {
23 template<typename R, typename List>
24 struct AsLanguageFunction;
25
26 template<typename R, typename... Types>
27 struct AsLanguageFunction<R, List<Types...>> : TypeConstant<R(Types...)> {};
28}
29
30template<typename R, concepts::TypeList T>
32
33namespace detail {
34 template<typename T>
35 struct AsListHelper {};
36
37 template<auto... values>
38 struct AsListHelper<ListV<values...>> : TypeConstant<List<Constexpr<values>...>> {};
39
40 template<template<typename...> typename Template, typename... Types>
41 struct AsListHelper<Template<Types...>> : TypeConstant<List<Types...>> {};
42
43 template<typename R, typename... Args>
44 struct AsListHelper<R(Args...)> : TypeConstant<List<Args...>> {};
45}
46
47template<typename T>
49
50namespace detail {
51 template<template<typename...> typename Template, typename List>
52 struct AsTemplateHelper {};
53
54 template<template<typename...> typename Template, typename... Types>
55 requires(concepts::ValidInstantiation<Template, Types...>)
56 struct AsTemplateHelper<Template, List<Types...>> : TypeConstant<Template<Types...>> {};
57}
58
59template<template<typename...> typename Template, concepts::TypeList T>
61
62template<concepts::TypeList T>
64
65namespace detail {
66 template<typename...>
67 struct ConcatHelper {};
68
69 template<typename... Ts, typename... Us, typename... Rest>
70 struct ConcatHelper<List<Ts...>, List<Us...>, Rest...> : ConcatHelper<List<Ts..., Us...>, Rest...> {};
71
72 template<typename T>
73 struct ConcatHelper<T> : TypeConstant<T> {};
74
75 template<>
76 struct ConcatHelper<> : TypeConstant<List<>> {};
77}
78
79template<concepts::TypeList... Lists>
80using Concat = Type<detail::ConcatHelper<Lists...>>;
81
82template<concepts::TypeList L, typename T>
84
85template<concepts::TypeList L, typename T>
87
88template<concepts::TypeList List>
90
91namespace detail {
92 template<typename T>
93 struct PopFrontHelper : TypeConstant<List<>> {};
94
95 template<typename T, typename... Rest>
96 struct PopFrontHelper<List<T, Rest...>> : TypeConstant<List<Rest...>> {};
97}
98
99template<concepts::TypeList L>
101
102namespace detail {
103 template<typename T>
104 struct PopBackHelper : TypeConstant<List<>> {};
105
106 template<typename T, typename U, typename... Rest>
107 struct PopBackHelper<List<T, U, Rest...>> : TypeConstant<PushFront<Type<PopBackHelper<List<U, Rest...>>>, T>> {};
108}
109
110template<concepts::TypeList L>
112
113namespace detail {
114 template<typename List, typename Acc, typename MetaFn>
115 struct FoldHelper {};
116
117 template<typename Acc, typename MetaFn>
118 struct FoldHelper<List<>, Acc, MetaFn> : TypeConstant<Acc> {};
119
120 template<typename T, typename... Rest, typename Acc, typename MetaFn>
121 struct FoldHelper<List<T, Rest...>, Acc, MetaFn>
122 : TypeConstant<Type<FoldHelper<List<Rest...>, Invoke<MetaFn, Acc, T>, MetaFn>>> {};
123}
124
125template<concepts::TypeList List, typename Init, concepts::MetaInvocable MetaFn>
127
128namespace detail {
129 template<typename List, typename Init, typename MetaFn>
130 struct FoldRightHelper {};
131
132 template<typename Init, typename MetaFn>
133 struct FoldRightHelper<List<>, Init, MetaFn> : TypeConstant<Init> {};
134
135 template<typename T, typename... Rest, typename Init, typename MetaFn>
136 struct FoldRightHelper<List<T, Rest...>, Init, MetaFn>
137 : TypeConstant<Invoke<MetaFn, Type<FoldRightHelper<List<Rest...>, Init, MetaFn>>, T>> {};
138}
139
140template<concepts::TypeList List, typename Init, concepts::MetaInvocable MetaFn>
142
143namespace detail {
144 template<typename Pred>
145 struct FilterReducer {
146 template<typename Acc, typename Val>
148 };
149}
150
151template<concepts::TypeList List, concepts::MetaInvocable Pred>
152using Filter = Fold<List, meta::List<>, detail::FilterReducer<Pred>>;
153
154namespace detail {
155 template<typename Needle, typename Replacement>
156 struct ReplaceReducer {
157 template<typename Acc, typename Val>
159 };
160}
161
162template<concepts::TypeList List, typename Needle, typename Replacement>
163using Replace = Fold<List, meta::List<>, detail::ReplaceReducer<Needle, Replacement>>;
164
165namespace detail {
166 template<typename Pred, typename Replacement>
167 struct ReplaceIfReducer {
168 template<typename Acc, typename Val>
170 };
171}
172
173template<concepts::TypeList List, concepts::MetaInvocable Pred, typename Replacement>
174using ReplaceIf = Fold<List, meta::List<>, detail::ReplaceIfReducer<Pred, Replacement>>;
175
176namespace detail {
177 template<typename...>
178 struct TransformHelper {};
179
180 template<typename... Types, typename Fun>
182 struct TransformHelper<List<Types...>, Fun> : TypeConstant<List<Invoke<Fun, Types>...>> {};
183}
184
185template<concepts::TypeList List, typename Function>
186using Transform = detail::TransformHelper<List, Function>::Type;
187
188namespace detail {
189 struct PushBackIfUnique {
190 template<concepts::TypeList Lst, typename T>
191 struct Impl : TypeConstant<PushBack<Lst, T>> {};
192
193 template<concepts::TypeList Lst, typename T>
194 requires(Contains<Lst, T>)
195 struct Impl<Lst, T> : TypeConstant<Lst> {};
196
197 template<concepts::TypeList Lst, typename T>
198 using Invoke = Type<Impl<Lst, T>>;
199 };
200}
201
202template<concepts::TypeList Lst>
203using Unique = Fold<Lst, List<>, detail::PushBackIfUnique>;
204
205namespace detail {
206 template<typename T, typename U>
207 struct ZipHelper : TypeConstant<List<>> {};
208
209 template<typename T, typename U, typename... Ts, typename... Us>
210 struct ZipHelper<List<T, Ts...>, List<U, Us...>>
211 : TypeConstant<Concat<List<List<T, U>>, typename ZipHelper<List<Ts...>, List<Us...>>::Type>> {};
212}
213
214template<concepts::TypeList T, concepts::TypeList U>
215requires(Size<T> == Size<U>)
217
218namespace detail {
219 template<typename T, usize N>
220 struct RepeatHelper;
221
222 template<typename T>
223 struct RepeatHelper<T, 0> : TypeConstant<List<>> {};
224
225 template<typename T>
226 struct RepeatHelper<T, 1> : TypeConstant<List<T>> {};
227
228 template<typename T, usize N>
229 requires(N > 1)
230 struct RepeatHelper<T, N>
231 : TypeConstant<Concat<Type<RepeatHelper<T, N / 2>>, Type<RepeatHelper<T, (N + 1) / 2>>>> {};
232}
233
234template<typename T, usize N>
236
237namespace detail {
238 template<typename... Types>
239 struct CartesianProductHelper {};
240
241 template<>
242 struct CartesianProductHelper<> : TypeConstant<List<List<>>> {};
243
244 template<typename... Types>
245 struct CartesianProductHelper<List<Types...>> : TypeConstant<List<List<Types>...>> {};
246
247 template<typename... Ts, typename... Rest>
248 struct CartesianProductHelper<List<Ts...>, Rest...>
249 : TypeConstant<Concat<Transform<Type<CartesianProductHelper<Rest...>>, BindBack<Quote<PushFront>, Ts>>...>> {};
250}
251
252template<concepts::TypeList... Types>
253using CartesianProduct = Type<detail::CartesianProductHelper<Types...>>;
254
255namespace detail {
256 template<typename...>
257 struct ConcatVHelper {};
258
259 template<auto... ts, auto... us, typename... Rest>
260 struct ConcatVHelper<ListV<ts...>, ListV<us...>, Rest...> : ConcatVHelper<ListV<ts..., us...>, Rest...> {};
261
262 template<typename T>
263 struct ConcatVHelper<T> : TypeConstant<T> {};
264
265 template<>
266 struct ConcatVHelper<> : TypeConstant<ListV<>> {};
267}
268
269template<concepts::InstanceOfV<ListV>... Lists>
270using ConcatV = Type<detail::ConcatVHelper<Lists...>>;
271
272namespace detail {
273 template<typename T>
274 struct ReverseVHelper {};
275
276 template<>
277 struct ReverseVHelper<ListV<>> : TypeConstant<ListV<>> {};
278
279 template<auto v>
280 struct ReverseVHelper<ListV<v>> : TypeConstant<ListV<v>> {};
281
282 template<auto v, auto... vs>
283 struct ReverseVHelper<ListV<v, vs...>> : TypeConstant<ConcatV<Type<ReverseVHelper<ListV<vs...>>>, ListV<v>>> {};
284}
285
286template<concepts::InstanceOfV<ListV> List>
288
289// To produce an integer sequence using a minimal number of template
290// instantiations, we partition the problem into halves, and construct
291// the correcct sequence using the Concat helper.
292namespace detail {
293#if __has_builtin(__make_integer_seq)
294 template<typename T, T... ns>
295 using ConvertToListV = ListV<ns...>;
296#elif __has_builtin(__integer_pack)
297 template<typename T, auto... ns>
298 using ConvertToListV = ListV<T(ns)...>;
299#else
300 template<typename T, typename X, typename Y>
301 struct MakeIntegerSequenceConcatHelper;
302
303 template<typename T, T... s1, T... s2>
304 struct MakeIntegerSequenceConcatHelper<T, ListV<s1...>, ListV<s2...>> {
305 using Type = ListV<s1..., (T(sizeof...(s1) + s2))...>;
306 };
307
308 template<typename T, usize count>
309 struct MakeIntegerSequenceHelper {
310 using A = meta::Type<MakeIntegerSequenceHelper<T, count / 2>>;
311 using B = meta::Type<MakeIntegerSequenceHelper<T, count - count / 2>>;
313 };
314
315 template<typename T>
316 struct MakeIntegerSequenceHelper<T, 1> : TypeConstant<ListV<T(0)>> {};
317
318 template<typename T>
319 struct MakeIntegerSequenceHelper<T, 0> : TypeConstant<ListV<>> {};
320#endif
321}
322
323template<typename T, usize count>
324#if __has_builtin(__make_integer_seq)
325using MakeIntegerSequence = __make_integer_seq<detail::ConvertToListV, T, count>;
326#elif __has_builtin(__integer_pack)
327using MakeIntegerSequence = detail::ConvertToListV<T, __integer_pack(count)...>;
328#else
330#endif
331
332template<usize count>
334
335template<usize count>
337
338template<typename... Types>
339using IndexSequenceFor = MakeIndexSequence<sizeof...(Types)>;
340}
Definition function.h:38
Definition core.h:164
Definition function.h:8
Definition list.h:127
Definition merge_interfaces.h:6
Fold< List, meta::List<>, detail::ReplaceIfReducer< Pred, Replacement > > ReplaceIf
Definition algorithm.h:174
constexpr bool All
Definition algorithm.h:20
detail::ConditionalHelper< value, T, U >::Type Conditional
Definition core.h:88
Type< detail::MakeIntegerSequenceHelper< T, count > > MakeIntegerSequence
Definition algorithm.h:329
T::Type Type
Definition core.h:26
ReverseV< MakeIntegerSequence< usize, count > > MakeReverseIndexSequence
Definition algorithm.h:336
Type< detail::AsTemplateHelper< Template, T > > AsTemplate
Definition algorithm.h:60
Type< detail::ConcatVHelper< Lists... > > ConcatV
Definition algorithm.h:270
constexpr usize Size
Definition list.h:114
Concat< List< T >, L > PushFront
Definition algorithm.h:83
Type< detail::AsListHelper< T > > AsList
Definition algorithm.h:48
Apply< Quote< Concat >, List > Join
Definition algorithm.h:89
Fold< List, meta::List<>, detail::FilterReducer< Pred > > Filter
Definition algorithm.h:152
Type< detail::FoldRightHelper< List, Init, MetaFn > > FoldRight
Definition algorithm.h:141
MakeIntegerSequence< usize, count > MakeIndexSequence
Definition algorithm.h:333
Type< detail::CartesianProductHelper< Types... > > CartesianProduct
Definition algorithm.h:253
Type< detail::ZipHelper< T, U > > Zip
Definition algorithm.h:216
Fold< Lst, List<>, detail::PushBackIfUnique > Unique
Definition algorithm.h:203
Type< detail::ReverseVHelper< List > > ReverseV
Definition algorithm.h:287
Type< detail::RepeatHelper< T, N > > Repeat
Definition algorithm.h:235
Concat< L, List< T > > PushBack
Definition algorithm.h:86
AsTemplate< vocab::Tuple, T > AsTuple
Definition algorithm.h:63
Type< detail::ApplyHelper< F, T > > Apply
Definition function.h:55
Type< detail::ConcatHelper< Lists... > > Concat
Definition algorithm.h:80
Type< Defer< Fun::template Invoke, Args... > > Invoke
Definition function.h:43
Type< detail::PopFrontHelper< L > > PopFront
Definition algorithm.h:100
detail::TransformHelper< List, Function >::Type Transform
Definition algorithm.h:186
Type< detail::AsLanguageFunction< R, T > > AsLanguageFunction
Definition algorithm.h:31
Fold< List, meta::List<>, detail::ReplaceReducer< Needle, Replacement > > Replace
Definition algorithm.h:163
Type< detail::FoldHelper< List, Init, MetaFn > > Fold
Definition algorithm.h:126
Type< detail::PopBackHelper< L > > PopBack
Definition algorithm.h:111
MakeIndexSequence< sizeof...(Types)> IndexSequenceFor
Definition algorithm.h:339
constexpr auto count
Definition count.h:37
Definition core.h:8
Definition core.h:5
Definition core.h:18