Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

Re^2: Range overlap (with a lot of ranges)

by Corion (Pope)
on May 24, 2010 at 12:59 UTC ( #841384=note: print w/replies, xml ) Need Help??

in reply to Re: Range overlap (with a lot of ranges)
in thread Range overlap (with a lot of ranges)

As "both" of your ranges are contingous, I think you can get away by testing whether the start and end points are "close enough" to a start/end point of a range. I would look at the "inversion lists" that the Unicode consortium proposes as an efficient way to implement (tests against) Unicode character ranges.

Some features that inversion lists provide, like fast negation, are not useful to you, so maybe you can get by with even less than what they provide. Maybe even just storing pairs (offset, length) for all your ranges and then doing a binary search for the range at hand already is enough. Maybe there even is a better data structure that allows you to simulatneously track start and end of your range and find the intervals they fall into, but I'm not aware of that.

Replies are listed 'Best First'.
Re^3: Range overlap (with a lot of ranges)
by BioLion (Curate) on May 24, 2010 at 13:09 UTC

    Cool, thanks - I'll follow this up and post anything I find useful...

    Just a something something...

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://841384]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (2)
As of 2020-02-26 01:11 GMT
Find Nodes?
    Voting Booth?
    What numbers are you going to focus on primarily in 2020?

    Results (113 votes). Check out past polls.