/* llsort.c
 * Sort a non-empty file of lines of ascii characters.
 * The lines of data are stored in a struct named MyNode.
 * Copyright (c) 2000 by Bill McDaniel

#include "csll_.c"  /* uses a circular singly linked list */
#define n 1000      /* n is the maximum length of the lines to be sorted */

FILE *infile, *outfile;
long int sort_column;

/* The following structure has a varying length, depending on the number
 * of characters in the string. It has the 'link' field first, because
 * that is where the routines in csll_.c expect them.
 * The info field is a place holder so that the displacement of the start
 * of the data can be calculated by the compiler.  (Some compilers expect
 * an array to have at least 1 element, so the info field CAN be declared
 * char info[1] ).  When space for the struct is allocated, enough space
 * is allocated to hold the link field, the length field, plus the data.

  struct MyNode
    { SllNode link;
      int length;
      char info[0];
    } MyNode;

/* The comparator routine
   The 2 parameters (a and b) come in as void pointers.  The first thing
   we have to do is to move them into p and q, which are pointers to the
   record type that has the fields we want to compare.  (For this particular
   program, we also adjust them so they will point to the column we want to

int LT_comp(void *a, void *b)
    MyNode *p=a, *q=b;
    (char *) a += sort_column-1;
    (char *) b += sort_column-1;
    if (p->length > sort_column)
      if (q->length > sort_column)
          p = a; q = b; return strcmp(p->info,q->info) < 0;
          q = b; return strcmp(" ",q->info) < 0;
      if (q->length > sort_column)
          q = b; return strcmp(" ",q->info) < 0;
        return 0;

/* the Visit routine */
void my_fprintf(void *p)
    fprintf(outfile,"%s", ((MyNode *)p)->info);

/* This is the main program for testing the code in csll_.c.  It actually
 * performs a useful service: it reads in a text file and sorts the lines
 * alphabetically. Invocation is: llsort infile outfile  [column]
int main (int argc,char **argv)
   MyNode *p;
   void   *list;
   long    int i;
   char    st[n], infn[256], outfn[256];
   char    params[4][14] =
             { "program name","input","output","sort pos" };

/* Pick off the command line arguments and display them.  */
   printf("ll_sort:\nargc = %d\n",argc);
   if (argc < 3) 
      printf("Usage: llsort infile outfile number \n"), exit(1);
   for (i=0; i < argc; i++)
     printf("argv [%ld]  <%12s>: %s\n",i,params[i],argv[i]);

/* pick off the file names */
   strcpy( infn, argv[1]);
   strcpy(outfn, argv[2]);
   printf("i/o files %s %s\n",infn,outfn);

/* pick off the starting sort column (if it exists) */
   sort_column = 1;
   printf("argc %d   argv[3] %s\n",argc,argv[3]);
   if (argc > 3 ) sort_column = atol(argv[3]);
   printf("sort_column %d\n",sort_column);
   if(!sort_column) sort_column=1;

/* open the files */
   infile = fopen(infn,"r");
   if (!infile) printf("File %s could not be found.\n",infn), exit(1);
   outfile = fopen(outfn,"w");

/* initialize the list */

/* read the input file and build the linked list */
   printf("Reading in the file\n");
   while (fgets(st,n,infile))      /* get 1 line */
       /* fetch a node that is just the right size */
       p = Fetch_A_Node(sizeof(MyNode)+strlen(st)+2);

       /* save the length of the string */
       p->length = strlen(st);

       /* copy the string into the info portion of the node */

       /* insert the node onto the tail end of the list */

/* sort the list using the comparator LT_comp */
   printf("Sorting: %s by column %d\n",infn, sort_column);
   printf("%c",7); /* beep */
   Sort(&list, LT_comp);

/* send the sorted records to the 'output' file */
   printf("Writing the new file \n");
   Traverse(list, my_fprintf);

   return 0;