Re: (OT?): List of ranges

Are there overlapping ranges? If not...

I would look into a SortedList. Say the class inside it is called "Range". Make it comparable, then I think you should be able to use Collections.binarySearch to find the location of the range that applies (if there is one). It'd take a bit of playing with, but it should work. (Oh, and put the key you're looking to into a Range object when searching.)

Rob

On May 11, 2009, at 5:53 AM, Johannes Schneider wrote:

Hi,

I have a bookkeeping problem. I have a big, big range of possible ids and need a way to find out whether one id has already been used.

My current (very simple implementation) consists of a sorted list of objects that cover an id range (each object has a start and end id).
Now I need a collection implementation that offers an efficient way to find an object for *any* id of its range.

Example:
Object 1: [1-3]
Object 2: [7-300]

Now I have the id "200" and have to find out which object's range contains that id. At the moment I have a simple list and iterate over every object... But of course that is not very efficient for big ranges.
Using a map is a possibility, but since the id ranges are very, very big (several millions) this is not very efficient.
I also want to merge two objects if they are direct neighbors.

Do you have any idea how I could solve that problem? Is there any collection out there that helps me to solve that?



Thanks,

Johannes


---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...