#
The Boost Multidimensional Array Library
(Boost.MultiArray)

## Synopsis

The Boost Multidimensional Array Library provides a multidimensional container of elements and semantically equivalent adaptors for arrays of contiguous data. The classes in this library behave as closely as possible to STL Containers, providing a more convenient and efficient implementation than the equivalent "vectors of vectors" formulation of N-dimensional arrays. Arrays are not re-sizable once constructed, but may be sliced and shaped, providing alternate views of the contained data.

## Table of Contents

1. Rationale
2. Related Work
3. Short Example
4. MultiArray Components
5. Construction and Assignment
6. Array View and Subarray Type Generators
7. Specifying Array Dimensions
8. Accessing Elements
9. Creating Views
10. Storage Ordering
11. Setting the Array Base
12. Changing an Array's Shape
13. MultiArray Concept
14. Test Cases

## Rationale

The C++ standard library provides several generic containers, but it does not provide any multidimensional array types. Using `std::vector`, you can simulate N-dimensional arrays as "nested vectors", but the interface is unwieldy and the memory overhead can be quite high. You can also use a native C++ arrays (i.e. `int arr[2][2][2];`), or a dynamically allocated array of contigous data which you treat as a multidimensional array. Using array_traits, you can extract from a statically defined C++ array iterators over its dimensions. In either case, however, dimensional data may be lost if it is passed to a function that is not properly specialized to accept it. Beyond the above, neither the `std::vector` nor C++ array-based solution provides a convenient method of honing in upon a specific subset or "view" of a multi-dimensional array.

Boost.MultiArray defines the MultiArray concept, a generic interface for N-dimensional containers. The primary components of this library model MultiArray and support adapting user data to model MultiArray as well.

## Related Work

boost::array and std::vector are one-dimensional containers of user data. Both manage their own memory. `std::valarray` is a low-level C++ Standard Library component meant to provide portable high performance for numerical applications. Blitz++ is an array library developed by Todd Veldhuizen. It uses advanced C++ techniques to provide near-Fortran performance for array-based numerical applications. array_traits is a beta library distributed with Boost that provides a means to create iterators over native C++ arrays. This library is analogous to boost::array in that it augments C style N-dimensional arrays, as `boost::array` does for C one-dimensional arrays.

## Short Example

What follows is a brief example of the use of `multi_array`:

>     #include "boost/multi_array.hpp"
>     #include <cassert>

>     int
>     main () {
>       // Create a 3D array that is 3 x 4 x 2
>       typedef boost::multi_array<double, 3> array_type;
>       typedef array_type::index index;
>       array_type A(boost::extents[3][4][2]);

>       // Assign values to the elements
>       int values = 0;
>       for(index i = 0; i != 3; ++i)
>         for(index j = 0; j != 4; ++j)
>           for(index k = 0; k != 2; ++k)
>             A[i][j][k] = values++;

>       // Verify values
>       int verify = 0;
>       for(index i = 0; i != 3; ++i)
>         for(index j = 0; j != 4; ++j)
>           for(index k = 0; k != 2; ++k)
>             assert(A[i][j][k] == verify++);

>       return 0;
>     }

## MultiArray Components

Boost.MultiArray provides three user-level class templates:

1. `multi_array` - defined in "boost/multi_array.hpp",
2. `multi_array_ref` - defined in "boost/multi_array_ref.hpp", and
3. `const_multi_array_ref` - defined in "boost/multi_array_ref.hpp"

`multi_array` is a container template. When instantiated, it allocates space for the number of elements corresponding to the dimensions specified at construction time.

`multi_array_ref` adapts an existing array of data to provide the `multi_array` interface. `multi_array_ref` does not own the data passed to it.

`const_multi_array_ref` is similar to `multi_array_ref` but guarantees that the contents of the array are immutable. It can thus wrap pointers of type T const*.

The three components exhibit very similar behavior. Aside from constructor parameters, `multi_array` and `multi_array_ref` export the same interface. `const_multi_array_ref` provides only the const portions of the `multi_array_ref` interface.

## Construction and Assignment

Each of the array types - `multi_array`, `multi_array_ref`, and `const_multi_array_ref` - provides a specialized set of constructors. For further information, consult their reference pages.

All of the non-const array types in this library provide assignment operators`operator=()`. Each of the array types `multi_array`, `multi_array_ref`, `subarray`, and `array_view` can be assigned from any of the others, so long as their shapes match. The const variants, `const_multi_array_ref`, `const_subarray`, and `const_array_view`, can be the source of a copy to an array with matching shape. Assignment results in a deep (element by element) copy of the data contained within an array.

## Array View and Subarray Type Generators

In some situations, the use of nested generators for array_view and subarray types is inconvenient. For example, inside a function template parameterized upon array type, the extra "template" keywords can be obfuscating. More likely though, some compilers cannot handle templates nested within template parameters. For this reason the type generators, `subarray_gen`, `const_subarray_gen`, `array_view_gen`, and `const_array_view_gen` are provided. Thus, the two typedefs in the following example result in the same type:

>     template <typename Array>
>     void my_function() {
>       typedef typename Array::template array_view<3>::type view1_t;
>       typedef typename boost::array_view_gen<Array,3>::type view2_t;
>       // ...
>     }

## Specifying Array Dimensions

When creating one of the Boost.MultiArray components, it is necessary to specify both the number of dimensions and the extent of each. Though the number of dimensions is always specified as a template parameter, two separate mechanisms have been provided to specify the extent of each.

The first method involves passing a Collection of extents to a constructor, most commonly a `boost::array`. The constructor will retrieve the beginning iterator from the container and retrieve N elements, corresponding to extents for the N dimensions. This is useful for writing dimension-independent code.

### Example

>       typedef boost::multi_array<double, 3> array_type;
>       boost::array<array_type::index, 3> shape = {{ 3, 4, 2 }};
>       array_type A(shape);

The second method involves passing the constructor an `extent_gen` object, specifying the matrix dimensions. By default, the library constructs a global `extent_gen` object `boost::extents`. In case of concern about memory used by these objects, defining `BOOST_MULTI_ARRAY_NO_GENERATORS` before including the library header inhibits its construction.

### Example

>       typedef boost::multi_array<double, 3> array_type;
>       array_type A(boost::extents[3][4][2]);

## Accessing Elements

The Boost.MultiArray components provide two ways of accessing specific elements within a container. The first uses the traditional C array notation, provided by `operator[]`.

### Example

>       typedef boost::multi_array<double, 3> array_type;
>       array_type A(boost::extents[3][4][2]);
>       A[0][0][0] = 3.14;
>       assert(A[0][0][0] == 3.14);

The second method involves passing a Collection of indices to `operator()`. N indices will be retrieved from the Collection for the N dimensions of the container.

### Example

>       typedef boost::multi_array<double, 3> array_type;
>       array_type A(boost::extents[3][4][2]);
>       boost::array<array_type::index,3> idx = {{0,0,0}};
>       A(idx) = 3.14;
>       assert(A(idx) == 3.14);

This can be useful for writing dimension-independent code, and under some compilers may yield higher performance than `operator[].`

## Creating Views

Boost.MultiArray provides the facilities for creating a sub-view of an already existing array component. It allows you to create a sub-view that retains the same number of dimensions as the original array or one that has less dimensions than the original as well.

Sub-view creation occurs by placing a call to operator[], passing it an `index_gen` type. The `index_gen` is populated by passing `index_range` objects to its `operator[]`. Similar to `boost::extents`, the library by default constructs the object `boost::indices`. You can suppress this object by defining `BOOST_MULTI_ARRAY_NO_GENERATORS` before including the library header. A simple sub-view creation example follows.

### Example

>       // myarray = 2 x 3 x 4

>       //
>       // array_view dims: [base,bound) (dimension striding default = 1)
>       // dim 0: [0,2)
>       // dim 1: [1,3)
>       // dim 2: [0,4) (strided by 2),
>       //

>       typedef array_type::index_range range;
>       array_type::array_view<3>::type myview =
>         myarray[ boost::indices[range(0,2)][range(1,3)][range(0,4,2)] ];

>       for (array_type::index i = 0; i != 2; ++i)
>         for (array_type::index j = 0; j != 2; ++j)
>           for (array_type::index k = 0; k != 2; ++k)
>     	assert(myview[i][j][k] == myarray[i][j+1][k*2]);

By passing an integral value to the index_gen, one may create a subview with fewer dimensions than the original array component (also called slicing).

### Example

>       // myarray = 2 x 3 x 4

>       //
>       // array_view dims:
>       // [base,stride,bound)
>       // [0,1,2), 1, [0,2,4)
>       //

>       typedef array_type::index_range range;
>       array_type::index_gen indices;
>       array_type::array_view<2>::type myview =
>         myarray[ indices[range(0,2)][1][range(0,4,2)] ];

>       for (array_type::index i = 0; i != 2; ++i)
>         for (array_type::index j = 0; j != 2; ++j)
>     	assert(myview[i][j] == myarray[i][1][j*2]);

### More on `index_range`

The `index_range` type provides several methods of specifying ranges for subview generation. Here are a few range instantiations that specify the same range.

### Example

>       // [base,stride,bound)
>       // [0,2,4)

>       typedef array_type::index_range range;
>       range a_range;
>       a_range = range(0,4,2);
>       a_range = range().start(0).finish(4).stride(2);
>       a_range = range().start(0).stride(2).finish(4);
>       a_range = 0 <= range().stride(2) < 4;
>       a_range = 0 <= range().stride(2) <= 3;

An `index_range` object passed to a slicing operation will inherit its start and/or finish value from the array being sliced if you do not supply one. This conveniently prevents you from having to know the bounds of the array dimension in certain cases. For example, the default-constructed range will take the full extent of the dimension it is used to specify.

### Example

>       typedef array_type::index_range range;
>       range a_range;

>       // All elements in this dimension
>       a_range = range();

>       // indices i where 3 <= i
>       a_range = range().start(3)
>       a_range = 3 <= range();
>       a_range = 2 < range();

>       // indices i where i < 7
>       a_range = range().finish(7)
>       a_range = range() < 7;
>       a_range = range() <= 6;

The following example slicing operations exhibit some of the alternatives shown above

>         // take all of dimension 1
>         // take i < 5 for dimension 2
>         // take 4 <= j <= 7 for dimension 3 with stride 2
>         myarray[ boost::indices[range()][range() < 5 ][4 <= range().stride(2) <= 7] ];

## Storage Ordering

Each array class provides constructors that accept a storage ordering parameter. This is most useful when interfacing with legacy codes that require an ordering different from standard C, such as FORTRAN. The possibilities are `c_storage_order`, `fortran_storage_order`, and `general_storage_order`.

`c_storage_order`, which is the default, will store elements in memory in the same order as a C array would, that is, the dimensions are stored from last to first.

`fortran_storage_order` will store elements in memory in the same order as FORTRAN would: from the first dimension to the last. Note that with use of this parameter, the array indices will remain zero-based.

### Example

>       typedef boost::multi_array<double,3> array_type;
>       array_type A(boost::extents[3][4][2],boost::fortran_storage_order);
>       call_fortran_function(A.data());

`general_storage_order` allows one to customize both the order in which dimensions are stored in memory and whether dimensions are stored in ascending or descending order.

### Example

>       typedef boost::general_storage_order<3> storage;
>       typedef boost::multi_array<int,3> array_type;

>       // Store last dimension, then first, then middle
>       array_type::size_type ordering[] = {2,0,1};

>       // Store the first dimension(dimension 0) in descending order
>       bool ascending[] = {false,true,true};

>       array_type A(extents[3][4][2],storage(ordering,ascending));

## Setting The Array Base

In some situations, it may be inconvenient or awkward to use an array that is zero-based. the Boost.MultiArray components provide two facilities for changing the bases of an array. One may specify a pair of range values to the extent_gen constructor in order to set the base value.

### Example

>       typedef boost::multi_array<double, 3> array_type;
>       typedef array_type::extent_range range;

>       array_type::extent_gen extents;

>       // dimension 0: 0-based
>       // dimension 1: 1-based
>       // dimension 2: -1 - based
>       array_type A(extents[2][range(1,4)][range(-1,3)]);

An alternative is to first construct the array normally then reset the bases. To set all bases to the same value, use the `reindex` member function, passing it a single new index value.

### Example

>       typedef boost::multi_array<double, 3> array_type;
>       typedef array_type::extent_range range;

>       array_type::extent_gen extents;

>       array_type A(extents[2][3][4]);
>       // change to 1-based
>       A.reindex(1)

An alternative is to set each base separately using the `reindex` member function, passing it a Collection of index bases.

### Example

>       typedef boost::multi_array<double, 3> array_type;
>       typedef array_type::extent_range range;

>       array_type::extent_gen extents;

>       // dimension 0: 0-based
>       // dimension 1: 1-based
>       // dimension 2: (-1)-based
>       array_type A(extents[2][3][4]);
>       boost::array<array_type::index,ndims> bases = {{0, 1, -1}};
>       A.reindex(bases);

## Changing an Array's Shape

The Boost.MultiArray arrays provide a reshape operation. While the number of dimensions must remain the same, the shape of the array may change so long as the total number of elements contained remains the same.

### Example

>       typedef boost::multi_array<double, 3> array_type;
>       typedef array_type::extent_range range;

>       array_type::extent_gen extents;
>       array_type A(extents[2][3][4]);
>       boost::array<array_type::index,ndims> dims = {{4, 3, 2}};
>       A.reshape(dims);

Note that reshaping an array does not affect the indexing.

## MultiArray Concept

Boost.MultiArray defines and uses the MultiArray concept. It specifies an interface for N-dimensional containers.

## Test Cases

Boost.MultiArray comes with a suite of test cases meant to exercise the features and semantics of the library. A description of the test cases can be found here.

## Credits

- Ronald Garcia is the primary author of the library.
- Jeremy Siek helped with the library and provided a sounding board for ideas, advice, and assistance porting to Microsoft Visual C++.
- Giovanni Bavestrelli provided an early implementation of an N-dimensional array which inspired feedback from the Boost mailing list members. Some design decisions in this work were based upon this implementation and the comments it elicited.
- Todd Veldhuizen wrote Blitz++, which inspired some aspects of this design. In addition, he supplied feedback on the design and implementation of the library.
- Jeremiah Willcock provided feedback on the implementation and design of the library and some suggestions for features.
- Beman Dawes helped immensely with porting the library to Microsoft Windows compilers.

Last modified: Tue Sep 10 11:14:15 EST 2002