C++ std::set_difference equivalent in Rust

community
6

Here’s a solution using filter and find_map:

use std::cmp::Ordering;

fn sorted_difference<T, U>(left: T, right: U) -> impl Iterator<Item = T::Item>
where
    T: IntoIterator,
    U: IntoIterator<Item = T::Item>,
    T::Item: Ord,
{
    let left = left.into_iter();
    let mut right = right.into_iter();

    let mut right_next = right.next();

    left.filter(move |elem| {
        let check = |other: T::Item| -> Option<(T::Item, bool)> {
            match elem.cmp(&other) {
                Ordering::Less => Some((other, true)),
                Ordering::Equal => Some((other, false)),
                Ordering::Greater => None,
            }
        };
        if let Some((new_right_next, result)) = right_next
            .take()
            .and_then(|o| check(o).or_else(|| right.find_map(check)))
        {
            right_next = Some(new_right_next);
            result
        } else {
            true
        }
    })
}

Edit: Slightly rewritten

use std::cmp::Ordering::*;

fn sorted_difference<T, U>(left: T, right: U) -> impl Iterator<Item = T::Item>
where
    T: IntoIterator,
    U: IntoIterator<Item = T::Item>,
    T::Item: Ord,
{
    let mut right = right.into_iter();
    let mut r_nx = right.next();

    left.into_iter().filter(move |l| {
        let f = |r| match l.cmp(&r) {
            Less => Some((r, true)),
            Equal => Some((r, false)),
            Greater => None,
        };
        r_nx.take()
            .and_then(|r| f(r).or_else(|| right.find_map(f)))
            .map_or(true, |(new_r_nx, keep)| {
                r_nx = Some(new_r_nx);
                keep
            })
    })
}