Partition with two predicate

user_10419533 0
Viewed 71

I am looking for a way to partition a Vec with two predicate :

  • One for the first partition point. For example x > 3
  • One for the last element of the partition. For example x < 7

And so for example this vector :

[1, 2, 3, 4, 5, 6, 7, 8, 9]

having this slice :

[4, 5, 6]

I think I can use partition_point twice like the example on std. But is there another method (or crate) where I can pass directly two predicate and slice between the first match of the first predicate and the first match of the second predicate ?

rust loops
2 Answers

If you know that slice actually fulfills this partitioning, your best bet is to use the double partition_point approach.

fn partition_twice_slice<T>(
    vs: &[T],
    start_pred: impl Fn(&T) -> bool,
    end_pred: impl Fn(&T) -> bool,
) -> &[T] {
    let start = vs.partition_point(start_pred);
    let end = start + vs[start..].partition_point(end_pred);
    &vs[start..end]
}

If you just need the first slice that fulfills the partitioning requirements, you can get more creative.

On iterators you can use skip_while and take_while:

fn partition_twice_iter<T>(
    vs: Vec<T>,
    start_pred: impl Fn(&T) -> bool,
    end_pred: impl Fn(&T) -> bool,
) -> Vec<T> {
    vs.into_iter()
        .skip_while(|el| start_pred(el))
        .take_while(|el| end_pred(el))
        .collect()
}

If you only need the slice, you can adapt this to find the bound indices:

fn partition_twice_slice<T>(
    vs: &[T],
    start_pred: impl Fn(&T) -> bool,
    end_pred: impl Fn(&T) -> bool,
) -> &[T] {
    let start = (0..vs.len())
        .find(|&i| start_pred(&vs[i]))
        .unwrap_or(vs.len());
    let end = (start..vs.len())
        .find(|&i| !end_pred(&vs[i]))
        .unwrap_or(vs.len());
    &vs[start..end]
}

Example usage:

fn main() {
    assert_eq!(
        partition_twice_iter(vec![1, 2, 3, 4, 5, 6, 7, 8, 9], |&x| x <= 3, |&x| x < 7),
        vec![4, 5, 6]
    );
    assert_eq!(
        partition_twice_slice(&[1, 2, 3, 4, 5, 6, 7, 8, 9], |&x| x <= 3, |&x| x < 7),
        &[4, 5, 6]
    );
}

Note that I turned around your x > 3 requirement to better fit the convention of partition_point.

user_136796710

This is pretty trivial to implement yourself. It's just a function that takes a slice and two predicates, and returns a subslice:

fn partition<T, P1, P2>(i: &[T], mut p1: P1, mut p2: P2) -> &[T]
    where P1: FnMut(&T) -> bool,
          P2: FnMut(&T) -> bool
{
    let mut start: usize = 0;

    while start < i.len() && !p1(&i[start]) {
        start += 1;
    }

    let mut end = start;

    while end < i.len() && p2(&i[end]) {
        end += 1;
    }

    &i[start..end]
}

(Playground)

user_5012500
Related