/* Problem 7--Skew
   Computing the skew of a binary tree is easily handled with recursion.
   However, since there is no specified limit to the number of strings
   being read in or to the length of the strings, this is a little
   tricky to accomplish in C, though in C++ or Java it wouldn't be as
   bad.  (I have committed myself to doing the problems in C.)
   Anyway, since the list is in preorder form, the root is first, so
   all the strings preceding the root constitute the left subtree, and
   all the strings following the root constitute the right subtree. */

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

typedef struct StrList {

 char *str;
 struct StrList *next;
} StrList;

typedef struct CList {

 char c;
 struct CList *next;
} CList;

int main (int argc, char **argv);
char *ReadStr (FILE *in);
int SkewCt (char **words, int ct);
char **ReadLines (FILE *in, int *ct);

int main (int argc, char **argv) {

  FILE *in, *out;
  int ct,cs,i;
  char **words;

 in = fopen ("prob7.in","r");
 out = fopen ("prob7.out","w");
 cs = 0;  /* Read in linked list of strings */
 while (NULL != (words = ReadLines (in,&ct))) {
  fprintf (out,"Case %d: The skew factor is %d\n",++cs,
           SkewCt (words,ct));
  for (i=0; i < ct; i++) free (words[i]);
  free (words);
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* This reads in a string of unspecified length from in. */
char *ReadStr (FILE *in) {

  int ct, c;
  char *str;
  CList *CL, *T;

 CL = NULL; /* Read in characters into a linked list until EOLN is */
 ct = 0;    /* reached. */
 while ((c = fgetc (in)) != '\n') {
  T = (CList *) malloc (sizeof (CList));
  T->c = c;
  T->next = CL;
  CL = T;
  ct++;
 }
 str = (char *) malloc (ct+1); /* Put characters into a string. */
 str[ct--] = 0;
 for (; ct >= 0; ct--) {
  str[ct] = CL->c;
  T = CL->next;
  free (CL);
  CL = T;
 }
 return str;
}

/* This reads in a list of strings one at a time, stopping when a blank
   line is reached. */

char **ReadLines (FILE *in, int *ct) {

  char *str;
  char **list;
  StrList *CL, *T;
  int i;

 CL = NULL; /* Put strings into a linked list. */
 *ct = 0;
 while ((str = ReadStr (in))[0] != 0) {
  T = (StrList *) malloc (sizeof (StrList));
  T->str = str;
  T->next = CL;
  CL = T;
  (*ct)++;
 }
 free (str); /* Put strings into an array, if there are more than 0 */
 if (*ct==0) return NULL;
 list = (char **) malloc (*ct*sizeof (char *));
 for (i=*ct-1; i >= 0; i--) {
  list[i] = CL->str;
  T = CL->next;
  free (CL);
  CL = T;
 }
 return list;
}

/* This is the recursive method that computes the skew of an array
   of ct words */
int SkewCt (char **words, int ct) {

  int i, left, right;

 if (ct==0) return 0; /* Base Case */
 for (i=1; i < ct; i++) /* Figure out the left and right subtrees */
  if (strcmp (words[0],words[i]) < 0) break;
 left = i-1; right = ct-i;
 return (left==right ? 0 : abs (left-right)-1) +
        SkewCt (&words[1],left) + SkewCt (&words[i],right);
}