/* Program CzechSoRt by Petr Olsak,   November 20, 1994, version 1.0 */
/* some corrections thanks Otakar Smrz: August 24, 1999, version 1.1 */

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

#define MAXLINE 1000
#define MAXITEMS 10

#define ch 1
#define Ch 2
#define cH 3
#define CH 4

#define UI int)(unsigned char

typedef struct LINES {
  char *line ;
  int len;
  struct LINES *next ;
} LINES ;

LINES *firstline, *startline, *curr;
long int numlines;


int ind[MAXITEMS], inr[MAXITEMS], maxpole, maxindex, gi1, gi2;

char commchar;


FILE *input, *output, *sorttab;

char sc, scret;
#define FGETC(INPUT) \
 (feof(INPUT)||i>=MAXLINE ? '\n' : (scret=sc, sc=fgetc(INPUT), scret))

char cline[MAXLINE];

int pass1[256], pass2[256], pass3[256], pass4[256];

void *myalloc (size)
  int size;
{
  void *p;
  p = malloc (size);
  if (p == NULL)
  {
    printf ("no memory, malloc failed\n");
    exit (1) ;
  }
  return p;
}


int readline ()
{
  register int i=0;

  while ((cline[i]=FGETC(input)) != '\n') i++;

  if (i==MAXLINE)
  {
    printf ("csr: max. line length is %d, sorry\n", MAXLINE);
    exit (1);
  }
  cline[i] = 0;
  return i+1;
}


void readparam ()
{
  int i=5, j, k=0;  char c;

  while (1)
  {
    j = i;
    while (cline[j] == ' ' || cline[j] == '\t') j++;
    while (isdigit (cline[j])) j++;
    c = cline[j];
    cline[j] = 0;
    ind[k] = atoi (&cline[i])-1 ;
    i = j+1;
    if (c == '-')
    {
      j = i;
      while (cline[j] == ' ' || cline[j] == '\t') j++;
      if (cline[j] == '$')
      {
	inr[k] = MAXLINE+1 ;
	c = cline[++j];
      }
      else
      {
	while (isdigit (cline[j])) j++;
	c = cline[j];
	cline[j] = 0;
	inr[k] = atoi (&cline[i])-1 ;
      }
    }
    else inr[k] = MAXLINE ;
    k++ ;
    if (k >= MAXITEMS)
    {
      printf ("csr: number of params must be <= %d", MAXITEMS);
      exit (1);
    }
    if (c != ',') { maxpole = k; return; }
    i = j+1;
  }
}



void inputlines ()
{
  int state=0, leng, i;

  firstline = NULL;
  numlines = 1;

  sc = fgetc (input);
  while (!feof(input))
  {
    if (firstline == NULL) firstline = curr = myalloc (sizeof (LINES)) ;
    else  curr = curr->next = myalloc (sizeof (LINES)) ;
    curr->next = NULL;
    curr->line = myalloc (leng = readline ());
    strcpy (curr->line, cline);
    curr->len = leng-1;
    switch (state)
    {
      case 0: if (cline[0] != commchar && cline[0] != 0)
		startline = curr, state = 1 ;
	      if (cline[0] == commchar && cline[1] == 'c' &&
	      cline[2] == 's' && cline[3] == 'r' && maxpole == 0)
		readparam ();
	      break ;
      case 1: if (cline[0] == commchar) state = 2 ;
	      else numlines++ ;
      case 2: if (cline[0] == commchar && cline[1] == 'c' &&
	      cline[2] == 's' && cline[3] == 'r' && maxpole == 0)
		readparam ();
    }
  }
  fclose (input);
  if (state == 0)
  {
    printf ("csr: nothing to do");
    exit (1);
  }
  if (maxpole == 0) maxpole = 1, ind[0] = 0, inr[0] = MAXLINE+1 ;
  printf ("  params: ");
  for (i=0; i < maxpole; i++)
  {
    if (inr[i] == MAXLINE) printf ("%d", ind[i]+1) ;
    else if (inr[i] == MAXLINE+1) printf ("%d-$", ind[i]+1) ;
	 else                     printf ("%d-%d", ind[i]+1, inr[i]+1) ;
    if (i < maxpole-1) printf (", ") ;
  }
  printf ("\n");
  return;
}


void outputlines ()
{
  curr = firstline;

  while (curr != NULL)
  {
    fprintf (output, "%s\n", curr->line);
    curr = curr->next;
  }
  fclose (output);
  return;
}




void scantable ()
{
  int i, j, k, state;  char c, c1, c2;

  for (i=0; i<256; i++)  pass1[i] = pass2[i] = pass3[i] = pass4[i] = -1;

  i = j = k = 1;

  commchar = fgetc (sorttab);
  while (fgetc (sorttab) != '\n' && !feof (sorttab)) ;

  if (feof (sorttab))
  {
    printf ("csr: no lines in sorttab\n") ;
    exit (1);
  }

  state=1;
  while (!feof (sorttab))
  {
    c = fgetc (sorttab);
    new:
    if (state == 1 && c == ' ') state = 2;
    if (state == 1) state = 0;
    if (c == ' ')   { j=i;             continue; }
    if (c == '\n')  { j=k=i; state =1; continue; }
    if (c == '<')
    {
      c1 = fgetc (sorttab);
      if (c1 != 'c' && c1 != 'C')
      {
	if (state==0) pass1[(UI)'<']=k, pass2[(UI)'<']=j, pass3[(UI)'<']=i;
	pass4[(UI)'<'] = i;
	i++; c = c1 ;
	goto new ;
      }
      c2 = fgetc (sorttab); c = fgetc (sorttab);
      if ((c1 != 'c' && c1 != 'C') || (c2 != 'h' && c2 != 'H') || c != '>')
      {
	printf ("error in sort.tab (composite CH?)");
	exit (1);
      }
      if (c1 == 'c')
      {
	if (c2 == 'h')  c = ch ;
	else            c = cH ;
      }
      else
      {
	if (c2 == 'h')  c = Ch ;
	else            c = CH ;
      }
    }
    if (state == 0) pass1[(UI)c] = k, pass2[(UI)c] = j ,pass3[(UI)c] = i;
    pass4[(UI)c] = i;
    i++;
  }
  fclose (sorttab);
  pass1[(UI)' ']  = 0;  pass1[(UI)'\t'] = 0;  pass1[0] = 0;
  pass2[(UI)' ']  = 0;  pass2[(UI)'\t'] = 0;  pass2[0] = 0;
  pass3[(UI)' ']  =-1;  pass3[(UI)'\t'] =-1;  pass3[0] = 0;
  pass4[(UI)' ']  =-1;  pass4[(UI)'\t'] =-1;  pass4[0] = 0;
  return;
}


int testw (w1, w2, l1, l2, pass)
  char *w1, *w2;
  int l1, l2, *pass;
{
  register int i1=0, i2=0;
  int c1, c2;

  while (1)
  {
     while (pass[(UI)w1[i1]] == -1) i1++;
     if (i1 >= l1) c1 = 0;
     else
     {
       if (w1[i1] == 'c' && i1 < l1-1)
       {
	 if (w1[i1+1] == 'h') if ((c1 = pass[ch]) != -1) { i1++;  goto ok1;}
	 if (w1[i1+1] == 'H') if ((c1 = pass[cH]) != -1) { i1++;  goto ok1;}
       }
       if (w1[i1] == 'C' && i1 < l1-1)
       {
	 if (w1[i1+1] == 'h') if ((c1 = pass[Ch]) != -1) { i1++;  goto ok1;}
	 if (w1[i1+1] == 'H') if ((c1 = pass[CH]) != -1) { i1++;  goto ok1;}
       }
       c1 = pass[(UI)w1[i1++]] ;
     }

     ok1: ;
     while (pass[(UI)w2[i2]] == -1) i2++;
     if (i2 >= l2) c2 = 0;
     else
     {
	if (w2[i2] == 'c' && i2 < l2-1)
       {
	 if (w2[i2+1] == 'h') if ((c2 = pass[ch]) != -1) { i2++;  goto ok2;}
	 if (w2[i2+1] == 'H') if ((c2 = pass[cH]) != -1) { i2++;  goto ok2;}
       }
       if (w2[i2] == 'C' && i2 < l2-1)
       {
	 if (w2[i2+1] == 'h') if ((c2 = pass[Ch]) != -1) { i2++;  goto ok2;}
	 if (w2[i2+1] == 'H') if ((c2 = pass[CH]) != -1) { i2++;  goto ok2;}
       }
       c2 = pass[(UI)w2[i2++]] ;
     }

     ok2: ;
     if (c1!=c2) return c2-c1;   /* je-li w1 < w2, je vystup kladny */

     if (c1 == 0) { gi1 = i1;  gi2 = i2; return 0; }
  }
}


int test (s1, s2, len1, len2)
  char *s1, *s2;
  int len1, len2;
{
  int pole, i1, i2, l1, l2, v;

  pole = 0;

  while (pole < maxpole)
  {
    i1 = i2 = ind[pole];

    if (i1 >= len1) i1 = len1 ;
    if (i2 >= len2) i2 = len2 ;

    while (1)
    {
      while (s1[i1] == ' ' || s1[i1] == '\t') i1++;
      while (s2[i2] == ' ' || s2[i2] == '\t') i2++;

      if (s1[i1] == 0 && s2[i2] == 0) break ;

      l1 = inr[pole] - i1 + 1 ;
      l2 = inr[pole] - i2 + 1 ;

      if ((v = testw (&s1[i1], &s2[i2], l1, l2, pass1)) != 0) return v;
      if ((v = testw (&s1[i1], &s2[i2], l1, l2, pass2)) != 0) return v;

      i1 += gi1 ; i2 += gi2 ;
      if (inr[pole] == MAXLINE) break ;

      if (i1 >= len1) i1 = len1 ;
      if (i2 >= len2) i2 = len2 ;
      if (i1 > inr[pole]) i1 = len1 ;
      if (i2 > inr[pole]) i2 = len2 ;
    }
    if (inr[pole] == MAXLINE) {
      l1 = i1 - ind[pole];
      l2 = i2 - ind[pole];
      i1 = i2 = ind[pole];
    }
    else {
      i1 = i2 = ind[pole];
      if (i1 >= len1) i1 = len1 ;
      if (i2 >= len2) i2 = len2 ;
      l1 = inr[pole] - i1 + 1 ;
      l2 = inr[pole] - i2 + 1 ;
    }
    if ((v = testw (&s1[i1], &s2[i2], l1, l2, pass3)) != 0) return v;
    if ((v = testw (&s1[i1], &s2[i2], l1, l2, pass4)) != 0) return v;

    pole++;
  }
  return 0;
}



void sort ()
{
  int j;
  long int numsort, i;
  char *lin;

  numsort = numlines;

  while (numsort>1)
  {
    curr = startline;

    for (i=1; i<numsort; i++)
    {
      if (test (curr->line,curr->next->line,curr->len,curr->next->len) < 0)
      {
	lin = curr->line;
	curr->line = curr->next->line;
	curr->next->line = lin;
	j = curr->len;  curr->len = curr->next->len;  curr->next->len = j;
      }
      curr = curr->next;
    }
    printf ("%d ", numsort);
    numsort--;
  }
  return;
}



int main (argc, argv)
  int argc;
  char *argv[];
{
  printf ("program CzechSoRt (csr), (c) Petr Olsak, 1994, 1999\n");
  if (argc != 4)
    return printf ("usage: csr input sort.tab output\n"), 2;
  input = fopen (argv[1], "r");
  if (input == NULL)
    return printf ("csr: not able to open input %s\n", argv[1]), 1;
  sorttab = fopen (argv[2], "r");
  if (sorttab == NULL)
    return printf ("csr: not able to open table %s\n", argv[2]), 1;

  printf ("  sorting table: %s\n", argv[2]);
  scantable ();
  printf ("  scanning input %s ...\n", argv[1]);
  inputlines ();
  printf ("  sorting ...");
  sort ();

  output = fopen (argv[3], "wt");
  if (output == NULL)
    return printf ("\ncsr: not able to open output %s\n", argv[3]), 1;
  printf ("\n  making output %s ...\n", argv[3]);
  outputlines ();
  return 0;
}