Range tree structure

[neon vault]

If I have a Range that spans from x to y, but let's say that those bounds can be included, excluded, or unbound (like std::ops::Bound) that can be ordered, how can/should I structure RangeSet?
RangeSet would be a way to store multiple ranges and allow requests such as

• range_start(range) which would return an ordered collection of all Ranges within RangeSet that have a range start within the range argument
• range_end(range) you can guess

At first I thought I could structure it like

struct RangeSet {
  ranges: HashSet<Rc<Range>>,
  starts: BTreeMap<RangeStart, Weak<Range>>,
  ends: BTreeMap<RangeEnd, Weak<Range>>,
}

But a problem arises with this approach: when removing a range from the set, how do we know which start/end to delete? We could check for any matching start/end and check if their Weak no longer returns a Some(T), but it seems a bit convoluted.

How could such a RangeSet be structured? What are your opinions on this?

Thank you for your future answers 😄

[uneven turtle]

What if two ranges have the same start?

[neon vault]

then both ranges get stored, as long as both ranges are not equal

[uneven turtle]

well your map has the start as the key, so you can't store both of them in the map, unless you change it to BTreeMap<RangeStart, Vec<Weak<Range>>> or something like that.

[neon vault]

Alright then, I see the issue, but what would be the ideal structure according to you for such tasks?

[spark loom]

https://en.m.wikipedia.org/wiki/Interval_tree not looked too closely but

[uneven turtle]

well, they're overlapping so not exactly

and the queries aren't the same

[neon vault]

yeah, I've looked into that, but I'm looking for a more general solution, where you have an object that have different metrics that can be queried and return the original object, so potentially more than just start/end

[uneven turtle]

Probably just two BTreeSet<Range>, but one is sorted by start and one is sorted by end.

[neon vault]

i see, so newtype pattern i guess for implementing two different Ord?

[uneven turtle]

yeah