Repository: TheAlgorithms/C-Plus-Plus
File: greedy_algorithms/gale_shapley.cpp (C++)

Code before:
        if (freeMan == n) break;

        int womanToPropose = men_prefs[freeMan][next_proposal[freeMan]];
        next_proposal[freeMan]++;
        int currentFiance = engagements[womanToPropose];

        if (currentFiance == -1) {
            engagements[womanToPropose] = freeMan;
            free_men[freeMan] = false;
        } else {
            if (find(women_prefs[womanToPropose].begin(), women_prefs[womanToPropose].end(), freeMan) <
                find(women_prefs[womanToPropose].begin(), women_prefs[womanToPropose].end(), currentFiance)) {
                engagements[womanToPropose] = freeMan;
                free_men[freeMan] = false;
                free_men[currentFiance] = true;
            }
        }
    }

    cout << "Stable Matches:\n";
    for (int woman = 0; woman < n; woman++) {
        cout << "Woman " << woman << " is engaged to Man " << engagements[woman] << endl;
    }
}

void runTestCase(int caseNum) {
    const int n = 4; // Number of men and women

    // Test Case 1
    if (caseNum == 1) {
        cout << "Test Case 1:\n";
        vector<vector<int>> women_prefs = {
            {1, 0, 3, 2}, // Alice
            {0, 1, 2, 3}, // Becky
            {1, 2, 0, 3}, // Cathy
            {3, 2, 1, 0}  // Diana
        };
        vector<vector<int>> men_prefs = {
            {0, 1, 2, 3}, // Bob
            {1, 0, 3, 2}, // Charlie
            {0, 2, 3, 1}, // David
            {2, 1, 0, 3}  // Edward
        };
        stableMatch(women_prefs, men_prefs, n);
    }
    
    // Test Case 2
    else if (caseNum == 2) {
        cout << "Test Case 2:\n";
        vector<vector<int>> women_prefs = {
            {0, 1, 2, 3}, // Eve

Review comment (suggestion):
```suggestion
void tests() {
```
please document all functions

Code after:
 */
namespace stable_matching {
/**
 * @brief The main function that finds the stable matching between two sets of elements 
 * using the Gale-Shapley Algorithm.
 * @note This doesn't work on negative preferences. the preferences should be continuous integers starting from 
 * 0 to number of preferences - 1.
 * @param primary_preferences the preferences of the primary set should be a 2D vector
 * @param secondary_preferences the preferences of the secondary set should be a 2D vector
 * @returns matches the stable matching between the two sets
 */
std::vector<std::uint32_t> gale_shapley(const std::vector<std::vector<std::uint32_t>>& secondary_preferences, const std::vector<std::vector<std::uint32_t>>& primary_preferences) {
    std::uint32_t num_elements = secondary_preferences.size();
    std::vector<std::uint32_t> matches(num_elements, -1);
    std::vector<bool> is_free_primary(num_elements, true);
    std::vector<std::uint32_t> proposal_index(num_elements, 0); // Tracks the next secondary to propose for each primary

    while (true) {
        int free_primary_index = -1;

        // Find the next free primary
        for (std::uint32_t i = 0; i < num_elements; i++) {
            if (is_free_primary[i]) {
                free_primary_index = i;
                break;
            }
        }

        // If no free primary is found, break the loop
        if (free_primary_index == -1) break;

        // Get the next secondary to propose
        std::uint32_t secondary_to_propose = primary_preferences[free_primary_index][proposal_index[free_primary_index]];
        proposal_index[free_primary_index]++;

        // Get the current match of the secondary
        std::uint32_t current_match = matches[secondary_to_propose];

        // If the secondary is free, match them
        if (current_match == -1) {
            matches[secondary_to_propose] = free_primary_index;
            is_free_primary[free_primary_index] = false;
        } else {
            // Determine if the current match should be replaced
            auto new_proposer_rank = std::find(secondary_preferences[secondary_to_propose].begin(),
                                                secondary_preferences[secondary_to_propose].end(),
                                                free_primary_index);
            auto current_match_rank = std::find(secondary_preferences[secondary_to_propose].begin(),
                                                 secondary_preferences[secondary_to_propose].end(),
                                                 current_match);