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

Code before:
/**
 * @file
 * @brief Stable Marriage Problem implementation
 * @details
 * This implementation utilizes the Gale-Shapley algorithm to find stable matches
 * between men and women based on their preferences.
 *
 * **Stable Marriage Problem** aims to find a stable matching between two equally sized 
 * sets of elements given an ordinal preference for each element. The algorithm was
 * introduced by David Gale and Lloyd Shapley in 1962.
 *
 * @author [B Karthik](https://github.com/BKarthik7)
 */

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

void stableMatch(const vector<vector<int>>& women_prefs, const vector<vector<int>>& men_prefs, int n) {
    vector<int> engagements(n, -1);
    vector<bool> free_men(n, true);
    vector<int> next_proposal(n, 0); // Tracks the next woman to propose for each man

    while (true) {
        int freeMan;
        for (freeMan = 0; freeMan < n; freeMan++) {
            if (free_men[freeMan]) break;
        }
        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;
            }
        }

Review comment (suggestion):
```suggestion
namespace greedy_algorithms {
```
this algorithm should be inside the greedy algorithms namespace

Code after:
/**
 * @file
 * @brief [Gale Shapley Algorithm](https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm)
 * @details
 * This implementation utilizes the Gale-Shapley algorithm to find stable matches.
 *
 * **Gale Shapley Algorithm** aims to find a stable matching between two equally sized 
 * sets of elements given an ordinal preference for each element. The algorithm was
 * introduced by David Gale and Lloyd Shapley in 1962.
 * 
 * Reference: 
 * [Wikipedia](https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm)
 * [Wikipedia](https://en.wikipedia.org/wiki/Stable_matching_problem)
 *
 * @author [B Karthik](https://github.com/BKarthik7)
 */

#include <iostream>   /// for std::u32int_t
#include <vector>     /// for std::vector
#include <algorithm>  /// for std::find
#include <cassert>    /// for assert

/**
 * @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