greensync / interval-tree Goto Github PK

The project description states that this is an augmented tree implementation when in fact it's very much a centered interval tree. Please fix.

Hello, I think am in need of an interval tree. I saw yours but it looks like it only handles a fixed set of ranges rather than allowing for inserts and deletes. Is that correct?

Context

Ultimately I am working on this https://twitter.com/schneems/status/1479554521307176960 where I want to speed up this code: https://github.com/zombocom/dead_end/blob/0170bf3df9c045e4d5f042c6b161ff0c30f2efda/lib/dead_end/code_frontier.rb#L152-L154. I need to find all elements in a collection that are between two values.

I've begun attempting to write an augmented interval tree based on a red-black tree and then specializing it to optimize for querying elements that are completely within a given range. I'm doing one insert and one search for every operation so both need to be equally fast. Right now with a plain binary tree my insert is fast, but searching for contained entries is slower than a naive array iteration of N elements.

It's my belief that adding annotations to the red-black tree, (and possibly reversing the sort interval, so it's sorted on end key first and start key last) will allow me to eliminate more nodes from my search and hopefully give me better than naive time.

Questions

• Can you verify that insert/delete are not implemented on this?
• Assuming it could insert/delete would this centered interval tree be a good structure for querying elements contained by a range?
• Any general advice, hints, or tips? Sorry for the random extra questions, I appreciate that this isn't stack overflow but wanted to see if you had any thoughts

BTW thanks for open-sourcing this.

Travis builds have been inexplicably failing recently, and it's kinda slow to pick up the jobs.

We use Buildkite for our private repos, but for security reasons, we shouldn't use it for public repos, where PR branches build automatically.

Elsewhere, I've seen we've had luck with GitHub Actions, so let's go with that.

In current implementation, the result is not consistent:

IntervalTree::Tree.new(10..10).search(10)
 => [10...11]

IntervalTree::Tree.new(10..10).search(10..10)
 => []

The result of query 10..10 should be [10...11], too.