How to interlace an iterator with itself from the end?

user_13115582 0
Viewed 87

I have an iterator in the form 0..=63, i.e.
0 1 2 3 4 ... 59 60 61 62 63.
Its .count() is 64.

How would I get the following iterator:
0 63 1 62 2 61 3 60 4 59 ...
(of course independent of the items present in the iterator), preferably without cloning?
The .count() should stay the same, as only the order of items should change.

I've looked in the standard library and couldn't find it, same in the itertools crate.

rust itertools iterator
3 Answers

Here's one way using only the standard library. It requires a DoubleEndedIterator and will skip the last item for odd sized iterators:

fn main() {
    let mut range = (0..=63).into_iter();
    let iter = std::iter::from_fn(|| Some([range.next()?, range.next_back()?])).flatten();
    dbg!(iter.collect::<Vec<_>>());
}

Output:

[src/main.rs:4] iter.collect::<Vec<_>>() = [
    0,
    63,
    1,
    62,
    2,
    61,
    3,
...

    30,
    33,
    31,
    32,
]

Playground

@Finomnis has posted a solution in case your input has an odd number of items.

user_3206150

You could use itertools::interleave to interleave forward and reverse iterators.

  • RangeInclusive<i32> doesn't implement ExactSizedIterator so there's no .len() function. We have to calculate it ourselves.
  • If the range has an odd length the extra item will show up in the forward half thanks to (len + 1).
let range = 0..=63;
let len = range.end() - range.start() + 1;
let iter = itertools::interleave(
    range.clone().take((len + 1) / 2),
    range.clone().rev().take(len / 2),
);

Playground

user_685870

This solution works for all iterators that implement DoubleEndedIterator:

Note that this solution is guaranteed to return all items, regardless of whether the iterator contains an even or odd number of them.

fn selfinterlace<Iter>(mut iter: Iter) -> impl Iterator<Item = Iter::Item>
where
    Iter: DoubleEndedIterator,
{
    let mut from_front = false;

    std::iter::from_fn(move || {
        from_front = !from_front;
        if from_front {
            iter.next()
        } else {
            iter.next_back()
        }
    })
}

fn main() {
    let range = (0..=8).into_iter();
    let iter = selfinterlace(range);
    println!("{:?}", iter.collect::<Vec<_>>());
}

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

The idea is that you store whether the next item should be from the front or the back, and then flip that in every iteration.

from_fn can take FnMut, meaning, it can take closures that store internal state. The internal state in this closure consists of the variables iter and from_front, which get moved into the closure through the move || keyword.

user_29028330
Related