How to do nested iteration of struct fields?

help
#1

I know there is something wrong, but I can not figure out how to solve this.
I have a vec of students over which I iterate. If any student is the only applicant for a gift (he/she wants to have gift x) they get assign to that gift. So in my mind I need those nested iterations with and also the mutable borrows. How can I solve this in an ideomatic way?

pub fn solve(&mut self) {
    for student in self.students.iter_mut() {
        let is_only_applicant_for_primary = !self.students.iter().any(|s| s.primary == s.primary && s != student);
        if is_only_applicant_for_primary {
            println!("Student {} is the only applicant for gift nr.{}", student.nr, student.primary);
            self.assign(student, student.primary);
        }
    }
}

fn assign(&mut self, student: &Student, gift_nr: u16) {
    let gift = self.gifts.remove((gift_nr - 1).into());
    self.assignments.push(Assignment::new(student.to_owned(), gift));
    self.students.retain(|s| s != student);
}

PS: I am fairly new to Rust so please do not hesitate to correct me on anything I might have not understood.

#2

Your code is not runnable as-is, but I suspect the problem is that you are trying to borrow the entirety of self mutably while part of it is also borrowed mutably (self.students.iter_mut()).

What you are trying to do doesn't quite make sense: you are iterating over the array of students while simultaneously trying to remove from it. That doesn't work (it usually doesn't work in other languages either, it may segfault, throw exceptions, or silently do the wrong thing). You'll have to consider re-designing your algorithm in a way that it does not need to mutate the students while they are being enumerated.

#3

I'm failing to connect your description of the task you're solving with your code:

s.primary == s.primary should always be true, which means is_only_applicant_for_primary boils down to "there is only one unique student in this collection (as per s != student)". (If there are never duplicate students in the list, this further boils down to "the collection of students is of size 1".)

#5

Oh yes, it should be student.primary == s.primary

@H2CO3
I thought so myself. But I am failing so come up with another idea. What I am trying to accomplish is to check if any student is the only one with a particular primary. If that is the case. The student will be assigned to that primary number and both the student and gift (according to the number) would then be removed from the structs student/gift list. So that they are out of the whole assignment process, since they already have a gift assigned.
Am I thinking to object oriented here that I want to store the vectors as a struct field?

#6

The usual way around this is to have a two step process that precalculates everything that would need to read the thing you’re modifying. My first attempt at writing this algorithm looks like this:

/// Assigns uncontested grants to students.
/// Returns an iterator of unassigned students
fn assign_grants<'s, 'g>(
    students: impl Iterator<Item = &'s Student>,
    grants: &'g mut Vec<Option<&'s Student>>,
) -> impl Iterator<Item = &'s Student> {
    let mut applicants: Vec<Vec<usize>> = vec![vec![]; grants.len()];
    let mut students: BTreeMap<usize, &Student> = students.enumerate().collect();

    for (&i, s) in students.iter() {
        applicants[s.primary].push(i);
    }

    let applicants = applicants; // Done mutating

    for (out, candidates) in grants.iter_mut().zip(applicants) {
        if out.is_none() && candidates.len() == 1 {
            let s = candidates[0];
            *out = Some(students.remove(&s).expect("Double Assignment!"));
        }
    }

    // Write next stage of matching here

    students.into_iter().map(|(_, v)| v)
}

(Playground)

Two things to note here:

  • I store students in a BTreeMap so that removals don’t change the associated index.
  • I pre-build an index of students by the grants they’ve applied for.
3 Likes
#7

I also took a shot at an alternate algorithm. I took a guess at what your data structures are (and kept them the same), but it's naturally just a guess. The approach is to first identify what needs to be removed from students, then to do the removal (keeping track of what was removed), and finally to shuffle things from gifts to assignments.

For that last step, mind the note in the comments about removing a list of indices from a Vec in non-decreasing order. It's quite likely a bug in your original example. A different approach (most likely requiring different data structures) would be better.

Playground

#8

(It's still a bug in my version too really, as the indices in the non-removed self.students are no longer valid once self.gifts has been altered.)

#9

I am sorry to say, but this is to advances for me to get what is going on there. I appreciate thy try.

This is what I was looking for. I think I understood everything. Thank you for the effort.