(OT?): List of ranges

[Johannes Schneider-5]

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@...

[Rob Eden]

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@...

[James Lemieux]

Totally agree with Rob's solution. I'd also have suggested exactly this if he didn't beat me to it. :-)

James

PS: To be crystal clear, I'm talking about:

SortedList<Range> s = ...;
int indexOfExistingRange = s.indexOf(new Range(id, id));

On Mon, May 11, 2009 at 11:27 AM, Rob Eden <rob@...> wrote:

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@...

[Jesse Wilson]

On Mon, May 11, 2009 at 3:53 AM, Johannes Schneider <mailings@...> wrote:

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?

You might also want to take a look at TreePair, which is currently an implementation-detail class in Glazed Lists.

https://glazedlists.dev.java.net/source/browse/glazedlists/extensions/jfreechart/source/ca/odell/glazedlists/jfreechart/TreePair.java?rev=1.13&view=markup

With it, you define some ranges [10-20], [30-50], [15-35], and then you can ask "how many ranges overlap 31?" In this case, it would return 2.

[Johannes Schneider-5]

Hi,

thanks for your suggestion.
I tried to implement it using SortedList - and it worked well.

But I have discovered that Collections.binarySearch returns the
insertion index for elements. So I have switched back to ArrayList. And
now I have a really great performance.


So thanks a lot for your help.


Regards,

Johannes

On 05/11/2009 08:27 PM, Rob Eden wrote:

> 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@...
>

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