Making two iterators for a data structure with less duplicated code?


#1

I have a Bitmap data structure, and I’d like to offer an iterator that takes ownership of the Bitmap and another that only borrows it. The code I have right now is very repetitive: I have an iterator structure for each case, and I implement Iterator for both of those structures—and the code inside those impl's is exactly the same [1]. I was wondering if there was a way to avoid so much duplication.

[1] https://gist.github.com/gnuvince/fe9e2b7850b3be146e3ae8871bd1f565


#2

I think I would just use a common local function that each fn next() can call.

fn iter_next(offset: &mut usize, bitmap: &BitMap) -> Option<u16> { ... }

#3

Ah, good idea, I hadn’t thought of this approach. I still have two Iterator structs, but at least the logic is not copy-pasted. Thanks a bunch!


#4

It would be really ergonomic, if the new impl trait feature (once stable) would allow you forgo explicitly making these structs. But it does not work in trait implementations in this way yet. Are there any extensions planned to allow associated types to be anonymous like that?


#5

I found it! I think with RFC 2071 it would be possible to get rid of the structs and have Rust fill in the right type implicitly.

I’m thinking about something like this:

struct Thing(Vec<u8>);

impl IntoIterator for Thing {
    type Item = u8;
    type IntoIter = impl Iterator<Item=u8>;
    fn into_iter(self) -> Self::IntoIter {
        self.0.into_iter()
    }
}

impl<'a> IntoIterator for &'a Thing {
    type Item = &'a u8;
    type IntoIter = impl Iterator<Item=&'a u8>;
    fn into_iter(self) -> Self::IntoIter {
        self.0.iter()
    }
}

I am only delegating to Vec's iterators here, but you’d be able to plug in any expression in the implementation whose type implements an iterator over the correct item.

Note, that this is probably many months away from landing on stable Rust.


#6

If you want them to truly use the same iterator type, you could make that conditional with Cow:

pub struct BitmapIterator<'a> {
    offset: usize,
    bitmap: Cow<'a, Bitmap>,
}

impl<'a> IntoIterator for &'a Bitmap {
    type Item = u16;
    type IntoIter = BitmapIterator<'a>;
    fn into_iter(self) -> Self::IntoIter {
        return BitmapIterator {
            offset: 0,
            bitmap: Cow::Borrowed(self),
        };
    }
}

impl IntoIterator for Bitmap {
    type Item = u16;
    type IntoIter = BitmapIterator<'static>;
    fn into_iter(self) -> Self::IntoIter {
        return BitmapIterator {
            offset: 0,
            bitmap: Cow::Owned(self),
        };
    }
}

That’s a little unsatisfactory because it requires runtime checks of the Cow variant. You could also make it compile-time generic like:

impl AsRef<Bitmap> for Bitmap {
    fn as_ref(&self) -> &Bitmap { self }
}
// &Bitmap already implements AsRef

pub struct BitmapIterator<B: AsRef<Bitmap>> {
    offset: usize,
    bitmap: B,
}

impl<B: AsRef<Bitmap>> Iterator for BitmapIterator<B> {
    type Item = u16;

    fn next(&mut self) -> Option<Self::Item> {
        let bitmap = self.bitmap.as_ref();
        // ...
    }
}