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

#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 LINE_LEN 16384

// Welche Zeichen sind als Anfang eines Wortes erlaubt?
#define is_word_beg(c) (isalpha(c) || ((c) == '_'))

// Welche Zeichen sind innerhalb eines Wortes erlaubt?
#define is_in_word(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 ==> das gäbe negativen Index!
#define son_ptr(w, c) ((w)->son[((unsigned char)(c))])

#ifdef PRINT_STAT 
// Max. Pfadlänge in der Statistik-Ausgabe
#define MAX_LEN 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 Knotens im Trie
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 char-Wert
} word_entry;


// Liefert einen Pointer auf n mit malloc angeforderte Bytes, mit Fehlerprüfung
void *my_malloc(size_t n);
// Liefert einen Pointer auf einen neu angelegten Positionsknoten
pos_entry *new_pos(const char *filename, int line_nr, int col_nr);
// 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 line_nr, int col_nr, const char *word);
// Ermittelt und speichert alle Worte in der Zeile line
void read_line(const char *filename, int line_nr, 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
// Da die Worttexte selbst ja nicht explizit im Trie gespeichert sind,
// wird das aktuelle Wort in line zusammengesetzt
// (1 Zeichen pro Rekursionsebene, Zeichen = Index des verwendeten Sohn-Pointers)
// t ist die Rekursionstiefe = Index des aktuellen Zeichens in line
void rek_list(word_entry *w, char *line, int d);
// Ermittelt rekursiv die Statistiken, d ... aktuelle Tiefe
void rek_stat(word_entry *w, int d);
// Gibt Statistiken über die Form des Trie aus
void statistics(void);


// Der Wurzel-Knoten des Trie = der Knoten für das "leere" Wort
word_entry top;
// Der Pointer darauf
word_entry *root = &top;

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

// Liefert einen Pointer auf n mit malloc angeforderte Bytes, 
// mit Fehlerprüfung, bei Fehler: Fehlermeldung und Programm-Abbruch
void *my_malloc(size_t n)
{
  void *p = malloc(n);

  if (p == NULL) {
    fprintf(stderr, "%s: Out of memory\n", prog_name);
    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
// (weil der Knoten ja hinten an der Positionsliste angehängt wird)
pos_entry *new_pos(const char *filename, int line_nr, int col_nr)
{
  pos_entry *p = (pos_entry *) (my_malloc(sizeof (pos_entry)));

  p->filename = filename;
  p->line = line_nr;
  p->column = col_nr;
  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 = (word_entry *) (my_malloc(sizeof (word_entry)));

  w->first_pos = w->last_pos = NULL;
  for (int i = 0; i <= UCHAR_MAX; ++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 noch 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 neuer Worteintrag
// und alle fehlenden dorthin führenden Zwischenknoten im Trie angelegt
// Dann wird ein neuer Positionseintrag (filename/line_nr/col_nr) 
// mit new_pos erzeugt und mit add_pos an das Wort angehängt
void save_word(const char *filename, int line_nr, int col_nr, const char *word)
{
  // t zeigt auf den Pointer, an dem der aktuelle Sub-Trie dranhängt
  word_entry **t = &root;
  // p zeigt auf den aktuellen Buchstaben im Wort
  for (const char *p = word; *p != '\0'; ++p) {
    t = &(son_ptr(*t, *p));
    if (*t == NULL) {
      *t = new_word();
    }
  }

  add_pos(new_pos(filename, line_nr, col_nr), *t);
}

// Ermittelt und speichert alle Worte in der Zeile line
// Achtung: line wird dabei modifiziert!
// filename und line_nr sind die Position der Zeile
void read_line(const char *filename, int line_nr, char *line)
{
  char *line_end = strchr(line, '\0');   // Zeiger auf das \0 am Zeilenende

  // Schleife mit einem Durchlauf pro Wort
  char *word_beg;            // Zeiger auf den ersten Char des nächsten Wortes
  char *word_end;            // Zeiger auf den ersten Char hinter dem Wort
  // Erster Durchlauf beginnt am Zeilenanfang zu suchen,
  // weitere Durchläufe beginnen unmittelbar hinter dem vorigen Wort
  for (word_beg = line; ; word_beg = word_end) { 
    // Suche den Beginn des nächsten Wortes
    for ( ; !is_word_beg(*word_beg); ++word_beg) {
      if (word_beg == line_end) {
        // Wir sind am Zeilenende angelangt, kein Wort mehr gefunden:
        // Die Zeile ist fertig verarbeitet
        return;                    
      }
    }

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

    // Mach aus dem aktuellen Wort einen einzelnen String:
    // Schreib ein '\0' unmittelbar hinter das Wort (Pfui!)
    *word_end = '\0';
    // Spalte von word = Entfernung vom Zeilenanfang (gezählt ab 1, nicht ab 0)
    int col_nr = (word_beg - line) + 1;
    // Speichere das Wort und seine Position
    save_word(filename, line_nr, col_nr, 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 = fopen(filename, "r");
  if (f == NULL) {
    fprintf(stderr, "%s: Can't open %s: %s\n", prog_name, filename,
            strerror(errno));
    exit(EXIT_FAILURE);
  }

  char line[LINE_LEN + 2];
  for (int line_nr = 1; fgets(line, sizeof (line), f); ++line_nr) {
    // Prüfung auf Zeilen länger LINE_LEN
    if ((strlen(line) == sizeof(line) - 1) &&
        (line[sizeof(line) - 2] != '\n')) {
      fprintf(stderr, "%s: Line too long on %s\n", prog_name, filename);
      exit(EXIT_FAILURE);
    }
    // Verarbeite alle Worte in line
    read_line(filename, line_nr, line);
  }

  if (ferror(f)) {
    fprintf(stderr, "%s: Can't read %s: %s\n", prog_name, filename,
            strerror(errno));
    exit(EXIT_FAILURE);
  }
  if (fclose(f) != 0) {
    fprintf(stderr, "%s: Can't close %s: %s\n", prog_name, 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 char *old_file = NULL; // Name des Files der vorigen Pos

  // Durchlaufe die Positionsliste
  for (const pos_entry *p = word->first_pos; p != NULL; p = p->next) {
    // Alle Pos-Einträge eines Files zeigen auf denselben Filenamen-String
    // ==> Pointer-Vergleich reicht aus, kein String-Vergleich nötig
    if (p->filename != old_file) {
      // Beginne neue Zeile mit neuem File
      old_file = p->filename;
      printf("\n%s:", p->filename);
    }
    printf(" %d/%d", 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 = root;  // Zeiger auf den aktuellen Trie-Knoten
  const char *p = word;  // Zeiger auf das aktuelle Zeichen im Wort

  // Steige Zeichen für Zeichen in den entsprechenden Sub-Trie ab
  while ((w != NULL) && (*p != '\0')) { 
    w = son_ptr(w, *p);
    ++p;
  }

  if ((w == NULL) || (w->first_pos == NULL)) {
    // Es gibt das Wort nicht im Trie,
    // oder der Knoten für das Wort ist ein Zwischenknoten ohne Positionen
    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[LINE_LEN + 2];
  while (fgets(line, sizeof (line), stdin)) {
    char *p = strchr(line, '\n');
    if (p == NULL) {
      fprintf(stderr, "%s: Incomplete line on stdin\n", prog_name);
      exit(EXIT_FAILURE);
    }
    *p = '\0';   // '\n' entfernen
    process_word(line);
  }

  if (ferror(stdin)) {
    fprintf(stderr, "%s: Can't read stdin: %s\n", prog_name, 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 rek_list(word_entry *w, char *line, int d)
{
  if (w->first_pos != NULL) {
    // Gib das Wort im aktuellen Knoten aus
    line[d] = '\0';
    printf("%s\n", line);
  }
  for (int i = 0; i <= UCHAR_MAX; ++i) {
    // Gib alle vorhandenen Söhne aus
    if (w->son[i] != NULL) {
      line[d] = i;  // Index des Sohnes = nächstes Zeichen im Wort
      rek_list(w->son[i], line, d + 1);
    }
  }
}
#endif

#ifdef PRINT_STAT
// Globale Variablen für die Statistiken
int cnt[MAX_LEN]; // Anzahl Worte pro Wortlänge
int cnt_max;      // Worte mit Länge > MAX_LEN
int total_words;  // Worte insgesamt
int len_sum;      // Summe der Wort-Längen
int max_word_len; // Größte Wort-Länge
int no_word_cnt;  // Anzahl der Zwischenknoten ohne Wort
int no_son_cnt;   // Anzahl der Knoten ohne Söhne

// Ermittelt rekursiv die Statistiken, d ... aktuelle Tiefe
void rek_stat(word_entry *w, int d)
{
  if (w->first_pos != NULL) {
    // Zähle das Wort im aktuellen Knoten
    ++total_words;
    len_sum += d;
    if (d > max_word_len) {
      max_word_len = d;
    }
    if (d >= MAX_LEN) {
      ++cnt_max;
    } else {
      ++cnt[d];
    }
  } else {
    // Leere Positions-Liste ==> Zwischenknoten ohne Wort
    ++no_word_cnt;
  }
  int sons = 0;
  for (int i = 0; i <= UCHAR_MAX; ++i) {
    if (w->son[i] != NULL) {
      ++sons;
      rek_stat(w->son[i], d + 1);
    }
  }
  if (sons == 0) {
    ++no_son_cnt;
  }
}

// Gibt Statistiken über die Wörter im Baum aus
void statistics(void)
{
  rek_stat(root, 0);

  for (int i = 0; i < MAX_LEN; ++i) {
    if (cnt[i] > 0) {
      printf("%5d Worte mit Länge %2d (%6.2f %%)\n", cnt[i], i,
             (cnt[i] * 100) / ((double) total_words));
    }
  }
  if (cnt_max > 0) {
    printf("%5d Worte mit Länge >%2d (%6.2f %%), größte Länge %d\n", cnt_max,
           MAX_LEN, (cnt_max * 100) / ((double) total_words), max_word_len);
  }
  printf("Insgesamt %d Worte, mittlere Länge %5.2f\n", total_words,
         len_sum / ((double) total_words));
  printf("%d Zwischenknoten ohne Wort, %d Knoten ohne Sohn\n", 
         no_word_cnt, no_son_cnt);
}
#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[])
{
  prog_name = argv[0];

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

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

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

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

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

  exit(EXIT_SUCCESS);
}