Filter the list of values ​​at compile time with gnu ++ 11 and not stdlib (Arduino environment)

Question

I am working on an Arduino project, which means that at the moment the C ++ dialect is a gnu ++ 11 C ++ 11 add- on, and stdlib is not available (no tuples, no arrays, nothing, the std namespace is just empty!).

For optimization reasons (the processor has 16 KB of FLASH, 2 KB of RAM, and this low-voltage version runs at 8 MHz). I want the compiler to maximize the execution time of the execution code, especially the interrupt service routines, with "friendly" data.

Now I would like to do the following:

given a list of (unique) integers, I want to extract the values ​​corresponding to an arbitrary filter. Then I want to create an index table that will allow the filtered elements to be reached through their starting indexes

For example, 2,10,4,7,9,3with a filter, it value < 8can give a filtered list 2,4,7,3and an index table 0,-1,1,2,-1,3.
The order of the elements in the filtered array does not matter as long as the index table remains consistent.

I insist that I need constant arrays . Producing this data dynamically would be trivial, but I want the compiler to do the job without executing any instructions at runtime.

The initial list will be set simple #define, and the results will be in a constant array , for example:

#define my_list 2,10,4,7,9,3

constexpr bool filter (int value) { return value < 8; }

const int    filtered_list [] = filter_list <filter>(my_list);
const size_t filtered_index[] = filter_index<filter>(my_list);

The question is how to implement these patterns filter_listand filter_indexa barebone C ++ 11 and without stdlib, if at all possible?

I'm not interested in error handling, anomalous cases, such as empty lists or duplicate values, have already been taken care of. I would prefer to see the simplest possible implementation, even if some assumptions about the reliability of the data are made.

The exact form of the template, filter, or source list does not matter either. All that matters is getting arrays from a unique list definition.
For example, I would not mind the syntax when each element of the list is declared separately (although I can not imagine how this can work).

++. , , Python , , std:: array std:: tuple, - .

Answer 1

. , ++ 11. int typename T, . , atmel gcc5 ++ 14.

#define LIST  2,10,4,7,9,3
constexpr bool less8(int v) { return v < 8; }

typedef bool(*predicate)(int);

template<int... values>
struct seq {};

template<int N>
struct array {
      const int   data[N];
};

template<int... values>
constexpr array<sizeof...(values)> to_array(seq<values...>) { return {{ values... }}; }

template<typename trueType, typename falseType>
constexpr falseType select(seq<0>, trueType, falseType) { return {}; }

template<typename trueType, typename falseType>
constexpr trueType select(seq<1>, trueType, falseType) { return {}; }

template<int... first, int... second>
constexpr seq<first..., second...> append(seq<first...>, seq<second...>) { return {}; }

template<predicate p, typename N, typename V>
struct filter_impl;

template<predicate p, int next>
struct filter_impl<p, seq<next>, seq<>> {
      using type = seq<>;
};

template<predicate p, int next, int first, int... rest>
struct filter_impl<p, seq<next>, seq<first, rest...>> {
      using type = decltype(
            append(
                  select(seq<p(first)>{}, seq<next>{}, seq<-1>{}),
                  typename filter_impl<p, decltype(select(seq<p(first)>{}, seq<next+1>{}, seq<next>{})), seq<rest...>>::type{}
            )
      );
};

extern constexpr auto  const_indices = to_array(filter_impl<less8, seq<0>, seq<LIST>>::type{});

Answer 2

, . . (, , ++ . , , , true, , show-stopper . , , array -.)

#include <sys/types.h>

template <typename T, size_t N>
struct array {
    T elem[N];
    constexpr size_t size() const { return N; }
    constexpr T operator[](size_t i) const { return elem[i]; }
    T* begin() { return elem; }
    const T* begin() const { return elem; }
    T* end() { return elem + N; }
    const T* end() const { return elem; }
};
template <typename T>
struct array<T, 0> {
    constexpr size_t size() const { return 0; }
    T* begin() { return nullptr; }
    const T* begin() const { return nullptr; }
    T* end() { return nullptr; }
    const T* end() const { return nullptr; }
};

template <typename T, T... x>
struct static_sequence { };

template <bool p, typename TrueT, typename FalseT>
struct conditional;
template <typename TrueT, typename FalseT>
struct conditional<true, TrueT, FalseT> {
    using type = TrueT;
};
template <typename TrueT, typename FalseT>
struct conditional<false, TrueT, FalseT> {
    using type = FalseT;
};
template <bool p, typename TrueT, typename FalseT>
using conditional_t = typename conditional<p, TrueT, FalseT>::type;

template <typename T, T x, typename S>
struct static_sequence_cons;
template <typename T, T x, T... Ss>
struct static_sequence_cons<T, x, static_sequence<T, Ss...>> {
    using type = static_sequence<T, x, Ss...>;
};
template <typename T, T x, typename S>
using static_sequence_cons_t = typename static_sequence_cons<T, x, S>::type;

template <typename T, bool(*pred)(T), T... N>
struct filter;
template <typename T, bool(*pred)(T)>
struct filter<T, pred> {
    using type = static_sequence<T>;
};
template <typename T, bool(*pred)(T), T hd, T... tl>
struct filter<T, pred, hd, tl...> {
private:
    using filter_tl = typename filter<T, pred, tl...>::type;
public:
    using type = conditional_t<pred(hd),
                               static_sequence_cons_t<T, hd, filter_tl>,
                               filter_tl>;
};
template <typename T, bool(*pred)(T), T... N>
using filter_t = typename filter<T, pred, N...>::type;

template <ssize_t curr_index, typename T, bool(*pred)(T), T... N>
struct filter_index;
template <ssize_t curr_index, typename T, bool(*pred)(T)>
struct filter_index<curr_index, T, pred> {
    using type = static_sequence<ssize_t>;
};
template <ssize_t curr_index, typename T, bool(*pred)(T), T hd, T... tl>
struct filter_index<curr_index, T, pred, hd, tl...> {
    using type = conditional_t<pred(hd),
        static_sequence_cons_t<ssize_t, curr_index, typename filter_index<curr_index + 1, T, pred, tl...>::type>,
        static_sequence_cons_t<ssize_t, -1, typename filter_index<curr_index, T, pred, tl...>::type>>;
};
template <typename T, bool(*pred)(T), T... N>
using filter_index_t = typename filter_index<0, T, pred, N...>::type;

template <typename T, T... x>
constexpr array<T, sizeof...(x)> static_sequence_to_array(
    static_sequence<T, x...>) {
    return array<T, sizeof...(x)> { x... };
}


//
// EXAMPLE USAGE
//
constexpr bool even(int n) {
    return n % 2 == 0;
}
constexpr auto x = static_sequence_to_array(
    filter_t<int, even, 0, 1, 2, 3, 4>{});
constexpr auto i = static_sequence_to_array(
    filter_index_t<int, even, 0, 1, 2, 3, 4>{});

static_assert(x.size() == 3, "Bad filter");
static_assert(x[0] == 0, "Bad filter");
static_assert(x[1] == 2, "Bad filter");
static_assert(x[2] == 4, "Bad filter");
static_assert(i.size() == 5, "Bad filter_index");
static_assert(i[0] == 0, "Bad filter_index");
static_assert(i[1] == -1, "Bad filter_index");
static_assert(i[2] == 1, "Bad filter_index");
static_assert(i[3] == -1, "Bad filter_index");
static_assert(i[4] == 2, "Bad filter_index");

Answer 3

, .

. , , . .

//////////////////////////////////////////////////////////////////////////////
// should allow to compile outside Arduino environment without std includes
typedef unsigned char uint8_t;
typedef unsigned size_t;

//////////////////////////////////////////////////////////////////////////////
// pseudo-stl

// barebone std::array
template <typename T, size_t N> struct array {
    T elem[N];
    constexpr size_t size() { return N; }
    constexpr T operator[](size_t i) { return elem[i]; }
};

// barebone std::integer_sequence
template <typename T, T... Values> struct integer_sequence
{
    typedef T value_type;
};

//////////////////////////////////////////////////////////////////////////////
// sequence filtering

// predicate functions prototype (means the sequence type must be convertible to int)
typedef bool(*predicate)(int);

// LISP-like 'if' (selects a parameter according to a boolean value)
template <bool Check, typename IfTrue, typename IfFalse> struct s_if;
template <typename IfTrue, typename IfFalse> struct s_if<true , IfTrue, IfFalse> {using type = IfTrue ;};
template <typename IfTrue, typename IfFalse> struct s_if<false, IfTrue, IfFalse> {using type = IfFalse;};
template <bool Check, typename IfTrue, typename IfFalse>
using f_if = typename s_if<Check, IfTrue, IfFalse>::type;

// LISP-like 'cons' for integer_sequence
template <typename T, T Car, typename Cdr> struct s_integer_sequence_cons;
template <typename T, T Car, T... Cdr> struct s_integer_sequence_cons<T, Car, integer_sequence<T, Cdr...>>
{ using type = integer_sequence<T, Car, Cdr...>; };
template <typename T, T Car, typename Cdr>
using f_cons = typename s_integer_sequence_cons<T, Car, Cdr>::type;

// LISP-like 'append' for integer_sequence
template <typename T, typename S1, typename S2> struct s_integer_sequence_append;
template <typename T, T... S1, T... S2> struct s_integer_sequence_append<T, integer_sequence<T, S1...>, integer_sequence<T, S2...>>
{ using type = integer_sequence<T, S1..., S2...>; };
template <typename S1, typename S2>
using f_append = typename s_integer_sequence_append<S1::value_type, S1, S2>::type;

// filter an integer_sequence according to a predicate
template <typename Sequence, predicate pred> struct s_filter;
template <typename T, predicate pred> struct s_filter<integer_sequence<T>, pred>
{
    using type = integer_sequence<T>; // termination condition
};
template <typename T, T Car, T...Cdr, predicate pred> struct s_filter<integer_sequence<T, Car, Cdr...>, pred>
{
    using tail = typename s_filter<integer_sequence<T, Cdr...>, pred>::type; // forward recursion on the sequence tail
    using type = f_if<pred(Car),            // if current element satisfies the predicate
                      f_cons<T, Car, tail>, // add it to the list
                      tail>;                // else skip it
};
template <typename Sequence, predicate pred>
using f_filter = typename s_filter<Sequence, pred>::type;

//////////////////////////////////////////////////////////////////////////////
// now for the indexation...

// returns the index of a value in a list of values, or -1 if not found
template <int I  , typename T> constexpr T find_index (T elem) { return -1; }
template <int I=0, typename T, typename... List> constexpr T find_index (T elem, T val, List... rest)
{ return elem == val ? I : find_index<I+1>(elem, rest...); }

// builds an index list allowing to reach each value final position from their initial position
template <typename Target, typename Origin> struct s_index_list;
template <typename T, typename Origin> struct s_index_list<integer_sequence<T>, Origin>
{ 
    using type = integer_sequence<T>; // termination of the Target list
};
template <typename T, T Car, T... Cdr, T...Origin> struct s_index_list<integer_sequence<T, Car, Cdr...>, integer_sequence<T, Origin...>>
{
    // as usual, the only way to loop is to recurse...
    using tail = typename s_index_list<integer_sequence<T, Cdr...>, integer_sequence<T, Origin...>>::type;
    using type = f_cons<T, find_index(Car, Origin...), tail>;
};
template <typename Target, typename Origin>
using f_index = typename s_index_list<Target, Origin>::type;

//////////////////////////////////////////////////////////////////////////////
// implementing sequences as arrays

// turn an integer_sequence into a (constant) array
template <typename T, T... x> constexpr array<T, sizeof...(x)> integer_sequence_to_array(integer_sequence<T, x...>)
{ return array<T, sizeof...(x)> { x... }; }

//////////////////////////////////////////////////////////////////////////////
// Putting all this marvelous piece of engineering to use
//

// our initial list
#define input_list 2,10,4,7,9,3

// convert the list into a sequence
typedef integer_sequence<uint8_t, input_list> input_sequence;

// define filtering predicates
constexpr bool test_group_1(int n) { return (n >> 3) == 0; } // values from 0 to 7
constexpr bool test_group_2(int n) { return (n >> 3) == 1; } // values from 8 to 15

// compute the two split sequences
typedef f_filter<input_sequence, test_group_1> sequence_1; // <unsigned char, 2u, 4u, 7u, 3u>
typedef f_filter<input_sequence, test_group_2> sequence_2; // <unsigned char, 10u, 9u>

// append them
typedef f_append<sequence_1, sequence_2> output_sequence; // <unsigned char, 2u, 4u, 7u, 3u, 10u, 9u>

// compute indexes
typedef f_index<output_sequence, input_sequence> output_indexes; // <unsigned char, 0u, 2u, 3u, 5u, 1u, 4u>

// turn the results into arrays
constexpr auto const_values  = integer_sequence_to_array(output_sequence{}); // [2, 4, 7, 3,10, 9]
constexpr auto const_indexes = integer_sequence_to_array(output_indexes {}); // [0, 2, 3, 5, 1, 4]

- . 20 , (Python, PHP, Perl, awk, ...),

#define my_list 2,10,4,7,9,3

const int    filtered_list [] = {2,4,7,3};
const size_t filtered_index[] = {0,-1,1,2,-1,3};

++.

, ++, - Arduino. , , . Arduino make , , " Arduino" , gnu ++ 11, stdlib.

, ++ , .

, , , . , , , .

LISP, , cons, append if, -, , . . , , .

, , , stdlib . , .

I finally came up with something that actually does the job of just under 100 lines of very confusing code.

I'm not looking for efficiency here, my lists are unlikely to contain more than a dozen values, but I would be happy to observe and learn to achieve the same result with less source code. Any members?