# Elemental Memory Arithmetic

Programming languages offer the possibility of working with variables and arrays of one dimension to n dimensions. Lets say that we have a language where we could only use one dimension arrays, how could we do construct n-dimensions arrays from one dimension arrays?
We could use one 1-dimension array of 1-dimension arrays of some type (lets say integer) to get a matrix (2-dimension array) (of integers). Applying the same idea for one more dimension, we could get a cube (of integers) and so on so forth. Note that by doing this we cannot ensure that all the elements will be located continuously in memory. Each array element of the outer array could be in a quite different memory address as shown in the next figures:
From the user point of view: One possible actual memory structure: This approach gives us some advantages, like sorting for instance. Think of having a matrix of characters and you want to sort by row (each row represents a line of text), instead moving the row, we could just swap the pointers, this is the values from the outer array. Also each row could be of different length (although it wouldn't be a matrix).

Sometimes is useful to have all the rows stored one after the other in memory. So is there any way to still have a matrix or a cube or n-dimension array?
Yes, there is! From a low level point of view, memory is just a big array of bytes but that does not stop us from having all sort of data structures, so there must be a way to construct them and in particular n-dimensions arrays.

Let's start with one dimension array: In this case there is nothing to do, since as we said before our language supports this structure.
Now how can we get a 2-dimensions array? If we have R rows and C columns, we can see it as R 1-dimension arrays of C elements each. Therefore the total amount of elements of the matrix is: R * C
We can allocate space for a 1-dimension array of R*C elements and start by storing the first row followed by the second and so on so forth until the last row: So, to get the element at row r and column c we can apply the formula:

```matrix[r,c] = array[r * (the size of the row) + c];
```
Note that all the rows have the same amount of elements, otherwise it wouldn't be a matrix. As we can see, each row has as many elements as columns the matrix has, therefore:
```the size of the row = the amount of columns of the row (or matrix) = C;

matrix[r,c] = array[r * C + c];
```
Lets take this idea one step further and apply it to a cube:
A cube will have 3 dimensions, lets call them X,Y,Z and likewise the matrix we have the total amount of element to be: X * Y * Z
We could then declare a 1-dimension array of X*Y*Z elements. We can see the cube as Z matrices of X rows and Y columns each: So in order to get the element at row: x, column: y and third coordinate z, we need to use the formula:
```cube[x,y,z] = array[z *X*Y + x*Y + y];
```
Note that for K = X,Y,Z and k = x,y,z
K denotes the length of dimension K and k denotes the value (from 0 to K-1) that we plug in cube[x,y,z] to get the value stored at that address.
Since a cube with Z = 1, this is, with only one matrix is the same as a matrix, then if we ask Z to be 1 we get:
```cube[x,y,z]= array[z *X*Y + x*Y + y];

But the only possible value for z would be 0, therefore:

cube[x,y,0]= array[0 *X*Y + x*Y + y] = array[x*Y+y];

if now we make a variable name change: x=r and y=c we get:

cube[x,y,0]= array[0 *X*Y + x*Y + y] = array[x*Y+y] = array[r*C+c ]= matrix[r,c];
```
So the index of our 1-dimension array where we will be storing the a n-dimension array is:

## The iterative approach:

```index[x] = x ; with n = 1;

index[x1,x2] = X2*x1 + x2; with n=2;

index[x1,x2,x3] = X1*X2*x3 + X2*x1 + x2; with n=3;

…

In a generic way:

index[x] = x ; with n = 1;

index[x1,x2,x3, …, xn] = X1*X2*X3*...*Xn-1*xn +  X1*X2*X3*...*Xn-2*xn-1 +  … + X1*X2*x3 + X2*x1 + x2; with n>1;
```
Note that the last term is: x2. Not x1. This is an important detail when generating the formula.

## The recursive approach:

It is not hard to see that:
```index[x] = x; with n = 1;

index[x1,x2]= X2*x1 + x2; with = 2;
```
This will be our base cases.
Now what? So, how can we tend to our base case?
Note that for n=3 (cube) what we do is to resolve how many matrices we have before the current one and then we can forget about the cube and work only with the current matrix as if it were the only one:
```index[r,c,z] = matrices before current one times the size of the matrix + index[r,c];

matrices before current one = z;

size of the matrix = X*Y;

index[r,c,z] = z*X*Y + index[r,c];

In a generic way:

index[x1,x2,x3,...,xn] = X1 * X2 * X3 * ... * Xn-1* xn + index[x1,x2,x3,...,xn-1]; with n>2;
```

Here is the Java code for both solutions:
```package memoryarithmetic;

/**
* This code demonstrates how from a single array we can build a matrix, a cube, etc of any dimension.
* The idea is to show how recursion can be used to achieve this. Also a non recursive
* solution is presented. Normally a compiler will use the non recursive approach.
*
* @author kriche
*
*/
public class MemoryArithmetic {

private int[] boundaries;
private E[] memory;

/**
* Construct a array with the dimensions given.
* @param boundaries
*/
public MemoryArithmetic(int... boundaries) {

this.boundaries= boundaries;

int dim= 1;
for (int boundary : boundaries)
dim*= boundary;

this.memory= (E[]) new Object[dim];

}

/*
* Including "Recursive" as part of the signature only for demo purposes.
*/
public void setValueAtRecursive(E value, int... coordinates) {
memory[getIndexRecursive(coordinates)]= value;
}

/*
* Including "Recursive" as part of the signature only for demo purposes.
*/
public E getValueAtRecursive(int... coordinates) {
return memory[getIndexRecursive(coordinates)];
}

/*
* Including "Iterative" as part of the signature only for demo purposes.
*/
public void setValueAtIterative(E value, int... coordinates) {
memory[getIndexIterative(coordinates)]= value;
}

/*
* Including "Iterative" as part of the signature only for demo purposes.
*/
public E getValueAtIterative(int... coordinates) {
return memory[getIndexIterative(coordinates)];
}

/*
* Including "Iterative" as part of the signature only for demo purposes.
*/
private int getIndexIterative(int... coordinates) {

int spaceDimensions= coordinates.length;

// a one dimension array:
if (spaceDimensions==1)
return coordinates;

// a matrix:
if (spaceDimensions==2)
return coordinates * boundaries + coordinates;

int index= boundaries * coordinates + coordinates;
int offset= boundaries * boundaries;

for (int i= 2; i < spaceDimensions; i++) {
index+= offset * coordinates[i];
offset*= boundaries[i];
}

return index;

}

/*
* Including "Recursive" as part of the signature only for demo purposes.
*/
private int getIndexRecursive(int coordinates[]) {
return getIndexRecursive(coordinates, coordinates.length);
}

/*
* Including "Recursive" as part of the signature only for demo purposes.
*/
private int getIndexRecursive(int coordinates[], int spaceDimensions) {

if (spaceDimensions==1)
//one simple array of objects
return coordinates;

// a matrix:
if (spaceDimensions==2)
return coordinates * boundaries + coordinates;

// cube or more dimesions, remove one dimension and call myself

int currentDimension= spaceDimensions - 1;

int spaceSize= 1;
for (int t =0; t < currentDimension; t++)
spaceSize*= boundaries[t];

return spaceSize * coordinates[currentDimension] + getIndexRecursive(coordinates, currentDimension);

}
}
```
Download this source code and a method that test it:
runnable and source

## One final observation:

Recall the formula:
```matrix[r,c] = array[r * C + c];
```
You might wonder what is the difference between rows and columns, this is: why this formula don't look "symmetric"? Is there anything different between rows and columns? No!! So why our formula does not treat columns and rows in the same manner? Or why don't we have:
```matrix[r,c] = array[c * R + r];
```
It just an implementation detail: we are saving the matrix row by row but we could have saved it column by column instead. This is, first the first column, then the seconds and so on so forth. And so we would have ended with the formula above. 