How to create a nested array of arbitrary depth in java?

Question

I am trying to create an array of arrays of arrays etc..., except I don't know how many nested levels deep it needs to be until runtime.

Depending on the input, I might need either int[], int[][], int[][][][][][], or anything else. (For context, I am trying to construct an N-dimensional grid for a cellular automaton, where N is passed as a parameter.)

I don't have any code for you because I have no idea how to go about this; I suspect is not possible at all using just arrays. Any help, or alternative solutions, would be appreciated.

Answer 1

You could do this with an Object[], limiting its members to either Object[] or int[].

For example, here's an array that goes three levels deep in one part, and two levels deep in another:

   Object[] myarray = new Object[] {
         new Object[] { new int[] { 1, 2 }, 
                        new int[] { 3, 4 }},
         new int[] { 5, 6 } 
    };

After you've created it, you may want to access members. In your case, you know the depth N up front, so you know at what depth to expect an Object[] and at what depth to expect an int[].

However, if you didn't know the depth, you could use reflection to determine whether a member is another Object[] level or a leaf int[].

    if ( myarray[0] instanceof Object[] ) {
           System.out.println("This should print true.");
    }

EDIT:

Here's a sketch [untested so far, sorry] of a method that access a member of an array of known depth, given an array of indices. The m_root member can be an Object[] or an int[]. (You could relax this further to support scalars.)

   public class Grid {
        private int m_depth;
        private Object m_root;
        ...
        public int get( int ... indices ) {
            assert( indices.length == m_depth );
            Object level = m_root;
            for ( int i = 0; i + 1 < m_depth; ++i ) {
                level = ((Object[]) level)[ indices[i] ];
            }
            int[] row = (int[]) level;
            return row[ indices[m_depth - 1] ];
        }
   }

Answer 2

This should be achievable using Object[], since arrays are objects:

int[] arr = {1,2,3};
int[] arr2 = {1,2,3};
int[] arr3 = {1,2,3};
int[] arr4 = {1,2,3};
Object[] arr5 = {arr, arr2}; // basically an int[][]
Object[] arr6 = {arr3, arr4}; // basically an int[][]
Object[] arr7 = {arr5, arr6}; // basically an int[][][]
// etc.

Note that one array doesn't have to contain arrays of the same dimensions:

Object[] arr7 = {arr5, arr};

To prevent this (and to allow for easier access to the data), I suggest writing a class which has an Object member (which will be your int[] or Object[]) and a depth variable and some nice functions to give you access to what you want.

ArrayLists will also work:

ArrayList array = new ArrayList();
array.add(new ArrayList());
array.add(new ArrayList());
((ArrayList)array.get(0)).add(new ArrayList());
// etc.

Answer 3

As your N increases going with nested arrays becomes less and less advantageous, especially when you have a grid structure. Memory usage goes up exponentially in N with this approach and the code becomes complex.

If your grid is sparsely populated (a lot of cells with the same value) you can instead have a collection of Cell objects where each of these holds a coordinate vector and the integer value of the cell. Every cell that is not in the collection is assumed to have a default value, which is your most common value.

For faster access you can use for example a k-d tree (https://en.wikipedia.org/wiki/K-d_tree) but that depends a bit on your actual use-case.

Answer 4

@Andy Thomas explains how to do this using Object[] for the higher levels of the multidimensional array. Unfortunately, this means that the types are not correct to allow indexing, or indeed to allow element access without typecasts.

You can't do this:

    Object[] array = ...
    int i = array[1][2][3][4];

To get types that allow you to do the above, you need to create an object whose real type is (for example) int[][][][].

But the flipside is that it is not really practical to use that style of indexing for N dimensional arrays where N is a variable. You can't write Java source code to do that unless you place a bound on N (i.e. up to 5) and treat the different cases individually. That becomes unmanageable very quickly.

Answer 5

The whole construct of multi-dimensional arrays is just the compiler doing some work for you on a big block of memory (ok as some have commented in java this is multiple blocks of memory). One way to deal with the problem you face is to use nested arraylists at runtime. Another (more performant) way is to just allocate a single-dimensional array of the size you need and do the indexing yourself. You could then hide the indexing code in a method that was passed all the details like an array de-reference.

private int[] doAllocate(int[] dimensions)
{
    int totalElements = dimensions[0];

    for (int i=1; i< dimensions.length; i++)
    {
        totalElements *= dimensions[i];
    }

    int bigOne = new int[totalElements];

    return bigOne;
}

private int deReference(int[] dimensions, int[] indicies, int[] bigOne)
{
    int index = 0;

    // Not sure if this is only valid when the dimensions are all the same.
    for (int i=0; i<dimensions.length; i++)
    {
        index += Math.pow(dimensions[i],i) * indicies[dimensions.length - (i + 1)];
    }

    return bigOne[index];
}

Answer 6

You can use Java reflection as Arrays are objects.

    public static void main(String[] args) throws InstantiationException,
        IllegalAccessException, ClassNotFoundException {
    Class<?> intClass = int.class;
    Class<?> oneDimensionalArrayClass = Class.forName("[I");

    Object oneDimensionalIntArray1 = Array.newInstance(intClass, 1);
    Array.set(oneDimensionalIntArray1, 0, 1);
    Object oneDimensionalIntArray2 = Array.newInstance(intClass, 1);
    Array.set(oneDimensionalIntArray2, 0, 2);
    Object oneDimensionalIntArray3 = Array.newInstance(intClass, 1);
    Array.set(oneDimensionalIntArray3, 0, 3);

    Object twoDimensionalIntArray = Array.newInstance(oneDimensionalArrayClass, 3);
    Array.set(twoDimensionalIntArray, 0, oneDimensionalIntArray1);
    Array.set(twoDimensionalIntArray, 1, oneDimensionalIntArray2);
    Array.set(twoDimensionalIntArray, 2, oneDimensionalIntArray1);

    System.out.println(Array.get(Array.get(twoDimensionalIntArray, 1), 0));

}

The class Array with its static methods gives access on items while you can specify the dimension of your arrays with the number of leading "[".

Answer 7

Fields like you wrote above a checked and created by the compiler. If you want a dynamic data structure during runtime you could create your own data structure. Search for Composite Pattern. A small snippet should show you how it works:

interface IGrid {
  void insert(IGrid subgrid);
  void insert(int[] values);
}
class Grid implements IGrid {
  private IGrid subgrid;
  void insert(IGrid subgrid) {this.subgrid = subgrid;}
  void insert(int[] values) {/* Do nothing */}
}
class SubGrid implements IGrid {
  private int[] values;
  void insert(IGrid subgrid) {/* Do nothing */}
  void insert(int[] values) {this.values = values;}
}

You could simply create a Subgrid for int[] or a Grid with a Subgrid for int[][]. It's only a rudimental solution, you would have to create some code for working on your automaton's levels and values. I would do it this way. Hope it will help :) And look forward for more solutions^^