/* windex.c
** Author: Ronald L. Rivest
** Helpful modifications from Carl Manning, Ron Greenberg.
** Documentation: see windex.doc
** Version: 1/26/90
** Basic functionality:
**       (1) input the file windex.tex into your tex source
**       (2) put index entries into your Tex document (e.g. foo.tex)
**           These are written out into file foo.idx by Tex.
**       (3) Run `windex foo' to compile index.  
**           Output is now in file foo.index
**       (4) Include in foo.tex the line
**                \makeatletter\@input{book.index}\makeatother
**           where you want the index to go.
*/

#include <stdio.h>
#include <malloc.h>
#include <ctype.h>
#include <strings.h>

/* Miscellaneous constants */
#define TRUE      1
#define FALSE     0
#define DEBUG     0
#define CR        '\r'
#define LF        '\n'
#define EOS       0       /* end of string */

/* WINDEX constants */
/* String constants */
#define WINDEX_BANNER     "WINDEX index-creation program. Version 1/26/90.\n"
#define INPUT_EXTENSION   ".idx"
#define OUTPUT_EXTENSION  ".index"
#define MAX_STRING_LENGTH 300
#define DEFAULT_FORMAT    "0" /* just print the page number */
char NULL_FORMAT[] =      ""; /* null format string */
#define NULL_SORT_CHARS   "-" /* nonblank characters to ignore when sorting  */
#define UNKNOWN           -1

/* Character constants: changing these constants changes syntax of windex */
#define SLASH     '/'     /* separates levels in sort key */
#define LANGLE    '<'     /* marks entry to start range */
#define RANGLE    '>'     /* marks entry to end range */
#define LBRACE    '{'     /* marks start of print value */
#define RBRACE    '}'     /* marks end of print value */
#define LBRACKET  '['     /* marks start of format string */
#define RBRACKET  ']'     /* marks end of format string */
#define ZERO      '0'     /* marks position of page or range in format */
#define COLON     ':'     /* marks beginning of page number */
#define BLANK     ' '     /* whitespace to ignore at beginning */
/* Windex policy switches */
#define MAKE_RANGES       TRUE    /* create ranges for adjacent page entries */
#define IGNORE_SMALL_WORDS TRUE   /* ignore initial small words in subitems */
				  /* when sorting them into order */

/* TEX constants */
#define TEX_BEGIN_GROUP    '{'
#define TEX_END_GROUP      '}'
#define TEX_EMPTY_GROUP    "{}"
#define TEX_BEGIN_INDEX    "\\begin{theindex}\n"
#define TEX_END_INDEX      "\n\n\\end{theindex}\n"
#define TEX_MAX_LEVEL      2
#define TEX_BEGIN_LEVEL0   "\n\\item "
#define TEX_BEGIN_LEVEL1   "\n   \\subitem "
#define TEX_BEGIN_LEVEL2   "\n      \\subsubitem "
#define TEX_AFTER_ENTRY    ", "  /* string to print after print value */
#define TEX_BETWEEN_PAGES  ", "  /* string to print between page entries */
#define TEX_BETWEEN_RANGE  "--"
/* end of TEX constants */

FILE *instream;                /* lines as produced by \index commands */
FILE *outstream;               /* actual latex commands to make index */

typedef                        /* for a page or a range of pages */
struct pageref {
  int  level;                  /* 0...TEX_MAX_LEVEL */
  char *sortkey[TEX_MAX_LEVEL+1];  /* values to sort/compare keys by */
  char *pv;                    /* print value or else NULL */
  char *format;                /* format or replacement for page reference */
  int  firstpageno;            /* first page number in range or UNKNOWN */
  int  lastpageno;             /* last page number in range or UNKNOWN */
  struct pageref *next;        /* link to next page reference */
} entry;

entry elist;
entry *elast;

/* mymalloc(n)
** allocate n bytes but check for out of memory condition 
*/
char *mymalloc(n)
int n;
{ char *p = malloc((unsigned)n);
  if (p == NULL) 
    { printf("\nERROR: Windex ran out of memory.\n"); 
      exit(0); 
    }
  return(p);
}

/* mystrdup(s)
** copy string s but check for out of memory condition
*/
char *mystrdup(s)
char *s;
{ char *p = mymalloc(strlen(s)+1);
  strcpy(p,s);
  return(p);
}

/* uppercase(c)
** convert character to uppercase
*/
char uppercase(c)
char c;
{ if (islower(c)) return(toupper(c));
  return(c);
}

/* printspage(s)
** TRUE if s is a format string that contains a spot to print a pageno
*/
printspage(s)
char *s;
{ if (*s == EOS) return(FALSE);
  if (*s == ZERO) return(TRUE);
  return(printspage(s+1));
}

/* sortpageno(e)
** return page to sort entry e by
*/
sortpageno(e)
entry *e;
{ if (e->firstpageno != UNKNOWN) return(e->firstpageno);
  return(e->lastpageno);
}

/* entrylesseq(e1,e2,format_first)
** Returns TRUE if entry e1 should come before (or is equal to) entry e2
** in the sorted list of entries.  This is the basic comparison operation
** for sorting the entries into order.
** if format_first == TRUE  then order by key, format, then page
** if format_first == FALSE then order by key, page, then format
*/
entrylesseq(e1,e2,format_first)
entry *e1,*e2;
int format_first;
{ int i,r;
  /* if e1 doesn't exist, then e2 comes first */
  if (e1 == NULL) return(FALSE);        
  /* if e2 doesn't exist, then e1 comes first */
  if (e2 == NULL) return(TRUE);

  /* compare sort keys and return TRUE if e1 sorts first,
  **                              FALSE if e2 sorts first. 
  */
  for (i=0;i<=e1->level && i<=e2->level;i++)
    { r = keycmp(i,e1,e2);
      if (r<0) return(TRUE);
      if (r>0) return(FALSE);
      /* level i keys are the same */
      if (e1->level == i && e2->level > i)  return(TRUE);
      if (e1->level > i  && e2->level == i) return(FALSE);
    }

  /* The sort keys are the same. */
  if (format_first)
    {
      r = strcmp(e1->format,e2->format);
      if (r<0) return(TRUE);
      if (r>0) return(FALSE);
      /* formats are the same */
      if (sortpageno(e1) <= sortpageno(e2)) return(TRUE);
      return(FALSE);
    }
  else /* sort by pageno, then format */
    { 
      if (sortpageno(e1)<sortpageno(e2)) return(TRUE);
      if (sortpageno(e1)>sortpageno(e2)) return(FALSE);
      /* sort pages are the same */
      if (strcmp(e1->format,e2->format)<=0) return(TRUE);
      return(FALSE);
    }
}  

/* skipspace(p)
** advance p beyond any space characters (space, tabs, CRs, etc.)
*/
char *skipspace(p)
char *p;
{ while (*p != EOS && isspace(*p)) p++;
  return(p);
}      

/* skipnonsortletters(p)
** advance p beyond any non-sorting letters: whitespace or '-'s.
*/
char *skipnonsortletters(p)
char *p;
{ char *q;
  if (*p == EOS) return(p);
  if (isspace(*p)) return(skipnonsortletters(p+1));
  q = NULL_SORT_CHARS;
  while (*q && *p != *q) q++;
  if (*q) return(skipnonsortletters(p+1));
  return(p);
}      

char *smallword[] =
{ "a", "about", "also", "an", "and", "as", "at",
  "by",
  "of",
  "for", "from",
  "in", "into", 
  "on", "onto",
  "the", "to",
  "with",
  "***" /* end marker */
};

/* skipsmallwords(p)
** advances p over any small words in the small word list.
** capitalization is ignored.
** small word must be followed by a blank
*/
char *skipsmallwords(p)
char *p;
{ int i;
  char *pp, *q;
  p = skipnonsortletters(p);
  for (i=0;strcmp("***",smallword[i]);i++)
    { q = smallword[i];
      pp = p;
      while (*pp && *q && uppercase(*pp) == uppercase(*q)) 
	{ pp++;
	  q++; 
	};
      if (*q==EOS && isspace(*pp)) 
	  return(skipsmallwords(pp));
    }
  return(p);
}

/* keycmp(i,e1,e2)
** compare e1->sortkey[i] with e2->sortkey[i]
** return -1 if e1 sorts first
**         0 if they are the same
**         1 if e2 sorts first
*/
keycmp(i,e1,e2)
int i;
entry *e1, *e2;
{ char *p1, *p2;
  int r;

  /* get sort keys */
  p1 = e1->sortkey[i];
  p2 = e2->sortkey[i];

  /* ignore initial small words when sorting subitems */
  if (i>0 && IGNORE_SMALL_WORDS)
    { p1 = skipsmallwords(p1);
      p2 = skipsmallwords(p2);
    }

  /* find position of their first difference, if any (ignoring case,
  ** blanks, hyphens) 
  */
  p1 = skipnonsortletters(p1); 
  p2 = skipnonsortletters(p2);
  while (*p1!=EOS && *p2!=EOS && uppercase(*p1) == uppercase(*p2)) 
    { p1 = skipnonsortletters(p1+1); 
      p2 = skipnonsortletters(p2+1);
    }
  if ( *p1 == EOS && *p2 != EOS ) 
    return(-1); /* e1 a prefix of e2 --> -1 */
  if ( *p2 == EOS && *p1 != EOS )
    return(1); /* e2 a prefix of e1 --> FALSE */
  /* sort alphabetically by uppercase version of letters, if possible */
  if (uppercase(*p1) < uppercase(*p2)) return(-1);
  if (uppercase(*p2) < uppercase(*p1)) return(1);

  /* now the uppercase version of the entries are known to be the same */
  /* redo the comparison, paying attention to case */
  /* sort upper case entry AFTER lower case entry */
  /* get sort keys */
  p1 = e1->sortkey[i];
  p2 = e2->sortkey[i];
  while (*p1!=EOS && *p2!=EOS && *p1 == *p2) 
    { p1 = skipnonsortletters(p1+1); 
      p2 = skipnonsortletters(p2+1);
    }
  /* sort alphabetically by differing cases of same letter, if possible */
  if (isupper(*p1) && islower(*p2)) return(1);
  if (isupper(*p2) && islower(*p1)) return(-1); 

  /* keys are totally identical */
  /* try to sort by blanks and hyphens ??? */
  r = strcmp(e1->sortkey[i],e2->sortkey[i]);
  if (r!=0)
    printf("\n----- WARNING: Keys `%s' and `%s' are almost identical.\n",
	   e1->sortkey[i],e2->sortkey[i]);
  return(r);
}

/* mergelists(e1,e2,format_first)
** This is the basic merge operation for a merge-sort.
** The entries e1 and e2 are the heads of two disjoint lists of entries.
** The result is the merged list of entries.
** The lists are destructively modified in this merge by modification 
** of the `next' entries.
** The `entrylesseq' operator is used for comparisons between entries.
** if format_first == TRUE  then merge by key, format, then page
** if format_first == FALSE then merge by key, page, then format
*/
entry *mergelists(e1,e2,format_first)
entry *e1, *e2;
int format_first;
{ entry head, *last = &head;
  head.next = NULL;
  while (TRUE) {
    if (e1 == NULL) { last->next = e2; return(head.next); }
    if (e2 == NULL) { last->next = e1; return(head.next); }
    if (entrylesseq(e1,e2,format_first))  
      { 
	if (DEBUG) 
	  { printf("\n [");
	    printsortkey(e1);
	    printf("] <= [");
	    printsortkey(e2);
	    printf("]");
	  }
	last->next = e1; last = e1; e1 = e1->next; 
      }
    else
      { 
	if (DEBUG) 
	  { printf("\n [");
	    printsortkey(e1);
	    printf("] > [");
	    printsortkey(e2);
	    printf("]");
	  }
	last->next = e2; last = e2; e2 = e2->next; 
      }
  }
}

/* sortlist(e,format_first)
** This a the merge-sort operator on list e of entries.
** The sort is a ``stable sort'', so entries with the same key stay
** in the same relative order.
** if format_first == TRUE then  sort by key, format, then page
** if format_first == FALSE then sort by key, page, then format
*/
entry *sortlist(e,format_first)
entry *e;
int format_first;
{ entry *f,*g;
  int i,len;
  if (e == NULL || e->next == NULL) return(e);
  if (DEBUG) 
    { printf("\n\nSorting:");
      printlist(e);
    }
  /* let f point to entry half-way down list */
  f = e; len = 0; while (f != NULL) {len++; f = f->next;}
  for (f=e,i=0; i<len/2-1; i++,f=f->next) ; 
  /* now split list into two */
  g = f->next;
  f->next = NULL;
  /* recurse and merge */
  e = sortlist(e,format_first);        /* first half of list */
  g = sortlist(g,format_first);        /* second half of list */
  e = mergelists(e,g,format_first);
  if (DEBUG) 
    { printf("\n\nSorting result:");
      printlist(e);
    }
  return(e); 
}

/* needsparent(e, f)
** Here e and f are entries in the sorted list: f = e->next.   
** The question is whether or not an entry should be added to precede f
** in the list, because f is a multi-level entry but no entry for the super-
** entries are present.  Since e is the predecessor of f in the list, we 
** don't need to add a parent (superentry) if 
**            f is at level 0
**                  (e.g. f = "FOO"), or
**            The f->level - 1 first keys of e are the same as f's:
**                  (e.g. e = "A/B", f = "A/B/C"),
**                  (e.g. e = "A/B/C/D", f = "A/B/E")
*/
needsparent(e, f)
entry *e, *f;
{ int i;
  if (f->level == 0) return(FALSE); 
  /* e is the prefix of f --> FALSE */
  for (i=0;i<=f->level-1;i++)
    if (strcmp(e->sortkey[i],f->sortkey[i])) return(TRUE); 
  return(FALSE);
}

/* addparentifnecessary(e)
** Add a new entry after e if the entry f following e is multi-level and
** it's superentries are not already in list.  This can be determined
** by examining e and f together, assuming the list entries are processed 
** in order.
*/
addparentifnecessary(e)
entry *e;
{ entry *f = e->next;
  int i;
  if (samesortkey(e,f)) return; /* same sortkey --> do nothing */
  if (f->level == 0) return;    /* f at level 0 --> do nothing */
  if (needsparent(e,f))
    { /* create a new entry for f's parent */
      entry *g = (entry *)mymalloc(sizeof(entry));
      g->level = f->level - 1;
      for (i=0;i<=TEX_MAX_LEVEL;i++) g->sortkey[i] = NULL;
      for (i=0;i<=g->level;i++)      g->sortkey[i] = mystrdup(f->sortkey[i]);
      g->pv = NULL;
      g->format = NULL_FORMAT;          /* no page numbers for super-entries */
      g->firstpageno = 0;
      g->lastpageno = 0;
      g->next = f;          /* splice g into list: e-->g-->f */
      e->next = g;
      addparentifnecessary(e); /* redo in case g now needs a parent */
    }
}

/* addparents()
** add all superentries that are needed to the entry list `elist',
** using the `addparentifnecessary' routine on each entry.
*/
addparents()
{ entry *e = &elist;
  while (e->next != NULL) 
    { addparentifnecessary(e);
      e = e->next;
    }
}

/* samesortkey(e,f)
** returns TRUE if and only if entries e and f have the same sort key
*/
samesortkey(e,f)
entry *e, *f;
{ int i;
  if (e->level != f->level) return(FALSE);
  for (i=0;i<=e->level;i++)
    if (strcmp(e->sortkey[i],f->sortkey[i])) return(FALSE);
  return(TRUE);
}

/* spliceout(e,f)
** splice out the entry f.  e is f's predecessor.
*/
spliceout(e,f)
entry *e,*f;
{ 
  e->next = f->next;

  /* save print value of f if e doesn't have a print value */
  if (e->pv == NULL && f->pv != NULL) 
    e->pv = f->pv;
  else if (e->pv != NULL &&
	   f->pv != NULL &&
	   strcmp(e->pv,f->pv) &&
	   strcmp(f->pv,f->sortkey[f->level])
	   )
    { printf("\n----- WARNING: Print value %s overridden for entry:\n",f->pv);
      printentry(f);
      printf("\n");
    }

  /* save format string (assumption: e's is the same or NULL_FORMAT */
  e->format = f->format;
}

/* compressentrylist()
** Loop through list `elist' of index entries, and combine adjacent
** entries to make page ranges whenever possible.
*/
compressentrylist()
{ entry *e = elist.next,*f;
  while (e != NULL && e->next != NULL)
    { f = e->next;
      if (!samesortkey(e,f))
	{ 
	  e=f;                           /* can't combine, move on to f */
	}
      else if (e->format == NULL_FORMAT)   /* Note NULL_FORMATs sort earlier */
	{ spliceout(e,f);
	  e->firstpageno = f->firstpageno;
	  e->lastpageno = f->lastpageno;
	}
      else if (strcmp(e->format,f->format))
	{                                /* different formats */
	  e=f;                           /* can't combine, move on to f */
	}
      else if (e->lastpageno == UNKNOWN && f->firstpageno == UNKNOWN)
	{ spliceout(e,f);                /* combine start and end of range */
	  e->lastpageno = f->lastpageno;
	                                 /* reprocess e */
	}
      else if (e->lastpageno == UNKNOWN && f->firstpageno != UNKNOWN)
	{ spliceout(e,f);                /* delete page in middle of range */
	}
      else if (f->firstpageno == UNKNOWN)
	{                                /* ERROR -- no start of range */
	  e = f;                         /* (will be reported later) */
	}
      else if ( e->lastpageno == f->firstpageno ||
	        e->lastpageno +1 == f->firstpageno)
	{ spliceout(e,f);                /* remove f */
	  e->lastpageno = f->lastpageno;
	                                 /* reprocess e */
	}
      else 
	{
	  e = f;                     /* process f next */
	}
    }
}

/* main(argc,argv)
** requires one command-line argument: the name of the file (no extension)
*/
main(argc,argv)
int argc; 
char **argv;
{ char fname[MAX_STRING_LENGTH];
  int i;

  /* If no arguments given, instruct user */
  if (argc == 1)
    { printf("\nUsage: windex filename\n");
      exit(0);
    }

  /* print banner */
  printf(WINDEX_BANNER);

  /* Open input and output files */
  strcpy(fname,argv[1]);
  strcat(fname,INPUT_EXTENSION);              /* input file = foo.idx */
  instream = fopen(fname,"r");
  if (instream == NULL)
    { printf("\nERROR: input file `%s' can not be opened.\n",fname);
      exit(0);
    }
  strcpy(fname,argv[1]);
  strcat(fname,OUTPUT_EXTENSION);            /* output file = foo.index */
  outstream = fopen(fname,"w");
  if (outstream == NULL)
    { printf("\nERROR: output file `%s' can not be opened.\n",fname);
      exit(0);
    }
  
  /* Initialize entry list to one entry, consisting of a null string */
  /* (The null string should sort first) */
  elist.level = 0;
  elist.next = NULL;
  for (i=0;i<TEX_MAX_LEVEL;i++) 
    elist.sortkey[i] = "";                 
  elast = &elist;

  /* Read the input file foo.idx */
  if (DEBUG) printf("\n\nInput: ");
  inputfile();
 
  /* Sort the entries into order, by key, format then page */
  elist.next = sortlist(elist.next,TRUE); 
  /* Debug printout */
  if (DEBUG) 
    { printf("\n\nSorted:"); printlist(elist.next); }

  /* Add parent superentries for those entries that need them */
  addparents();  
  /* Debug printout */
  if (DEBUG) 
    { printf("\n\nSorted with parents:"); printlist(elist.next); }

  /* Combine pages into ranges as appropriate */
  compressentrylist();
  /* Debug printout */
  if (DEBUG) 
    { printf("\n\nSorted with parents and ranges:"); printlist(elist.next); }

  /* Sort the entries into order, by key, page, then format */
  elist.next = sortlist(elist.next,FALSE); 
  /* Debug printout */
  if (DEBUG) 
    { printf("\n\nSorted:"); printlist(elist.next); }

  /* print out the output file */
  makeindex();

  fclose(instream);
  fclose(outstream);
}

/* scanbalance(bufferp,out)
** input:    bufferp is a pointer to an input buffer
**              the first character of bufferp is LBRACE or LBRACKET
**           out is a pointer to an output buffer
** The procedure copies bufferp up to the matching delimiter into out.
** The outermost delimeters are converted to TEX_BEGIN_GROUP..TEX_END_GROUP
** (So if there is nothing between the delimiters, we get TEX_EMPTY_GROUP.)
** This procedure returns a pointer to the character after the final delimiter.
*/
char *scanbalance(bufferp,out)
char *bufferp;
char *out;
{ int n = 0;
  char c, *q = out;
 top: c = *q++ = *bufferp++;
      if (c == LBRACKET || c == LBRACE) n++;        /* left delimiter */
      if (c == RBRACKET || c == RBRACE) n--;        /* right delimiter */
      if (c == EOS || c == CR || c == LF || n == 0)
	/* end of string or all matched */
	{ /* convert outermost delimiters to TEX_BEGIN_GROUP..TEX_END_GROUP */
	  out[0] = TEX_BEGIN_GROUP;
	  *(q-1) = TEX_END_GROUP;
	  *q = EOS;                           /* terminate output string */
	  return(bufferp); 
	}
      goto top;
}

/* printsortkey(e)
** print out the sort key of entry e in form similar to input form 
*/
printsortkey(e)
entry *e;
{ printf("%s",e->sortkey[0]);
  if (e->level>=1) printf("/%s",e->sortkey[1]);
  if (e->level>=2) printf("/%s",e->sortkey[2]);
}

/* printentry(e)
** print out the entry e in form similar to input form.
*/
printentry(e)
entry *e;
{ printf("\n");
  if (e==NULL) printf("NULL");
  printsortkey(e);
  if (e->pv != NULL) printf("%s",e->pv);
  /* else            printf("{%s}",e->sortkey[e->level]); */
  if (e->lastpageno == UNKNOWN)  printf("%c",LANGLE);
  if (e->firstpageno == UNKNOWN) printf("%c",RANGLE);
  if (e->format != NULL) printf("[%s]",e->format);
  printf(":%d",sortpageno(e));
  fflush(stdout);
}

/* printlist(e)
** print out the list of entries starting at e 
*/
printlist(e)
entry *e;
{ while (e != NULL) { printentry(e); e = e->next; }
}


/* inputfile()
** read the input file a line at a time and process each line.
** print a warning if any line begins with ``\indexentry{''
*/ 
inputfile()
{ char buffer[MAX_STRING_LENGTH];
  int oldstylewarn;	/* flag:  only give the warning once */
  oldstylewarn = FALSE;

  while (NULL != fgets(buffer,MAX_STRING_LENGTH-1,instream))
    { if ((!oldstylewarn) && oldstyle(buffer))
	{ oldstylewarn = TRUE;
	  printf("\n----- WARNING:  You appear not to have \\input windex.tex.");
	  printf("\n      Proceeding anyway.\n"); 
	};
     inputline(buffer); 
    }
}


/* oldstyle(buffer)
** true if buffer starts with "\indexentry{"
*/
oldstyle(buffer)
char *buffer;
{ int i = 0;
  while ((buffer[i] == "\\indexentry{"[i]) && (++i < 12)) ;
  return(i == 12);
}


/* inputline(buffer)
** Scan an input line and create an entry for it.
*/
inputline(buffer)
char *buffer;
{ char key[MAX_STRING_LENGTH];    /* sort key */
  char pv[MAX_STRING_LENGTH];     /* print value */
  char format[MAX_STRING_LENGTH]; /* format string for page number */
  char *bufferp,*keyp,*pvp;
  entry *e;
  int pvseen;    /* flag if print-value has been seen */
  int i,pageno;

  /* Create a new empty entry for this line */
  e = (entry *)mymalloc(sizeof(entry));
  e->level = 0;
  for (i=0;i<TEX_MAX_LEVEL;i++) e->sortkey[i] = NULL;
  e->pv = NULL;
  e->format = DEFAULT_FORMAT;
  e->firstpageno = 0;
  e->lastpageno = 0;

  /* scan line */
  bufferp = buffer;          /* input buffer pointer */
  keyp = key;                /* sort key output pointer */
  key[0] = EOS;              /* sort key is null string */
  pvp = pv;                  /* print value output pointer */
  pvseen = FALSE;            /* print value not seen yet */
  strcpy(format,DEFAULT_FORMAT);
  while (*bufferp==BLANK) bufferp++; /* skip leading blanks */
  while (*bufferp && *bufferp != CR && *bufferp != LF)
    { switch (*bufferp) {

      case LANGLE: /* LANGLE (<) is flag to start a page range */
		e->lastpageno = UNKNOWN;
		bufferp++; 
		break;

      case RANGLE: /* RANGLE (>) is flag to end a page range */
		e->firstpageno = UNKNOWN;
		bufferp++; 
		break;

      case LBRACE: /* LBRACE ({) marks beginning of print value string */
		bufferp = scanbalance(bufferp,pv); /* copy string into pv */
		pvp = pv + strlen(pv);
		pvseen = TRUE;
		break;

      case LBRACKET: /* LBRACKET ([) marks start of format string */
		bufferp = scanbalance(bufferp,format); 
		break;

      case COLON: /* COLON (:) marks beginning of page number */
		pageno = atoi(++bufferp); 
		if (e->firstpageno != UNKNOWN) e->firstpageno = pageno;
		if (e->lastpageno != UNKNOWN) e->lastpageno = pageno;
		goto saveline;               /* and break out of loop */

      case SLASH: /* SLASH marks superentry divisions */
		bufferp++;            /* skip over the slash */
		*keyp = EOS;          /* terminate sort key */
		e->sortkey[e->level] = mystrdup(key);
		keyp = key;
		e->level = e->level + 1;
		if (e->level > TEX_MAX_LEVEL)
		  printf("\n----- WARNING: Too many levels in entry: %s",
			   buffer);
		break;

      default:  /* Copy character into sort key */
		*keyp++ = *bufferp++;
      }
    }

  saveline: 
  /* If we haven't seen a sort key, this is probably a blank line. 
  ** Don't save this entry on the list.
  */
  if (strlen(key)==0) return;

  /* Terminate sort key */
  *keyp = EOS;

  /* Copy sort key into newly allocated string */
  e->sortkey[e->level] = mystrdup(key);

  /* Copy print value into newly allocated string */
  if (pvseen) e->pv = mystrdup(pv);

  /* Copy format into newly allocated string, if format exists */
  if (strcmp(format,TEX_EMPTY_GROUP)==0)  /* empty format means no page */
    { e->format = NULL_FORMAT;            /* (used for super-entry) */
    }
  else if (format[0] != EOS) 
    { e->format = mystrdup(format); 
    }

  /* If format doesn't contain a spot for pageno, then make pageno = 0 */
  /* so it sorts at front */
  if (!printspage(e->format))
    e->firstpageno = e->lastpageno = 0;
 
  /* Append new entry to end of list. elast points to end of list */
  e->next = NULL;
  elast->next = e; 
  elast = e;

  if (DEBUG) printentry(e);
}


/* printvalueaux(f,e)
** returns NULL if sort key of e is the different than f's
** otherwise returns printvalue of e, if it exists
** otherwise returns printvalueaux of e's successor
*/
char *printvalueaux(f,e)
entry *f, *e;
{ 
  if (e == NULL) return(NULL);
  if (!samesortkey(f,e)) return(NULL);
  if (e->pv != NULL) return(e->pv);
  return(printvalueaux(f,e->next));
} 

/* printvalue(f)
** returns print value for entry f, or sort key if no print value given
** checks succeeding entries with same sort key to see if any of them
** have a print value given, and if so, uses that 
*/
char *printvalue(f)
entry *f;
{ char *pv;
  pv = printvalueaux(f,f);
  if (pv != NULL) return(pv);
  return(f->sortkey[f->level]);
} 

/* makeindex()
** Runs through the list elist, and prints out the output file foo.index.
*/
makeindex()
{ entry *e = &elist;
  entry *f;
  int n = 0;       /* number of entries printed */
  int entry_printed_last = FALSE; /* TRUE if entry printed last, 
				     FALSE if page printed last */
  char *q;

  if (e->next == NULL) 
    { 
      printf("No output produced (no entries found in input file).\n",n);
      return; 
    }

  fprintf(outstream,TEX_BEGIN_INDEX);

  while (e->next != NULL)
    {  f = e->next; /* entry to print is f */
       n++;

       /* Check for unbalanced page ranges and print warnings */
       if (f->lastpageno == UNKNOWN)
	 { printf("\n----- WARNING: closing entry not found to match following starting %c entry:",LANGLE);
	   printentry(f);
	   printf("\n");
	 }
       if (f->firstpageno == UNKNOWN)
	 { printf("\n----- WARNING: starting entry not found to match following ending %c entry:",RANGLE);
	   printentry(f);
	   printf("\n");
	 }

       /* Print entry text if necessary */
       if (!samesortkey(e,f))
	 { /* Key of f is different than key of predecessor e */
	   /* print appropriately indented entry with subitems, etc. */
	   if      (f->level == 0) fprintf(outstream,TEX_BEGIN_LEVEL0);
	   else if (f->level == 1) fprintf(outstream,TEX_BEGIN_LEVEL1);
	   else if (f->level == 2) fprintf(outstream,TEX_BEGIN_LEVEL2);
	   /* print ``print value'' for f */
	   fprintf(outstream,"%s",printvalue(f));
	   entry_printed_last = TRUE;
	 }

       /* print TEX_AFTER_ENTRY or TEX_BETWEEN_PAGES if necessary */
       if (strcmp(f->format,NULL_FORMAT)==0)
	 { ; /* no page entry to be printed, so no separator */
	 }
       else if (entry_printed_last) 
	 fprintf(outstream,TEX_AFTER_ENTRY);
       else if (entry_printed_last == FALSE)
	 fprintf(outstream,TEX_BETWEEN_PAGES);
       
       /* Print page number in its format */
       if (strcmp(f->format,NULL_FORMAT)) 
	 { /* check for no page number printed */
	   if (!printspage(f->format))
	     fprintf(outstream,"%s",f->format);
	   else /* insert page or page range */
	     { /* print first part of format */
	       q = f->format;
	       while (*q && *q != ZERO) 
		 { fprintf(outstream,"%c",*q); q++; }
	       /* print first page number */
	       fprintf(outstream,"%d",f->firstpageno);
	       /* if necessary, print range */
	       if (f->lastpageno != f->firstpageno)
		 {
		   fprintf(outstream,"%s",TEX_BETWEEN_RANGE);
		   fprintf(outstream,"%d",f->lastpageno);
		 }
	       q++;  /* skip the zero */
	       while (*q) fprintf(outstream,"%c",*q++); 
	     }
	   entry_printed_last = FALSE;
	 }

       /* go on to next entry */
       e = e->next;
    }
  fprintf(outstream,TEX_END_INDEX);
  printf("Done. %d entries processed.\n",n);
}