6.13 Arrays

Appending [] to a built-in or user-defined type yields an array. The array element i of an array A can be accessed as A[i]. By default, attempts to access or assign to an array element using a negative index generates an error. Reading an array element with an index beyond the length of the array also generates an error; however, assignment to an element beyond the length of the array causes the array to be resized to accommodate the new element. One can also index an array A with an integer array B: the array A[B] is formed by indexing array A with successive elements of array B. A convenient Java-style shorthand exists for iterating over all elements of an array; see array iteration.

The declaration

real[] A;

initializes A to be an empty (zero-length) array. Empty arrays should be distinguished from null arrays. If we say

real[] A=null;

then A cannot be dereferenced at all (null arrays have no length and cannot be read from or assigned to).

Arrays can be explicitly initialized like this:

real[] A={0,1,2};

Array assignment in Asymptote does a shallow copy: only the pointer is copied (if one copy if modified, the other will be too). The copy function listed below provides a deep copy of an array.

Every array A of type T[] has the virtual members

The member A.length evaluates to the length of the array. Setting A.cyclic=true signifies that array indices should be reduced modulo the current array length. Reading from or writing to a nonempty cyclic array never leads to out-of-bounds errors or array resizing.

The member A.keys evaluates to an array of integers containing the indices of initialized entries in the array in ascending order. Hence, for an array of length n with all entries initialized, A.keys evaluates to {0,1,...,n-1}. A new keys array is produced each time A.keys is evaluated.

The functions A.push and A.append append their arguments onto the end of the array, while A.insert(int i ... T[] x) inserts x into the array at index i. For convenience A.push returns the pushed item. The function A.pop() pops and returns the last element, while A.delete(int i, int j=i) deletes elements with indices in the range [i,j], shifting the position of all higher-indexed elements down. If no arguments are given, A.delete() provides a convenient way of deleting all elements of A. The routine A.initialized(int n) can be used to examine whether the element at index n is initialized. Like all Asymptote functions, push, append, pop, insert, delete, and initialized can be "pulled off" of the array and used on their own. For example,

int[] A={1};
A.push(2);         // A now contains {1,2}.
A.append(A);       // A now contains {1,2,1,2}.
int f(int)=A.push;
f(3);              // A now contains {1,2,1,2,3}.
int g()=A.pop;
write(g());        // Outputs 3.
A.delete(0);       // A now contains {2,1,2}.
A.delete(0,1);       // A now contains {2}.
A.insert(1,3);     // A now contains {2,3}.
A.insert(1 ... A); // A now contains {2,2,3,3}
A.insert(2,4,5);   // A now contains {2,2,4,5,3,3}.

The [] suffix can also appear after the variable name; this is sometimes convenient for declaring a list of variables and arrays of the same type:

real a,A[];

This declares a to be real and implicitly declares A to be of type real[].

In the following list of built-in array functions, T represents a generic type. Note that the internal functions alias, array, copy, concat, sequence, map, and transpose, which depend on type T[], are defined only after the first declaration of a variable of type T[].

new T[]

returns a new empty array of type T[];

new T[] {list}

returns a new array of type T[] initialized with list (a comma delimited list of elements);

new T[n]

returns a new array of n elements of type T[]. These n array elements are not initialized unless they are arrays themselves (in which case they are each initialized to empty arrays);

T[] array(int n, T value, int depth=intMax)

returns an array consisting of n copies of value. If value is itself an array, a deep copy of value is made for each entry. If depth is specified, this deep copying only recurses to the specified number of levels;

int[] sequence(int n)

if n >= 1 returns the array {0,1,...,n-1} (otherwise returns a null array);

int[] sequence(int n, int m)

if m >= n returns an array {n,n+1,...,m} (otherwise returns a null array);

int[] sequence(int n, int m, int skip)

if m >= n returns an array {n,n+1,...,m} skipping by skip (otherwise returns a null array);

T[] sequence(T f(int), int n)

if n >= 1 returns the sequence {f_i :i=0,1,...n-1} given a function T f(int) and integer int n (otherwise returns a null array);

T[] map(T f(T), T[] a)

returns the array obtained by applying the function f to each element of the array a. This is equivalent to sequence(new T(int i) {return f(a[i]);},a.length);

T2[] map(T2 f(T1), T1[] a)

constructed by running from mapArray(Src=T1, Dst=T2) access map;, returns the array obtained by applying the function f to each element of the array a;

int[] reverse(int n)

if n >= 1 returns the array {n-1,n-2,...,0} (otherwise returns a null array);

int[] complement(int[] a, int n)

returns the complement of the integer array a in {0,1,2,...,n-1}, so that b[complement(a,b.length)] yields the complement of b[a];

real[] uniform(real a, real b, int n)

if n >= 1 returns a uniform partition of [a,b] into n subintervals (otherwise returns a null array);

int find(bool[] a, int n=1)

returns the index of the nth true value in the boolean array a or -1 if not found. If n is negative, search backwards from the end of the array for the -nth value;

int[] findall(bool[] a)

returns the indices of all true values in the boolean array a;

int search(T[] a, T key)

For built-in ordered types T, searches a sorted array a of n elements for k, returning the index i if a[i] <= key < a[i+1], -1 if key is less than all elements of a, or n-1 if key is greater than or equal to the last element of a;

int search(T[] a, T key, bool less(T i, T j))

searches an array a sorted in ascending order such that element i precedes element j if less(i,j) is true;

T[] copy(T[] a)

returns a deep copy of the array a;

T[] concat(... T[][] a)

returns a new array formed by concatenating the given one-dimensional arrays given as arguments;

bool alias(T[] a, T[] b)

returns true if the arrays a and b are identical;

T[] sort(T[] a)

For built-in ordered types T, returns a copy of a sorted in ascending order;

T[][] sort(T[][] a)

For built-in ordered types T, returns a copy of a with the rows sorted by the first column, breaking ties with successively higher columns. For example:

string[][] a={{"bob","9"},{"alice","5"},{"pete","7"},
              {"alice","4"}};
// Row sort (by column 0, using column 1 to break ties):
write(sort(a));

produces

alice   4
alice   5
bob     9
pete    7
T[] sort(T[] a, bool less(T i, T j), bool stable=true)

returns a copy of a sorted in ascending order such that element i precedes element j if less(i,j) is true, subject to (if stable is true) the stability constraint that the original order of elements i and j is preserved if less(i,j) and less(j,i) are both false;

T[][] transpose(T[][] a)

returns the transpose of a;

T[][][] transpose(T[][][] a, int[] perm)

returns the 3D transpose of a obtained by applying the permutation perm of new int[]{0,1,2} to the indices of each entry;

T sum(T[] a)

for arithmetic types T, returns the sum of a. In the case where T is bool, the number of true elements in a is returned;

T min(T[] a)
T min(T[][] a)
T min(T[][][] a)

for built-in ordered types T, returns the minimum element of a;

T max(T[] a)
T max(T[][] a)
T max(T[][][] a)

for built-in ordered types T, returns the maximum element of a;

T[] min(T[] a, T[] b)

for built-in ordered types T, and arrays a and b of the same length, returns an array composed of the minimum of the corresponding elements of a and b;

T[] max(T[] a, T[] b)

for built-in ordered types T, and arrays a and b of the same length, returns an array composed of the maximum of the corresponding elements of a and b;

pair[] pairs(real[] x, real[] y);

for arrays x and y of the same length, returns the pair array sequence(new pair(int i) {return (x[i],y[i]);},x.length);

pair[] fft(pair[] a, int sign=1)

returns the unnormalized Fast Fourier Transform of a (if the optional FFTW package is installed), using the given sign. Here is a simple example:

int n=4;
pair[] f=sequence(n);
write(f);
pair[] g=fft(f,-1);
write();
write(g);
f=fft(g,1);
write();
write(f/n);
pair[][] fft(pair[][] a, int sign=1)

returns the unnormalized two-dimensional Fourier transform of a using the given sign;

pair[][][] fft(pair[][][] a, int sign=1)

returns the unnormalized three-dimensional Fourier transform of a using the given sign;

realschur schur(real[][] a)

returns a struct realschur containing a unitary matrix U and a quasitriangular matrix T such that a=U*T*transpose(U);

schur schur(pair[][] a)

returns a struct schur containing a unitary matrix U and a triangular matrix T such that a=U*T*conj(transpose(U));

real dot(real[] a, real[] b)

returns the dot product of the vectors a and b;

pair dot(pair[] a, pair[] b)

returns the complex dot product sum(a*conj(b)) of the vectors a and b;

real[] tridiagonal(real[] a, real[] b, real[] c, real[] f);

Solve the periodic tridiagonal problem Lx=f and return the solution x, where f is an n vector and L is the n \times n matrix

[ b[0] c[0]           a[0]   ]
[ a[1] b[1] c[1]             ]
[      a[2] b[2] c[2]        ]
[                ...         ]
[ c[n-1]       a[n-1] b[n-1] ]

For Dirichlet boundary conditions (denoted here by u[-1] and u[n]), replace f[0] by f[0]-a[0]u[-1] and f[n-1]-c[n-1]u[n]; then set a[0]=c[n-1]=0;

real[] solve(real[][] a, real[] b, bool warn=true)

Solve the linear equation ax=b by LU decomposition and return the solution x, where a is an n \times n matrix and b is an array of length n. For example:

import math;
real[][] a={{1,-2,3,0},{4,-5,6,2},{-7,-8,10,5},{1,50,1,-2}};
real[] b={7,19,33,3};
real[] x=solve(a,b);
write(a); write();
write(b); write();
write(x); write();
write(a*x);

If a is a singular matrix and warn is false, return an empty array. If the matrix a is tridiagonal, the routine tridiagonal provides a more efficient algorithm (see tridiagonal);

real[][] solve(real[][] a, real[][] b, bool warn=true)

Solve the linear equation ax=b and return the solution x, where a is an n \times n matrix and b is an n \times m matrix. If a is a singular matrix and warn is false, return an empty matrix;

real[][] identity(int n);

returns the n \times n identity matrix;

real[][] diagonal(... real[] a)

returns the diagonal matrix with diagonal entries given by a;

real[][] inverse(real[][] a)

returns the inverse of a square matrix a;

real[] quadraticroots(real a, real b, real c);

This numerically robust solver returns the real roots of the quadratic equation ax^2+bx+c=0, in ascending order. Multiple roots are listed separately;

pair[] quadraticroots(explicit pair a, explicit pair b, explicit pair c);

This numerically robust solver returns the complex roots of the quadratic equation ax^2+bx+c=0;

real[] cubicroots(real a, real b, real c, real d);

This numerically robust solver returns the real roots of the cubic equation ax^3+bx^2+cx+d=0. Multiple roots are listed separately.

Asymptote includes a full set of vectorized array instructions for arithmetic (including self) and logical operations. These element-by-element instructions are implemented in C++ code for speed. Given

real[] a={1,2};
real[] b={3,2};

then a == b and a >= 2 both evaluate to the vector {false, true}. To test whether all components of a and b agree, use the boolean function all(a == b). One can also use conditionals like (a >= 2) ? a : b, which returns the array {3,2}, or write((a >= 2) ? a : null, which returns the array {2}.

All of the standard built-in libm functions of signature real(real) also take a real array as an argument, effectively like an implicit call to map.

As with other built-in types, arrays of the basic data types can be read in by assignment. In this example, the code

file fin=input("test.txt");
real[] A=fin;

reads real values into A until the end-of-file is reached (or an I/O error occurs).

The virtual members dimension, line, csv, word, and read of a file are useful for reading arrays. For example, if line mode is set with file line(bool b=true), then reading will stop once the end of the line is reached instead:

file fin=input("test.txt");
real[] A=fin.line();

Since string reads by default read up to the end of line anyway, line mode normally has no effect on string array reads. However, there is a white-space delimiter mode for reading strings, file word(bool b=true), which causes string reads to respect white-space delimiters, instead of the default end-of-line delimiter:

file fin=input("test.txt").line().word();
real[] A=fin;

Another useful mode is comma-separated-value mode, file csv(bool b=true), which causes reads to respect comma delimiters:

file fin=input("test.txt").csv();
real[] A=fin;

To restrict the number of values read, use the file dimension(int) function:

file fin=input("test.txt");
real[] A=fin.dimension(10);

This reads 10 values into A, unless end-of-file (or end-of-line in line mode) occurs first. Attempting to read beyond the end of the file will produce a runtime error message. Specifying a value of 0 for the integer limit is equivalent to the previous example of reading until end-of-file (or end-of-line in line mode) is encountered.

Two- and three-dimensional arrays of the basic data types can be read in like this:

file fin=input("test.txt");
real[][] A=fin.dimension(2,3);
real[][][] B=fin.dimension(2,3,4);

Sometimes the array dimensions are stored with the data as integer fields at the beginning of an array. Such 1, 2, or 3 dimensional arrays can be read in with the virtual member functions read(1), read(2), or read(3), respectively:

file fin=input("test.txt");
real[] A=fin.read(1);
real[][] B=fin.read(2);
real[][][] C=fin.read(3);

One, two, and three-dimensional arrays of the basic data types can be output with the functions write(file,T[]), write(file,T[][]), write(file,T[][][]), respectively.