How to store a bidirectional relationship between

问题:

I have an array of nations, and I want to generate the relationship between those nations, so that the relationship between nation A and nation B is always identical to the relationship between nation B and nation A.

For example, Japan and Ecuador have a relationship value of 15. I want to be able to run both get_relationship("Japan", "Ecuador"); and get_relationship("Ecuador", "Japan"); and always get 15. Ideally, I don't want to have to store this value twice, as I don't want to have to bother to keep it in sync.

Below is my current experimental code. Note that I'm storing nations as a HashMap of (name as String, Nation as struct) for unrelated reasons, mainly so I can pull up the desired Nation object by name alone.

extern crate rand;

use std::collections::HashMap;
use rand::Rng;

struct Nation;

pub struct NationManager {
    nations: HashMap<String, Nation>, // The string is the nation's name
    rels: HashMap<String, HashMap<String, i8>>, // Again, both Strings are names
}

impl NationManager {
    fn generate_relationships(&mut self) {
        let mut random_rel: i8 = rand::thread_rng().gen_range(1, 101);
        for (source, _) in &self.nations {
            for (target, _) in &self.nations {
                if source > target {
                    self.rels
                        .get(source)
                        .expect("ERROR")
                        .insert(target.clone(), random_rel);
                } else if source < target {
                    self.rels
                        .get(target)
                        .expect("ERROR")
                        .insert(source.clone(), random_rel);
                } else {
                    continue;
                }
            }
        }
    }
}

fn main() {}

I don't think this is the best way to achieve the desired result, and it doesn't compile at the moment; is it actually possible to nest two for loops like this?

error: cannot borrow immutable borrowed content as mutable
  --> src/main.rs:19:21
   |
19 |                       self.rels
   |  _____________________^ starting here...
20 | |                         .get(source)
21 | |                         .expect("ERROR")
   | |________________________________________^ ...ending here: cannot borrow as mutable

error: cannot borrow immutable borrowed content as mutable
  --> src/main.rs:24:21
   |
24 |                       self.rels
   |  _____________________^ starting here...
25 | |                         .get(target)
26 | |                         .expect("ERROR")
   | |________________________________________^ ...ending here: cannot borrow as mutable

回答1:

First things first: the issue you have is that get returns an immutable reference, and you try to insert in there. You would want to use get_mut to get a mutable reference on which insert can be performed.

---

However I would recommend altering the design:

1. Storing a map name -> ID,
2. Using ID as the key in the other maps.

The main advantage of this scheme being that numerical IDs are much cheaper/efficient than Strings.

pub struct NationManager {
    last_id: u32,
    name_to_id: HashMap<String, u32>,
    relationships: HashMap<(u32, u32), i8>, // (smaller ID, larger ID) -> score
}

Performing a look-up of the relationship between two countries will involve knowing their IDs (two look-ups in name_to_id) and then looking up the relationship score.

The flattening of relationships would tremendously simplify your generation step as well:

impl NationManager {
    fn generate_relationships(&mut self) {
        let random_rel: i8 = rand::thread_rng().gen_range(1, 101);
        for source in 0..self.last_id {
            for target in (source + 1)..self.last_id {
                self.relationships.insert((source, target), random_rel);
            }
        }
    }
}

Note: actually, a domain analysis could let us use a much smaller ID as well; you shouldn't need more than 65,535 nations, so u16 is definitely sufficient, and it's likely that u8 (255 nations) would be sufficient as as well (there are 193 nations registered in the UN).

回答2:

The problem is that you are using the wrong method. HashMap::get does not allow you to mutate the result:

fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> 
    where K: Borrow<Q>,
          Q: Hash + Eq,

You want get_mut:

fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> 
    where K: Borrow<Q>,
          Q: Hash + Eq,