/*
** sort.c for Sort in /
**
** Made by Averous Julien-Pierre
** Login   <j.averous@sourcemac.com>
**
** Started on  Sat May 12 12:49:08 2007 Averous Julien-Pierre
** Last update Sat May 12 12:49:21 2007 Averous Julien-Pierre
*/

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

/* Stock a word */
typedef struct
{
  char*		word;
  unsigned int	size;
} s_word;

/* Stock parameters */
typedef struct
{
  char*	fpath_in;
  char*	fpath_out;
  char	sep_in;
  char	way;
  char *kind;
}	s_usage;

/* Prototype of parameter manager */
int usage (int argc, char** argv, s_usage* u);

/* Prototype of quick sort (for size) function */
void quick_sort_size (s_word* tab, int p, int r);

/* Prototype of quick sort partition (for size) function */
int sq_part_size (s_word* tab, int p, int r);

/* Prototype of quick sort (for word) function */
void quick_sort_word (s_word* tab, int p, int r);

/* Prototype of quick sort partition (for word) function */
int sq_part_word (s_word* tab, int p, int r);


/*!
** Main callpoint
**
** @param argc Argument count
** @param argv Argument tab
**
** @return Error code
*/
int main (int argc, char* argv[])
{
  s_word*		list = NULL;
  unsigned int		sz_list = 0;
  s_word		word;
  unsigned int		i;
  s_usage		use;

  FILE*			f_in;
  FILE*			f_out;

  int			c;

  /* Get parameter */
  memset ((void*)&use, 0, sizeof (s_usage));
  if (!usage (argc, argv, &use))
    return 1;

  /* Open/create files */
  if (!(f_in = fopen (use.fpath_in, "r")))
  {
    fprintf (stderr, "Can't open file\n");
    return 2;
  }
  if (!(f_out = fopen (use.fpath_out, "w")))
  {
    fprintf (stderr, "Can't create file\n");
    return 3;
  }

  /* Loading word list */
  while (!feof (f_in))
  {
    word.word = NULL;
    word.size = 0;

    while ((c = fgetc (f_in)) != EOF && c != use.sep_in)
    {
      word.word = realloc (word.word, word.size + 1);
      word.word[word.size] = c;
      word.size++;
    }
    if (!word.word)
      continue;

    list = realloc (list, (sz_list + 1) * sizeof (s_word));
    list[sz_list] = word;
    sz_list++;
  }

  /* Sort */
  if (strcmp (use.kind, "word") == 0)
    quick_sort_word (list, 0, sz_list - 1);
  else if (strcmp (use.kind, "size") == 0)
    quick_sort_size (list, 0, sz_list - 1);

  /* Write output */
  if (use.way == 'a')
  {
    for (i = 0; i < sz_list; i++)
    {
      fwrite(list[i].word, list[i].size, 1, f_out);
      fwrite(&(use.sep_in), 1, 1, f_out);
    }
  }
  else
  {
    for (i = sz_list - 1; i; i--)
    {
      fwrite(list[i].word, list[i].size, 1, f_out);
      fwrite(&(use.sep_in), 1, 1, f_out);
    }
    if (sz_list)
    {
      fwrite(list[0].word, list[0].size, 1, f_out);
      fwrite(&(use.sep_in), 1, 1, f_out);
    }
  }

  /* Close file */
  fclose (f_in);
  fclose (f_out);

  /* No error */
  return 0;
}


int usage (int argc, char** argv, s_usage* u)
{

  if (!u)
    return 0;

  if (argc != 6)
  {
    fprintf (stderr, "usage : %s input-word-file input-word-separator output-word-file sort-way sort-kind\n", argv[0]);
    return 0;
  }

  if (argv[4][0] != 'd' && argv[4][0] != 'a')
  {
    fprintf (stderr, "sort-way should be 'd' (descendent) or 'a' (ascendent)\n");
    return 0;
  }

  if (strcmp (argv[5], "word") != 0 && strcmp (argv[5], "size") != 0)
  {
    fprintf (stderr, "sort-kind should be by 'size' of by 'word'\n");
    return 0;
  }

  u->fpath_in = argv[1];
  u->sep_in = argv[2][0];

  u->fpath_out = argv[3];

  u->way = argv[4][0];

  u->kind = argv[5];

  return 1;
}

/*!
** Do a quick sort (by size) on a word list
**
** @param tab The word list to sort
** @param p The low bound of the tab
** @param r The hight bound of the tab
*/
void quick_sort_size (s_word* tab, int p, int r)
{
  int q;

  if (p < r)
  {
    q = sq_part_size (tab, p, r);
    quick_sort_size (tab, p, q);
    quick_sort_size (tab, q + 1, r);
  }
}

/*!
** Partition a tab for a quick sort (by size)
**
** @param tab The tab to partitionate
** @param p The low bound of tab
** @param r The hight bound of tab
**
** @return Pivot of the two part for the quick sort
*/
int sq_part_size (s_word* tab, int p, int r)
{
  unsigned int	pivot = tab[p].size;
  int		i = p - 1, j = r + 1;
  s_word	temp;

  while (1)
  {
    do
      j--;
    while (tab[j].size > pivot);

    do
      i++;
    while (tab[i].size < pivot);

    if (i < j)
    {
      temp = tab[i];
      tab[i] = tab[j];
      tab[j] = temp;
    }
    else
      return j;
  }
  return j;
}


/*!
** Do a quick sort (by word) on a word list
**
** @param tab The word list to sort
** @param p The low bound of the tab
** @param r The hight bound of the tab
*/
void quick_sort_word (s_word* tab, int p, int r)
{
  int q;

  if (p < r)
  {
    q = sq_part_word (tab, p, r);
    quick_sort_word (tab, p, q);
    quick_sort_word (tab, q + 1, r);
  }
}

/*!
** Partition a tab for a quick sort (by word)
**
** @param tab The tab to partitionate
** @param p The low bound of tab
** @param r The hight bound of tab
**
** @return Pivot of the two part for the quick sort
*/
int sq_part_word (s_word* tab, int p, int r)
{
  int		i = p - 1, j = r + 1;
  s_word	temp;

  while (1)
  {
    do
      j--;
    while (strcmp (tab[j].word, tab[p].word) > 0);

    do
      i++;
    while (strcmp (tab[i].word, tab[p].word) < 0);

    if (i < j)
    {
      temp = tab[i];
      tab[i] = tab[j];
      tab[j] = temp;
    }
    else
      return j;
  }
  return j;
}