search

chaimleib / intervaltree

A mutable, self-balancing interval tree. Queries may be by point, by range overlap, or by range containment.
Apache License 2.0
636 stars 108 forks source link

Is `intervaltree.at(pt)` upper bound inclusive? #128

Closed hongyuchen1030 closed 1 year ago

hongyuchen1030 commented 1 year ago

So I used the following intervals to build the tree

intervals = [[-0.351  0.        ],
                    [0.         0.1745], 
                    [-1.75    0.75],
]

tree = IntervalTree(intervals )

And then I want to find all intervals that overlaps with 0

res = tree.at(0)

It will only return the intervals [0. 0.1745], [-1.75 0.75], and the first interval that has 0 as its maximum will not return.

Is the intervaltree.at(pt) not upper bound inclusive? And if so, how to get an upper-bound inclusive query result? Thanks

chaimleib commented 1 year ago

All intervals in intervaltree are half-open intervals, including the lower bound but not the upper bound. Unless you do some hackery with the internal boundary table, there is no way to query on the upper bounds of contained intervals, since the upper bound is not part of the interval's range.

hongyuchen1030 commented 1 year ago

Thank you for your reply and information. I fixed it by re-implementing the tree._search_point function in my local.

Also thanks for making this open-source package! It helps with our project progress a lot.

chaimleib commented 1 year ago

Welcome!

If you modify _search_point without also modifying how the tree is built, traversed and balanced, you may occasionally be missing results.

hongyuchen1030 commented 1 year ago

Thanks so much for your information. I will take a deeper look into it.