Make it possible to fetch a range from sorted collections when bounds are not representable.

[bwhmather]

I would like to re-open the discussion on supporting range queries on sorted collections (BTreeMap, BTreeSet) where there is no way to create an object representing one or both of the bounds. What I would like to suggest has previously been proposed by @Stebalien as part of the discussion on merging RangeArgument (rust-lang/rust#27787). It appears that it was temporarily dropped in order to get something working released but unfortunately was not picked up again.

Given a BTreeSet<(A, B)>, we would like to be able to query for all tuples with a particular value of A and any value of B. There is currently no way of doing this without knowing the maximum and minimum values of B. If B is a template argument then there is no generic way to find the bounds, and in many cases (e.g. str) a maximum or minimum value simply doesn't exist.

I think that the best way to fix this would be to replace the RangeArgument bound on the argument to range with a new trait containing a single method that takes a reference to a value and returns whether it is above, below or inside the range.

Something like:

trait OrderedRange<T: ?Sized> where T: Ord {
    fn range_cmp(&self, value: &T) -> Ordering;
}

Implementations could be added for the existing start/end based range types for backwards compatibility.
Complexity and real performance should be near identical.

Questions:

• Is there any reason that I am missing why we might not want to do this? Is there another approach that could be taken to solve this problem?
• Should this affect the existing range methods, or should we add new ones?
• What should the trait be called?
• Should we reuse Ordering or add a new enum for below, inside, and above?
• How do we efficiently support ranges that are unbounded in one direction?

If this would be acceptable in principle then I would be interested in taking it through the full proccess.

[cake4289]

One major issue that comes to mind is that this is another case where a bad implementation could cause unsoundness. Ord is already required to satisfy certain axioms (not checked by the compiler) in order for functions requiring Ord to be sound - and OrderedRange would have the same restriction.

In general, though, I think that this is a very good idea. For instance, given a type ℚ representing the rational numbers, one may wish to construct the range √2 < x < π. This is impossible given the current definition of what constitutes a range, but is made trivial by using a closure to represent the range.

[Centril]

Seems like this fits the bill: #2553.