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 that I do not know how many levels of nested levels there should be before execution.

Depending on the input, I may need int[] , int[][] , int[][][][][][] or something else. (For context, I'm trying to build an N-dimensional grid for a cellular automaton, where N is passed as a parameter.)

I have no code for you, because I have no idea how to do this; I suspect this is not possible at all using only arrays. Any help or alternative solutions would be appreciated.

Answer 1

You can do this with Object [], restricting its members to either Object [] or int [].

For example, here is an array that runs 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 } }; 

Once you have created it, you can access the elements. In your case, you know the depth N in front, so you know at what depth the object [] is expected, and at what depth int [] is expected.

However, if you do not know the depth, you can use reflection to determine if the element is a different level of Object [] or an int [] sheet.

  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 accesses an array element of a known depth, given an array of indices. The m_root element can be Object [] or int []. (You can relax this 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 can be achieved 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 a single array must not contain arrays of the same size:

 Object[] arr7 = {arr5, arr}; 

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

ArrayList 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 grows with nested arrays, it becomes less and less profitable, especially if you have a grid structure. Memory usage at an exponential exponential exponential approximation increases, and the code becomes complex.

If your grid is sparsely populated (many cells with the same value), you can instead have a set of Cell objects, where each of them contains a coordinate vector and an integer cell value. It is assumed that each cell that is not part of the collection has a default value, which is your most common value.

For faster access, you can use, for example, the kd 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 higher levels of a multidimensional array. Unfortunately, this means that types are not valid to allow indexing or to really allow access to an element without types.

You cannot 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 flipside is that it is not very practical to use this indexing style for N dimensional arrays, where N is a variable. You cannot write Java source code to do this unless you set the binding to N (i.e., before 5) and handle different cases separately. It becomes unmanageable very quickly.

Answer 5

The whole construction of multidimensional arrays is just a compiler that does some work for you on a large block of memory (well, as some comment in java, these are several blocks of memory). One way to solve the problem you are facing is to use nested arraylists at runtime. Another (more efficient) way is to simply select a one-dimensional array of the required size and independently perform indexing. Then you can hide the index code in the method to which all the details were passed, such as de-reference the array.

 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, because 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 Array class with static methods provides access to elements, while you can specify the dimension of your arrays with the number of leading "[".

Answer 7

Fields, as you wrote above, are checked and created by the compiler. If you need a dynamic data structure at run time, you can create your own data structure. Find the Composite Pattern . A small snippet should show you how this 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 can simply create a Subgrid for int[] or a Grid with a Subgrid for int[][] . This is just a rudimentary solution, you will need to create code to work at your levels and values ​​of the machine. I would do it like this. Hope this helps :) And look forward to new solutions ^^