// Cross-Reference-Liste, mit Trie
//
// Aufruf: xref-trie file ...
//
// Klaus Kusche, 2002

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <ctype.h>
// Für UCHAR_MAX (größtmöglicher Wert eines unsigned char)
#include <limits.h>

// Statistiken einschalten
#define PRINT_STAT 1

// Sortierte Ausgabe des Baumes einschalten
//#define PRINT_LIST 1


// Max. Länge einer Input-Zeile
#define LINELEN 16384

// Welche Buchstaben sind Anfang eines Wortes?
#define iswordbeg(c) (isalpha(c) || ((c) == '_'))

// Welche Buchstaben gehören zu einem Wort?
#define isinword(c) (isalnum(c) || ((c) == '_'))

// Makro zum Zugriff auf den zu c gehörigen Sohn-Pointer von w
// Wichtig: c in einen unsigned char verwandeln!
// Per Default ist char meist signed ==> gäbe negativen Index!
#define sonptr(w, c) ((w)->son[((unsigned char)(c))])

#ifdef PRINT_STAT 
// Max. Pfadlänge in Statistik-Ausgabe
#define MAXLEN 30
#endif

// Typ eines Eintrags der Positionsliste
typedef struct _pos_entry {
  const char *filename;      // File, in dem die Position liegt (= argv[...])
  int line;                  // Zeilennummer
  int column;                // Spaltennummer
  struct _pos_entry *next;   // Verkettung zur nächsten Position
} pos_entry;

// Typ eines Trie-Knotens
typedef struct _word_entry {
  pos_entry *first_pos;      // Head der Positionsliste des Wortes
  pos_entry *last_pos;       // Tail der Positionsliste des Wortes
                             // Ist das ein Zwischenknoten ohne Wort,
                             // sind beide NULL
  struct _word_entry *son[UCHAR_MAX + 1];  // Sohn-Pointer für jeden ASCII-Wert
} word_entry;


// Liefert einen Pointer auf n mit malloc angeforderte Bytes, mit Fehlerprüfung
void *mymalloc(size_t n);
// Liefert einen Pointer auf einen neu angelegten Positionsknoten
pos_entry *new_pos(const char *filename, int linenr, int colnr);
// Liefert einen Pointer auf einen neu angelegten, leeren Wortknoten
word_entry *new_word(void);
// Hängt die Position pos *hinten* an die Positionsliste von word an
void add_pos(pos_entry *pos, word_entry *word);
// Speichert eine neue Position des (neuen oder bekannten) Wortes word
void save_word(const char *filename, int linenr, int colnr, const char *word);
// Ermittelt und speichert alle Worte in der Zeile line
void read_line(const char *filename, int linenr, char *line);
// Liest und verarbeitet den angegebenen File zeilenweise
void read_file(const char *filename);
// Gibt alle Positionen der Positionsliste des Wortes word aus
void list_pos(const word_entry *word);
// Sucht das angegebene Wort word im Trie, gibt seine Positionen aus
void process_word(const char *word);
// Liest und verarbeitet den Input vom Terminal (ein Wort pro Zeile!)
void process_input(void);
// Gibt rekursiv alle Wörter im Trie in Sortier-Reihenfolge aus
void reklist(word_entry *w, char *line, int t);
// Ermittelt rekursiv die Statistiken, t ... aktuelle Tiefe
void rekstat(word_entry *w, int t);
// Gibt Statistiken über die Form des Trie aus
void statistics(void);


// Die Wurzel des Trie = Knoten für das "leere" Wort
word_entry top;
word_entry *root = &top;

// Der Programmname (für Fehlermeldungen)
const char *progname;

// Liefert einen Pointer auf n mit malloc angeforderte Bytes, mit Fehlerprüfung
void *mymalloc(size_t n)
{
  void *p;

  if ((p = malloc(n)) == NULL) {
    fprintf(stderr, "%s: Out of memory\n", progname);
    exit(EXIT_FAILURE);
  }

  return p;
}

// Liefert einen Pointer auf einen neu angelegten Positionsknoten
// Die Argumente enthalten die im Knoten einzutragende Position
// Die Verkettung des neuen Knotens wird auf NULL gesetzt
pos_entry *new_pos(const char *filename, int linenr, int colnr)
{
  pos_entry *p;

  p = (pos_entry *) (mymalloc(sizeof (pos_entry)));
  p->filename = filename;
  p->line = linenr;
  p->column = colnr;
  p->next = NULL;
  return p;
}

// Liefert einen Pointer auf einen neu angelegten Wortknoten
// Der Knoten ist leer (keine Söhne, keine Positionen)
word_entry *new_word(void)
{
  word_entry *w;
  int i;

  w = (word_entry *) (mymalloc(sizeof (word_entry)));
  w->first_pos = w->last_pos = NULL;
  for (i = 0; i < UCHAR_MAX + 1; ++i) {
    w->son[i] = NULL;
  }

  return w;
}

// Hängt die Position pos *hinten* an die Positionsliste des Wortknotens wort an
// Achtung: Bei Tries kann die Liste auch leer sein
// (wenn das bisher ein Zwischenknoten war, der keinem Wort entsprach)
void add_pos(pos_entry *pos, word_entry *word)
{
  if (word->first_pos == NULL) {
    word->first_pos = pos;       // Erster Eintrag
  } else {
    word->last_pos->next = pos;
  }

  word->last_pos = pos;
}

// Sucht das Wort word im Trie
// Gibt es das Wort noch nicht, wird ein frischer Worteintrag
// und alle fehlenden dorthin führenden Zwischenknoten im Trie angelegt
// und ein frischer Positionseintrag (filename/linenr/colnr) angehängt.
// Gibt es das Wort schon,
// wird an dessen Positionsliste ein frischer Eintrag angehängt.
void save_word(const char *filename, int linenr, int colnr, const char *word)
{
  word_entry **t; // Zeiger dorthin, wo der aktuelle Subtrie dranhängt
  const char *p;  // Zeiger auf den aktuellen Buchstaben im Wort

  t = &root;
  for (p = word; *p != '\0'; ++p) {
    t = &(sonptr(*t, *p));
    if (*t == NULL) {
      *t = new_word();
    }
  }

  add_pos(new_pos(filename, linenr, colnr), *t);
}

// Ermittelt und speichert alle Worte in der Zeile line
// Achtung: line wird dabei modifiziert!
// filename und linenr sind die Position der Zeile
void read_line(const char *filename, int linenr, char *line)
{
  char *line_end;            // Zeiger auf das \0 am Zeilenende
  char *word_beg;            // Zeiger auf den ersten Char des nächsten Wortes
  char *word_end;            // Zeiger auf den ersten Char hinter dem Wort
  int colnr;                 // Spalte

  line_end = strchr(line, '\0');
  for (word_beg = line; ; word_beg = word_end) { // Ein Durchlauf pro Wort
    // Suche den ersten Buchstaben des nächsten Wortes
    for ( ; !iswordbeg(*word_beg); ++word_beg) {
      if (word_beg == line_end) {      // Am Zeilenende, nichts gefunden:
        return;                        // Die Zeile ist fertig verarbeitet
      }
    }

    // Suche den ersten Buchstaben hinter dem Wort
    for (word_end = word_beg + 1; isinword(*word_end); ++word_end) {
    }

    // Mach aus dem Wort einen einzelnen String: Schreib \0 ans Ende (Pfui!)
    *word_end = '\0';
    // Spalte = Entfernung vom Zeilenanfang (ab 1, nicht ab 0)
    colnr = (word_beg - line) + 1;
    // Speichere das Wort und seine Position
    save_word(filename, linenr, colnr, word_beg);
  }
}

// Liest und verarbeitet den angegebenen File zeilenweise
// Bricht bei zu langen Zeilen mit Fehler ab!
void read_file(const char *filename)
{
  FILE *f;
  char line[LINELEN + 2];
  int linenr;

  if ((f = fopen(filename, "r")) == NULL) {
    fprintf(stderr, "%s: Can't open %s: %s\n", progname, filename,
            strerror(errno));
    exit(EXIT_FAILURE);
  }

  for (linenr = 1; fgets(line, sizeof (line), f); ++linenr) {
    if ((strlen(line) == sizeof(line) - 1) &&
        (line[sizeof(line) - 2] != '\n')) {
      fprintf(stderr, "%s: Line too long on %s\n", progname, filename);
      exit(EXIT_FAILURE);
    }
    read_line(filename, linenr, line);
  }

  if (ferror(f)) {
    fprintf(stderr, "%s: Can't read %s: %s\n", progname, filename,
            strerror(errno));
    exit(EXIT_FAILURE);
  }
  if (fclose(f) != 0) {
    fprintf(stderr, "%s: Can't close %s: %s\n", progname, filename,
            strerror(errno));
    exit(EXIT_FAILURE);
  }
}

// Gibt alle Positionen der Positionsliste des Wortes word aus
// Alle Positionen aus einem File werden in einer Zeile ausgegeben
// (mit dem Filenamen einmal am Zeilenanfang)
// Kommt eine Position aus einem neuen File, wird eine neue Zeile begonnen
void list_pos(const word_entry *word)
{
  const pos_entry *p;
  const char *oldfile = NULL; // Name des Files der vorigen Pos

  for (p = word->first_pos; p != NULL; p = p->next) {
    if (p->filename != oldfile) {
      oldfile = p->filename;
      printf("\n%s:", p->filename);
    }
    printf(" %u/%u", p->line, p->column);
  }

  putchar('\n');
}

// Sucht das angegebene Wort word im Trie
// Gibt das Wort und seine Positionen (mittels list_pos)
// oder "nicht gefunden" aus
void process_word(const char *word)
{
  word_entry *w;
  const char *p;  // Zeiger auf den aktuellen Buchstaben im Wort

  for (w = root, p = word; 
       (w != NULL) && (*p != '\0'); 
       w = sonptr(w, *p), ++p) {
  }

  if ((w == NULL) || (w->first_pos == NULL)) {
    printf("*** %s: Not found! ***\n", word);
  } else {
    printf("*** %s:", word);
    list_pos(w);
  }
}

// Liest und verarbeitet den Input vom Terminal (ein Wort pro Zeile!)
void process_input(void)
{
  char line[LINELEN + 2];
  char *p;

  while (fgets(line, sizeof (line), stdin)) {
    if ((p = strchr(line, '\n')) == NULL) {
      fprintf(stderr, "%s: Incomplete line on stdin\n", progname);
      exit(EXIT_FAILURE);
    }
    *p = '\0';   // '\n' entfernen
    process_word(line);
  }

  if (ferror(stdin)) {
    fprintf(stderr, "%s: Can't read stdin: %s\n", progname, strerror(errno));
    exit(EXIT_FAILURE);
  }
}

#ifdef PRINT_LIST
// Gibt den gesamten Trie rekursiv aus
// Da die Worttexte selbst ja nicht explizit im Trie gespeichert sind,
// wird das aktuelle Wort in line zusammengesetzt
// (1 Zeichen pro Rekursionsebene = Index des verwendeten Sohn-Pointers)
// t ist die Rekursionstiefe = Index des aktuellen Zeichens in line
void reklist(word_entry *w, char *line, int t)
{
  int i;

  if (w->first_pos != NULL) {
    // Gib das Wort im aktuellen Knoten aus
    line[t] = '\0';
    printf("%s\n", line);
  }
  for (i = 0; i <= UCHAR_MAX; ++i) {
    // Gib alle Söhne aus
    if (w->son[i] != NULL) {
      line[t] = i;
      reklist(w->son[i], line, t + 1);
    }
  }
}
#endif

#ifdef PRINT_STAT
// Globale Variablen für die Statistiken
int cnt[MAXLEN]; // Anzahl Worte pro Wortlänge
int cntmax;      // Worte mit Länge > MAXLEN
int total;       // Worte insgesamt
int sum;         // Summe der Wort-Längen
int maxlen;      // Größte Wort-Länge
int empty;       // Anzahl der Zwischenknoten ohne Wort
int nosons;      // Anzahl der Knoten ohne Söhne

// Ermittelt rekursiv die Statistiken, t ... aktuelle Tiefe
void rekstat(word_entry *w, int t)
{
  int i, sons;

  if (w->first_pos != NULL) {
    // Zähle das Wort im aktuellen Knoten
    ++total;
    sum += t;
    if (t > maxlen)
      maxlen = t;
    if (t >= MAXLEN)
      ++cntmax;
    else
      ++cnt[t];
  } else {
    ++empty;
  }
  for (sons = 0, i = 0; i <= UCHAR_MAX; ++i) {
    if (w->son[i] != NULL) {
      ++sons;
      rekstat(w->son[i], t + 1);
    }
  }
  if (sons == 0) {
    ++nosons;
  }
}

// Gibt Statistiken über die Wörter im Baum aus
void statistics(void)
{
  int i;

  rekstat(root, 0);

  for (i = 0; i < MAXLEN; ++i) {
    if (cnt[i] > 0) {
      printf("%5d Worte mit Länge %2d (%6.2f %%)\n", cnt[i], i,
             (cnt[i] * 100) / ((double) total));
    }
  }
  if (cntmax > 0) {
    printf("%5d Worte mit Länge >%2d (%6.2f %%), größte Tiefe %d\n", cntmax,
           MAXLEN, (cntmax * 100) / ((double) total), maxlen);
  }
  printf("Insgesamt %d Worte, mittlere Länge %5.2f\n", total,
         sum / ((double) total));
  printf("%d Zwischenknoten ohne Wort, %d Knoten ohne Sohn\n", empty, nosons);
}
#endif

// Liest und speichert alle Worte aus allen als Argument angegebenen Files
// Liest Worte vom Terminal und gibt deren gespeicherte Position aus
int main(int argc, const char *argv[])
{
  int i;

#ifdef PRINT_LIST
  // hier wird das Wort beim Ausgeben Zeichen für Zeichen eingetragen
  char line[LINELEN + 2];
#endif

  progname = argv[0];

  //// Files einlesen und speichern
  if (argc == 1) {
    fprintf(stderr, "Usage: %s file ...\n", argv[0]);
    exit(EXIT_FAILURE);
  }
  for (i = 1; i < argc; ++i) {
    read_file(argv[i]);
  }

#ifdef PRINT_LIST
  // Wortliste ausgeben
  reklist(root, line, 0);
#endif

#ifdef PRINT_STAT
  // Statistik ausgeben
  statistics();
#endif

  //// Wörter einlesen und suchen
  process_input();

  exit(EXIT_SUCCESS);
}