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