1 /*
2  * Copyright 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ANDROID_AUDIO_UTILS_VARIADIC_UTILS_H
18 #define ANDROID_AUDIO_UTILS_VARIADIC_UTILS_H
19 
20 #include <array>
21 #include <cmath> // for std::sqrt
22 #include <ostream>
23 #include <tuple>
24 #include <utility>
25 
26 namespace android {
27 namespace audio_utils {
28 
29 /**
30  * We provide operator overloading for variadic math and printing.
31  *
32  * A object allowed for variadic operation requires the following:
33  *   1) variadic constructor
34  *   2) support std::get<>
35  *   3) support std::tuple_size<>
36  *   4) support std::tuple_element<>
37  *
38  * Examples of common variadic classes: std::pair, std::tuple, std::array.
39  *
40  * User defined variadic classes will need to create overloaded functions for
41  * std::get, std::tuple_size, std::tuple_element.
42  *
43  * Overloads and functions always check whether the type of the argument is
44  * variadic to prevent false application, unless parameters include a variadic index sequence.
45  * This makes shorter function names safe from name collision as well.
46  */
47 
48 template <typename T, template <typename...> class C>
49 struct is_template : std::false_type {};
50 template <template <typename...> class C, typename... args>
51 struct is_template<C<args...>, C> : std::true_type {};
52 
53 template <typename T> using is_tuple = is_template<std::decay_t<T>, std::tuple>;
54 template <typename T> using is_pair = is_template<std::decay_t<T>, std::pair>;
55 
56 /* is_array<T>::value , different than std::is_array<T>::value */
57 template <typename T>
58 struct is_array_impl : std::false_type {};
59 template <typename T, size_t N>
60 struct is_array_impl<std::array<T, N>> : std::true_type {};
61 template <typename T>
62 struct is_array : is_array_impl<std::decay_t<T>> {};
63 
64 /* is_variadic<T>::value is true if T supports std::tuple_size<T> */
65 struct is_variadic_impl {
66     // SFINAE test(0) prefers this if std::tuple_size<T>::value exists
67     template <typename T> static int test(int, int[std::tuple_size<T>::value] = nullptr);
68     template <typename T> static bool test(...);
69 };
70 
71 template <typename T>
72 struct is_variadic : std::integral_constant<bool,
73     std::is_same<decltype(is_variadic_impl::test<std::decay_t<T>>(0)), int>::value> {};
74 
75 /**
76  * We allow variadic OP variadic or variadic OP scalar or scalar OP variadic
77  *
78  * where OP is +, -, *, /.
79  *
80  * Deep operations are possible on nested variadics, for example:
81  *
82  * std::cout << std::make_pair(0, std::make_pair(1 , 2)) + 2;
83  * -> (2, (3, 4))
84  *
85  */
86 
87 #define MAKE_VARIADIC_BINARY_OPERATOR(OPERATOR, OPERATOR_NAME) \
88 template <typename T1, typename T2, std::size_t... I> \
89 constexpr auto OPERATOR_NAME##_VS(const T1& t1, const T2& t2, std::index_sequence<I...>); \
90 template <typename T1, typename T2, std::size_t... I> \
91 constexpr auto OPERATOR_NAME##_VV(const T1& t1, const T2& t2, std::index_sequence<I...>); \
92 template <typename T1, typename T2, \
93          std::enable_if_t<is_variadic<T1>::value && !is_variadic<T2>::value, int> = 0> \
94 constexpr auto operator OPERATOR(const T1& t1, const T2& t2) { \
95     return OPERATOR_NAME##_VS(t1, t2, std::make_index_sequence<std::tuple_size<T1>::value>{}); \
96 } \
97 template <typename T1, typename T2, \
98          std::enable_if_t<!is_variadic<T1>::value && is_variadic<T2>::value, int> = 0> \
99 constexpr auto operator OPERATOR(const T1& t1, const T2& t2) { \
100     return OPERATOR_NAME##_VS( \
101             t2, t1, std::make_index_sequence<std::tuple_size<T2>::value>{}); \
102 } \
103 template <typename T1, typename T2, \
104          std::enable_if_t<is_variadic<T1>::value && is_variadic<T2>::value, int> = 0> \
105 constexpr auto operator OPERATOR(const T1& t1,  const T2& t2) { \
106     static_assert(std::tuple_size<T1>::value == std::tuple_size<T2>::value, \
107                   #OPERATOR_NAME " size must match"); \
108     return OPERATOR_NAME##_VV(t1, t2, std::make_index_sequence<std::tuple_size<T1>::value>{}); \
109 } \
110 template <typename T1, typename T2, \
111          std::enable_if_t<is_variadic<T1>::value && !is_variadic<T2>::value, int> = 0> \
112 constexpr auto operator OPERATOR##=(T1& t1, const T2& t2) { \
113     t1 = OPERATOR_NAME##_VS(t1, t2, std::make_index_sequence<std::tuple_size<T1>::value>{}); \
114     return t1; \
115 } \
116 template <typename T1, typename T2, \
117          std::enable_if_t<is_variadic<T1>::value && is_variadic<T2>::value, int> = 0> \
118 constexpr auto operator OPERATOR##=(T1& t1,  const T2& t2) { \
119     static_assert(std::tuple_size<T1>::value == std::tuple_size<T2>::value, \
120                   #OPERATOR_NAME " size must match"); \
121     t1 = OPERATOR_NAME##_VV(t1, t2, std::make_index_sequence<std::tuple_size<T1>::value>{}); \
122     return t1; \
123 } \
124 template <typename T1, typename T2, std::size_t... I> \
125 constexpr auto OPERATOR_NAME##_VS(const T1& t1, const T2& t2, std::index_sequence<I...>) { \
126     return T1{std::get<I>(t1) OPERATOR t2...}; \
127 } \
128 template <typename T1, typename T2, std::size_t... I> \
129 constexpr auto OPERATOR_NAME##_VV(const T1& t1, const T2& t2, std::index_sequence<I...>) { \
130     return T1{std::get<I>(t1) OPERATOR std::get<I>(t2)...}; \
131 } \
132 
133 MAKE_VARIADIC_BINARY_OPERATOR(+, plus)
134 MAKE_VARIADIC_BINARY_OPERATOR(-, minus)
135 MAKE_VARIADIC_BINARY_OPERATOR(*, multiplies)
136 MAKE_VARIADIC_BINARY_OPERATOR(/, divides)
137 
138 #undef MAKE_VARIADIC_BINARY_OPERATOR
139 
140 /**
141  * We overload ostream operators for stringification or printing.
142  *
143  * Nested variadics are properly printed.
144  *
145  * std::cout << std::make_pair(1, 2) << std::make_tuple(1., 2., 3.)
146  *           << std::make_pair(0, std::make_pair(3, 4));
147  */
148 
149 // forward declaration of helper
150 template <class charT, class traits, class T, std::size_t... I>
151 auto& ostream_variadic(
152         std::basic_ostream<charT, traits>& os,
153         const T& t,
154         std::index_sequence<I...>);
155 
156 // operator overload
157 template <class charT, class traits, class T, \
158          std::enable_if_t<is_variadic<T>::value, int> = 0> \
159 auto& operator<<(std::basic_ostream<charT, traits>& os, const T& t) { \
160     return ostream_variadic(os, t, std::make_index_sequence<std::tuple_size<T>::value>{}); \
161 }
162 
163 // helper function (recursively calls <<)
164 template <class charT, class traits, class T, std::size_t... I>
165 auto& ostream_variadic(
166         std::basic_ostream<charT, traits>& os,
167         const T& t,
168         std::index_sequence<I...>) {
169     os << "(";
170     // ((os << (I == 0 ? "" : ", ") << std::get<I>(t)), ...); is C++17
171     int temp[] __attribute__((unused)) = { (os << (I == 0 ? "" : ", ") << std::get<I>(t), 0) ... };
172     return os << ")";
173 }
174 
175 /**
176  * We have a fold operator which converts a variadic to a scalar using
177  * a binary operator.
178  *
179  * Following standard binary operator convention, it is a left-associative fold.
180  *
181  * Example:
182  *
183  * fold(std::plus<>(), std::make_pair(1, 2));
184  *
185  * This is a shallow operation - does not recurse through nested variadics.
186  */
187 
188 // helper
189 template <size_t index, typename Op, typename T,
190           std::enable_if_t<index == 0 && is_variadic<T>::value, int> = 0>
191 constexpr auto fold(Op&& op __attribute__((unused)), T&& t) {
192     return std::get<index>(std::forward<T>(t));
193 }
194 
195 // helper
196 template <size_t index, typename Op, typename T,
197           std::enable_if_t<(index > 0) && is_variadic<T>::value, int> = 0>
198 constexpr auto fold(Op&& op, T&& t) {
199     return op(fold<index - 1>(std::forward<Op>(op), t), std::get<index>(std::forward<T>(t)));
200 }
201 
202 // variadic
203 template <typename Op, typename T,
204           std::enable_if_t<is_variadic<T>::value, int> = 0>
205 constexpr auto fold(Op&& op, T&& t)  {
206     return fold<std::tuple_size<T>::value - 1>(std::forward<Op>(op), std::forward<T>(t));
207 }
208 
209 
210 /**
211  * tupleOp returns a tuple resulting from an element-wise operation on two variadics.
212  *
213  * the type of each tuple element depends on the return value of the op.
214  *
215  * This is a shallow operation - does not recurse through nested variadics.
216  */
217 // helper
218 template <typename Op, typename T1, typename T2, std::size_t... I,
219          std::enable_if_t<is_variadic<T1>::value && is_variadic<T2>::value, int> = 0>
220 constexpr auto tupleOp(Op&& op, T1&& t1, T2&& t2, std::index_sequence<I...>) {
221     return std::make_tuple(
222             op(std::get<I>(std::forward<T1>(t1)), std::get<I>(std::forward<T2>(t2)))...);
223 }
224 
225 // variadic
226 template <typename Op, typename T1, typename T2,
227          std::enable_if_t<is_variadic<T1>::value && is_variadic<T2>::value, int> = 0>
228 constexpr auto tupleOp(Op&& op, T1&& t1, T2&& t2) {
229     static_assert(std::tuple_size<std::remove_reference_t<T1>>::value
230             == std::tuple_size<std::remove_reference_t<T2>>::value,
231             "tuple size must match");
232     return tupleOp(std::forward<Op>(op),
233                    std::forward<T1>(t1),
234                    std::forward<T2>(t2),
235                    std::make_index_sequence<
236                            std::tuple_size<std::remove_reference_t<T1>>::value>());
237 }
238 
239 /**
240  *  equivalent compares two variadics OR scalars
241  *
242  * equivalent(std::make_pair(1, 2), std::make_tuple(1, 2)) == true
243  *
244  * Does a deep compare through nested variadics.
245  *
246  * Does not do short-circuit evaluation.
247  * C++17 will allow for a better implementation of this.
248  */
249 
250 // scalar
251 template <typename T1, typename T2,
252           std::enable_if_t<!is_variadic<T1>::value && !is_variadic<T2>::value, int> = 0>
253 constexpr bool equivalent(const T1& t1, const T2& t2) {
254     return t1 == t2;
255 }
256 
257 // variadic / scalar mismatch overload
258 template <typename T1, typename T2,
259           std::enable_if_t<is_variadic<T1>::value != is_variadic<T2>::value, int> = 0>
260 constexpr bool equivalent(const T1& t1 __attribute__((unused)),
261         const T2& t2 __attribute__((unused))) {
262     return false;
263 }
264 
265 // variadic
266 template <typename T1, typename T2,
267           std::enable_if_t<is_variadic<T1>::value && is_variadic<T2>::value, int> = 0>
268 constexpr bool equivalent(const T1& t1, const T2& t2) {
269     return std::tuple_size<T1>::value == std::tuple_size<T2>::value
270         && fold([](const bool& v1, const bool& v2) { return v1 && v2; },
271                 tupleOp([](const auto &v1, const auto &v2) { return equivalent(v1, v2); },
272                           t1, t2));
273 }
274 
275 /**
276  *  The innerProduct is the dot product of two 1D variadics.
277  *
278  * innerProduct(std::make_pair(1, 2), std::make_pair(3, 4)) == 11
279  */
280 
281 template <typename T1, typename T2,
282           std::enable_if_t<is_variadic<T1>::value && is_variadic<T2>::value, int> = 0>
283 constexpr auto innerProduct(const T1& t1, const T2& t2) {
284     return fold(std::plus<>{}, t1 * t2);
285 }
286 
287 /**
288  * The outerProduct is the tensor product of two 1D variadics.
289  *
290  * This only returns tuples, regardless of the input.
291  *
292  * outerProduct(std::make_tuple(1, 2), std::make_tuple(1, 2)) ==
293  * std::make_tuple(1, 2, 2, 4);
294  *
295  */
296 
297 // helper
298 template <typename T1, typename T2, std::size_t... I>
299 constexpr auto outerProduct(const T1& t1, const T2& t2, std::index_sequence<I...>)  {
300     return std::tuple_cat(std::get<I>(t1) * t2 ...);
301 }
302 
303 // variadic
304 template <typename T1, typename T2,
305           std::enable_if_t<is_variadic<T1>::value && is_variadic<T2>::value, int> = 0>
306 constexpr auto outerProduct(const T1& t1, const T2& t2) {
307     return outerProduct(t1, t2, std::make_index_sequence<std::tuple_size<T1>::value>());
308 }
309 
310 /**
311  * tail_variadic returns the tail offset by a template size_t Offset
312  * of a variadic object. It always returns a tuple.
313  */
314 
315 // helper
316 template <size_t Offset, typename T, std::size_t... I>
317 constexpr auto tail_variadic(T&& t, std::index_sequence<I...>) {
318     return std::make_tuple(std::get<I + Offset>(std::forward<T>(t))...);  // force a tuple here
319 }
320 
321 // variadic
322 template <size_t Offset, typename T,
323           std::enable_if_t<is_variadic<T>::value, int> = 0>
324 constexpr auto tail_variadic(T&& t) {
325     return tail_variadic<Offset>(
326            std::forward<T>(t),
327            std::make_index_sequence<std::tuple_size<
328                    std::remove_reference_t<T>>::value - Offset>());
329 }
330 
331 /**
332  * The outerProduct_UT is the tensor product of two identical length 1D variadics,
333  * but only the upper triangular portion, eliminating the symmetric lower triangular
334  * half.  This is useful for the outerProduct of two parallel variadics.
335  *
336  * This only returns tuples, regardless of the input.
337  *
338  * outerProduct_UT(std::make_tuple(1, 2, 3), std::make_tuple(1, 2, 3)) ==
339  * std::make_tuple(1, 2, 3, 4, 6, 9);
340  */
341 
342 // helper
343 template <typename T1, typename T2, std::size_t... I>
344 constexpr auto outerProduct_UT(const T1& t1, const T2& t2, std::index_sequence<I...>)  {
345     return std::tuple_cat(std::get<I>(t1) * tail_variadic<I>(t2) ...);
346 }
347 
348 // variadic
349 template <typename T1, typename T2,
350           std::enable_if_t<is_variadic<T1>::value && is_variadic<T2>::value, int> = 0>
351 constexpr auto outerProduct_UT(const T1& t1, const T2& t2) {
352     static_assert(std::tuple_size<T1>::value == std::tuple_size<T2>::value,
353                   "tuple size must match");
354     return outerProduct_UT(t1, t2, std::make_index_sequence<std::tuple_size<T1>::value>());
355 }
356 
357 /**
358  * to_array does a conversion of any variadic to a std::array whose element type is
359  * the input variadic's first tuple element and whose size is the tuple size.
360  * This is a shallow operation and does not work on nested variadics.
361  */
362 
363  // helper
364 template <typename T, std::size_t...I>
365 constexpr auto to_array(const T &t, std::index_sequence<I...>) {
366     return std::array<std::tuple_element_t<0, T>, std::tuple_size<T>::value>{std::get<I>(t)...};
367 }
368 
369 // variadic
370 template <typename T>
371 constexpr auto to_array(const T &t) {
372      return to_array(t, std::make_index_sequence<std::tuple_size<T>::value>());
373 }
374 
375 /**
376  * We create functor versions of the inner and outer products to
377  * pass in as a type argument to a template.  A tuple and an array
378  * return variant are provided.
379  *
380  * See related: std::function<>.
381  */
382 
383 template <typename T>
384 struct innerProduct_scalar {
385     constexpr auto operator()(const T &lhs, const T &rhs) const {
386         return innerProduct(lhs, rhs);
387     }
388 };
389 
390 template <typename T>
391 struct outerProduct_tuple {
392     constexpr auto operator()(const T &lhs, const T &rhs) const {
393         return outerProduct(lhs, rhs);
394     }
395 };
396 
397 template <typename T>
398 struct outerProduct_UT_tuple {
399     constexpr auto operator()(const T &lhs, const T &rhs) const {
400         return outerProduct_UT(lhs, rhs);
401     }
402 };
403 
404 template <typename T>
405 struct outerProduct_array {
406     constexpr auto operator()(const T &lhs, const T &rhs) const {
407         return to_array(outerProduct(lhs, rhs));
408     }
409 };
410 
411 template <typename T>
412 struct outerProduct_UT_array {
413     constexpr auto operator()(const T &lhs, const T &rhs) const {
414         return to_array(outerProduct_UT(lhs, rhs));
415     }
416 };
417 
418 /**
419  * for_each is used to apply an operation to each element of a variadic OR scalar object.
420  *
421  * auto t = std:make_tuple(1, 2);
422  * for_each([](int &x) { ++x; }, t);
423  *
424  * Related: std::for_each<>
425  * Note difference from std::apply, which forwards tuple elements as arguments to a function.
426  */
427 
428 // helper
429 template <typename T, typename Op, std::size_t... I >
430 constexpr void for_each(T& t, Op op, std::index_sequence<I...>) {
431     int temp[] __attribute__((unused)) = {(op(std::get<I>(t)), 0)...};
432 }
433 
434 // variadic
435 template <typename T, typename Op,
436           std::enable_if_t<is_variadic<T>::value, int> = 0>
437 constexpr void for_each(T& t, Op op) {
438     for_each(t, op, std::make_index_sequence<std::tuple_size<T>::value>());
439 }
440 
441 // scalar version applies if not a class, rather than not a variadic
442 template <typename T, typename Op,
443           std::enable_if_t<!std::is_class<T>::value, int> = 0>
444 constexpr void for_each(T& t, Op op) {
445     op(t);
446 }
447 
448 /**
449  * We make variants of the unary function std::sqrt()
450  * and the binary std::min(), std::max() to work on variadics.
451  *
452  * These are shallow operations and do not work on nested variadics.
453  *
454  * TODO: update to variadic function application for C++17
455  * with built-in std::apply, std::invoke, and constexpr lambdas.
456  *
457  */
458 
459 #define MAKE_VARIADIC_STD_UNARY_FUNCTION(FUNCTION) \
460 template <typename T, \
461           std::enable_if_t<!is_variadic<T>::value, int> = 0> \
462 constexpr auto FUNCTION(const T &t) { \
463     return std::FUNCTION(t); \
464 } \
465 template <typename T, std::size_t... I > \
466 constexpr auto FUNCTION(const T &t, std::index_sequence<I...>) { \
467     return T{audio_utils::FUNCTION(std::get<I>(t))...}; \
468 } \
469 template <typename T, \
470           std::enable_if_t<is_variadic<T>::value, int> = 0> \
471 constexpr auto FUNCTION(const T& t) { \
472     return audio_utils::FUNCTION(t, std::make_index_sequence<std::tuple_size<T>::value>()); \
473 }
474 
475 MAKE_VARIADIC_STD_UNARY_FUNCTION(sqrt);
476 
477 #undef MAKE_VARIADIC_STD_UNARY_FUNCTION
478 
479 #define MAKE_VARIADIC_STD_BINARY_FUNCTION(FUNCTION) \
480 template <typename T1, typename T2, \
481           std::enable_if_t<!is_variadic<T1>::value && !is_variadic<T2>::value, int> = 0> \
482 constexpr auto FUNCTION(const T1 &t1, const T2 &t2) { \
483     return std::FUNCTION(t1, t2); \
484 } \
485 template <typename T1, typename T2, std::size_t... I > \
486 constexpr auto FUNCTION(const T1 &t1, const T2 &t2, std::index_sequence<I...>) { \
487     return T1{audio_utils::FUNCTION(std::get<I>(t1), std::get<I>(t2))...}; \
488 } \
489 template <typename T1, typename T2, \
490           std::enable_if_t<is_variadic<T1>::value && is_variadic<T2>::value, int> = 0> \
491 constexpr auto FUNCTION(const T1 &t1, const T2 &t2) { \
492     static_assert(std::tuple_size<T1>::value == std::tuple_size<T2>::value, \
493                   #FUNCTION " size must match"); \
494     return audio_utils::FUNCTION( \
495             t1, t2, std::make_index_sequence<std::tuple_size<T1>::value>()); \
496 }
497 
498 MAKE_VARIADIC_STD_BINARY_FUNCTION(min);
499 MAKE_VARIADIC_STD_BINARY_FUNCTION(max);
500 
501 /* is_iterator<T>::value is true if T supports std::iterator_traits<T>
502 
503    TODO: poor resolution on iterator type, prefer emulating hidden STL templates
504    __is_input_iterator<>
505    __is_forward_iterator<>
506    ...
507  */
508  // helper
509 struct is_iterator_impl {
510     // SFINAE test(0) preferred if iterator traits
511     template <typename T,
512               typename = typename std::iterator_traits<T>::difference_type,
513               typename = typename std::iterator_traits<T>::value_type,
514               typename = typename std::iterator_traits<T>::pointer,
515               typename = typename std::iterator_traits<T>::iterator_category>
516               static int test(int);
517     template <typename T> static bool test(...);
518 };
519 
520 template <typename T>
521 struct is_iterator : std::integral_constant<bool,
522     std::is_same<decltype(is_iterator_impl::test<std::decay_t<T>>(0)), int>::value> {};
523 
524 
525 } // namespace audio_utils
526 } // namespace android
527 
528 #endif // !ANDROID_AUDIO_UTILS_VARIADIC_UTILS_H
529