How to implement trait for fixed size array of any size

I have the following trait:

trait Find<T, U>
where
    U: Ord + PartialOrd + Eq + PartialEq,
{
    fn find(array: &T, key: U) -> Option<usize>;
}

and I'd like to impl it for fixed size arrays. This works:

impl<T: Ord> Find<[T; 32], T> for [T; 32] {
    fn find(array: &[T; 32], key: T) -> Option<usize> {
        find(&array[0..], key)
    }
}

but would have to be implemented for each size from 0 to 32 individually. Is there any way to implement a trait for N size arrays?

You will need the const generics feature, which is not stable yet.

2 Likes

I was afraid of that. Thanks.

If you are willing to use const generics in any capacity, my crate staticvec has several examples of doing exactly this kind of thing that you might find useful as a reference.

1 Like

Until const generics land in stable, the work around is to use macros when given a finite number of impls:

trait Find<U : Eq + Ord>
{
    fn find (self: &'_ Self, key: U) -> Option<usize>;
}

impl<T : Eq + Ord> Find<T> for [T] {
    fn find (self: &'_ [T], key: T) -> Option<usize>
    {
        self.iter().position(|x| *x == key)
    }
}

macro_rules! impl_find_for_array {(
    $($N:literal)*
) => (
    $(
        impl<T : Eq + Ord> Find<T> for [T; $N] {
            fn find (self: &'_ [T; $N], key: T) -> Option<usize>
            {
                <[T] as Find<T>>::find(&self[..], key)
            }
        }
    )*
)}

impl_find_for_array! {
    00
    01 02 03 04 05 06 07 08
    09 10 11 12 13 14 15 16
    17 18 19 20 21 22 23 24
    25 26 27 28 29 30 31 32
}

If you're only going to use the array as a slice, I would do something more general like:

pub trait Find<K> {
    fn find(&self, key: &K) -> Option<usize>;
}

impl<T, K> Find<K> for T
where
    T: AsRef<[K]>,
    K: PartialEq,
{
    fn find(&self, key: &K) -> Option<usize> {
        self.as_ref().iter().position(|x| x == key)
    }
}
4 Likes

This worked out great, though this exercise was for a binary search method, so I modified it a bit:

impl<S, T> Find<T> for S
where
    S: AsRef<[T]>,
    T: Eq + PartialEq + Ord + PartialOrd,
{
    fn find(&self, key: &T) -> Option<usize> {
        let (mut start, mut stop) = (0, self.as_ref().len());
        while start < stop {
            let mid = (start + stop) / 2;
            match self.as_ref()[mid] {
                ref val if val == key => return Some(mid),
                ref val if val < key => start = mid + 1,
                ref val if val > key => stop = mid,
                _ => (),
            }
        }
        None
    }
}

Thanks again.

A bit of code review:

Ord implies all the rest of those, just just T: Ord is sufficient.

Perhaps you want

match self.as_ref()[mid].cmp(key) {
    Ordering::Equal => return Some(mid),
    Ordering::Less => start = mid + 1,
    Ordering::Greater => stop = mid,
}

This can overflow if T is a ZST; consider let mid = start + (stop-start)/2; instead.

1 Like

Thanks for the review! I had forgotten about Ordering::*, thanks for that.
I don't follow your last comment, however. What's a ZST? As for the calculation, how is it different?

start + (stop - start)/2 == (2 * start + stop - start)/2 == (start + stop)/2

A ZST is a Zero-Sized Type, such as struct Foo;, struct Foo {}, enum Foo { OneVariant }, PhantomData<_>, [_; 0], or anything recursively made of ZSTs exclusively.

Since an instance of a ZST is zero-sized, it is perfectly possible to have arrays / slices made of a ZST with a gigantic number of elements, such as usize::MAX elements.

In that case, if the element we are looking for is on the right half of such a gigantic array, the expression (start + stop) / 2 overflows usize when computing start + stop; then...

  • either this panic!s when overflow-checks are enabled (enabled by default on debug; disabled by default on release)

  • or it leads to a logic bug.

    • To see how, let's imagine that usize is u8 (to use smaller numbers). Then usize::MAX == 255 and if we go over it we "wrap around" as if 256 were 0 (one can imagine a clock having 256 hours).

      Then if the first comparison yields Less, we have
      start = 127 and stop = 255, and when computing mid, instead of
      mid = start + (stop - start) / 2 = 191, we get:
      mid = (start + stop) / 2 = (127 + 255) / 2 = 126 / 2 = 63
      since 1_u8 + 255_u8 = 0_u8

  • Demo (compare debug vs release)

4 Likes

It's not very practical to find a ZST though, since there's only one possible value, empty. A vector of ZSTs is basically just a glorified counter for its length.

That's a good point. I guess a binary search over ZSTs can always just return the first item? Given that Ord requires Eq which requires a == a, it seems like all instances of a ZST must be equal.