Un-interleave an iterator into two separate iterators

Question

Similar to this question: How do I interleave two Rust vectors by chunks of threes into a new vector?

Instead, I'd like to perform the opposite behavior. Separate an iterator into two different iterators without having to collect their contents (a.k.a. I do not want to use unzip).

Furthermore, I want to separate an iterator without collecting the entire contents of the original iterator.

Here is an semi-example:

#[derive(Debug)] struct Foo(i32); fn main() { // note array elements of Foo cannot be copied or cloned // v1: [0, 1, 2, 3] // v2: [4, 5, 6, 7] let v1 = (0..4).map(|num| Foo(num)).collect::<Vec<_>>(); let v2 = (4..8).map(|num| Foo(num)).collect::<Vec<_>>(); // generate interleaved iterator // interleaved: [0, 1, 4, 5, 2, 3, 6, 7] let interleaved = v1.chunks(2) .zip(v2.chunks(2)) .flat_map(|(c1, c2)| c1.iter().chain(c2)); println!("interleaved: {:?}", interleaved.collect::<Vec<_>>()); // regenerate interleaved iterator let interleaved = v1.chunks(2) .zip(v2.chunks(2)) .flat_map(|(c1, c2)| c1.iter().chain(c2)); let mut v3: Vec<&Foo> = vec![]; let mut v4: Vec<&Foo> = vec![]; for (idx, item) in interleaved.enumerate() { if idx % 4 < 2 { v3.push(item); } else { v4.push(item); } } println!("v3: {:?}, v4: {:?}", v3, v4); }

I'd like to find an idiomatic solution to un-interleave the iterator, without having to collect their references into a container.

More generally, I'd like to figure out how to reduce an iterator of n elements down to m elements where n >= m. In this case, I would want to reduce my interleaved iterator of length 8 down to an iterator with chunks of 2 of length 4. Then the chunked iterator would be separated into two other iterators.

In that sense, I want to "parse" my iterator into chunks of 2.

Out of the two iterators that this operation would produce, imagine you consume the second one fully and leave the first one untouched. This means you must have fully consumed the original (chunked) iterator, but half of the elements still have to be stored somewhere (where?). I don't think you can do better than your solution of separating it into two Vecs. — apilat
– apilat, Commented Feb 12, 2021 at 0:07

kmdreko · Accepted Answer · 2021-02-12 00:04:36Z

If the original iterator implements Clone, then you can clone it and do enumerate() + filter() separately:

fn uninterleave<T, I: Iterator<Item = T> + Clone>( iter: I, ) -> (impl Iterator<Item = T>, impl Iterator<Item = T>) { let iter1 = iter .clone() .enumerate() .filter(|(i, _)| i % 4 < 2) .map(|(_, value)| value); let iter2 = iter .enumerate() .filter(|(i, _)| i % 4 >= 2) .map(|(_, value)| value); (iter1, iter2) } fn main() { let v = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; let iter = v.iter(); let (iter1, iter2) = uninterleave(iter); for value in iter1 { print!("{} ", value); } println!(); for value in iter2 { print!("{} ", value); } }

Prints:

0 1 4 5 8 9 2 3 6 7

can this be done without cloning an iterator? I would specifically want to know how I could split a single iterator into two. This solution is valid for clonable iterators but would not work for non-clonable iterators.
I don't know a way without cloning or collecting. Both iterators would need a mutable reference to the original, which isn't allowed. And even if that could work, the issue with building two iterators from one is as @apilat's comment describes: iterating one would iterate the original, meaning it could skip over values that the other iterator wouldn't be able to recover. To avoid losing data, you'd have to know which one to poll from next, which seems like it'd defeat the purpose.

Collectives™ on Stack Overflow

Un-interleave an iterator into two separate iterators

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related