#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <ctype.h>
#include <string.h>


// GET MAX ---------------------------
int get_max(char **tab, int n)
{
  int max = 0;
  int k;

  for (int i = 1; i <= n; i++)
    if (strlen(tab[i]) > max)
    {
      max = strlen(tab[i]);
      k = i;
    }
  return max;
}
//++++++++++++++++++++++++++++++++++++++++++++++++

//GET SIZE ---------------------------
int get_size()
{
  FILE *file = fopen("pop.txt","r");
  char c = 0;
  int ilosc = 0;
  for (c = getc(file); c != EOF; c = getc(file))
  {
    if (c == '\n')
    {
      ilosc++;
    }
  }
    fclose(file);
    return ilosc;
}
//++++++++++++++++++++++++++++++++++++++++++++++++

// COUNTING SORT ------------------------------------------
void counting_sort(char **Tab1, char **Tab2, int n, int k)
{
  int ASCII = 127;
  int Tab_pom[1000]; //Tablica pomocnicza do zliczania

  // Zerowanie tablicy
  for(int i = 0; i <= ASCII; i++)
  {
      Tab_pom[i] = 0;
  }

  for(int i = 1; i <= n; i++)
  {
    Tab_pom[Tab1[i][k]] = Tab_pom[Tab1[i][k]] + 1;
  }

  for(int i = 1; i <= ASCII; i++)
  {
      Tab_pom[i] = Tab_pom[i] + Tab_pom[i-1];
  }

  //Sortowanie
  for(int i = n; i >= 1;i--)
  {
      Tab2[Tab_pom[Tab1[i][k]]] = Tab1[i];
      Tab_pom[Tab1[i][k]] = Tab_pom[Tab1[i][k]]-1;
  }
}
// ++++++++++++++++++++++++++++++++++++++++++++++++

//RADIX SORT ---------------------------
void RADIX_SORT(char **Tab1, char **Tab2,char **Tab3, int n,int max)
{
  for(int i = max; i >= 0; i--)
  {
    counting_sort(Tab1,Tab2,n,i);
    Tab3 = Tab1;
    Tab1 = Tab2;
    Tab2 = Tab3;
  }
}
//++++++++++++++++++++++++++++++++++++++++++++++++




//==============================================================
// MAIN --------------------------------------------------------

int main()
{

int a = get_size();

char **A = (char**) malloc(a*sizeof(char*));
char **B = (char**) malloc(a*sizeof(char*));
char **pom = (char**) malloc(a*sizeof(char*));



// ODCZYT PLIKU ----------------------------

FILE *file=fopen("pop.txt","r");
char slowo[100];
char c[1024];
int o=1;
int ilosc=0;
bool digit;

  while(fscanf(file,"%s",c)==true)
  {
    digit=false;
    ilosc=strlen(c);
    for(int i=0;i<ilosc;i++)
    {
      if(c[i]>=48&&c[i]<=57) // od 0 do 9
      {
        digit=true;
      }
    }
      if(!digit)
      {
        A[o]=(char*) malloc(sizeof(char)*100);
        strcpy(A[o],c);
        o++;
      }
  }
fclose(file);

//++++++++++++++++++++++++++++++++++++++++++++++++

int max = get_max(A,a); // Znajdujemy najdluzszy napis
RADIX_SORT(A,B,pom,a,max); //RADIX SORT

//++++++++++++++++++++++++++++++++++++++++++++++++

// POSORTOWANE - ZAPIS DO PLIKU -----------------------

FILE *f=fopen("pop_sorted.txt","w");
    for(int i=1;i<=a;i++)
    {
        fprintf(f,"%s\n",A[i]);
    }
fclose(f);

//++++++++++++++++++++++++++++++++++++++++++++++++

    return 0;
}