knr/qsort.c

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

/** 2022.10.04 this includes exercize 5-15/5-16 working on 5-17 **/

/** 
    errata
       undefined behaviour when you use -n on non numeric data
*/
#define MAXLINES 20000     /* max #lines to be sorted */
//   int readlines(char *lineptr[], int nlines);
//   void writelines(char *lineptr[], int nlines);
#define MAXLEN 1000  /* max length of any input line */
#define ERR_TOOBIG 1 /** too big */
#define ARGUMENT_PROBLEM 2 /** something wrong in commandline arguments given */

int getline1(char *, int);
char *lineptr[MAXLINES];  /* pointers to text lines */

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void swap(void *v[], int, int);
void qsort1(void *v[], int left, int right, int noSort, int caseInsensitive, int directory,
               int (*comp)(void *, void *, int, int));
int numcmp(char *, char *, int, int);
int isAlphaNumeric(char);
//helper function for zero()
void zerome(int*);
//initializes an array of ints
void zero (int*, int);

//helper function to reverse an array v
// why hasn't this got a function prototype? @TODO
void reverse(void *v[], int left, int right)
	{
	   int i, last;
	  if (left >= right)
		return;
  	  swap(v,left,right);
	  reverse(v,left+1,right-1);
	}

void zerome(int* c)
{
  *c = 0;
}


void zero (int* a, int len)
{
  for (int i =0; i<len; i++)  
    zerome( a+i );
  // apparently this doesn't work
  // zerome( a+sizeof(i)*i );
}




   /* sort input lines */
int   main(int argc, char *argv[])
   {
       int strcmp1(char *s, char *t);
       int strcmp2(char *s, char *t, int u, int v);

       int fieldcount = 1; // cardinal. we always start with 1

       // step 1 - figure out how many fields we're talking about here
       for (int i=0; i< argc; i++)
         if ( strcmp1(argv[i], "-l") ==0 ) fieldcount++;

       int help = 0; // only one help will get us help.

       // ok now we've got a number of fields we have to deal with

       // we need their positions, as to skip them
       //sets field[0] as 0
       //turns out we were one too high at fieldcount+1
       int field [fieldcount] ;
       zero(field,fieldcount);
       
       // length of fields, they can be different
       int fieldlen [fieldcount] ;
       zero(fieldlen,fieldcount);

       for (int i=0; i< argc; i++)
         {
           if ( strcmp1(argv[i], "-l") ==0 )
             {
             field[i+1] = i;  //we need this position
             // @TODO needs sanity checking
             if ((i+1) > argc)
               {
                 printf ("-l out of bounds");
                 return ARGUMENT_PROBLEM;
               }          
             fieldlen[i+1]=atoi(argv[i+1]); //is this the right format?

             /*

-l l1 -l l2 -l l3 -l l4 -l l5 

-------|-------------|-|-|-------|
l1       l2          l3l4   l5

*/
             }          
         }

       /* flags*/
       int numeric[fieldcount]; 
       int backwards[fieldcount];
       int caseInsensitive[fieldcount];
       int directory[fieldcount];
       int noSort[fieldcount];
       //initialize
       zero(numeric,fieldcount);
       zero(backwards,fieldcount);
       zero(caseInsensitive,fieldcount) ;
       zero(directory,fieldcount);
       zero(noSort,fieldcount);         

       /** WIP */
       for (int i=0, j=0; i < fieldcount; i++) //we're iterating fields here. we start with 0.
         {
           int nextfield = field[i];  //we go from j to nextfield
          
           for (; j<argc; j++) //we only iterate to the end of either argv OR the field
             //we are iterating on argv so argv[j] is the thing we are using
             {
               if (j==nextfield && nextfield != 0)
                 i++; 
               // printf("*** argc %d %s \n",argc,argv[i]);
               noSort[i]          |= (strcmp1(argv[j], "-x") == 0);
               numeric[i]         |= (strcmp1(argv[j], "-n") == 0);
               caseInsensitive[i] |= (( strcmp1(argv[j], "-f") == 0 ) || ( strcmp1(argv[j], "-df") ==0 ));
               backwards[i]       |= ( strcmp1(argv[j], "-r") ==0 ) ;
               directory[i]       |= (( strcmp1(argv[j], "-d") ==0 ) || ( strcmp1(argv[j], "-df") ==0 ));
               // we don't have to check for -l because we already did that
               
               // only one of these
               help |=  (( strcmp1(argv[j], "-h") ==0 ) || ( strcmp1(argv[j], "--help") ==0 ));
             }
           //           j++; //do we need this??
         }
       
	if (help)
         {
		printf ("./qsort [-l OPTIONS]* \n");
          printf (" OPTIONS: \n");
		printf (" -x : don't actually sort fields \n");
		printf (" -n : sort by number \n");
		printf (" -r : reverse (5-14) \n");
		printf (" -f : fold lower/upper case together (5-15)  \n");
		printf (" -d : sort as if directory structure (5-16)  \n");
		printf (" -fd : -f and -d (5-16)  \n");
		printf (" -l N demarcates the next field by N \n");
		return(0); //bail
         }

     printf("fieldcount %d\n",fieldcount);
     
     //shotgun debugging flags
     for (int i = 0; i < fieldcount; i++)
       {  
         printf ("numeric, %d \ncaseInsensitive %d\nbackwards %d\nnosort %d\ni %d\ndirectory %d\n\n",numeric[i],caseInsensitive[i],backwards[i],noSort[i],i,directory[i]);
       }

     int nlines = -1;        /* number of input lines read */
     
     int first = 0;
     int last = -1;

     if ((nlines = readlines(lineptr, MAXLINES)) >= 0) //read lines
       {
         for (int i =0 ; i < fieldcount; i++) //is fieldcount 0 or 1 here if there's none?
           {
             first = field[i];
             //what happens if someone uses -l 0?
             if (fieldlen[0]==0) //we didn't get a -l
               {
                 last = nlines-1;
               }
             else
               last = first+fieldlen[i];
             if (last == 0)
               last = nlines-1;
                 
             //do the sort
             //something's wrong here on the normal sort
             qsort1( (void**) lineptr, first, last, noSort[i], caseInsensitive[i], directory[i],
                     (int (*)(void*,void*,int,int)) (numeric ? numcmp : strcmp2 ) );

             //this part seems to work
             if(backwards[i])
               reverse((void**)lineptr, first, last);            
           }
         
         //output
         writelines(lineptr, nlines);
         
         return 0;
       } else {
       printf("input %d too big to sort, contact devs with this error message \n",nlines);
       return ERR_TOOBIG;
       }
   }


   /* qsort:  sort v[left]...v[right] into increasing order */
void qsort1(void *v[], int left, int right, int noSort, int caseInsensitive, int directory,
               int (*comp)(void *, void *, int, int))
   {
       if (noSort) return; // do nothing on no sort

       int i, last;
       if (left >= right)    /* do  nothing if array contains */
           return;           /* fewer than two elements */
       swap(v, left, (left + right)/2);
       last = left;
       for (i = left+1; i <= right;  i++)
         if ((*comp)(v[i], v[left], caseInsensitive, directory) < 0)
             swap(v, ++last, i);
       swap(v, left, last);
       qsort1(v, left, last-1,  noSort, caseInsensitive, directory, comp);
       qsort1(v, last+1, right, noSort, caseInsensitive, directory, comp);
   }

/** includes blanks */
int isAlphaNumeric(char a)
{
 return
   (
        ( (a >= 'A') && (a <= 'Z') ) ||
        ( (a >= '0') && (a <= '9') ) ||
        ( (a >= 'a') && (a <= 'z') ) ||
 	(a == ' ')
    );
}

/* strcmp:  return <0 if s<t, 0 if s==t, >0 if s>t */
int strcmp2(char *s, char *t, int caseInsensitive, int dirmode)
   {
       for ( ; *s == *t; s++, t++)
           if (*s == '\0')
               return 0;
       int ci= caseInsensitive;
       char str = *s;
       //if c is lowercase
       char stt = *t;

       // 4 cases
       // shouldn't affect dirmode since both str and stt *are both* alphanumeric here
       if (ci)
         {
	           if  (((str >= 'a') && (str <= 'z'))
	             && ((stt >= 'a') && (stt <= 'z')))  //s and t are both lowercase
	               return *s - *t; //compare as normal

	           if  ((str >= 'a') && (str <= 'z'))
	               return *s - *t -32; // s is but t isn't... drop s down

	           if  ((stt >= 'a') && (stt <= 'z'))
	               return *s - *t +32; // t is but s isn't... drop t up

         }
      if (dirmode)
	//check to make sure we're dealing with
        // assumption: treat all non alphanumeric, non space, non numbers as the same, ie we're not checking them
	// for 5-16
	{

     // what if there's only one?  This isn't specified by the question.
	if (isAlphaNumeric(str) || isAlphaNumeric(stt))
        	return *s - *t;

	// all other characters are equal
	return (char)0;
	}
	return *s - *t; //neither? then it doesn't matter
   }

int strcmp1(char *s, char *t)
{
  int u=1; //case insensitive desirable here?
  int v=0; //dirmode not needed here
  return strcmp2(s,t,u,v);
}

  /* writelines:  write output lines */
   void writelines(char *lineptr[], int nlines)
   {
       while (nlines-- > 0)
           printf("%s\n", *lineptr++);
   }


   /* numcmp:  compare s1 and s2 numerically */
   int numcmp(char *s1, char *s2, int dud, int dud2)
   {
       //dud, dud2 is not used
       double v1, v2;

       v1 = atof(s1);
       v2 = atof(s2);
       if (v1 < v2)
           return -1;
       else if (v1 > v2)
           return 1;
       else
           return 0;
   }




   int getline1(char s[],int lim)
   {
       int c, i;

       for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)
           s[i] = c;
       if (c == '\n') {
           s[i] = c;
           ++i;
       }
       s[i] = '\0';
       return i;
   }


   /* readlines:  read input lines */
   int readlines(char *lineptr[], int maxlines)
   {
       int len, nlines;
       char *p, line[MAXLEN];

       nlines = 0;
       while ((len = getline1(line, MAXLEN)) > 0)
	{
  	   p = malloc(sizeof(char)*len);
           if (nlines >= maxlines || p == NULL)
               return -1;
           else {
               line[len-1] = '\0';  /* delete newline */
               strcpy(p, line);
               lineptr[nlines++] = p;
           }
	}
       return nlines;
   }
   /* swap:  interchange v[i] and v[j] */
   void swap(void *v[],  int i, int j)
   {
       void *temp;

       temp = v[i];
       v[i] = v[j];
       v[j] = temp;
   }