Function matchertools::gale_shapley

pub fn gale_shapley<'a, T>(
    input_men_preferences: &'a HashMap<&T, Vec<&T>>, 
    input_women_preferences: &'a HashMap<&T, Vec<&T>>
) -> HashMap<&'a T, &'a T> where
    T: Eq + Hash, 

Returns a HashMap indicating who is engaged to whom using the Gale-Shapley algorithm

I use the terms 'man' and 'women' here because it helps me relate to the words used in the original stable marriage problem.

Remarks:

The number of men and women should be equal. In other words, input_men_preferences and input_women_preferences should have the same number of keys. Also, each 'man' in input_men_preferences should indicate the 'ranking' of each woman in the associated vec. Same holds true for women - man: each woman in input_women_preferences should indicate her preference in the associated vec.

Arguments:

• input_men_preferences - HashMap of each men to a vec of women, ordered by preference. The most preferred woman comes first in the vec
• input_women_preferences - HashMap of each woman to a vec of men, ordered by preference. The most preferred man comes first in the vec

Returns:

A Hashmap<T, T> which maps each man to a woman. This mapping will be stable.

Examples

use std::collections::{HashMap};
let mut men_preferences= HashMap::new();
let mut women_preferences = HashMap::new();

men_preferences.insert(&"julius", vec![&"cleopatra", &"boudica"]);
men_preferences.insert(&"vercingetorix", vec![&"boudica", &"cleopatra"]);

women_preferences.insert(&"cleopatra", vec![&"julius", &"vercingetorix"]);
women_preferences.insert(&"boudica", vec![&"vercingetorix", &"julius"]);

// TODO: Remove the mutable reference
let engaged_man_woman =
    matchertools::gale_shapley(&men_preferences, &women_preferences);

assert_eq!(engaged_man_woman.get(&&"julius"), Some(&&"cleopatra"));
assert_eq!(engaged_man_woman.get(&&"vercingetorix"), Some(&&"boudica"));