Potential Bug in overlappers Function

[yaz1]

Hi,
I detected a bug in overlappers function that it did not return all overlapping intervals with a point. When tested with few intervals, the code works fine. However, with large number of intervals, inserts and deletes, overlappers does not return all overlapping intervals. I verified that by simply printing the tree before each call to overlappers and checking the output of overlappers. In some cases, overlappers function doesn't return all overlapping intervals,
When I tested my code with another implementation of intervaltree(http://algs4.cs.princeton.edu/93intersection/IntervalST.java.html), I found no bugs.

I apologize that I am not able to provide more details due to a deadline that I have to meet. I suggest more stress testing.

[charcuterie]

Thanks. I'll write some more testing when I have time.

[charcuterie]

How are you representing a point? I have a class that I was using for simple tests -- SimpleInterval -- and it doesn't do any bounds checking. If you're trying to represent a point at 1 with new SimpleInterval(1, 1), you'll get a bunch of weird things happening.

[yaz1]

I don't remember exactly, but I was not using SimpleInterval class.

…

On Thu, Jan 25, 2018 at 4:50 PM, Mason M Lai ***@***.***> wrote: How are you representing a point? I have a class that I was using for simple tests -- SimpleInterval -- and it doesn't do any bounds checking. If you're trying to represent a point at 1 with new SimpleInterval(1, 1), you'll get a bunch of weird things happening. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#2 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKDQL1OwBP7WT0tqxrMylLR2ODc1cu3Wks5tOSFxgaJpZM4QBEDL> .

-- Best Regards, Yazeed Alabdulkarim

[charcuterie]

This repo is actually pretty old. About a year ago, I moved this over to my work account and integrated it into their codebase. I did a lot more testing there, fixed a bunch of things, and everything seems to work fine. I'll pull that code over here.

[hkoueke]

This repo is actually pretty old. About a year ago, I moved this over to my work account and integrated it into their codebase. I did a lot more testing there, fixed a bunch of things, and everything seems to work fine. I'll pull that code over here.

Hello Charlotte. Any news about the updated codebase? I would like to use it in a project... Also, how can i subclass Interval to add a value ? Say [3000 - 6000] interval value is 180? One last query. How can i compute all numbers which, taken in provided set of intervals sum up to a particular number? Sorry for the long text!

[bluebear94]

I think @charcuterie has been inactive since 2016. Pretty unfortunate, since I happen to be using this code as well.

[bluebear94]

Another possibly related bug: next() throws NoSuchElementException, even if hasNext() returns true:

java.util.NoSuchElementException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1447)
	at java.util.HashMap$KeyIterator.next(HashMap.java:1469)
	at datastructures.IntervalSetTree$OverlapperIterator.next(IntervalSetTree.java:1253)
	at datastructures.IntervalSetTree$OverlapperIterator.next(IntervalSetTree.java:1)
	at flirora.arcompu.item.io.AddressMap.dereference(AddressMap.java:102)

[charcuterie]

Sorry, since 2016 I underwent a sex change and am working in the cosmetology field. Didn't realize people were actually using this code. I'll try to find some time and look at it again.