Consider a standard library trait for determining if an index is valid and/or a Index-able's bounds

At the moment, there's no way in the standard library to generically be able to find the bounds of something when indexing it. This usually comes into play with Index types, though not exclusively.

The motivating example in my case is a KDTree, a KDTree requires indexing some data structure at a different index every level, modulo the dimensional of the vector. This could obviously suits the Vec type very well, but I'm planning on also using a custom sparse vector to interface with some C code.

Of course, it's not overly arduous to define this trait myself. In fact, looking over this RFC, this ended up being far more general than my specific problem, and doesn't even work for it (if it returns Bounded::Unknown or Bounded::Unbounded, my program would choke). Regardless, it just seems... odd... to not have a generic way of asserting the bounds of an indexable type when such a thing is possible.

After playing around, my proposal looks like this:

enum Bounded<T> {
    /// There are bounds for this type,
    /// but they cannot be (easily) computed.
    /// However, they can be easily verified.
    Unknown,
    /// There are no bounds for this type, any
    /// index value will produce valid output
    /// from Index. This also means any
    /// call to valid_index will yield true.
    Unbounded,
    /// The element of this struct represents the
    /// exact bounds of the indexable in some way.
    /// All (and only) values within these bounds as defined
    /// by the trait implementation are valid indices.
    Bounded(T),
}

/// A BoundedIndex can easily verify that an index is valid.
/// It also may be able to report its exact bounds in some way.
trait BoundedIndex<Idx>: Index<Idx> {
    type Bounds;
    fn bounds(&self) -> Bounded<Self::Bounds> { Bounded::Unknown }

    fn valid_index(&self, index: Idx) -> bool;
}

I have a playground link with an example for Vec (known bounds as a usize len) and HashMap (unknown bounds) here: http://is.gd/W1uvF1

Another example may be a Range, where the bounds are a tuple: (lower, higher).

Not everything needs to implement this, but I think having a trait so you can require that you have a way to know the bounds of an Index-able is important. I've certainly come across the need more than once.

I'm still not entirely happy with the bounds functionality. Ideally it feels like there should also be a universal way to use the contents in a Bounded::Bounded, but that may not be true.

Start with the proposed Bounded and BoundedIndex definitions and the linked playground examples for Vec and HashMap. Compare the stated needs for KDTree, sparse vectors, and Range with the unresolved bounds semantics. Done means reaching an agreed standard-library trait design suitable for an RFC.