// Cross-Reference-Liste, mit binärem Suchbaum (unbalanciert)
//
// Aufruf: xref-tree file ...
//
// Klaus Kusche, 2002, 2026

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

// Statistiken einschalten
#define PRINT_STAT 1

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

// "Pointer-auf-Pointer"-Variante verwenden
#define DBL_PTR 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) == '_'))

#ifdef PRINT_STAT 
// Max. Baumtiefe in der Statistik-Ausgabe
#define MAX_STAT_DEPTH 100
#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 Eintrags des Wortbaumes
typedef struct _word_entry {
  const char *text;          // Text des Wortes
  pos_entry *first_pos;      // Head der Positionsliste des Wortes
  pos_entry *last_pos;       // Tail der Positionsliste des Wortes
  struct _word_entry *left, *right; // Söhne des Knotens
} word_entry;


// Liefert einen Pointer auf n mit malloc angeforderte Bytes, mit Fehlerprüfung
void *my_malloc(size_t n);
// Liefert einen Pointer auf eine strdup-Kopie von s, mit Fehlerprüfung
char *save_str(const char *s);
// 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 Wortknoten
word_entry *new_word(const char *word, pos_entry *pos);
// 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 Baum, 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 Baum in Sortier-Reihenfolge aus
void rek_list(word_entry *w);
// Ermittelt rekursiv die Statistiken, d ... aktuelle Tiefe
void rek_stat(word_entry *w, int d);
// Gibt Statistiken über die Form des Baumes aus
void statistics(void);


// die Wurzel des Baumes
word_entry *root = NULL;

// 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 eine mit strdup angelegte Kopie von s,
// mit Fehlerprüfung, bei Fehler: Fehlermeldung und Programm-Abbruch
char *save_str(const char *s)
{
  char *p = strdup(s);

  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
// word ist das im Knoten einzutragende Wort, pos dessen erste Position
// Beide Söhne im neuen Knoten werden auf NULL gesetzt
//
// Achtung: word darf nicht direkt gespeichert werden
// (weil es auf den internen Zeilenpuffer von read_file zeigt
// und daher beim Lesen der nächsten Zeile überschrieben wird),
// sondern es muss eine dynamisch erzeugte *Kopie* im Knoten gespeichert werden!
word_entry *new_word(const char *word, pos_entry *pos)
{
  word_entry *w = (word_entry *) (my_malloc(sizeof (word_entry)));

  w->text = save_str(word);
  w->first_pos = w->last_pos = pos;
  w->left = w->right = NULL;  // ein neuer Baum-Knoten hat nie Söhne!

  return w;
}

// Hängt die Position pos *hinten* an die (nichtleere!) Positionsliste
// des Wortknotens wort an
void add_pos(pos_entry *pos, word_entry *word)
{
  word->last_pos->next = pos;
  word->last_pos = pos;
}

// Es wird mit new_pos ein neuer Positionseintrag
//   (filename/line_nr/col_nr) angelegt
//
// Dann wird das Wort word im Baum gesucht
// Gibt es das Wort noch nicht, wird mittels new_word
// ein neuer Worteintrag erzeugt (mit dem neuen Pos-Eintrag)
// und an der richtigen Stelle an den Baum angehängt
//
// Gibt es das Wort schon,
// wird der neue Pos-Eintrag mittels add_pos an dessen Positionsliste angehängt
#ifdef DBL_PTR
// Variante mit "Pointer auf Pointer"
void save_word(const char *filename, int line_nr, int col_nr, const char *word)
{
  // Wir brauchen in jedem Fall einen neuen Pos-Eintrag
  pos_entry *pos = new_pos(filename, line_nr, col_nr);

  // Zeiger auf den Zeiger zum aktuellen Word-Knoten:
  // Das kann root sein (beim allerersten Wort),
  // oder der left- oder right-Pointer des Vaterknotens.
  //
  // Wenn dort, wo p_w hinzeigt, ein NULL-Pointer steht,
  // gehört an dieser Stelle der Pointer
  // auf das neu angelegte Wort angehängt!
  word_entry **p_w = &root;

  // Suche das Wort im Baum
  for (;;) {
    // Zeiger auf den aktuellen Wort-Knoten
    // w = *p_w, d.h. w ist der Pointer aus der Speicherstelle,
    // auf die p_w gerade zeigt
    word_entry *w = *p_w;
    if (w == NULL) {
      // Aktueller Teilbaum ist leer ==> Wort nicht gefunden
      // Neuen Knoten anlegen: Er gehört dort angehängt, wo p_w hinzeigt
      *p_w = new_word(word, pos);
      return;
    }

    // strcmp ist aufwändig, nur einmal machen!
    int cmp = strcmp(word, w->text); 
    if (cmp < 0) {        // word ist kleiner als der aktuelle Knoten
      p_w = &(w->left);   // im linken Teilbaum weitersuchen
    } else if (cmp > 0) { // word ist größer als der aktuelle Knoten
      p_w = &(w->right);  // im rechten Teilbaum weitersuchen
    } else {
      // cmp == 0, Knoten word gefunden, neue Position dort dazuspeichern
      add_pos(pos, w);
      return;
    }
  }
}
#else
// Alternative ohne "word_entry **w;"
void save_word(const char *filename, int line_nr, int col_nr, const char *word)
{
  // Wir brauchen in jedem Fall einen neuen Pos-Eintrag
  pos_entry *pos = new_pos(filename, line_nr, col_nr);

  if (root == NULL) {
    // Leerer Baum: Neues Wort wird oberster Knoten
    root = new_word(word, pos);
    return;
  }
  
  word_entry *w = root;  // der aktuelle Knoten
  for (;;) {
    // strcmp ist aufwändig, nur einmal machen!
    int cmp = strcmp(word, w->text);  
    if (cmp < 0) {
      // neues Wort ist kleiner als Knoten w ==> muss links von Knoten w sein
      if (w->left == NULL) {
        // wenn dort nichts mehr ist: Neues Wort dort anhängen
        w->left = new_word(word, pos);
        return;
      } else {
        // sonst: im linken Teilbaum weitersuchen
        w = w->left;
      }
    } else if (cmp > 0) {
      // neues Wort ist größer als Knoten w ==> analog für rechts
      if (w->right == NULL) {
        w->right = new_word(word, pos);
        return;
      } else {
        w = w->right;
      }
    } else {
      // cmp == 0, Knoten word gefunden, neue Position dort dazuspeichern
      add_pos(pos, w);
      return;
    }
  }
}
#endif

// 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 Baum
// Gibt das Wort und seine Positionen (mittels list_pos)
// oder "nicht gefunden" aus
void process_word(const char *word)
{
  word_entry *w = root;
  while (w != NULL) {
    // strcmp ist aufwändig, nur einmal machen!
    int cmp = strcmp(word, w->text);
    if (cmp < 0) {
      w = w->left;
    } else if (cmp > 0) {
      w = w->right;
    } else {
      printf("*** %s:", word);
      list_pos(w);
      return;
    }
  }

  printf("*** %s: Not found! ***\n", word);
}

// 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 rekursiv alle Wörter im Baum in Sortier-Reihenfolge aus
void rek_list(word_entry *w)
{
  if (w == NULL) {
    return;
  }
  
  rek_list(w->left);
  printf("%s\n", w->text);
  rek_list(w->right);
}
#endif

#ifdef PRINT_STAT
// Globale Variablen für die Statistiken
int cnt[MAX_STAT_DEPTH];  // Anzahl der Knoten mit Tiefe i
int cnt_max;              // Anzahl der Knoten mit Tiefe >= MAX_STAT_DEPTH
int total;                // Anzahl der Knoten insgesamt
int sum_d;                // Summe der Tiefe aller Knoten
int max_depth;            // Größte Tiefe

// Ermittelt rekursiv die Statistiken, d ... aktuelle Tiefe
void rek_stat(word_entry *w, int d)
{
  if (w == NULL) {
    return;
  }
  
  ++total;
  sum_d += d;
  
  if (d > max_depth) {
    max_depth = d;
  }
  
  if (d >= MAX_STAT_DEPTH) {
    ++cnt_max;
  } else {
    ++cnt[d];
  }
  
  rek_stat(w->left, d + 1);
  rek_stat(w->right, d + 1);
}

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

  for (int i = 0; i < MAX_STAT_DEPTH; ++i) {
    if (cnt[i] > 0) {
      printf("%5d Worte mit Tiefe  %2d (%6.2f %%)\n", cnt[i], i,
             (cnt[i] * 100) / ((double) total));
    }
  }
  if (cnt_max > 0) {
    printf("%5d Worte mit Tiefe >%2d (%6.2f %%), größte Tiefe %d\n", cnt_max,
           MAX_STAT_DEPTH, (cnt_max * 100) / ((double) total), max_depth);
  }

  // Berechnung der optimalen Tiefe = vollständiger, balanzierter Baum
  int tiefe;      // Aktuelle Tiefe im Baum
  int pot = 1;    // Nächste Zweierpotenz = Anzahl der Knoten der nächsten Ebene
  int opt_sum_d = 0;  // Summe der Tiefe aller Knoten der bisherigen Ebenen
  int rest = total;   // Anzahl der verbleibenden Knoten
  // Summiere alle vollständigen Ebenen im Baum auf
  for (tiefe = 0; pot <= rest; ++tiefe) {
    opt_sum_d += pot * tiefe;
    rest -= pot;
    pot *= 2;
  }
  // addiere die Tiefen der letzten, unvollständigen Ebene
  opt_sum_d += rest * tiefe;
  
  printf("Insgesamt %d Worte, mittlere Tiefe %5.2f (optimal: %5.2f)\n",
         total, sum_d / ((double) total), opt_sum_d / ((double) total));
}
#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];

  // 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);
#endif

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

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

  exit(EXIT_SUCCESS);
}