Add range searches to TreeMap/TreeSet

[thestinger]

TreeMap (and TreeSet) should provide a variant of find that returns an iterator instead of the value, for finding the start (or end) of a range of values in O(log n). It would probably make sense to expose lower_bound and upper_bound like C++ does in std::map too.

The basic functionality is pretty simple, it's just the same process as find but each node along the way is pushed onto an iterator's stack, which is then returned. However, it would be nice to get values in the reverse direction too, especially without needing to walk down the tree twice. In C++, the lazy iterators are bidirectional - but that's because they have pointers to walk (which really wouldn't work for an owned tree in Rust, and is likely slower).

[lucab]

That would be really appreciated!

[dim-an]

@thestinger hi, I have some progress on this issue and I would like to try to resolve it, if you don't mind.

However I need some advice:

1. iterators returned from find_iter/lower_bound/upper_bound can not return exact size_hint, am I right? We'll need to return some estimation, won't we?
2. Didn't you think about another approach to iteration? To keep in the iterator stack all ancestors of current node, using this approach we can get parents of the node and iterate in both directions using the same iterator.

[thestinger]

It can return an upper bound but it won't be able to return a lower bound, so it would return (0, Some(tree.len())).

Iterating in both directions from the same iterator isn't a pattern represented by iterators in Rust, because a pair of iterators is more useful. A double-ended iterator is possible for some of the iterators, but it would be slower so it can't just replace the normal iterators.

[dim-an]

@thestinger I implemented lower_bound/upper_bound, please review: #8227

[dim-an]

If pull request (#8227) is accepted and merged (as I hope ^_^), it will be easy to implement find_iter. Though it's not clear to me what this method should return. Option<TreeMapIterator> ? TreeMapIterator that might point to empty sequence? Both options look little bit ugly for me.

Also I can't find a good example of situation when I would want use find_iter, but not lower_bound_iter or upper_bound_iter.

What do you think about it?

[thestinger]

I'm going to call this done. There's the potential for a find_iter convenience function but it's unnecessary, and can be added once there's a use case.