What datatype to use in Java to match interval?

Question

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 min() and max() 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?

Yes, but is there a standard datastructure in java that fulfills this requirement? — wvdz, Apr 10 '15 at 13:45
Does your object implement Comparable interface, comparing on that field? What does your object look like? — Rohit Jain, Apr 10 '15 at 13:45
I maintain class of that object myself, so I can add anything I want — wvdz, Apr 10 '15 at 13:48
How about [Arrays.binarySearch()](https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch%28T[],%20T,%20java.util.Comparator%29)? — gtgaxiola, Apr 10 '15 at 13:51

score 4 · Accepted Answer · edited May 23 '17 at 12:00

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;

dimo414 · Answer 2 · 2016-09-20T00:47:34.340

2

No need to reinvent the wheel, Guava provides the Range, RangeSet, and RangeMap classes. See the Ranges Explained docs for more details.

edited Sep 20 '16 at 00:47

answered Apr 10 '15 at 13:52

dimo414

47,227
18
148
244

While this may be a good solution, I was asking for a standard Java data structure. – wvdz Apr 10 '15 at 16:16
`NavigableMap` is also very useful, but limiting yourself to "standard" data structures is an unnecessary impedance. No modern Java codebase is complete without Guava (and much of Guava made its way into Java 8). – dimo414 Apr 10 '15 at 17:07
I'm customizing an ERP system. Adding extra libraries is not trivial for me, that's why I will only resort to this if I really have to. – wvdz Apr 10 '15 at 17:11

What datatype to use in Java to match interval?

2 Answers2