CODEWITHSUNDEEP
javadata-structures
wvdz
wvdz

Reputation: 16641

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 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?

Upvotes: 5

Views: 2599

Answers (2)

dimo414
dimo414

Reputation: 48824

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

Upvotes: 2

Damir Ciganović-Janković
Damir Ciganović-Janković

Reputation: 981

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;

Upvotes: 4

Related Questions