[SciPy-User] Scipy.spatial: Interval data structure?

[Nathaniel Smith]

On Fri, Dec 13, 2013 at 10:47 AM, James Anderson
<James.R.Anderson at utah.edu> wrote:
> I’m looking for a reasonably fast interval tree structure in Python and
> Scipy.Spatial seems like the right place for this structure to live.  I need
> the basic queries of “All intervals intersecting a point” and “All intervals
> intersecting an interval”
>
> The only other interval tree I’ve found is in Banyan, but that requires
> compilation and most of my users are on Windows so I try to restrict my
> dependencies to the ones they can easily download from Gohlke’s site.
>
> Right now I’m thinking of coding my own interval tree in pure Python, but
> before I do that is there an existing way of doing this with Scipy I am
> missing?

I don't know of any implementation in scipy.

bx-python has an interval tree implementation, that I think has a
pure-Python version.

For a hack implementing an interval-tree-like structure using the
stdlib sqlite module, there's also this trick:
  http://www.logarithmic.net/pfh/blog/01235197474
which is what rERPy uses:
  https://github.com/rerpy/rerpy/blob/master/rerpy/events.py
But not sure this is the most useful approach unless you need some of
the other advantages of sqlite.

Before spending a lot of effort on writing new code you might see if
cgohlke would be willing to add banyan to his list, or if the banyan
developers are interested in distributing .whl's for windows...

-n