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?

get the key first and split it with the "-" character. Then, test your value if it is within the range. — Oneb, May 24 '12 at 05:38
@nhahtdh +1 to this question. If that would be the case, you'll be having multiple results upon getting the value. — Oneb, May 24 '12 at 05:40
@nhahtdh I did not understand your question? Could you please as more detailed manner? — user414967, May 24 '12 at 05:44
Can you have Object A from 3-50, then Object B from 13-65? In that case, we have an overlap from 13-50, which can return both A and B. — nhahtdh, May 24 '12 at 05:46
I wouldn't use a map for this. I would start trying with a modified R-Tree or something similar. Although this means to implement your own version of the tree... — hage, May 24 '12 at 05:47
Did you see this posting: looks very similar to your need: [http://stackoverflow.com/questions/3519901/get-values-for-keys-within-a-range-in-java](http://stackoverflow.com/questions/3519901/get-values-for-keys-within-a-range-in-java) — Sam Goldberg, May 25 '12 at 14:27
Yaa.. thanks a lot!!! In this way I can solve the problem!!! — user414967, May 28 '12 at 04:12

hage · Answer 1 · 2012-05-24T08:41:06.243

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.

It seems a bit overkill for the purpose. Anyway, do you know any implementation of this algorithm? — nhahtdh, May 24 '12 at 06:01
@nhahtdh I wouldn't say it's overkill if you can find an implementation (I'm not aware of one in Java). The tree has a good look up complexity and space is needed just for two doubles + the object reference — hage, May 24 '12 at 06:06

nhahtdh · Accepted Answer · 2012-05-24T06:19:45.407

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.

score 1 · Answer 3 · answered May 24 '12 at 05:56

If this is a non overlapping and equi distant range i.e. range split by say 50, you can solve this problem by maintaining hash for the max numbers like

50 - 'some object', 100 - 'some other object', etc..

if the input is 10, derive the immediate multiple of 50 and get the value for that key.

You can arrive at immediate multiple of 50

take mode on input say for the input 90 i.e. 90 % 50 = 40
compute diff of step 1 result with 50. i.e. 50 - 40 = 10
add step 2 result to input i.e. 90 + 10 = 100

score 0 · Answer 4 · answered May 24 '12 at 05:42

0

You need to map the ranges to a single key, why dont you use something like a rangemanager object which returns for anyvalue between min and max the key 1 for example. alternativly you can put the someobject as a value for all keys between 1 and 50 using a for loop, but this would be a waste in my eyes.

answered May 24 '12 at 05:42

CloudyMarble

36,908
70
97
130

I thought of doing in that way first. But I have to loop all the values. If there are no other way I would use that only. – user414967 May 24 '12 at 05:45

timerange in java

4 Answers4