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 :)

Answer 1

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);
    }
}