Forward or backward loop depend on condition?

help
1

I want write code like this:

        fn find_item(
            fp: &Foo,
            criteria: impl Fn(&Foo, usize) -> bool,
            search_dir_forward: bool,
        ) -> Option<usize> {
            let n = fp.len();
            let range = if search_dir_forward {
                0..n
            } else {
                (0..n).rev()
            };

            for i in range {
                if criteria(fp, i) {
                    return Some(i);
                }
            }

            None
        }

but it is impossible. Because of 0..n and (0..n).rev() has different types.

Is any way to do it, without macros or boxed iterator?

2

This looks like a workaround for a badly designed Foo. Why doesn't Foo just implement DoubleEndedIterator?

2 Likes
3

You can work with the either crate to avoid boxing…

use either::Either;

fn find_item(
    fp: &Foo,
    criteria: impl Fn(&Foo, usize) -> bool,
    search_dir_forward: bool,
) -> Option<usize> {
    let n = fp.len();
    let range = if search_dir_forward {
        Either::Left(0..n)
    } else {
        Either::Right((0..n).rev())
    };

    for i in range {
        if criteria(fp, i) {
            return Some(i);
        }
    }

    None
}

This is probably find, but in very high-performance loops, the Iterator implementation for Either could be problematic if used like this, because for loops call .next repeatedly, which means repeatedly checking for whether it’s the Left or Right case.

In such settings, the .for_each-style iterator APIs may be more performant, though threading through this an early-return from the outer function can be a bit of a dance… e.g.

use either::Either;
use std::ops::ControlFlow::{Break, Continue};

fn find_item(
    fp: &Foo,
    criteria: impl Fn(&Foo, usize) -> bool,
    search_dir_forward: bool,
) -> Option<usize> {
    let n = fp.len();
    let mut range = if search_dir_forward {
        Either::Left(0..n)
    } else {
        Either::Right((0..n).rev())
    };

    if let Break(r) = range.try_for_each(|i| {
        if criteria(fp, i) {
            return Break(Some(i));
        }
        Continue(())
    }) {
        return r;
    }

    None
}

In this specific case, instead of an if … { return/break Some(item) } inside of a loop, you can probably use Iterator::find instead, too.

use either::Either;

fn find_item(
    fp: &Foo,
    criteria: impl Fn(&Foo, usize) -> bool,
    search_dir_forward: bool,
) -> Option<usize> {
    let n = fp.len();
    let mut range = if search_dir_forward {
        Either::Left(0..n)
    } else {
        Either::Right((0..n).rev())
    };

    range.find(|&i| criteria(fp, i))
}
4

this cannot be done with the builtin Range<usize> type, you'll have to create your own iterator type. example:

// use isize to simplify the negative step
// be careful for overflow and underflow
struct MyRange {
    current: isize,
    last: isize,
    step: isize,
}

impl Iterator for MyRange {
    type Item = usize;
    // this example is edited so it "fuses" the iterator
    fn next(&mut self) -> Option<isize> {
        if self.current == self.last {
            return None;
        }
        let current = self.current;
        self.current += self.step;
        Some(current as usize)
    }
}

if you want the .. syntax, you can implement conversion functions from the standard Range<> type, but with different directions, something like:

// one example of extension trait
impl RangeExt for Range<usize> {
    fn forward(self) -> MyRange { todo!() }
    fn backward(self) -> MyRange { todo!() }
}

let range = if search_dir_forward {
    (0..n).forward()
} else {
    (0..n).backward()
};

// an alternative conversion function could be:
impl RangeExt for Range<usize> {
    fn with_direction(self, is_forward: bool) -> MyRange { todo!() }
}
let range = (0..n).with_direction(search_dir_forward);