tidemanfinal

#include <cs50.h>
#include <stdio.h>
#include <string.h>

#define MAX 9  // max number of candidates that can be in the election. 9

int preferences[MAX][MAX];  // preferences[i][j] is a 2d array to represent the number of voters who prefer candiate[i] over candidate[j], using an adjacency matrix

bool locked[MAX][MAX];  // 2d boolean array, used to keep track of the candidate graph. if locked[i][j] == TRUE, we've locked in the edge pointing from candidate "i" to candidate "j"

typedef struct  // struct used to declare each pair, which has a winner & loser
{
    int winner;
    int loser;
}
pair;

string candidates[MAX];  // array of strings, for the candidates names, candidate[0] is the 1st candidate. candidate[1] is the 2nd candidate etc...
pair pairs[MAX * (MAX - 1) / 2];  // array of the MAX amount of candidates * (MAX amount of candidates - argc) / 2, so we can fit all of the pair structs in each index of pairs[]

int pair_count;  // global variables: pair_count & candidate_count, representing the number of "pairs" & number of "candidates" in the arrays: pairs[] & candidates[]
int candidate_count;

bool vote(int rank, string name, int ranks[]);  // function prototypes
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);
bool check_cycle(int winner, int loser);

int main(int argc, string argv[])
{
    if (argc < 2)  // check for invalid usage
    {
        printf("Usage: tideman [candidate ...]\n");
        return 1;
    }

    candidate_count = argc - 1;  // populate array of candidates
    if (candidate_count > MAX)
    {
        printf("Maximum number of candidates is %i\n", MAX);
        return 2;
    }

    for (int i = 0; i < candidate_count; i++) // loop through & populate the candidates[] array
    {
        candidates[i] = argv[i + 1]; // take user input for their "candidate" in argv (+1 to exclude ".\tideman") + store it in the candidate[] array
    }

    for (int i = 0; i < candidate_count; i++)  // outer nested forloop, to go through 1 row (i) of locked[][] at a time
    {
        for (int j = 0; j < candidate_count; j++)  // inner nested loop, to go through every column (j) of locked[][] before the outer loop executes again, to check the next row
        {
            locked[i][j] = false;  // set the current element at locked[i][j] to FASLE
        }
    }

    pair_count = 0;  // set pairs_count at the start of main() to equal 0.
    int voter_count = get_int("Number of voters: ");
    printf("\n");

    for (int i = 0; i < voter_count; i++)  // outer nested forloop, to go through every voter declared
    {
        int ranks[candidate_count];  // creates a seperate array of ranks[] for the voter at "i", with as many elements equal to "candidate_count". ranks[i] is this voter's ith preference

        for (int j = 0; j < candidate_count; j++)  // inner loop to query for the current voters prefered candidates, until this matches the candidate_count. it will then store these in this voters ranks[] preferences
        {
            string name = get_string("Candiate prefered rank %i: ", j + 1);  // record the candidate rank for the current "voter" at "j" (+1 to make it count from voter 1 insteaf of voter 0).
            if (!vote(j, name, ranks))  // the current value of "j" here represents the current voter being checked, the candidate "name" they picked & the current "ranks[]" 1d array for this voter. This is passed into vote()
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }
        printf("Current ranks array %d %d %d:", ranks[0], ranks[1], ranks[2]);
        printf("\n");
        record_preferences(ranks);

    }
    printf("\n");
    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}


bool vote(int rank, string name, int ranks[])  // update ranks given a new vote. this function takes in the arguments "rank", "name", and "ranks[]"" as mentioned on line 79
{
    for (int i = 0; i < candidate_count; i++)  // loop through against every potential candidate in the election
    {
        if (strcmp(candidates[i], name) == 0)  // check if the user's inputted "name" inpuuted on line 78 matches the current candidate in the candidates[] array looped through above. if TRUE (== 0)
        {
            ranks[rank] = i; // here "i" represents the index of current candidate in the candidates[] array. we update the ranks[] array with the ith candidate index, indicating this voter's current candidate preference to record.
            return true;  // function will return TRUE after grabbing this ith candidate + storing it in the correct index of the ranks[] array (first candidate voter picked into ranks[0], second into ranks[1] etc)
        }
    }
    return false;  // return FALSE if the above is not met, so this vote() function is looped through again in main()
}
void record_preferences(int ranks[])  // record each voter's preferences[][] by referencing their previous ranks[]
{
    printf("\n");
    for (int i = 0; i < candidate_count; i++)   // outer forloop to increment "i" (for the row candidate) from 0, representing the current index of the candidate rank[] we want to reference in the 2d preferences[HERE][] array accurately
    {
        for (int j = 0; j < candidate_count; j++)  // inner forloop to increment a j counting variable (for the column candidate) from 0 to represent the current index of the candidate rank[] we want to reference in the 2d preferences[][HERE] array accurately
        {
            if (i < j)
            {
                preferences[ranks[i]][ranks[j]]++; // add 1 tally mark to prefrences[i][j] in accordance to the current value of the counting variables i and j in the nested forloops, in context to the candidates in the 1d ranks[] array
            }
        }
    }
}

void add_pairs(void)  // Record pairs of candidates where one is preferred over the other
{
    for (int i = 0; i < candidate_count; i++) // outer forloop to increment a i counting variable (for the row candidate) from 0 to represent the current index of the candidate in the rows of preferences[HERE][]
    {
        for (int j = 0; j < candidate_count; j++)  // inner forloop to increment a j counting variable (for the column candidate) from 0 to represent the current index of the candidate in the columns of preferences[][HERE]
        {
            if (preferences[i][j] > preferences[j][i])  // if whatever is in preferences[i][j] has a greater value than in preferences[j][i] (that the candidate in preferences[i](Row) has more tally marks than the candidate in preference [j](Column)
            {
                pairs[pair_count].winner = i;  // update the [current index] of the pairs[] array and set the value taken from preferences[i] (column) to be the winner
                pairs[pair_count].loser = j;  // update the [current index] of the pairs[] array and set the value taken from preferences[j] (row) to be the loser
                pair_count++; // update 1 count to the paircount to tally the total number of pairs counted in this program
            }
        }
    }
    return;
}

void sort_pairs(void)
{
  while (1)  // this while loop is set to "true (1)" and it'll run forever until an exit condition is met
  {
      int swapped = 0;  // counting variable to indicate if a swap has been currently performed going through the bubble sort or not. This is set to 0 at the start of this while loop every time.
      pair temp;  // declaring a temp variable to store variables we want to swap in

      for (int i = 0; i < pair_count -1; i++)  // Loop through entire array of pairs[]. In a bubble sort , we need to -1 off of the pair_count being checked against. Because there's nothing to compare the last element to.
      {
          // check if the margin difference between the candidate.winner - the candidate.loser in [i] is < the margin difference between the candidate.winner - the candidate.loser in [i + 1]
          if (preferences[pairs[i].winner][pairs[i].loser] - preferences[pairs[i].loser][pairs[i].winner] < preferences[pairs[i + 1].winner][pairs[i + 1].loser] - preferences[pairs[i].loser][pairs[i].winner])
          {
              temp = pairs[i];  // take the data in pairs[i] and move it inside of temp
              pairs[i] = pairs[i + 1];  // take the data in pairs[i + 1] and move it to pairs[i]
              pairs[i + 1] = temp;  // take the data we stores in temp and move it into [i +1] to complete the swap.
              swapped = 1;  // update swapped to == 1 to indicate the full swap has been coomplete
          }
      }

      if (swapped == 0) // check if swapped equals "false"
      {
          break;  // if it does, break the loop
      }
  }
}

void lock_pairs(void)  // lock pairs into the candidate graph in order, without creating cycles
{
    for (int i = 0; i < pair_count; i++)  // forloop through pairs[], to get the pairs with the highest strengh of victory (starting with pairs[0])
    {
        if (!check_cycle(pairs[i].winner, pairs[i].loser))  // if check_cycle returns FALSE (no cycle will be created using check_cycles()) for the current .winner @ pairs[i] and .loser @ pairs[i]
        {
            locked[pairs[i].winner][pairs[i].loser] = true;  // set locked(for this)[.winner][.loser] at pairs[i] to TRUE, drawing a line;
        }
        printf("Locked[i][j] %s \n", locked[pairs[i].winner][pairs[i].loser] ? "true" : "false");
    }
    return;
}

bool check_cycle(int start, int end)  // "int start" is "pairs[i].winner" & "int end" is the "pairs[i].loser"
{
    if (locked[end][start] == true) // base case, if a path already exists between the ending node and starting node
    {
        return true; // return "true", indacating a edge exists between this starting node (candidate) and ending node (candidate)
    }
    // recursive case, that will track if an edge exists between any two nodes, & plot new startinh nodes, to see if a backedge exists between any 2 nodes in the graph
    for (int i = 0; i < candidate_count; i++)   // loop through all possible candidates[] in the graph
    {
        if ((locked[i][start]) == true) // if a path already exists between the ending node at [i] and the orignal starting node
        {
            if (check_cycle(i, end) == true)  // pass in the ending node at [i] as the new starting node + check if a path already exists between it & the original ending node
            {
                return true;
            }
        }
    }
    return false; // else return FALSE if no edges can be found betweeb the two nodes
 }

void print_winner(void) // print the winner of the election
{
    bool winner;

    for (int i = 0; i < candidate_count; i++)  // nested outer loop, through all rows in locked[i][], checking for candidate [i]
    {
        winner = true; // set winner to TRUE on each passthrough of this loop

        for (int j = 0; j < candidate_count; j++) // nested inner loop, through all of the columns in locked[][] for candidate [j] with this inner nested loop
        {
            if (locked[j][i] == true) // if at anyt point when looping through the columns of candidates in [j], if we find any candidate at j with an arrow pointing ot them from a candidate at [i]
            {
                winner = false; // assign the value of "false" to winner on this passthrough of this loop
            }
        }
        // if after looping through the entire locked[][] 2d array column by column, every index in locked [j][i] was set to "false"
        // determining candidate[j] has NO other candidates with an arrow pointing torwards them, winner is set to true
        if (winner == true)
        {
            printf("%s\n", candidates[i]);
        }
    }
    return;
}