#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define MAXSENHAS 430000

struct senha{
	char *palavra;
	int tamanho;
	int frequencia;
};
typedef struct senha Senha;

void LerSenhas(Senha **senhas, char *filepath)
{
	FILE *fp;
	int n = 0, tam, freq;
	char pass[200];

	fp = fopen(filepath, "r");

	while (fscanf(fp, "%d %d %[^\n]", &tam, &freq, pass) == 3)
	{
		senhas[n] = (Senha*)malloc(sizeof(Senha));
		senhas[n]->tamanho = tam;
		senhas[n]->frequencia = freq;
		senhas[n]->palavra = (char*)malloc((tam+1) * sizeof(char));
		pass[tam] = '\0';
		strcpy(senhas[n]->palavra, pass);
		n++;
	}

	fclose(fp);
}

void BubbleSort(Senha **senhas)
{
    int n;
    char *temp;
    bool troca = true;
    int nSenhas = MAXSENHAS;
    while (nSenhas > 0 && troca == true)
    {
        troca = false;
        for (n = 0; n < nSenhas - 1; n++)
        {
            if (strcmp(senhas[n]->palavra, senhas[n+1]->palavra) > 0)
            {
                troca = true;
                temp = senhas[n]->palavra;
                senhas[n]->palavra = senhas[n+1]->palavra;
                senhas[n+1]->palavra = temp;
            }
        }
        nSenhas--;
    }
}

int main(){
    int n;

	Senha** senhas;
	senhas = (Senha**)malloc(MAXSENHAS * sizeof(Senha*));
	LerSenhas(senhas, "senhas.txt");

    clock_t begin = clock();
    BubbleSort(senhas);
    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("%f\n", time_spent);
    printf("%s", senhas[0]->palavra);

	for (n = 0; n < MAXSENHAS ; n++)
		free(senhas[n]);
	free(senhas);

	return 0;
}