Find and remove adjacent elements in 2d array?

help
1

So I have Vec<Vec<Foo>>, and fn criteria(&Foo, &Foo)->bool.

I want to look at Vec<Vec<Foo>> as flat structure, row by row,
where the last element of Vec<Vec<Foo>>[0] and the first element of Vec<Vec<Foo>>[1] are adjacent.

And I want to find all ajdancent Foo that match criteria and remove them.

I wrote the code, but it looks too verbose,
can anybody suggest something to simplify the code bellow?

fn find_and_remove(vec_of_vec: &mut Vec<Vec<Foo>>) {
    let mut prev: Option<(usize, &Foo)> = None;
    let mut to_remove = vec![];
    for (i, cur) in vec_of_vec.iter().flatten().enumerate() {
        if let Some((prev_i, prev_val)) = prev {
            if (prev_i + 1) == i && criteria(prev_val, cur) {
                to_remove.push(prev_i);
                to_remove.push(i);
            }
        }
        prev = Some((i, cur));
    }

    let mut n: usize = vec_of_vec.iter().map(Vec::len).sum();
    'main_loop: for j in (0..vec_of_vec.len()).rev() {
        let start = n - vec_of_vec[j].len();
        loop {
            let Some(last_idx) = to_remove.last() else {
                break 'main_loop;
            };
            if start <= *last_idx {
                vec_of_vec[j].remove(*last_idx - start);
                to_remove.pop();
            } else {
                break;
            }
        }
        n = start;
    }
}
2

How do you define "removing adjacent elements matching the criterion"?

  • Which one of the two items passed to the predicate should be removed?
  • What if there are more than two consecutive elements matching the criterion?
3

Both of them.

All of them should be removed.

4

Unfortunately it's one of the tasks that is disproportionally tricky due to safety and borrowing rules.

If you can copy Foo, then you could use:

let mut previous_foo = None;
vec.retain(|this| {
   !previous_foo.insert(this.clone()).is_some_and(|prev| prev == this)
})

You can also just use retain to make processing of to_remove faster.

5

Here's one way (using a collect indices and retain approach).

And here's pretty much the same thing, but much shorter, using itertools.

2 Likes
6

If this is a 2D array where all the rows are the same length, then also consider representing the entire array as a flat Vec<Foo> with length m * n, and retrieving elements like v[i * row_len + j].

This can often improve performance (better cache locality, reduced allocator traffic) and may simplify some algorithms.

2 Likes
7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.