Returning different iterator adapters from same method

[killkrt]

Hi,

Which is the best way to return different types of iterator when you need to apply some different adapters over a container?
For example depending suppose that because of some internal conditions you may need to filter or to chain and then return its result.
I would like to avoid creating a Vec where pushing all elements and returning it.

Here an example:

struct QuadTree {
    data: Vec<i32>,
    children: Vec<QuadTree>,
    subdivided: bool,
}

impl QuadTree {
    fn filter(&self, min: i32) -> impl Iterator<Item = &i32> {
        if !self.subdivided {
            self.data
                .iter()
                .filter(move |&&d| d >= min)
        } else {
            let mut v = core::iter::Filter::empty::<i32>(); // <-- This is not compiling
                                                            //     Anyway I am wondering if this 
                                                            //     would be a good approach.
            for q in &self.children {
                v.chain(q.filter(min));
            }
            v
        }
    }
}

fn main() {

}

Thank you

[H2CO3]

It doesn't compile because impl Trait must stand in for a single static type, but you effectively want dynamic typing here.

You can either return a Box<dyn Iterator<Item = …>>, or keep the impl Iterator and realize the dynamism by returning an enum for which you implement Iterator manually, by matching on it. If you only need a dichotomous decision, you can use the either crate.

[2e71828]

The easiest way in this case will be to return a boxed iterator:

impl QuadTree {
    fn filter(&self, min: i32) -> Box<dyn '_ + Iterator<Item = &i32>> {
        if !self.subdivided {
            Box::new(self.data
                    .iter()
                    .filter(move |&&d| d >= min)
            )
        } else {
            Box::new(self.children.iter().flat_map(move |child| child.filter(min)))
        }
    }
}

Rust Playground

Normally, I'd suggest the either crate (which @H2CO3 mentioned), but it runs into problems here due to the recursion: The non-leaf case has a static type dependent on the total recursion depth, so you have to insert a Box<dyn ...> anyway for that side to compile.

[killkrt]

Thank you (also to @H2CO3)!

Anyway (it is a little out of topic) I have not fully understood why you have to specify the anonymous lifetime in dyn '_ + ..., I am checking the error, but it's not clear to me if it is because of the reference in the associated type Item = &i32 or because of the generic type of the Box itself (so the dyn argument)

[H2CO3]

Every type has a lifetime; it's just when you have a trait object, its actual underlying type is not known to the outside world, hence something at the interface boundary has to indicate what the lifetime/validity of the underlying type is. This depends purely on the lifetimes of the references the type holds (contains), and not on the interface of any of its methods.

[2e71828]

If you're willing to write an iterator from scratch, you can also use a single Vec instead of a chain of boxes to keep track of things:

(untested, but compiles)

pub struct QuadTree {
    data: Vec<i32>,
    children: Vec<QuadTree>,
    subdivided: bool,
}

pub enum QuadTreeItem<'a> {
    Node(&'a QuadTree),
    Leaf(i32)
}

pub enum QuadTreeDepthIter<'a> {
    Start(&'a QuadTree),
    Running {
        stack: Vec<std::slice::Iter<'a, QuadTree>>,
        leaves: std::slice::Iter<'a, i32>,
    },
    Done
}

impl<'a> QuadTreeDepthIter<'a> {
    pub fn skip_node(&mut self) {
        use QuadTreeDepthIter::*;
        match self {
            Start(_) => { *self = Done; },
            Done => {},
            Running { stack, leaves } => {
                if leaves.len() > 0 {
                    *leaves = [].iter();
                } else {
                    stack.pop();
                    if stack.is_empty() { *self = Done; }
                }
            }
        }
    }
}

impl<'a> Iterator for QuadTreeDepthIter<'a> {
    type Item = QuadTreeItem<'a>;
    fn next(&mut self)->Option<QuadTreeItem<'a>> {
        use QuadTreeDepthIter::*;
        use QuadTreeItem::*;
        match self {
            Start(root) => {
                let root = *root;
                *self = Running {
                    stack: vec![root.children.iter()],
                    leaves: [].iter(),
                };
                Some(Node(root))
            },
            Done => None,
            Running { stack, leaves } => {
                if let Some(x) = leaves.next() {
                    return Some(Leaf(*x))
                }
                while !stack.is_empty() {
                    match stack.last_mut().unwrap().next() {
                        None => {
                            stack.pop();
                        },
                        Some(node @ &QuadTree{subdivided: true, ref children, ..}) => {
                            stack.push(children.iter());
                            return Some(Node(node))
                        },
                        Some(node @ &QuadTree{subdivided: false, ref data, ..}) => {
                            *leaves = data.iter();
                            return Some(Node(node))
                        }
                    }
                }
                *self = Done;
                None
            }
        }
    }
}

impl QuadTree {
    pub fn dfs(&self)->QuadTreeDepthIter {
        QuadTreeDepthIter::Start(self)
    }
    
    pub fn filter(&self, min: i32) -> impl Iterator<Item = i32> + '_ {
        use QuadTreeItem::*;
        self.dfs().filter_map(move |item| match item {
            Node(_) => None,
            Leaf(x) if x < min => None,
            Leaf(x) => Some(x)
        })
    }
}

Rust Playground