data.array ≡

Perform an inclusive scan on the given array.

>>> inclusive_scan<uint8>({1, 2, 3}, add);
{1, 3, 6}

Compute the prefix sum of the given array.

>>> prefix_sum<uint1>({1});
{1}

>>> prefix_sum<uint3>({0, 1, 2, 3});
{0, 1, 3, 6}

An inline function that returns the smallest N elements seen in a sequence of elements so far, provided one at a time over multiple calls. Internally, this is achieved by using a pipeline of N atomic stages each of which accepts an element, compares it with its current smallest, and swaps the two if the provided lambda returns true. The remaining element is then passed onto the next stage, or discarded if no stage follows. This iterative nature is suitable for use inside a [[pipelined]] function which would supply one piece of data per cycle (for example, extracted from a memory).

One use case for this component would be as part of a multi-pass sorter; the first pass over the dataset would extract the smallest N elements, and by preventing those returned elements from being considered again each following pass would extract the next smallest N elements until the dataset is fully sorted.

const auto N = 6;
uint8[N] input = {5, 1, 3, 2, 7, 3};
optional<uint8>[6] sorted = pipelined_last(N, [input, N](index_t<N> tid)
{
    return partial_sort<6>(input[tid], less_than<uint8>, tid == N - 1);
});
print(sorted);
// {{true, 1}, {true, 2}, {true, 3}, {true, 3}, {true, 5}, {true, 7}}

Bitonic sorting network. Sorts the passed array such that cmp(x[i], x[i + 1]) is true for all items.

>>> bitonic_sort({4, 2, 3, 1}, less_than<uint32>);
{1, 2, 3, 4}

Given an array of optional<T>, return the last (highest array index) item with is_valid true. If there are no items with is_valid true, then the returned optional<T> has is_valid set to false.

>>> last_valid<uint8>({{false, 0xAB}, {false, 0x22}});
{false, 0xAB}

>>> last_valid<uint8>({{true, 0xCD}, {true, 0xFF}});
{true, 0xFF}

Transpose rows and columns in a 2-dimensional array.

Shift the elements of an arbitrary-typed array right by the given number of positions, with the possibility of returning a different number of elements as the input array. Once the input array has been exhausted, default (zero)-initialized elements will be shifted in from the end of the array.

>>> shift_array_right<5>({0, 1, 2, 3, 4}, 0);
{0, 1, 2, 3, 4}

>>> shift_array_right<4>({0, 1, 2, 3, 4}, 2);
{2, 3, 4, 0}

>>> shift_array_right<4>({0, 1, 2, 3, 4}, 10);
{0, 0, 0, 0}

Drop first M elements of an array

>>> drop<2>({0, 1, 2, 3, 4});
{2, 3, 4}

Return an array containing all but the first element

>>> tail({0, 1, 2, 3, 4});
{1, 2, 3, 4}

Take first M elements of an array

>>> take<2>({0, 1, 2, 3, 4});
{0, 1}

Return the array without the last element

>>> init({0, 1, 2, 3, 4});
{0, 1, 2, 3}

Intersperse a value between elements of an array

>>> intersperse(-1, {0, 1, 2, 3, 4});
{0, -1, 1, -1, 2, -1, 3, -1, 4}

Shift the elements of an arbitrary-typed array left by the given number of positions, with the possibility of returning a different number of elements as the input array. Once the input array has been exhausted, default (zero) -initialized elements will be shifted in from the beginning of the array.

>>> uint32[5] a = shift_array_left({0, 1, 2, 3, 4}, 0);
{0, 1, 2, 3, 4}

>>> uint32[4] a = shift_array_left({0, 1, 2, 3, 4}, 2);
{0, 0, 0, 1}

>>> uint32[4] a = shift_array_left({0, 1, 2, 3, 4}, 10);
{0, 0, 0, 0}

Rotate the elements of an arbitrary-typed array right by the given number of positions, with the possibility of returning a different number of elements as the input array. Elements that are rotated past the beginning of the array will wrap-around and re-appear at the end of the array. If this wrap-around behaviour is not strictly necessary, consider if shift_array_right may be more efficient.

>>> uint32[5] a = rotate_array_right({0, 1, 2, 3, 4}, 0);
{0, 1, 2, 3, 4}

>>> uint32[4] a = rotate_array_right({0, 1, 2, 3, 4}, 2);
{ 2, 3, 4, 0}

Rotate the elements of an arbitrary-typed array left by the given number of positions, with the possibility of returning a different number of elements as the input array. Elements that are rotated past the end of the array will wrap-around and re-appear at the beginning of the array. If this wrap-around behaviour is not strictly necessary, consider if shift_array_left may be more efficient.

>>> uint32[5] a = rotate_array_left({0, 1, 2, 3, 4}, 0);
{0, 1, 2, 3, 4}

>>> uint32[4] a = rotate_array_left({0, 1, 2, 3, 4}, 2);
{3, 4, 0, 1}

Map array of input values to result values.

>>> map([](bool b){ return !b; }, {true, false, false});
{false, true, true}

>>> map([](uint32 a){ return a + 1; }, {1, 2, 3});
{2, 3, 4}

Map array of indices to result values.

>>> map_indices<3>(id)
{0, 1, 2}

Right-associative fold of an array.

When f is associative reduce is more efficient.

>>> foldr(f, {0, 1, 2, 3})
f(0, f(1, f(2, 3)));

>>> foldr(f, {1})
1

Left-associative fold of an array.

When f is associative reduce is more efficient.

>>> foldl(f, {0, 1, 2, 3})
f(3, f(2, f(1, 0)));

>>> foldl(f, {1})
1

Implement a binary reducer tree using a function to reduce a pair of inputs.

>>> reduce(add, {0x9, 0x2, 0x5});
0x10

>>> reduce<bool>([](bool x, bool y){ return x || y; }, {false, true, false});
true

Implements map-reduce. Inputs are first mapped into the appropriate result type, and then reduced to a single output using a binary reduction tree.

map_reduce
    ( [](uint8 a){ return a % 2 == 0; }
    , [](bool x, bool y){ return x && y; }
    , {2, 4, 6}
    );
// true; all values are even.

Returns true if any of the elements are true.

>>> or({true})
true

>>> or({false})
false

>>> or({true,true,false})
true

Returns true if all of the elements are true.

>>> and({true})
true

>>> and({false})
false

>>> and({true,true,false})
false

Returns true if any of the elements of array satisfies the predicate.

>>> any([](uint8 x){ return x > 3; }, {1, 2, 3});
false

>>> any([](uint8 x){ return x > 3; }, {1, 2, 3, 4});
true

Returns true if all elements of the array satisfy the predicate.

>>> all([](uint8 x){ return x < 3; }, {1, 2});
true

>>> all([](uint8 x){return x < 3; }, {1, 2, 3});
false

Combines elements of two arrays using specified function.

>>> zip_with(add, {1, 2, 3}, {4, 5, 6});
{5, 7, 9}

>>> zip_with(make_optional<uint8>, {true, true, false}, {1, 2, 3});
{{true, 1}, {true, 2}, {false, 3}}

Map array of input values and their indices to result values.

>>> zip_with_indices( [](index_t<4> i, uint8 byte)
                      {
                          return even(i) ? 0xFF : byte;
                      }
                    , {0x00, 0xAB, 0xBC, 0xDE}
                    )
{0xFF, 0xAB, 0xFF, 0xDE}

Combines two arrays into an array of pairs.

>>> zip({true, false, false}, {1, 2, 3});
{{true, 1}, {false, 2}, {false, 3}}

Returns array with each element value equal to its index.

>>> indices<4>();
{0, 1, 2, 3}

>>> uint32[7] a = indices();
{0, 1, 2, 3, 4, 5, 6}

Returns minimum element from an array of integers.

>>> minimum({5, 3, 87, 22});
3

Returns maximum value in the array of integers.

>>> maximum({5, 3, 87, 22});
87

Sum elements in an array.

>>> sum<uint9>({0xFF, 0x2F, 0x5E});
0x18C

Given an array of optional<T>, return the first (lowest array index) item with is_valid true. If there are no items with is_valid true, then the returned optional<T> has ‘is_valid’ set to false.

>>> first_valid<uint8>({{false, 0xAB}, {false, 0x22}});
{false, 0x22}

>>>  first_valid<uint8>({{true, 0xCD}, {true, 0xFF}});
{true, 0xCD}

Copies an array or creates a subset of an array.

>>> copy_array({1, 2, 3, 4}, 1, {0xFF, 0xFF, 0xFF}, 0, 2);
{2, 3, 0xFF}

De-duplicate array elements with user-supplied equality predicate. For each element e, check the previous elements for duplicates. If there are any duplicates, mark element e as invalid. Returns an array of optionals where all valid elements are unique.

>>> unique_by(order::equal<uint32>, {0, 1, 0});
{{true, 0}, {true, 1}, {false, 0}}

De-duplicate array elements. Similar to unique_by but uses the == operator. For each element e, check the previous elements for duplicates. If there are any duplicates, mark element e as invalid. Returns an array of optionals where all valid elements are unique.

>>> unique({0, 1, 0});
{{true, 0}, {true, 1}, {false, 0}}

Element-wise equality comparison of arrays using specified function.

>>> equal_by(optional::equal<uint8>, {{true, 0xFF}}, {{false, 0xFF}});
false

>>> equal_by(pair::equal<uint8, bool>, {{0xAB, true}, {0xCD, false}}, {{0xAB, true}, {0xCD, false}});
true

Element-wise comparison of arrays for equality using ==.

>>> equal({0x22, 0x1E, 0xFA}, {0x22, 0x1E, 0xFA});
true

>>> equal({true, false}, {false, false});
false

Transform an array into a pair of arrays using a projection.

>>> unzip_with<bool, uint8>(optional_to_pair<uint8>, {{true, 0x33}, {false, 0xFF}});
{{true, false}, {0x33, 0xFF}}

Transform an array of pairs into a pair of arrays.

>>> unzip<uint8, bool>({{0xAF, false}, {0xCE, true}, {0x12, false}});
{{0xAF, 0xCE, 0x12}, {false, true, false}}

Construct an array with all elements equal to the same value

>>> repeat<4>(false);
{false, false, false, false}

>>> uint8[5] a = repeat(0);
{0, 0, 0, 0, 0}

Construct array of one element with specified value

>>> singleton(false);
{false}

Return an array of repeated applications of f to x.

prop> iterate(f, x) == {x, f(x), f(f(x), ...}

>>> iterate<4>([](bool x){ return !x; }, true)
{true, false, true, false}

>>> bool[5] a = iterate([](bool x){ return !x; }, true);
{true, false, true, false, true}

Access element i. Equivalent to x[i]. If i is greater than or equal to N then a assert is triggered.

>>> at({0, 1, 2, 3}, 2)
2

Return the first element in the array. Equivalent to x[0].

>>> front({0, 1, 2})
0

Return the last element in the vector. Equivalent to x[N - 1].

>>> back({0, 1, 2})
2