Sequoia
Loading...
Searching...
No Matches
TypeAlgorithms.hpp
Go to the documentation of this file.
1
2// Copyright Oliver J. Rosten 2025. //
3// Distributed under the GNU GENERAL PUBLIC LICENSE, Version 3.0. //
4// (See accompanying file LICENSE.md or copy at //
5// https://www.gnu.org/licenses/gpl-3.0.en.html) //
7
8#pragma once
9
10#include "sequoia/Core/Meta/Sequences.hpp"
11
12#include <source_location>
13#include <string_view>
14#include <tuple>
15
18namespace sequoia::meta
19{
20 //==================================================== type_comparator ===================================================//
21
22 namespace impl
23 {
24 using trial_type = void;
25 constexpr std::string_view trial_type_name{"void"};
26
27 namespace wrapped_type
28 {
29 template <typename T>
30 [[nodiscard]]
31 constexpr std::string_view name() noexcept
32 {
33 return std::source_location::current().function_name();
34 }
35
36 [[nodiscard]]
37 constexpr std::size_t prefix_length() noexcept
38 {
39 return name<trial_type>().find(trial_type_name);
40 }
41
42 [[nodiscard]]
43 constexpr std::size_t suffix_length() noexcept
44 {
45 return name<trial_type>().length() - prefix_length() - trial_type_name.length();
46 }
47 }
48 }
49
50 template<class T>
51 [[nodiscard]]
52 consteval std::string_view type_name()
53 {
54 using namespace impl::wrapped_type;
55 constexpr auto wrappedName{name<T>()};
56 constexpr auto prefixLength{prefix_length()};
57 constexpr auto nameLength{wrappedName.length() - prefixLength - suffix_length()};
58 return wrappedName.substr(prefixLength, nameLength);
59 }
60
61 template<class T, class U>
62 struct type_comparator : std::bool_constant<type_name<T>() < type_name<U>()>
63 {};
64
65 template<class T, class U>
66 using type_comparator_t = type_comparator<T, U>::type;
67
68 template<class T, class U>
69 inline constexpr bool type_comparator_v{type_comparator<T, U>::value};
70
71 //==================================================== lower_bound ===================================================//
72
73 template<class T, class U, template<class, class> class Compare>
74 struct lower_bound;
75
76 template<class T, class U, template<class, class> class Compare>
77 inline constexpr auto lower_bound_v{lower_bound<T, U, Compare>::value};
78
79 template<template<class...> class TT, class... Ts, class U, template<class, class> class Compare>
80 struct lower_bound<TT<Ts...>, U, Compare>
81 {
82 constexpr static std::size_t N{sizeof...(Ts)};
83
84 template<std::size_t Lower, std::size_t Upper>
85 requires (Lower <= Upper) && (Upper <= N)
86 constexpr static std::size_t get() noexcept {
87 if constexpr (Lower == Upper)
88 return Lower;
89 else
90 {
91 constexpr auto partition{(Lower + Upper) / 2};
92 if constexpr(Compare<std::tuple_element_t<partition, std::tuple<Ts...>>, U>::value)
93 return get<partition + 1, Upper>();
94 else
95 return get<Lower, partition>();
96 }
97 }
98
99 constexpr static std::size_t value{get<0, N>()};
100 };
101
102 //==================================================== filter ===================================================//
103
104 template<class T, class U>
105 struct filter;
106
107 template<class T, class U>
108 using filter_t = filter<T, U>::type;
109
110 template<template<class...> class TT, class... Ts, std::size_t... Is>
111 requires ((Is < sizeof...(Ts)) && ...)
112 struct filter<TT<Ts...>, std::index_sequence<Is...>>
113 {
114 using type = TT<std::tuple_element_t<Is, std::tuple<Ts...>> ...>;
115 };
116
117 template<class T, template<class> class Trait>
118 struct filter_by_trait;
119
120 template<class T, template<class> class Trait>
121 using filter_by_trait_t = filter_by_trait<T, Trait>::type;
122
123 template<template<class...> class TT, class... Ts, template<class> class Trait>
124 struct filter_by_trait<TT<Ts...>, Trait>
125 {
126 using type = filter_t<TT<Ts...>, make_filtered_sequence<std::false_type, Trait, Ts...>>;
127 };
128
129 //==================================================== drop ===================================================//
130
131 template<class T, std::size_t N>
132 struct drop;
133
134 template<class T, std::size_t N>
135 using drop_t = drop<T, N>::type;
136
137 template<template<class...> class TT, class... Ts, std::size_t N>
138 requires (N >= sizeof...(Ts))
139 struct drop<TT<Ts...>, N>
140 {
141 using type = TT<>;
142 };
143
144 template<template<class...> class TT, class... Ts, std::size_t N>
145 struct drop<TT<Ts...>, N>
146 {
147 using type = filter_t<TT<Ts...>, shift_sequence_t<std::make_index_sequence<sizeof...(Ts) - N>, N>>;
148 };
149
150 //==================================================== keep ===================================================//
151
152 template<class T, std::size_t N>
153 struct keep;
154
155 template<class T, std::size_t N>
156 using keep_t = keep<T, N>::type;
157
158 template<template<class...> class TT, class... Ts, std::size_t N>
159 requires (N >= sizeof...(Ts))
160 struct keep<TT<Ts...>, N>
161 {
162 using type = TT<Ts...>;
163 };
164
165 template<template<class...> class TT, class... Ts, std::size_t N>
166 struct keep<TT<Ts...>, N>
167 {
168 using type = filter_t<TT<Ts...>, std::make_index_sequence<N>>;
169 };
170
171 //==================================================== insert ===================================================//
172
173 template<class T, class U, std::size_t I>
174 struct insert;
175
176 template<class T, class U, std::size_t I>
177 using insert_t = insert<T, U, I>::type;
178
179 template<template<class...> class TT, class U>
180 struct insert<TT<>, U, 0>
181 {
182 using type = TT<U>;
183 };
184
185 namespace impl
186 {
187 template<class...>
188 struct do_insert;
189
190 template<class... Ts>
191 using do_insert_t = do_insert<Ts...>::type;
192
193 template<template<class...> class TT, class T, class... Us, std::size_t... Is, std::size_t... Js>
194 struct do_insert<T, TT<Us...>, std::index_sequence<Is...>, std::index_sequence<Js...>>
195 {
196 using type = TT<std::tuple_element_t<Is, std::tuple<Us...>>..., T, std::tuple_element_t<Js, std::tuple<Us...>>...>;
197 };
198 }
199
200 template<template<class...> class TT, class... Us, class T, std::size_t I>
201 requires (I <= sizeof...(Us))
202 struct insert<TT<Us...>, T, I>
203 {
204 using type = impl::do_insert_t<T,
205 TT<Us...>,
206 std::make_index_sequence<I>,
207 shift_sequence_t<std::make_index_sequence<sizeof...(Us) - I>, I>>;
208 };
209
210 //==================================================== erase ===================================================//
211
212 template<class T, std::size_t I>
213 struct erase;
214
215 template<class T, std::size_t I>
216 using erase_t = erase<T, I>::type;
217
218 template<template<class...> class TT, class T, class... Ts>
219 struct erase<TT<T, Ts...>, 0>
220 {
221 using type = TT<Ts...>;
222 };
223
224 template<template<class...> class TT, class... Ts, std::size_t I>
225 struct erase<TT<Ts...>, I>
226 : filter<TT<Ts...>,
227 concat_sequences_t<std::make_index_sequence<I>,
228 shift_sequence_t<std::make_index_sequence<sizeof...(Ts)-I-1>, I+1>>>
229 {};
230
231 //==================================================== merge ===================================================//
232
233 template<class T, class U, template<class, class> class Compare>
234 struct merge;
235
236 template<class T, class U, template<class, class> class Compare>
237 using merge_t = merge<T, U, Compare>::type;
238
239 template<template<class...> class TT, class... Ts, template<class, class> class Compare>
240 struct merge<TT<Ts...>, TT<>, Compare>
241 {
242 using type = TT<Ts...>;
243 };
244
245 template<template<class...> class TT, class... Ts, template<class, class> class Compare>
246 requires (sizeof...(Ts) > 0)
247 struct merge<TT<>, TT<Ts...>, Compare>
248 {
249 using type = TT<Ts...>;
250 };
251
252 template<template<class...> class TT, class T, class U, template<class, class> class Compare>
253 struct merge<TT<T>, TT<U>, Compare>
254 {
255 using type = TT<U, T>;
256 };
257
258 template<template<class...> class TT, class T, class U, template<class, class> class Compare>
259 requires (Compare<T, U>::value)
260 struct merge<TT<T>, TT<U>, Compare>
261 {
262 using type = TT<T, U>;
263 };
264
265 namespace impl
266 {
267 template<class T, class U, std::size_t I, template<class, class> class Compare>
268 struct merge_from_position;
269
270 template<class T, class U, std::size_t I, template<class, class> class Compare>
271 using merge_from_position_t = merge_from_position<T, U, I, Compare>::type;
272
273 template<template<class...> class TT, class... Us, std::size_t I, template<class, class> class Compare>
274 struct merge_from_position<std::tuple<>, TT<Us...>, I, Compare>
275 {
276 using type = TT<Us...>;
277 };
278
279 template<template<class...> class TT, class T, class... Us, std::size_t I, template<class, class> class Compare>
280 struct merge_from_position<TT<T>, TT<Us...>, I, Compare>
281 {
282 constexpr static auto N{sizeof...(Us)};
283 constexpr static auto Pos{I + lower_bound_v<drop_t<TT<Us...>, I>, T, Compare>};
284 using type = insert_t<TT<Us...>, T, Pos>;
285 };
286
287 template<template<class...> class TT, class T, class... Ts, class... Us, std::size_t I, template<class, class> class Compare>
288 struct merge_from_position<TT<T, Ts...>, TT<Us...>, I, Compare>
289 {
290 using first_merge = merge_from_position<TT<T>, TT<Us...>, 0, Compare>;
291 using type = merge_from_position_t<TT<Ts...>, typename first_merge::type, first_merge::Pos + 1, Compare>;
292 };
293 }
294
295 template<template<class...> class TT, class... Ts, class... Us, template<class, class> class Compare>
296 requires (sizeof...(Ts) > 0) && (sizeof...(Us) > 0)
297 struct merge<TT<Ts...>, TT<Us...>, Compare> : impl::merge_from_position<TT<Ts...>, TT<Us...>, 0, Compare>
298 {};
299
300 //==================================================== stable_sort ===================================================//
301
302 template<class T, template<class, class> class Compare>
303 struct stable_sort;
304
305 template<class T, template<class, class> class Compare>
306 using stable_sort_t = stable_sort<T, Compare>::type;
307
308 template<template<class...> class TT, template<class, class> class Compare>
309 struct stable_sort<TT<>, Compare>
310 {
311 using type = TT<>;
312 };
313
314 template<template<class...> class TT, class T, template<class, class> class Compare>
315 struct stable_sort<TT<T>, Compare>
316 {
317 using type = TT<T>;
318 };
319
320 template<template<class...> class TT, class... Ts, template<class, class> class Compare>
321 struct stable_sort<TT<Ts...>, Compare>
322 {
323 constexpr static auto partition{sizeof...(Ts) / 2};
324 using type = merge_t<stable_sort_t<keep_t<TT<Ts...>, partition>, Compare>,
325 stable_sort_t<drop_t<TT<Ts...>, partition>, Compare>,
326 Compare>;
327 };
328
329 //==================================================== find ===================================================//
330
331 template<class T, class U>
332 struct find;
333
334 template<class T, class U>
335 inline constexpr std::size_t find_v{find<T, U>::index};
336
337 template<template<class...> class TT, class U>
338 struct find<TT<>, U>
339 {
340 constexpr static std::size_t index{};
341 };
342
343 template<template<class...> class TT, class T, class... Ts, class U>
344 struct find<TT<T, Ts...>, U>
345 {
346 constexpr static std::size_t index{std::is_same_v<T, U> ? 0 : 1 + find_v<TT<Ts...>, U>};
347 };
348}
Generated by doxygen 1.9.6