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

Code before:
/**
 * @namespace
 * @brief Greedy Algorithms
 */
namespace greedy_algorithms {
/**
 * @namespace
 * @brief Functions for the Gale Shapley Algorithm
 */
namespace stable_matching {
void gale_shapley(const std::vector<std::vector<int>>& set_2_prefs, const std::vector<std::vector<int>>& set_1_prefs) {
    int n = set_2_prefs.size();
    std::vector<int> engagements(n, -1);
    std::vector<bool> free_set_1_s(n, true);
    std::vector<int> next_proposal(n, 0); // Tracks the next set_2 to propose for each set_1

    while (true) {
        int free_set_1;
        for (free_set_1 = 0; free_set_1 < n; free_set_1++) {
            if (free_set_1_s[free_set_1]) break;
        }
        if (free_set_1 == n) break;

        int set_2_to_propose = set_1_prefs[free_set_1][next_proposal[free_set_1]];
        next_proposal[free_set_1]++;
        int currentFiance = engagements[set_2_to_propose];

        if (currentFiance == -1) {
            engagements[set_2_to_propose] = free_set_1;
            free_set_1_s[free_set_1] = false;
        } else {
            if (std::find(set_2_prefs[set_2_to_propose].begin(), set_2_prefs[set_2_to_propose].end(), free_set_1) <
                std::find(set_2_prefs[set_2_to_propose].begin(), set_2_prefs[set_2_to_propose].end(), currentFiance)) {
                engagements[set_2_to_propose] = free_set_1;
                free_set_1_s[free_set_1] = false;
                free_set_1_s[currentFiance] = true;
            }
        }
    }

    std::cout << "Stable Matches:\n";
    for (int set_2 = 0; set_2 < n; set_2++) {
        std::cout << "set_2's " << set_2 << " is matched to set_1's " << engagements[set_2] << std::endl;
    }
    std::cout << std::endl;
}
}  // namespace stable_matching
}  // namespace greedy_algorithms

/**
 * @brief Self-test implementations

Review comment (suggestion):
```suggestion
    while (free_set_1 != n) {
```
wouldn't this work aswell?
would remove a forever loop with a better condition

Code after:
/**
 * @namespace
 * @brief Greedy Algorithms
 */
namespace greedy_algorithms {
/**
 * @namespace
 * @brief Functions for the Gale-Shapley Algorithm
 */
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 {