/ Javascript

Arbitrary Dimensional Array

Have you ever wondered an object greater then 3 Dimensional. Ofcourse, we all know about 2D and 3D Objects but what about 4D or 5D or 6D or 10D. Wikipedia says 4D is Space and Time and anything beyond is imaginary, but you simply cannot imagine 4D and above object.

== 4 D Object Visualization ==

So lets just build something which is hard to imagine. In computer memory, Everything can be saved in the memory as a flat structure. So if we can visualize pointers, we can visualize Arbitrary Dimensional Array as a flat structure in memory connected with pointers. Lets look at the example in Javascript to understand the concept -

var a = [[[[]]]]; // Initialize a 4D Array
a[0][0][0][0] = 0; // Putting value in one index
a[0][0][0][1] = 1;
for(var x of a) {
    for(var y of x) {
        for(var z of y) {
            for(var q of z) {
                console.log(q);
            }
        }
    }
}

// Output //
0
1

As seen in the above example, we had to do 4 loops just to access each element. Also, if you wish to put elements automatically, you need to define those many loops. This is pretty tedious and requires concept like iterator to be able to access each element in some order.

Most of the Javascript engines are written in C++, so lets just try to build a header file which can initialize Arbitrary Dimensional Array, efficiently save it in memory and also define iterator which can move either in Row-Major order and Column-Major order.

== Variadic Templates - ==
Variadic template is a template, which can take an arbitrary number of template arguments of any type. Both the classes & functions can be variadic. Here's a variadic class template: (Definition from cplusplus.com)

template<typename... Arguments>
class VariadicTemplate;

So, basically what we will try to do is instantiate a variadic templated class and we will also write a base case for the same class. As I already said Artbitrary Dimensional Array in the memory can be analyzed as an array of an array and so on.
lets just create the prototype -

template <typename T, size_t D, size_t... Dims>
class Array {
public :
    Array<T,Dims...>* arr;
    size_t Dims_Size, initial;
    static T ValueType;
    class FirstDimensionMajorIterator;
    class LastDimensionMajorIterator;

// Base Case

template <typename T, size_t D>
class Array<T,D> {
public:
    static T ValueType;
    T *arr;
    size_t initial;
    class FirstDimensionMajorIterator;
    class LastDimensionMajorIterator;

I think writing this code is probably the toughest part since its hard to visualize why do we need a class with same name but different template arguments.
From here on, all we need to do is define the following -

  • Constructor
  • Parameterized Constructor
  • Move Constructor
  • Assignment Operator
  • [] Operator to access a particular element
  • Increment and Decrement Operator for Iterators.

Once the above concepts are written, the following test case should work fine.

void initialtest(){
ndarray::Array<int, 3, 3, 3> a, b;
int counter = 0;
for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
        for(int k=0; k<3; k++){
            a[i][j][k] = counter;
            b[k][j][i] = counter;
            counter++;
        }
    }
}
std::cout<<"Total Elements Added - " << counter <<std::endl;
counter=0;
for(auto it = a.fmbegin(); it != a.fmend(); ++it){
    assert(*it == counter);
    counter++;
}
std::cout<<"Total Elements Iterated in First Dimension Order - " << counter <<std::endl;
counter=0;
for(auto it = b.lmbegin(); it != b.lmend(); ++it){
    assert(*it == counter);
    counter++;
}

std::cout<<"Total Elements Iterated in Last Dimension Order - " << counter<<std::endl;

}

Click here to check out the complete source code. Make sure to compile with C++11.

Feel free to post any comments by Emailing me here - prashantban[at]gmail[dot]com