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

// assert() muss *immer* Code generieren ==> NDEBUG abschalten!
#undef NDEBUG

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

// Statistiken einschalten
#define PRINT_STAT 1

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

// Rekursive Konsistenzprüfung des Baumes einschalten
#define CHECK_TREE 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
  int bal;                   // Balance: 0 ... balanciert
                             // -1 ... linkslastig, 1 ... rechtslastig
  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);
// Hilfsfunktionen zum Balancieren: Rotiere den Baum
void right_rot(word_entry **root_ptr);
void left_rot(word_entry **root_ptr);
// Rekursive Hilfsfunktion für save_word
int save_word_rek(word_entry **root_ptr, pos_entry *pos, const char *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
// Prüft den Baum mit Wurzel w rekursiv
int rek_check(word_entry *w);
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->bal = 0;   // Neue Knoten sind Blätter, Blätter haben Balance 0
  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;
}

// Hilfsfunktionen zum Balancieren: Rotiere den Baum,
// auf den *root_ptr zeigt, nach rechts
void right_rot(word_entry **root_ptr) 
{
  // Die Wurzel des aktuell betrachteten Teilbaumes
  // = der Knoten, auf den *root_ptr zeigt
  word_entry *w = *root_ptr;
  // Deren linker Sohn (zu hohe Seite)      
  word_entry *left = w->left;  
  if (left->bal == 1) {
    // Höhere Seite hängt nach innen schief ==> Doppel-Rotation
    // left_right = Innerer (rechter) Sohn von left
    word_entry *left_right = left->right;
    // Wenn left_right nach links hängt,
    // so ist der neue rechte Teilbaum rechtslastig, sonst balanciert
    // Wenn left_right nach rechts hängt,
    // so ist der neue linke Teilbaum linkslastig, sonst balanciert
    // Ist left_right balanciert, sind es auch beide neuen Teilbäume
    w->bal = (left_right->bal == -1) ? 1 : 0;
    left->bal = (left_right->bal == 1) ? -1 : 0;
    // Die neue Wurzel ist immer balanciert
    left_right->bal = 0;
    // Rotiere: left_right wird neue Wurzel,
    // die Wurzel wird rechter Sohn und bekommt links left_right's rechten Baum
    // left wird linker Sohn und bekommt rechts left_right's linken Baum
    w->left = left_right->right;
    left->right = left_right->left;
    left_right->left = left;
    left_right->right = w;
    *root_ptr = left_right;
  } else {
    // Höhere Seite hängt nach außen schief ==> Einfache Rotation
    // Beim Löschen könnte das Ergebnis unbalanciert sein,
    // aber beim Einfügen sind die Knoten danach immer balanciert
    w->bal = 0;
    left->bal = 0;
    // Rotiere: left wird Wurzel,
    // die Wurzel wird deren rechter Sohn und bekommt links left's rechten Baum
    w->left = left->right;
    left->right = w;
    *root_ptr = left;
  }
}

// Dasselbe für Rotationen nach links
void left_rot(word_entry **root_ptr) 
{
  // Die Wurzel des aktuell betrachteten Teilbaumes
  // = der Knoten, auf den *root_ptr zeigt
  word_entry *w = *root_ptr;
  // Deren rechter Sohn (zu hohe Seite)      
  word_entry *right = w->right;
  if (right->bal == -1) {
    // Höhere Seite hängt nach innen schief ==> Doppel-Rotation
    // right_left = Innerer (linker) Sohn von right
    word_entry *right_left = right->left;
    // Wenn right_left nach rechts hängt,
    // so ist der neue linke Teilbaum linkslastig, sonst balanciert
    // Wenn right_left nach links hängt,
    // so ist der neue rechts Teilbaum rechtslastig, sonst balanciert
    // Ist right_left balanciert, sind es auch beide neuen Teilbäume
    w->bal = (right_left->bal == 1) ? -1 : 0;
    right->bal = (right_left->bal == -1) ? 1 : 0;
    // Die neue Wurzel ist immer balanciert
    right_left->bal = 0;
    // Rotiere: right_left wird neue Wurzel,
    // die Wurzel wird linker Sohn und bekommt rechts right_left's linken Baum
    // right wird rechter Sohn und bekommt links right_left's rechten Baum
    w->right = right_left->left;
    right->left = right_left->right;
    right_left->right = right;
    right_left->left = w;
    *root_ptr = right_left;
  } else {
    // Höhere Seite hängt nach außen schief ==> Einfache Rotation
    // Beim Löschen könnte das Ergebnis unbalanciert sein,
    // aber beim Einfügen sind die Knoten danach immer balanciert
    w->bal = 0;
    right->bal = 0;
    // Rotiere: right wird Wurzel,
    // die Wurzel wird deren linker Sohn und bekommt rechts right's linken Baum
    w->right = right->left;
    right->left = w;
    *root_ptr = right;
  }
}

// Rekursive Hilfsfunktion für save_word: root_ptr zeigt auf den Pointer,
// an dem der Teilbaum hängt, in dem das Wort sein müsste
// (das kann root oder der left- oder right-Pointer des Vaterknotens sein)
// word ist das Wort, pos die neue Position
//
// Ist *root_ptr NULL, wird das Wort dort als neues Blatt eingehängt
//
// Die Funktion balanciert wenn notwendig den Teilbaum, auf den *root_ptr zeigt
//
// Returnwert ist 1, wenn der Baum gewachsen ist, und 0 sonst
int save_word_rek(word_entry **root_ptr, pos_entry *pos, const char *word)
{
  if (*root_ptr == NULL) {
    *root_ptr = new_word(word, pos); // Neuen Knoten anlegen und dort anhängen
    return 1;                        // Teilbaum ist gewachsen (von 0 auf 1)
  } else {
    // Die Wurzel des aktuell betrachteten Teilbaumes
    // = der Knoten, auf den *root_ptr zeigt
    word_entry *w = *root_ptr;       
    // strcmp ist aufwändig, nur einmal machen!
    int cmp = strcmp(word, w->text);
    if (cmp < 0) {
      // links einfügen
      if (save_word_rek(&(w->left), pos, word) == 1) {
        // Linker Teilbaum ist gewachsen
        if (w->bal == -1) {
          // Baum hing schon nach links, neue Balance -2 ==> Rotation notwendig!
          right_rot(root_ptr);
          return 0; // nach der Rotation ist die Höhe gleichgeblieben
        } else if (w->bal == 0) {
          // Baum war bisher balanciert ==> Wird höher und hängt jetzt nach links
          w->bal = -1;
          return 1;
        } else {
          // Baum hing bisher nach rechts ==> Wird ausgeglichen, bleibt gleich hoch
          w->bal = 0;
          return 0;
        }
      } else {
        // Baum ist gleich hoch geblieben ==> nichts zu tun
        return 0;
      }
    } else if (cmp > 0) {
      // rechts einfügen
      if (save_word_rek(&(w->right), pos, word) == 1) {
        // Rechter Teilbaum ist gewachsen
        if (w->bal == 1) {
          // Baum hing schon nach rechts, neue Balance 2 ==> Rotation notwendig!
          left_rot(root_ptr);
          return 0; // nach der Rotation ist die Höhe gleichgeblieben
        } else if (w->bal == 0) {
          // Baum war bisher balanciert ==> Wird höher und hängt jetzt nach rechts
          w->bal = 1;
          return 1;
        } else {
          // Baum hing bisher nach links ==> Wird ausgeglichen, bleibt gleich hoch
          w->bal = 0;
          return 0;
        }
      } else {
        // Baum ist gleich hoch geblieben ==> nichts zu tun
        return 0;
      }
    } else {
      // cmp == 0, Knoten word gefunden, neue Position dort dazuspeichern
      add_pos(pos, w);
      return 0;   // Baum hat sich nicht verändert
    }
  }
}

// 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
void save_word(const char *filename, int line_nr, int col_nr, const char *word)
{
  // Wir brauchen in jedem Fall einen neuen Pos-Eintrag
  save_word_rek(&root, new_pos(filename, line_nr, col_nr), word);
}

// 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 CHECK_TREE
// Prüft den Baum mit Wurzel w (darf nicht NULL sein) rekursiv
// 1. Stimmt die Sortier-Reihenfolge?
// 2. Stimmt die Balance und das Feld bal?
// Returnwert ist die Höhe des Baumes
int rek_check(word_entry *w)
{
  int l_height, r_height;
  
  if (w->left == NULL) {
    l_height = 0;
  } else {
    assert(strcmp(w->left->text, w->text) < 0);
    l_height = rek_check(w->left);
  }
  if (w->right == NULL) {
    r_height = 0;
  } else {
    assert(strcmp(w->right->text, w->text) > 0);
    r_height = rek_check(w->right);
  }

  assert(r_height - l_height == w->bal);
  return ((w->bal <= 0) ? l_height : r_height) + 1;
}
#endif

#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 CHECK_TREE
  // Konsistenz des Baumes prüfen
  if (root != NULL) {
    rek_check(root); 
  }
#endif

#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);
}