Implement `.range()` for `RedBlackTreeMap`/`RedBlackTreeSet` about rpds HOT 7 CLOSED

Not currently, but it is something we want to implement.

from rpds.

Are you open to pull requests?

from rpds.

Sure, PRs are welcomed :)

from rpds.

So I've been looking into how best to implement the range function. Would it be worth it to add a parent reference to each node? That way we can create a range iterator that will be very optimized.

For example: suppose a tree of the following. If I range from 3..9 (all inclusive) I start an inorder traversal, arrive at 3 and give back an iterator. Now all I need to do on each .next() is continue the inorder traversal until I reach 9.

     5
    /  \
  3      8
 / \    / \
2   4  7   9

That said, this all requires that we add a parent reference to each node. This would offer big savings in very large trees.

from rpds.

I don't think you need the a parent field to do this efficiently. Take a look at how the current iterator works: it maintains a stack that will let you go to the parent node.

Try to modify the current iterator (and the normal iterator just calls the "range" iterator with the range (Unbounded, Unbounded)).

You need to change dig():

to not go left unless left is within the range.

from rpds.

I've taken a look at this, and it seems there's a choice to be made: if I try to reuse the existing ArcIter implementation then I need to get rid of size_hint, since there's no efficient way to initialize left_index and right_index unless we're iterating over the whole tree. An alternative would be to introduce a new struct (RangeIter say). That would cause some code duplication, though.

Do you have any thoughts?

from rpds.

Good point: it will not be a implement ExactSizeIterator. I think we can have the best of both worlds: we can have a RangeIter that does not override size_hint() and does not implement ExactSizeIterator.

Then we can make Iter just a wrapper around a RangeIter (with range (Unbounded, Unbounded)). Iter will still implement ExactSizeIterator, but it only needs to have logic to maintain {right,left}_index

from rpds.