Converting between different iterators over the same Item type

I have an iterator from an external library over a type, in this case the iterator is EdgeIter<'a> and the Item type is EdgeRef<'a>. Now I want to implement my own iterator over my own items, containing an EdgeRef<'a>, but provide additional methods. So I want to have the iterator GraphEdges<'a> over Items of type GraphEdge<'a>:

pub struct GraphEdge<'a>  {
    edge: EdgeRef<'a>,
}
impl<'a> GraphEdge<'a>  {
    pub fn contains_weight(&self, w: &usize) -> bool {
        // ...
    }
    pub fn max_weight(&self) -> Option<&'a usize> {
        // ...
    }
}

And also the iterator GraphEdges<'a> provides additional methods:

pub struct GraphEdges<'a>  {
    iter: EdgeIter<'a>,
}
impl<'a> std::iter::Iterator for GraphEdges<'a> {
    type Item = GraphEdge<'a>;
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.map(GraphEdge::from).next()
    }
}
impl<'a> From<EdgeIter<'a>> for GraphEdges<'a> {
    fn from(iter: EdgeIter<'a>) -> Self {
        Self {
            iter
        }
    }
}
impl<'a> GraphEdges<'a>  {
    pub fn max_edge(&self) -> Option<<Self as Iterator>::Item> {
        // ...
    }
    pub fn max_weight(&self) -> Option<usize> {
        // ...
    }
    pub fn group_by_weight(&self) -> Vec<Vec<GraphEdge<'a>>> {
        // ...
    }
    pub fn sort_by_weight(&mut self) -> Vec<usize> {
        // ...
    }
    // how can I do this?
    pub fn filter_by_weight(self, w: &usize) -> Self {
        self.filter(|e| e.contains_weight(w))
    }
}

Here, the result of self.filter(|e| e.contains_weight(w)) is of type Filter<GraphEdges<'a>, [closure@...]>, but I would like the type to remain GraphEdges<'a>, and would like to only change the behaviour of the iterator, i.e. the contained items, not their type.
How is this supposed to be done?
Should I make GraphEdges an enum, which can represent Filters, Maps and EdgeIters internally?
Should I implement a GraphIterator trait which contains all of my methods and implement it for all Iterators over GraphEdges and use impl Traits as returns... that actually sounds like it would work.. :sweat_smile:

Just leaving this here for documentation and maybe someone has an even better idea.

You can make it generic over the iterator type:

pub struct GraphEdges<'a, I>
where
    I: Iterator<Item = EdgeRef<'a>>,
{
    iter: I,
}

However, in this case it's probably easier just to skip the custom type and provide these as functions:

pub fn graph_iter<'a>(iter: EdgeIter<'a>) -> impl Iterator<Item = GraphEdge<'a>> {
    iter.map(GraphEdge::from)
}

pub fn filter_by_weight<'a, I>(iter: I, w: usize) -> impl Iterator<Item = GraphEdge<'a>>
where
    I: Iterator<Item = GraphEdge<'a>>,
{
    iter.filter(|e| e.contains_weight(w))
}

I'm not sure how the other methods of GraphEdges work; how do they find things like the max edge and weight if they only have immutable access to the iterator? It seems to me like GraphEdges should contain a Vec<GraphEdge<'a>> or something instead of an iterator.

1 Like

Yeah the impl Trait solution is not possible yet unfortunately because traits can't require methods returning impl Trait. There is an RFC though. (existential-types)