DoubleEndedIterator for Vec

Question

How to check if a given list/range is a suffix of another range/list. I tried to implement this using DoubleEndedIterator trait which provides facility of backward iteration. But the Vec collection from Rust standard library doesn't implement DoubleEndedIterator trait.

use std::iter::Peekable;

pub fn ends_with<'a, 'b, FirstList, FirstItemType, SecondList, SecondItemType, BinaryPredicate>(
    first_list: FirstList,
    second_list: SecondList,
    binary_predicate: BinaryPredicate) -> bool
where
    FirstList: IntoIterator<Item = &'a FirstItemType>,
    FirstList: DoubleEndedIterator<Item = &'a FirstItemType>,
    FirstItemType: 'a,
    SecondList: IntoIterator<Item = &'b SecondItemType>,
    SecondList: DoubleEndedIterator<Item = &'b SecondItemType>,
    SecondItemType: 'b,
    BinaryPredicate: Fn(&FirstItemType, &SecondItemType) -> bool
{
    let mut f_itr = first_list.rev().into_iter().peekable();
    let mut s_itr = second_list.rev().into_iter().peekable();

    while let (Some(f), Some(s)) = (f_itr.peek(), s_itr.peek()) {
        if !binary_predicate(*f, *s) {
            return false;
        }
        let _ = f_itr.next();
        let _ = s_itr.next();
    }

    f_itr.peek().is_some() || s_itr.peek().is_none()
}

fn main() {
    let first_list = vec![1, 2, 3, 4, 5, 6];
    let second_list = vec![4, 5, 6];

    let res = ends_with(&first_list, &second_list, |first_item, second_item| {
        *first_item == *second_item
    });

    assert!(res);
}

Error

error[E0277]: the trait bound `&Vec<{integer}>: DoubleEndedIterator` is not satisfied
  --> src/main.rs:34:29
   |
34 |     let mut res = ends_with(&first_list, &second_list, |first_item, second_item| {
   |                   --------- ^^^^^^^^^^^ the trait `DoubleEndedIterator` is not implemented for `&Vec<{integer}>`
   |                   |
   |                   required by a bound introduced by this call
   |
note: required by a bound in `ends_with`
  --> src/main.rs:9:16
   |
3  | pub fn ends_with<'a, 'b, FirstList, FirstItemType, SecondList, SecondItemType, BinaryPredicate>(
   |        --------- required by a bound in this function
...
9  |     FirstList: DoubleEndedIterator<Item = &'a FirstItemType>,
   |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `ends_with`

error[E0277]: the trait bound `&Vec<{integer}>: DoubleEndedIterator` is not satisfied
  --> src/main.rs:34:42
   |
34 |     let mut res = ends_with(&first_list, &second_list, |first_item, second_item| {
   |                   ---------              ^^^^^^^^^^^^ the trait `DoubleEndedIterator` is not implemented for `&Vec<{integer}>`
   |                   |
   |                   required by a bound introduced by this call
   |
note: required by a bound in `ends_with`
  --> src/main.rs:12:17
   |
3  | pub fn ends_with<'a, 'b, FirstList, FirstItemType, SecondList, SecondItemType, BinaryPredicate>(
   |        --------- required by a bound in this function
...
12 |     SecondList: DoubleEndedIterator<Item = &'b SecondItemType>,
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `ends_with`

For more information about this error, try `rustc --explain E0277`.

Answer 1

You want to put the DoubleEndedIterator bound on the iterator type, not on the iterable type (i.e., the type that implements IntoIterator). For example, for FirstList, you need to write the bound as FirstList::IntoIter: DoubleEndedIterator<Item = &'a FirstItemType>,. IntoIter is an associated type defined on the IntoIterator trait.

Also, first_list.rev().into_iter().peekable() needs to be changed to first_list.into_iter().rev().peekable() because rev() is not defined by the IntoIterator trait.

pub fn ends_with<'a, 'b, FirstList, FirstItemType, SecondList, SecondItemType, BinaryPredicate>(
    first_list: FirstList,
    second_list: SecondList,
    binary_predicate: BinaryPredicate,
) -> bool
where
    FirstList: IntoIterator<Item = &'a FirstItemType>,
    FirstList::IntoIter: DoubleEndedIterator<Item = &'a FirstItemType>,
    FirstItemType: 'a,
    SecondList: IntoIterator<Item = &'b SecondItemType>,
    SecondList::IntoIter: DoubleEndedIterator<Item = &'b SecondItemType>,
    SecondItemType: 'b,
    BinaryPredicate: Fn(&FirstItemType, &SecondItemType) -> bool,
{
    let mut f_itr = first_list.into_iter().rev().peekable();
    let mut s_itr = second_list.into_iter().rev().peekable();

    while let (Some(f), Some(s)) = (f_itr.peek(), s_itr.peek()) {
        if !binary_predicate(*f, *s) {
            return false;
        }
        let _ = f_itr.next();
        let _ = s_itr.next();
    }

    f_itr.peek().is_some() || s_itr.peek().is_none()
}

fn main() {
    let first_list = vec![1, 2, 3, 4, 5, 6];
    let second_list = vec![4, 5, 6];

    let res = ends_with(&first_list, &second_list, |first_item, second_item| {
        *first_item == *second_item
    });

    assert!(res);
}