timerange in java

Question

In Java is there any way to store time ranges as key in Hashmap? I have one HashMap and I store times time range. For example:
I enter 0-50 range as key and for that key I will store some other objects as value. Now when I say 10 I should be able to get the corresponding value for that key.
Any value between 0-50 should get that object.

Map map = new HashMap();
map.put(0-50,"some object")
map.put(51-100,"some other object")

now when I say map.get(10) it should be able to get the "some object". Please suggest how to do this?

Answer 1

I wouldn't use a map, instead I would try with a R-Tree. A R-tree is a tree structure created for indexing spatial data. It stores rectangles. It is often used to test if a point (coordinate) is lying within an other geometry. Those geometries are approximated by rectangles and those are stored in the tree.

To store a rectangle (or the information about it) you only need to save the lower left and upper right corner coordinates. In your case this would be the lower and upper bound of the time span. You can think of it, as if all y values of the coordinates were 0. Then you can query the tree with your time value.

And of course you would save the value at each leaf (time span/rectangle)

A simple search on google for r-tree java brought up some prominising results. Implementing your own R-tree isn't trivial, but it is not too complicated if you understood the principle of re-arranging the tree upon insertion/deletion. In your one dimensional case it might get even simpler.

Answer 2

Assumptions: Non-overlapping ranges.

You can store the starting point and ending point of the ranges in an TreeSet. The starting point and ending point are objects that store the starting time and ending time respectively, plus (a reference to) the object. You have to define comparison function, so that the objects are ordered by the time.

You can obtain the object by using floor() or ceiling() function of TreeSet.

Note that the ranges should NOT overlap, even at the endpoints (e.g. 3-6 and 6-10)

This will give you log complexity for range insertion and query.