« Return to Thread: (OT?): List of ranges
Re: (OT?): List of ranges
by Rob Eden
::
Rate this Message:
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@...
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@...
« Return to Thread: (OT?): List of ranges
| Free embeddable forum powered by Nabble | Forum Help |
