0
\$\begingroup\$

Adopted some suggestions from the answer of my previous post. Here is the code:

trait MaxElem<T> {
    fn max_elem<'a>(&'a self) -> &'a T;
}

impl<T> MaxElem<T> for [T] where T: Ord {
    fn max_elem<'a>(&'a self) -> &'a T {
        max_elem_helper(self, 0, self.len())
    }
}


fn max_elem_helper<'a, T>(array: &'a [T], left: usize, right: usize) -> &'a T 
    where T: Ord
{
    if right - left == 1 {
        return &array[left];
    }
    let mid = (left + right) / 2;
    let max1 = max_elem_helper(array, left, mid);
    let max2 = max_elem_helper(array, mid, right);
    if max1 > max2 {
        max1
    } else {
        max2
    }
}

#[cfg(test)]
mod test {
    use max_elem::MaxElem;
    #[test]
    fn test_max_elem() {
        let array = [11, 2, 9, 1, 3, 88]; 
        let m = array.max_elem(); 
        assert_eq!(*m, 88);
    }
}

All suggestions are welcome.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$
  1. The code panics with a stack overflow if you provide an empty array:

    #[test]
    fn test_empty() {
        let array: [u8; 0] = [];
        array.max_elem();
    }
    
    thread 'test::test_empty' has overflowed its stack
    fatal runtime error: stack overflow
    error: Process didn't exit successfully: `/private/tmp/max/target/debug/max-426b0349be06fd52` (signal: 6, SIGABRT: process abort signal)
    
  2. The tests don't work unless the crate is named max_elem. Instead, use use super::MaxElem instead.

  3. You could choose to embed the helper method inside of the other function, giving a natural scoping (and preventing the need for the longer name):

    impl<T> MaxElem<T> for [T]
        where T: Ord
    {
        fn max_elem<'a>(&'a self) -> &'a T {
            fn helper<'a, T>(array: &'a [T], left: usize, right: usize) -> &'a T
                where T: Ord
            {
                // ...
            }
    
            helper(self, 0, self.len())
        }
    }
    
  4. Instead of passing in the entire slice and left / right; try splitting the slice into smaller parts via split_at. Then the slice itself tracks the beginning and the end.

  5. The function cmp::max exists.


Overall, there's a nice functional implementation that weighs-in at about 20 lines.

use std::cmp;

trait MaxElem<T> {
    fn max_elem<'a>(&'a self) -> Option<&'a T>;
}

impl<T> MaxElem<T> for [T] where T: Ord {
    fn max_elem<'a>(&'a self) -> Option<&'a T> {
        let len = self.len();

        match len {
            0 | 1 => self.first(),
            _ => {
                let mid = len / 2;
                let (left, right) = self.split_at(mid);

                let left = left.max_elem();
                let right = right.max_elem();

                match (left, right) {
                    (Some(a), Some(b)) => Some(cmp::max(a, b)),
                    _ => left.or(right)
                }
            }
        }
    }
}

#[cfg(test)]
mod test {
    use super::MaxElem;

    #[test]
    fn test_max_elem() {
        let array = [11, 2, 9, 1, 3, 88];
        assert_eq!(Some(&88), array.max_elem());
    }

    #[test]
    fn test_empty() {
        let array: [u8; 0] = [];
        assert_eq!(None, array.max_elem());
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Since the slice is passed by reference, size shouldn't really matter, right? \$\endgroup\$
    – qed
    Sep 19, 2016 at 20:41
  • 1
    \$\begingroup\$ @qed which "size" are you referring to? A slice is a fat pointer; it contains the start of the data and a length, so it takes 2 usize worth of space. The helper method doubles that, requiring a total of 4 usizes. \$\endgroup\$
    – Shepmaster
    Sep 19, 2016 at 20:49
  • \$\begingroup\$ Looks lovely. :-) \$\endgroup\$
    – qed
    Sep 19, 2016 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.