How to iterate and modify, iterator with int indexes

help
1

I've got some code that implements a geometric data structure called a "doubly connected edge list" (DCEL). It's used for algorithms related to polygons. It stores arrays of vertices, edges, and faces. I use IDs (usize) to refer to these elements in their arrays. I have a function that returns an iterator to walk the edges around a polygon face:

type EdgeId = usize;
...
for edge_id in dcel.walk_around_face(start_edge_id) {
    dcel.edges[edge_id].incident_face = f;
}

The problem here is that my iterator borrows the data structure. So that line inside the loop fails the borrow check.

pub struct FaceEdgeWalkIterator<'d> {
    dcel: &'d DCEL,
    start: EdgeId,
    current: EdgeId
    ...
}
impl<'d> Iterator for FaceEdgeWalkIterator<'d> {
    type Item = EdgeId;
    fn next(&mut self) -> Option<EdgeId> {
        let to_ret = self.current;
        self.edge = self.dcel.edges[self.current].next;
        ...

However I think my code should be safe. The iterator uses properties of the edges like next, but does not touch the incident_face property.

I know I can use unsafe here to get a raw pointer to dcel.edges before the loop and just blast away. But I wonder if there are any standard ways to handle this?

let edges_hack = ptr::addr_of_mut!(self.dcel.edges);
for e_id in self.dcel.walk_around_face(start) {
    let edge_ref = unsafe { &mut (*edges_hack)[e_id] };
    edge_ref.incident_face = f;
}
2

You could try to make the iterator return a mut ref to the individual item. If that doesn't work you could put the unsafe there, as that would give you a good safe API boundary. Maybe you would need to have a Iterator for shared and mut refs, but the stdlib does the same.
Alternatively ou could somehow first store what you want to do on which element and then apply all those operations.

3

I think your pointer solution is UB but I am not 100% sure. You should check it with MIRI. I think this line

self.edge = self.dcel.edges[self.current].next;

invalidates edges_hack.

What I would do is to introduce interior mutability for incident_face. Another option would be to get rid of the iterator trait and implement a lending iterator that hands out a mut reference to DCEL together with the index.