The title of the reference is missing

[mvaled]

The README states that this data structures is based on the one described by

Cormen et al. (2009, Section 14.3: Interval trees, pp. 348–354)

but it doesn't gives the title of the book.

[mvaled]

Hi @jonathanGB

I'm considering this crate on a project. I was in need to implement an interval tree to perform faster lookups in match-like syntax which is always like:

match value {
    value < u0       => r0,
    l1 <= value < u1 => r1,
    ...
}

There maybe gaps and the match may result a builtin Undefined value (which is like None in Python).

Other crates I found use std::ops::Range which disallow some kind of ranges. So this crate may save me a lot of work.

But I like to read the original paper as well.

[mvaled]

I've just realized we can't attach a data value to a node in the tree. So I probably won't be able to use your crate directly.

I imagine because while re-balancing the tree or merging nodes there's no standard way of merging arbitrary data values. And worse, while splitting nodes there's no way to split the data values.

[mvaled]

I found a full reference in the wiki page https://en.wikipedia.org/wiki/Interval_tree#CITEREFCormenLeisersonRivestStein2009:

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill, ISBN 978-0-262-03384-8

[jonathanGB]

Hi @mvaled, sorry for the late response. I've updated the reference in the README.

As per your other question, I'm not sure to understand what you are trying to do. You want to associate an extra metadata to each node in the interval tree?

[mvaled]

Hi @mvaled, sorry for the late response. I've updated the reference in the README.

As per your other question, I'm not sure to understand what you are trying to do. You want to associate an extra metadata to each node in the interval tree?

Hi @jonathanGB,

I've postpone the usage of interval trees for now. Nevertheless the idea is that in a match-like construction like:

match value {
    value < u0       => r0,
    l1 <= value < u1 => r1,
    ...
}

The branch to be executed could be selected by finding the intervals (left-hand-side of =>) that contain value and the metadata would the right-hand-side of the branch. This would avoid executing each condition.

But since this is just an optimization and requires a lot more work to be done, I've decided to postpone any optimization until the program is completely functional.

Thanks.

PD: Since you did put the reference in commit 959e1d11a5ba27808a4f441c6f853c393d8ba717, I'm closing this issue.