wvdz wvdz - 1 year ago 42
Java Question

What datatype to use in Java to match interval?

I have a list of objects that implement non-overlapping ranges, e.g.:

1 to 10
11 to 20
21 to 50
51 to 100

They provide
to retrieve those values.

I need a datastore to easily retrieve the right object, given a value that must be in its interval.

The easiest way I can think of is to create an ordered arraylist and simply traverse it until I found the correct interval. So in this case a lookup is done in O(N).

Are there more efficient data structures available in the standard Java library to do this task?

Answer Source

You could try using the NavigableMap, that method is explained in this answer: Using java map for range searches, the 'no holes' aproach.

Example implementation using TreeMap:

// Create TreeMap
NavigableMap<Integer, MyInterval> map = new TreeMap<>();

// Putting values
map.put(interval1.min(), myInterval);
map.put(interval2.min(), myInterval);

// Retrieving values
int value = 15;
MyInterval interval = map.floorEntry(value).getValue();

// Check if value is smaller than max()
if (value <= interval.max())
    return interval;
return null;