Array utility functions

A collection of functions operating on arrays. More...

Functions
template<class T , int N>
T	jem::min (const ArrayExpr< T, N > &e)
	Computes the minimum value of an array expression. More...
template<class T , int N>
T	jem::max (const ArrayExpr< T, N > &e)
	Computes the maximum value of an array expression. More...
template<class T , int N>
T	jem::sum (const ArrayExpr< T, N > &e)
	Computes the sum of all elements in an array expression. More...
template<class T , int N>
T	jem::product (const ArrayExpr< T, N > &e)
	Computes the product of all elements in an array expression. More...
template<class T , int N>
bool	jem::testall (const ArrayExpr< T, N > &e)
	Tests whether all elements in an array expression are true. More...
template<class T , int N>
bool	jem::testany (const ArrayExpr< T, N > &e)
	Tests whether at least one element in an array expression is true. More...
template<class T >
void	jem::shift (const ArrayExpr< T, 1 > &e, int k)
	Shifts all elements in a one-dimensional array expresion. More...
template<class T >
void	jem::cshift (const ArrayExpr< T, 1 > &e, int k)
	Shifts all elements in a one-dimensional array expression in a circular way. More...
template<class T >
void	jem::reverse (const ArrayExpr< T, 1 > &e)
	Reverses the elements in a one-dimensional array expression. More...
template<class T , int N>
Array< T, N >	jem::reshape (const Array< T, 1 > &a, const Tuple< int, N > &sh)
	Converts a one-dimensional array to a multi-dimcnsional array. More...
template<class T , int N>
bool	jem::equal (const ArrayExpr< T, N > &lhs, const ArrayExpr< T, N > &rhs)
	Tests whether two array expressions are equal. More...
ArrayExpr< int, 1 >	jem::iarray (int n)
	Returns an enumeration of integers as an array expression. More...
ArrayExpr< int, 1 >	jem::iarray (const SliceTo &s)
	Returns an enumeration of integers as an array expression. More...
ArrayExpr< int, 1 >	jem::iarray (const Slice &s)
	Returns an enumeration of integers as an array expression. More...
ArrayExpr< int, 1 >	jem::iarray (const SliceFromTo &s)
	Returns an enumeration of integers as an array expression. More...
template<class T , int N>
Array< T, N >	jem::makeContiguous (const Array< T, N > &a)
	Converts an array to a contiguous array. More...
template<class T >
void	jem::sort (const Array< T > &a)
	Sorts a one-dimensional array in ascending order. More...
template<class T >
void	jem::sort (const Array< int > &perm, const Array< T > &a)
	Sorts an array in ascending order through an index array. More...
template<class T >
int	jem::binarySearch (const T &value, const Array< T > &a)
	Searches a sorted array for an element with a specific value. More...
template<class T >
int	jem::lowerBound (const T &value, const Array< T > &a)
	Searches a sorted array for the first element with a specific value. More...
template<class T >
int	jem::upperBound (const T &value, const Array< T > &a)
	Searches a sorted array for the first element that is larger than a specific value. More...
template<class T >
SliceFromTo	jem::equalRange (const T &value, const Array< T > &a)
	Searches a sorted array for a set of elements that all have a specific value. More...

Detailed Description

#include <jem/base/array/utilities.h>

This header file exports a collection of functions that perform various operations on Array objects and array expressions. Supported operations are:

• reduce an array to a scalar;
• shift the elements in an array;
• test whether two arrays are equal;
• sort an array and find a specific element.

Note that these functions are also available through the general header file <jem/base/Array.h>.

Function Documentation

template<class T , int N>

T jem::min

(

const ArrayExpr< T, N > &

e

)

Computes the minimum value of the array expression or Array object e.

Parameters

e	- an array expression or an Array object.

Returns

The smallest element in the array. The return value is undefined if the array is empty.

Precondition

The type T supports the < operator.

Examples:

Array.cpp.

template<class T , int N>

T jem::max

(

const ArrayExpr< T, N > &

e

)

Computes the minimum value of the array expression or Array object e.

Parameters

e	- an array expression or an Array object.

Returns

The largest element in the array. The return value is undefined if the array is empty.

Precondition

The type T supports the < operator.

Examples:

Array.cpp.

template<class T , int N>

T jem::sum

(

const ArrayExpr< T, N > &

e

)

Computes the sum of all elements in the array expression or Array object e.

Parameters

e	- an array expression or an Array object.

Returns

The sum of all elements in the array. The return value is undefined if the array is empty.

Precondition

The type T supports the + operator.

Examples:

Array.cpp, and Tuple.cpp.

template<class T , int N>

T jem::product

(

const ArrayExpr< T, N > &

e

)

Computes the product of all elements in the array expression or Array object e.

Parameters

e	- an array expression or an Array object.

Returns

The product of all elements in the array. The return value is undefined if the array is empty.

Precondition

The type T supports the * operator.

Examples:

meshgen.cpp.

template<class T , int N>

bool jem::testall

(

const ArrayExpr< T, N > &

e

)

Tests whether all elements in the array expression or Array object e are true.

Parameters

e	- an array expression or an Array object.

Returns

true if all elements in the array evaluate to true, and false otherwise. The return value is undefined if the array is empty.

Precondition

The type T can be converted to a boolean.

template<class T , int N>

bool jem::testany

(

const ArrayExpr< T, N > &

e

)

Tests whether at least one element in the array expression or Array object e is true.

Parameters

e	- an array expression or an Array object.

Returns

true if at least one elements in the array evaluates to true, and false otherwise. The return value is undefined if the array is empty.

Precondition

The type T can be converted to a boolean.

template<class T >

void jem::shift	(	const ArrayExpr< T, 1 > &	e,
		int	k
	)

Shifts all elements in the one-dimensional array expression e k places to the right. Thus, element e[i] becomes element e[i + k]. If k is negative, the elements are shifted to the left. The last k elements (or the first k elements if k is negative) are discarded, while the first k (or last k) elements are unchanged.

If k is larger than or equal to the size of the array expression e, then this functin does nothing.

Parameters

e	- a one-dimensional, lvalue array expression.
k	- an integer specifying how many places the elements in a should be shifted to the right.

Precondition

The type T provides an assignment operator
and e is an lvalue expression.

template<class T >

void jem::cshift	(	const ArrayExpr< T, 1 > &	e,
		int	k
	)

Like the function shift(), this function shifts all elements in the one-dimensional array expression e k places to the right. Thus, element e[i] becomes element e[i + k]. If k is negative, the elements are shifted to the left. Unlike shift(), however, the last k elements (or the first k elements if k is negative) are `wrapped around' and become the first (or last) k elements.

If k is larger than the size of the array a, then k is replaced by (k % a.size()).

Parameters

e	- a one-dimensional, lvalue array expression.
k	- an integer specifying the number of places that the elements in a should be shifted to the right.

Precondition

the type T provides an assignment operator
and e is an lvalue expression.

template<class T >

void jem::reverse

(

const ArrayExpr< T, 1 > &

e

)

Reverses the order in which the elements are stored in the one-dimensional array expression e. That is, the first element becomes the last element; the second element becomes the second last element; and so on.

Parameters

e	- a one-dimensional, lvalue array expression.

Precondition

the type T provides an assignment operator
and e is an lvalue expression.

template<class T , int N>

Array<T,N> jem::reshape	(	const Array< T, 1 > &	a,
		const Tuple< int, N > &	sh
	)

Converts the one-dimensional array a to an N-dimensional array with shape sh. The returned array points to the same data block as the argument array a. Any modifications to the returned array are therefore visible in a, and the other way around.

Let r denote the array returned by this function. The mapping of the elements in r and the argument array a is defined as follows:

• if N equals two:
  r(i,j) == a[ i + j * sh[0] ];

• if N equals three:
  r(i,j,k) == a[ i + j * sh[0] + k * sh[0] * sh[1] ];

• if N equals four:
  r(i,j,k,p) == a [ i + j * sh[0] + k * sh[0] * sh[1] + p * sh[0] * sh[1] * sh[2] ].

A different mapping can be obtained by invoking the member function Array::transpose() on the returned array.

Parameters

a	- a one-dimensional Array.
sh	- the shape of the converted array.

Returns

An N-dimensional array pointing to the same data block as the argument array a.

Precondition

product(sh) == a.size()

Examples:

Array.cpp.

template<class T , int N>

bool jem::equal	(	const ArrayExpr< T, N > &	lhs,
		const ArrayExpr< T, N > &	rhs
	)

Tests whether the shapes and the elements of the array expressions lhs and rhs are equal.

Parameters

lhs	- an array expression or an Array object.
rhs	- another array expression or an Array object.

Returns

equal( lhs.shape(), rhs.shape() ) &&
testall( lhs == rhs )

ArrayExpr<int,1> jem::iarray

(

int

n

)

Returns a one-dimensional array expression of length n that represents the integer array

[0, 1, 2, ..., n - 1].

Parameters

n	- the length of the returned array expression.

Precondition

n >= 0

Returns

A one-dimensional array expression enumerating all non-negative integers that are smaller than n.

Examples:

Array.cpp, and meshgen.cpp.

ArrayExpr<int,1> jem::iarray

(

const SliceTo &

s

)

Returns a one-dimensional array expression that represents the integer array

[0, 1, 2, ..., s.last() - 1].

Parameters

s	- a slice specifying the length of the returned array expression.

Returns

A one-dimensional array expression enumerating all integers selected by the slice object s.

ArrayExpr<int,1> jem::iarray

(

const Slice &

s

)

Returns a one-dimensional array expression that represents the integer array

[i, i + k, i + 2 * k, ..., i + n * k]

with i = s.first() and k = s.stride(), and with n the largest integer such that

i + n * k < s.last().

Parameters

s	- a slice specifying the integers in the returned array expression.

Returns

A one-dimensional array expression enumerating all integers selected by the slice object s.

ArrayExpr<int,1> jem::iarray

(

const SliceFromTo &

s

)

Returns a one-dimensional array expression that represents the integer array

[i, i + 1, i + 2, ..., j - 1]

with i = s.first() and j = s.last().

Parameters

s	- a slice specifying the integers in the returned array expression.

Returns

A one-dimensional array expression enumerating all integers selected by the slice object s.

template<class T , int N>

Array<T,N> jem::makeContiguous

(

const Array< T, N > &

a

)

Returns an array that has the same shape as the array a; that has the same elements as a; and that is stored contiguously in memory. If the array a is already contiguous, then this function simply returns a.

Parameters

a	- an Array object.

Returns

A contiguous array containing the same elements as a.

See also

Array::isContiguous().

template<class T >

void jem::sort

(

const Array< T > &

a

)

Sorts the elements stored in the one-dimensional array a in such a way that

a[i + 1] >= a[i]

for all valid indices i.

The worst-case time compexity of this function is O(n*log(n)) with n the length of the array a.

Parameters

a	- a one-dimensional Array that is to be sorted.

Precondition

The type T supports the assignment operator; and the type T supports the < operator.

Note

The current implementation is based on heap sort.

Examples:

TextInput.cpp.

template<class T >

void jem::sort	(	const Array< int > &	perm,
		const Array< T > &	a
	)

Sorts the elements in the index array perm in such a way that

a[ perm[i + 1] ] >= a[ perm[i] ]

for all valid indices i.

The worst-case time compexity of this function is O(n*log(n)) with n the length of the array perm.

Parameters

perm	- an Array of which the elements are valid indices into the array a.
a	- an Array object.

Precondition

The type T provides a < operator.

Note

The current implementation is based on heap sort.

template<class T >

int jem::binarySearch	(	const T &	value,
		const Array< T > &	a
	)

Returns the index of the element with value value in the sorted array a. If there is no such element, a negative integer is returned. If there are multiple elements with the value value, the index of any one of those elements is returned.

The worst-case time complexity of this function is O(log(n)) with n the length of the array a.

Parameters

value	- the value of the element to be found.
a	- an Array that has been sorted in ascending order.

Returns

The index of the element with value value, or a negative integer if there is no element with that value.

Precondition

The array a has been sorted in ascending order;
and the type T provides the < operator.

See also

sort().

template<class T >

int jem::lowerBound	(	const T &	value,
		const Array< T > &	a
	)

Returns the index of the first element with value value in the sorted array a. If there is no such element, the returned index refers to the first element with a value larger than value. If value is larger than the largest element in the array, the size of the array is returned.

The worst-case time complexity of this function is O(log(n)) with n the length of the array a.

Parameters

value	- the value of the element to be found.
a	- an Array that has been sorted in ascending order.

Returns

the index of the first element with value value, or the index of the first element that is larger than value, or the size of the array.

Precondition

The array a has been sorted in ascending order;
and the type T provides the < operator.

template<class T >

int jem::upperBound	(	const T &	value,
		const Array< T > &	a
	)

Returns the index of the first element with a value that is larger than value in the sorted array a. If there is no such element, the size of the array a is returned.

The worst-case time complexity of this function is O(log(n)) with n the length of the array a.

Parameters

value	- the value of the element to be found.
a	- an Array that has been sorted in ascending order.

Returns

the index of the first element that is larger than value, or the size of the array a.

Precondition

The array a has been sorted in ascending order;
and the type T provides the < operator.

See also

sort().

template<class T >

SliceFromTo jem::equalRange	(	const T &	value,
		const Array< T > &	a
	)

Returns a SliceFromTo object representing the indices of the elements that all have the value value in the sorted array a. If s denotes the returned slice object, then

a[i] == value

for all indices i that meet the condition

i >= s.first() && i < s.last()

If there are no elements with the value value, then the returned slice object represents an empty range of indices.

The worst-case time complexity of this function is O(log(n)) with n the length of the array a.

Parameters

value	- the value of the elements to be found.
a	- an Array that has been sorted in ascending order.

Returns

A SliceFromTo representing the indices of the elements with value value.

Precondition

The array a has been sorted in ascending order;
and the type T provides the < operator.

See also

sort().