Bug #91238 for Set-IntervalTree: Allow zero-length intervals (points)

Sat Dec 07 12:14:55 2013 phin [...] mailnesia.com - Ticket created

Subject:

Allow zero-length intervals (points)

Please allow intervals of zero length, i.e. intervals with the same start and end point. A very practical use case for this: storing a bunch of timestamps and returning those in a specified interval.

Mon Dec 09 12:36:51 2013 BENBOOTH [...] cpan.org - Correspondence added

Hi, On Sat Dec 07 12:14:55 2013, phin@mailnesia.com wrote: Show quoted text

> Please allow intervals of zero length, i.e. intervals with the same > start and end point. A very practical use case for this: storing a > bunch of timestamps and returning those in a specified interval.

Unfortunately, the underlying C++ algorithm (which I did not write) was originally designed to work on both-ends-open intervals, and doesn't support zero-length intervals (well, it accepts them but then returns incorrect results). My XS wrapper converts between the half-open intervals you supply and the both-ends-open intervals the C++ code expects. I'm sure it's possible to convert the C++ code to use half-open intervals natively, but I'm not sure if/when I will find time to work on this. I do have a github repository here: https://github.com/benwbooth/Set-IntervalTree So, if you're feeling adventurous you could check out the src/interval_tree.h file and see how hard it would be to do the conversion. If you make any progress, please send a pull request and I will merge it in. Any help is greatly appreciated!

Mon Dec 09 12:36:52 2013 The RT System itself - Status changed from 'new' to 'open'

Thu Aug 14 17:27:58 2014 erik [...] zasran.com - Correspondence added

Subject:	[rt.cpan.org #91238] Allow zero-length intervals (points)
Date:	Wed, 13 Aug 2014 16:26:07 -0700
To:	bug-Set-IntervalTree [...] rt.cpan.org
From:	Erik Steffl <erik [...] zasran.com>

Given that datasets can include zero length intervals, is there any way to handle them now? Context: I am using Set::IntervalTree for IP range to location mapping ands there are lot of ranges that are just one IP address. What exactly do you mean when you say C++ code only supports open ended intervals? If I have interval 3 to 5 then are 3 and 5 inside the interval? Or is only 4 inside this interval? thanks! erik

Thu Aug 14 17:38:58 2014 BENBOOTH [...] cpan.org - Correspondence added

On Thu Aug 14 17:27:58 2014, erik@zasran.com wrote: Show quoted text

> Given that datasets can include zero length intervals, is there any > way to handle them now? > > Context: I am using Set::IntervalTree for IP range to location > mapping ands there are lot of ranges that are just one IP address. > > What exactly do you mean when you say C++ code only supports open > ended intervals? If I have interval 3 to 5 then are 3 and 5 inside the > interval? Or is only 4 inside this interval? > > thanks! > > erik

There's a C++ header file in the source code for Set::IntervalTree that contains all the interval tree logic. I didn't write it; I only adapted it from some code I found on the internet, added templates, etc. The original code uses both-ends inclusive intervals, but the perl wrapper converts those to half-open intervals. I tried allowing zero-length intervals in the perl wrapper, but it gave unexpected results ( for example, the overlap function would return things it shouldn't or it wouldn't return things it should). So someone needs to go through that C++ code, convert everything to half-open intervals, and make sure that zero-length interval overlaps work as expected. I haven't done this because I don't have any use for this module anymore. So the simplest stopgap was to disallow zero-length intervals until someone provides a fix. I'm more than happy to accept patches or hand this module off to another maintainer.