Implement .range() for RedBlackTreeMap/RedBlackTreeSet

[FallingSnow]

Is it possible to search RedBlackTreeMap like std's BTreeMap range function?

[orium]

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

[FallingSnow]

Are you open to pull requests?

[orium]

Sure, PRs are welcomed :)

[FallingSnow]

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.

[orium]

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():

rpds/src/map/red_black_tree_map/mod.rs

Lines 1135 to 1149 in b713506

	fn dig(stack: &mut Vec<&Node<K, V>>, backwards: bool) {
	let child = stack.last().and_then(|node| {
	let c = if backwards {
	&node.right
	} else {
	&node.left
	};
	Node::borrow(c)
	});
	if let Some(c) = child {
	stack.push(c);
	IterArc::dig(stack, backwards);
	}
	}

to not go left unless left is within the range.

[jneem]

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?

[orium]

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