/*
Problema 22.  Ordenação de uma lista de nomes.

- Escreva um programa que recebe uma lista de nomes, um nome por
  linha, e que imprime esses nomes em ordem alfabética.  Não imponha
  nenhuma restrição no número de nomes, nem no comprimento de cada
  nome.
*/

#include <stdio.h>
#include <stdlib.h>

char **leia_strings(int *N);
char *leia_linha();

void *mallocc(size_t nbytes);
void *reallocc(void *v, size_t nbytes);
  
void ordene(char *v[] , int N);
int strcompare(char u[], char v[]);

int main()
{
  int N, i;
  char **v = leia_strings(&N);

  ordene(v, N);

  for (i = 0; i < N; i++) 
    printf("%s\n", v[i]);

  free(v);
  return 0;
}

char **leia_strings(int *N)
{
  char **v, *s;
  int t = 4, i = 0;

  v = mallocc(t * sizeof(int *));

  s = leia_linha();
  while (s) {  /* equivalente a s != NULL */ 
    if (i > t - 1) {
      t *= 2;
      v = reallocc(v, t * sizeof(char *));
    }
    v[i++] = s;
    s = leia_linha();    
  }
  
  *N = i;
  return v;
}

char *leia_linha()
{
  char *v, *w, c;
  int t = 4, i = 0, j, z;

  v = mallocc(t * sizeof(char));

  z = scanf("%c", &c);
  while (z > 0 && c != '\n') {
    if (i > t - 2) {
      t *= 2;
      v = reallocc(v, t * sizeof(char));
    }
    v[i++] = c;
    z = scanf("%c", &c);    
  }

  if (z < 1 && i == 0) {
    free(v);
    return NULL;
  }
  
  v[i] = '\0';

  w = mallocc((i + 1) * sizeof(char));
  for (j = 0; j <= i; j++)
    w[j] = v[j];

  free(v);
  return w;
}

void *mallocc(size_t nbytes)
{
  void *ptr;
  ptr = malloc(nbytes);
  if (ptr == NULL) {
    printf ("Socorro! malloc devolveu NULL!\n");
    exit(EXIT_FAILURE); /* EXIT_FAILURE: definido pelo sistema */
  }
  return ptr;
}

void *reallocc(void *v, size_t nbytes)
{
  void *ptr;
  ptr = realloc(v, nbytes);
  if (ptr == NULL) {
    printf ("Socorro! realloc devolveu NULL!\n");
    exit(EXIT_FAILURE); /* EXIT_FAILURE: definido pelo sistema */
  }
  return ptr;
}

/* ordene: ordenacao por insercao */
void ordene(char *v[] , int N)
{
  int i, j;
  for (i = 1; i < N; i++) {
    for (j = i; j > 0 && strcompare(v[j], v[j - 1]) < 0; j--) { 
      char *t = v[j - 1];
      v[j - 1] = v[j];
      v[j] = t;
    } 
  }
}

int strcompare(char u[], char v[])
{
  int i = 0;

  while (u[i] == v[i] && u[i] != '\0')
    i++;

  return u[i] - v[i];
}