How to work around “Single-Ended-Iterator” when dealing with`.rev()`

[TieWay59]

Here is my use case, I want to achieve things like some_string.chars().rev().scan().rev()

But this is impossible because scan() doesn't return DoubleEndedIterator.

My solution would be like that at present:

let mut b: Vec<_> = s.chars().rev().scan(1, cmp).collect();
b.drain(..).rev();

I also tried this:

let mut b: Vec<_> = s.chars().rev().scan(1, cmp).collect(); // <- clippy #[warn(clippy::needless_collect)]
b.into_iter().rev();

Clippy suggests me to write the wrong one:

s.chars().rev().scan(1, cmp).rev();

I wonder what's the best way to avoid this collection cost?

---

my version info:

rustup 1.24.3 (ce5817a94 2021-05-31)
info: This is the version for the rustup toolchain manager, not the rustc compiler.
info: The currently active `rustc` version is `rustc 1.56.0 (09c42c458 2021-10-18)`

If you are interested, I can show you why I need this feature, in the following.

I was working on a leetcode problem Shortest Distance to a Character - LeetCode

Originally I wrote code like this:

impl Solution {
    pub fn shortest_to_char(s: String, c: char) -> Vec<i32> {
        let cmp = |dist: &mut i32, e: char| {
            if e == c {
                *dist = 0;
            } else {
                *dist += 1;
            }
            Some(*dist)
        };
        s.chars()
            .scan(s.len() as i32, cmp)
            .zip(s.chars().rev().scan(s.len() as i32, cmp).rev())
            .map(|e| e.0.min(e.1))
            .collect()
    }
}

this code is tricky but also very funny, I avoid use index variables to iterate the string twice and I even reused the closure.
But saddly it won't compile. As talked previously, I changed my code as blow and it is accepted by Leetcode.

impl Solution {
    pub fn shortest_to_char(s: String, c: char) -> Vec<i32> {
        let cmp = |dist: &mut i32, e: char| {
            if e == c {
                *dist = 0;
            } else {
                *dist += 1;
            }
            Some(*dist)
        };
        let mut b: Vec<_> = s.chars().rev().scan(s.len() as i32, cmp).collect();
        s.chars()
            .scan(s.len() as i32, cmp)
            .zip(b.drain(..).rev())
            .map(|e| e.0.min(e.1))
            .collect()
    }
}

Can I write a better one avoiding collect the vectore b?

[quinedot]

Your reversed iterator finds, for each position, the distance to the closest matching character to the right (or some value at least as large as the length). But you can't know how far it is from the first character (for example) to the closest matching character to the right without first examining at least some of the characters to the right.

That is, your zip can never work the way you intended. In order to find the "to the right" half of the solution in a single pass, that iterator will have to output in right-to-left order. Otherwise you'll have to look ahead, or collect, or do something else than just scan.

You can collect the "to the left" solution half (which is in the correct order to return), and then compare against the "to the right" solution half in place: Playground.

[TieWay59]

Thank you for your reply, actually, the second code block is Accepted by the leetcode judger. Maybe I didn't make it clear. I am not stuck in solving this problem, but I don't feel right with this code style, because I think b: Vec<i32> is unnecessary, but I can't avoid collecting it.

My b: Vec<i32> is the rightward part. As you can see in zip , I need to rev() again to get the right order matching leftward.

[quinedot]

Yes, I didn't think your twice-collecting version didn't work, but you asked how to avoid that. (My suggestion only collects once.)

So let me try to rephrase: If you want to be able to collect once into the end result with a map over two zipped iterators like in your OP, then the first item you pull out of the zipped iterator is going to need to look like:

(
    a, // "distance" to the next `e` to the left (there is none: `s.len()`)
    b, // distance to the next `e` to the right (3 in the example)
)

The iterator that produces 3 has to know that index 3 is the first matching index. The only way this is possible with your scan approach is if it has scanned the entire string backwards. So either

• you have to scan multiple times, stopping at the correct index each time, or
• you scan once but store the other results somewhere

The first is quite inefficient and the second is what you wanted to avoid, in some guise or another.

Thus, you need a different approach. Making two passes is one such approach.

---

It's also possible I'm misunderstanding the question, in which case, could you rephrase?

[H2CO3]

Here's an O(n log n) time and O(n) space complexity solution. It is pretty simple because it is basically a direct translation of the specification into code, and it uses binary search for finding the closest match upon each iteration:

pub fn shortest_to_char(s: String, c: char) -> Vec<i32> {
    let indexes: Vec<_> = s.chars()
        .enumerate()
        .filter_map(|(i, x)| if x == c { Some(i) } else { None })
        .collect();
    
    (0..s.len())
        .map(|i| {
            match indexes.binary_search(&i) {
                Ok(_) => 0,
                Err(j) => {
                    let candidates = [
                        indexes.get(j.saturating_sub(1)),
                        indexes.get(j),
                        indexes.get(j.saturating_add(1)),
                    ];
                    <_>::into_iter(candidates)
                        .flatten()
                        .copied()
                        .map(|j| if i < j { j - i } else { i - j } as i32)
                        .min()
                        .unwrap()
                }
            }
        })
        .collect()
}

(I was lazy with Unicode and I assumed s.chars().count() == s.len(), because the Leetcode page seems to assume the same, but of course the code can be modified trivially to support non-ASCII characters.)

[TieWay59]

I got your idea.

Sorry I didn't look closer into your playground link. And yes, your workaround really handles my question. If I didn't stick to using collection at the end of the function, I would write something similar to yours.

Although I'm still looking forward to seeing something similar to "double .rev()", I should mark your post as the solution later.

Many thanks to you again.

[TieWay59]

Yes, very intuitive. I can understand what you mean while reading the code the first time.

However, I also love my solution which saved a little bit keys to hit.