The array_sequence Data Structure

Usage: #include "sequence.h"

An array_sequence<T> is a concrete implementation of the sequence ADT/concept that maintains a dynamically-sized array. If you are familiar with std::vector in the C++ standard library, array_sequence is essentially a parallel version of it. It implements most of the same operations but with span-efficient algorithms instead of purely sequential ones.

Its elements are accessed with the square bracket operator, just like an array in C or C++'s std::array or std::vector, so S[i] is the i-th element of S.

array_sequence is a class template, which means it is parameterized by an argument that indicates the type of the elements in the sequence. In C++, different instantiations of the same class template are considered to be different types, so array_sequence<int>, array_sequence<double>, and array_sequence<array_sequence<int>> are three different types.

Constructors

There are four main constructors for array_sequence. Writing just the name and type with no arguments gives an empty sequence. Empty braces mean the same thing, but empty round brackets do not!

par::array_sequence<int> A;            // A is [] (empty list, but still with type int)
par::array_sequence<int> A{};          // same
par::array_sequence<int> A();          // NOT a sequence: this declares a function called A!

Giving a length $n$ gives you that many elements, each set to the default value for the type, which is zero for numbers. This costs $O(n)$ work and $O(1)$ span.

par::array_sequence<int> B(3);         // B is [0, 0, 0]

Giving a length and a value fills the sequence with that many copies of the value, again $O(n)$ work and $O(1)$ span.

par::array_sequence<int> C(3, 7);      // C is [7, 7, 7]

Listing the elements in braces gives a sequence containing exactly those elements (this is called an initializer list). This is usually the clearest way to write a short sequence out by hand. It is optional to put an = between the name and the list^*.

par::array_sequence<int> D{1, 2, 3};      // D is [1, 2, 3]
par::array_sequence<int> D = {1, 2, 3};   // same

Whenever the values have a concrete type that the compiler can see, you can leave out the template argument (<int>) and let the compiler deduce it for you.

par::array_sequence E{1, 2, 3};        // E is an array_sequence<int> = [1, 2, 3]
par::array_sequence F{1.5, 2.5};       // F is an array_sequence<double> = [1.5, 2.5]
par::array_sequence G(3, 7);           // G is an array_sequence<int> = [7, 7, 7]

Watch the brackets. Round brackets and braces do not mean the same thing here, and this catches people out. If what you write between braces could be a list of elements, that is what you get.

par::array_sequence<int> A(3);         // [0, 0, 0]      three elements
par::array_sequence<int> B{3};         // [3]            one element
par::array_sequence<int> C(10, 2);     // [2, 2, ... ]   ten elements
par::array_sequence<int> D{10, 2};     // [10, 2]        two elements

Round brackets call the corresponding constructor; braces provide an initializer list of elements. Empty round brackets are worse still: par::array_sequence<int> A(); declares a function called A that returns a sequence, rather than making one. Use A or A{}.

Building an array sequence

`tabulate`	Work	Span
`auto tabulate( size_t n, // the length of the sequence auto&& f // the element function )`	$\displaystyle\sum_{i=0}^{n-1} \mathcal{W}(f(i))$	$\displaystyle\max_{i=0}^{n-1} \mathcal{S}(f(i))$

tabulate takes a length n and a function f, and creates an array_sequence of length n such that the i-th element is f(i). The work and span bounds assume that invoking f takes constant time.

Often we will use a lambda as the function f. For example, to create a sequence S of length 1000 such that S[i] == i, i.e., the sequence [0,1,2,...,999], we could write

auto S = par::tabulate(1000, [](int i) { return i; });

The type of S will be array_sequence<int>. Note that we did not have to specify the value type T explicitly, it was deduced from the return type of the lambda (int). If we want a different type, we can explicitly specify a return type for the lambda:

auto S = par::tabulate(1000, [](int i) -> double { return i; });

`to_sequence`	Work	Span
`auto to_sequence( sequence auto&& S // the sequence to convert )`	$O(\|S\|)$	$O(1)$

to_sequence converts a value of any sequence type into an array_sequence. The cost bounds assume that each element of the sequence being converted can be materialized in constant time.

For example, we can convert a std::vector into an array_sequence by writing

std::vector v{1,2,3};
auto a = par::to_sequence(v);

Reading an array sequence

`size`	Work	Span
`size_t size() const`	$O(1)$	$O(1)$

size returns the number of elements in the sequence.

`operator[]`	Work	Span
`T& operator[]( size_t i // the index of the element )`	$O(1)$	$O(1)$

S[i] is the i-th element of S, counting from zero. It can be read from and, unless S is const, assigned to.

par::array_sequence<int> S{1,2,3};
int x = S[0];              // x == 1
S[2] = 10;                 // S == [1,2,10]

const par::array_sequence<int> S2{1,2,3};
int y = S2[0];              // y == 1, reading is fine
S2[2] = 10;                 // does not compile, S2 is const

Comparing array sequences

Two sequences with the same element type can be compared directly. == is true when they are the same length and their elements are equal. The ordering operators compare them the way a dictionary orders words: element by element from the front, so a sequence that is a prefix of another comes first, and the empty sequence comes before everything. In the worst case a comparison costs $O(|S|)$ work and $O(\log |S|)$ span, but it stops as soon as it finds a difference.

par::array_sequence<int> A{1, 2, 3}, B{1, 2, 3}, C{1, 2, 4}, P{1, 2};

bool same    = (A == B);   // true
bool differ  = (A != C);   // true
bool smaller = (A < C);    // true, they first differ at the last element, and 3 < 4
bool prefix  = (P < A);    // true, P is a prefix of A

Copying slices

`take`	Work	Span
`auto take( size_t n // how many elements to keep ) const`	$O(n)$	$O(1)$

S.take(n) returns a new array_sequence holding the first n elements of S. It is an error for n to exceed the length of S.

`drop`	Work	Span
`auto drop( size_t n // how many elements to discard ) const`	$O(\|S\| - n)$	$O(1)$

S.drop(n) returns a new array_sequence holding everything after the first n elements of S. It is an error for n to exceed the length of S.

par::array_sequence<int> S{1,2,3,4};
auto a = S.take(2);      // a == [1,2]
auto b = S.drop(2);      // b == [3,4]

Both copy; they do not view the original. Changing S afterwards leaves a and b untouched. This means they are expensive; they cost linear work. This is unlike subseq, which returns a view into the original sequence in constant work. In most situations you should prefer subseq.

Mutating member functions

Since array_sequence mirrors std::vector, it also has operations that change a sequence in place. push_back, emplace_back, pop_back, clear, resize, reserve, assign and swap behave as their std::vector counterparts do. insert and erase differ: they take an index rather than an iterator, so S.insert(0, 9) puts 9 at the front and S.erase(0) removes the first element.

They are also sequential, so growing a sequence an element at a time gives it span proportional to its length, which throws away the parallelism the rest of this library exists to provide. So, generally, you should not need any of them. Prefer to build sequences with parallel operations such as tabulate, map and filter.

None of these are thread safe. Two threads modifying the same sequence, or one modifying it while another reads it, is a data race. The result is undefined: the program may give wrong answers, crash, or appear to work right up until it does not. Nothing in the library protects you from this, and no amount of testing will reliably reveal it.