How to implement trait for fixed size array of any size

help
1

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?

1 Like
2

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

4 Likes
3

I was afraid of that. Thanks.

4

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
5

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
}
6

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)
    }
}
5 Likes
7

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.

8

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.

3 Likes
9

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
10

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
11

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.

12

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.

13

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.