I write a complex program in Java where I need to manage many large sparse matrix that contain integer values. Example:
int A[][][][];
int B[][][];
int C[][];
In order to saving memory, space, etc, I decided to store this data in TreeMap. I know that exist a lot of libraries that do it better but I would try to implement my personal solution. First of all I created a class Index that identifies the indeces of this array without knowing how many they are.
public class Index implements Comparable<Index> {
private final int[] index;
public Index(int ... index) {
this.index = index;
}
@Override
public int toCompare(Index i) {
...
}
}
Obviously I've used this class to define my three Maps in this way:
Map <Index, Integer> mapA = new TreeMap <> ();
Map <Index, Integer> mapB = new TreeMap <> ();
Map <Index, Integer> mapC = new ...
Now, I need to store the data from the matrix that I previous create to those Maps. The most easy way is use 4/3/2/.. loops, but I accept with pleasure others solutions.
for(int s = 0; s < s_max; s++) {
for(int c = 0; c < c_max; c++) {
for(int o = 0; o < o_max; o++) {
for(int d = 0; d < d_max; d++) {
mapA.put(new Index(s,c,o,d), A[s][c][o][d]);
}
}
}
}
The focus of the problem is when I need to retrieve the data, but let's me explain. The more usually operations between those maps are multiplications and additions considering them as matrix or arrays. I can't make 6(..) nested loops every times that I need to perform operations likes this below (I can't insert images because my reputation is still low):
http://postimg.org/image/7m8v0kiwn/
My questions are:
Note that you don’t need to create an Index class; the type you need already exists.
From the documentation of IntBuffer.compareTo:
Two int buffers are compared by comparing their sequences of remaining elements lexicographically, without regard to the starting position of each sequence within its corresponding buffer.
So if you wrap integer array holding the indices and keep the position and limit at their defaults, the buffers will provide the desired behavior.
Performing the array to map conversion in a general way works, if you consider that in Java, each multi-dimensional array is also an instance of Object[], regardless of their base type. I.e., the type int[][] is a subtype of Object[] whose elements are instances of int[] which is a subtype of Object. Further, Object[][] is a subtype of Object[] whose elements are of type Object[] which is a subtype of Object.
Therefore you can process all dimensions the same way as Object[] to traverse it and only have to care about the actual type at the last dimension, which is always int[] for any n-dimensional int array:
/** accepts all int arrays from one to 255 dimensions */
public static TreeMap<IntBuffer,Integer> toMap(Object array) {
int dim=1;
for(Class<?> cl=array.getClass(); ; cl=cl.getComponentType())
if(Object[].class.isAssignableFrom(cl)) dim++;
else if(cl==int[].class) break;
else throw new IllegalArgumentException(array.getClass().getSimpleName());
TreeMap<IntBuffer,Integer> map=new TreeMap<>();
fill(map, new int[dim], 0, array);
return map;
}
private static void fill(TreeMap<IntBuffer, Integer> map, int[] i, int ix, Object array) {
int next=ix+1;
i[ix]=0;
if(next<i.length)
for(Object part: (Object[])array) {
if(part!=null) fill(map, i, next, part);
i[ix]++;
}
else
for(int val: (int[])array) {
if(val!=0) map.put(IntBuffer.wrap(i.clone()), val);
i[ix]++;
}
}
This solution handles the dimensions recursively though a non-recursive one is in principle possible. However, the recursion depth is naturally limited to the number of dimensions of the array/matrix.
It will put only non-zero values into the map and also skip any null sub-array, thus it doesn’t mind if the array representation is already sparse.
An example usage might look like
int[][][][] array=new int[5][5][5][5];
array[1][2][3][4]=42;
array[4][3][2][1]=1234;
TreeMap<IntBuffer, Integer> sparse=toMap(array);
sparse.forEach((index,value)-> {
for(int ix:index.array()) System.out.print("["+ix+']');
System.out.println("="+value);
});
which will print:
[1][2][3][4]=42
[4][3][2][1]=1234
Another example:
int[][] id = {
{1},
{0, 1},
{0, 0, 1},
{0, 0, 0, 1},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1},
};
TreeMap<IntBuffer, Integer> idAsMap = toMap(id);
System.out.println(idAsMap.size()+" non-zero values");
idAsMap.forEach((index,value)-> {
for(int ix:index.array()) System.out.print("["+ix+']');
System.out.println("="+value);
});
will print:
7 non-zero values
[0][0]=1
[1][1]=1
[2][2]=1
[3][3]=1
[4][4]=1
[5][5]=1
[6][6]=1