3D Mapping Data Structure in Guava

Question

I am implementing a genetic algorithm for constraint based university exam scheduling. For constraint checking to be efficient, I need data structures which contain most of the information before evaluation.

Right now I am using the Table structure from Guava as follows:

Table<Integer, Integer, ArrayList<Student>> clashesMatrix = HashBasedTable.create();

This means that I have students in common between exam i and exam j in a 2D matrix. However now I wish to take this a step further by having students in common between 3 exams i.e I need a sort of 3D matrix. I need this because one of my constraints is to check for two or three consecutive exams in a row for students and it would be more efficient to have this kind of data before checking constraints.

Is there a particular data structure in Guava which could be used for this purpose? Or is there a way in which I can alter the Table above to cater for three exams perhaps?

I would appreciate your help since this is for my degree thesis! Thanks :)

Are you basically looking for an _easier_ structure to work with - that is essentially `Map>>>`? — Scott, Apr 21 '14 at 12:46
yes @Scott I'm looking for something easier to work with. I found Table very easy to work with for 2D structure but when it comes to 3D I didn't find something similar yet — Bernice, Apr 25 '14 at 20:12

score 3 · Accepted Answer · edited May 23 '17 at 11:49

Your previous question already aimed at a similar direction. Now you need another dimension. And you added the (important!) information that the keys are always Integer values. As mentioned in my answer to your previous question, the autoboxing/autounboxing may have a performance impact here, but this should be noticable only for "large" data structures (deliberately not mentioning what exactly "large" means).

For a general, "N-dimensional" indexing, you might consider an own key type. Particularly, something like an IntTuple. (In fact, you could use a List<Integer> as the key type, but this may have some drawbacks). With such an IntTuple class, with proper implementations of hashCode and equals, you can easily define an arbitrary, N-dimensional data structure, that may be used in a form that is convenient and efficient:

Map<IntTuple, List<Student>> map = new HashMap<IntTuple, List<Student>>();

List<Student> students = new ArrayList<Student>();

map.put(IntTuple.of(1,2,3), students);

List<Student> s = map.get(IntTuple.of(1,2,3));

However, note that depending on the exact queries that you want to make, a different structure may be more appropriate. For example, this structure does not allow queries like

"Give me all students where the second element of the 'key tuple' has the value 'x'"

If you need this kind of query, then a different data structure may be more appropriate.

(I had such an IntTuple class in my "snippets directory", I'll insert it here for convenience...)

import java.util.Arrays;

class IntTuple 
{
    static IntTuple of(int ... values)
    {
        return new IntTuple(values);
    }

    private final int data[];
    private IntTuple(int ... data)
    {
        this.data = data;
    }

    public int getDimensions()
    {
        return data.length;
    }

    public int get(int index)
    {
        return data[index];
    }
    @Override
    public String toString()
    {
        return Arrays.toString(data);
    }
    @Override
    public int hashCode()
    {
        return Arrays.hashCode(data);
    }
    @Override
    public boolean equals(Object object)
    {
        if (this == object)
        {
            return true;
        }
        if (object == null)
        {
            return false;
        }
        if (!(object instanceof IntTuple))
        {
            return false;
        }
        IntTuple other = (IntTuple)object;
        return Arrays.equals(data, other.data);
    }
}

Thanks a lot for your detailed answer :) I have to look into what exact queries I need from my data structure first as you pointed out, but this was very interesting and if I don't have any specific queries, I will go for it. Do you have any suggestions regarding other similar data structures that you know of? — Bernice, Apr 21 '14 at 17:59
@Bernice None in particular. I already pointed out in my answer to the other question that the possibility to obtain *either* rows *or* columns from a Guava Table can be a neat feature, but particulularly for higher dimensions, things may become tricky: The queries may then refer to "slices" (or "subspaces") with arbitrary dimensions. E.g. 1D: "Give me all elements with coordinates (3,4,x) for arbitrary x", or 2D: "Give me all elements with coordinates (3,y,x) for arbitrary x and y" and so on. It really depends on what you want to **do** with this data structure. — Marco13, Apr 21 '14 at 18:07

3D Mapping Data Structure in Guava

1 Answers1