// Textfile zeilenweise sortieren (qsort)
// mit Zeilennummern
// mit dyn. Daten für die Zeilentexte und das Zeilenarray
// mit File-I/O für Zeilen beliebiger Länge ("schöne" Variante)
// 
// Aufruf: textsort-dyn3 [infile [outfile]]
// Ist kein Filename angegeben, wird stdin bzw. stdout verwendet
// 
// Klaus Kusche, 2010

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

// Max. Länge für das Einlesen mit fgets (incl. \n\0) 
#define FGETS_LEN 4096

// Anzahl der beim ersten malloc angelegten Zeilen
#define FIRST_MALLOC 100

// Struktur für unser Array von Zeilen
typedef struct {
  const char *text;   // Zeiger auf den dynamisch angelegten Text der Zeile
  int lineNr;         // Zeilennummer der Zeile
} line_t;

const char *progName;  // Der Programmname (argv[0]), für Fehlermeldungen

void *checkMalloc(void *p);
void errMsg(const char *operation, const char *fileName);
int lineCmp(const void *p1, const void *p2);
char *strAppend(char *dest, const char *src);
char *readLine(FILE *inFile);

// Prüfe das Ergebnis von malloc und strdup: Darf nicht NULL sein!
void *checkMalloc(void *p)
{
  if (p == NULL) {
    fprintf(stderr, "%s: out of memory\n", progName);
    exit(EXIT_FAILURE);
  }
  return p;
}

// Gib eine schöne Fehlermeldung aus und beende das Programm
// operation ... wobei ist der Fehler passiert?
// fileName  ... welcher File war betroffen?
void errMsg(const char *operation, const char *fileName)
{
  fprintf(stderr, "%s: error %s %s: %s\n",
          progName, operation, fileName, strerror(errno));
  exit(EXIT_FAILURE);
}

// Vergleichsfunktion für qsort
// p1 und p2 zeigen auf die zu vergleichenden Elemente des Arrays "lines"
// Diese Elemente sind Strukturen,
// und die Zeilentexte, auf die die Member "text" dieser beiden struct's zeigen,
// müssen verglichen werden
int lineCmp(const void *p1, const void *p2)
{
// Möglichkeit 1:
  //const line_t *s1 = (const line_t *) p1;
  //const line_t *s2 = (const line_t *) p2;
  //return strcmp(s1->text, s2->text);

// Möglichkeit 2:
  return strcmp(((const line_t *) p1)->text,
                ((const line_t *) p2)->text);
}

// Vergrößere den dyn. angelegten String dest und hänge src hinten an
// Ergebnis: Pointer auf den neuen dest
char *strAppend(char *dest, const char *src)
{
  // Länge des Ergebnisses berechnen, + 1 für Ende-Markierung
  // size_t ist der Standard-int-Typ für Längen (meist unsigned long int)
  size_t len = strlen(dest) + strlen(src) + 1;
  // dynamischen Ergebnis-String vergrößern
  dest = (char *) checkMalloc(realloc(dest, len));
  // neues Stück an das Ergebnis anhängen
  strcat(dest, src);

  return dest;
}

// Lies eine Zeile (egal wie lange) bis und incl. \n aus inFile
// Liefert einen Pointer auf eine dynamisch angelegte Kopie der gelesenen Zeile
// oder NULL, wenn nichts mehr gelesen werden konnte
char *readLine(FILE *inFile)
{
  char line[FGETS_LEN];       // String für das Einlesen mit fgets

  if (!fgets(line, sizeof(line), inFile)) {
    // schon das erste Lesen schlägt fehlt ==> Nichts gelesen, Fehler-Return
    return NULL;
  }
  // es wurde etwas gelesen ==> in dynamischen String kopieren
  char *result = (char *) checkMalloc(strdup(line));

  // solange line kein \n enthält: Nächstes Stück der Zeile lesen und dazufügen
  // (man könnte auch result prüfen, aber line prüfen ist schneller)
  while (strchr(line, '\n') == NULL) {
    if (!fgets(line, sizeof(line), inFile)) {
      // Kein nächstes Stück mehr lesbar (Datei zu Ende?)
      // Ergebnis-String hat noch kein \n
      // ==> häng eins an und returniere das Ergebnis
      return strAppend(result, "\n");
    }
    result = strAppend(result, line);
  }

  return result;
}

int main(int argc, const char *argv[])
{
  FILE *inFile, *outFile;               // Eingabe-File und Ausgabe-File
  const char *inFileName, *outFileName; // Filenamen der beiden Files

  progName = argv[0];
  if (argc > 3) {
    fprintf(stderr, "Aufruf: %s [infile [outfile]]\n", progName);
    exit(EXIT_FAILURE);
  }

  // mach den File auf, wenn auf der Befehlszeile ein Filenamen angegeben wurde
  // verwende stdin bzw. stdout, wenn kein Filenamen angegeben wurde
  if (argc >= 2) {
    inFileName = argv[1];
    if ((inFile = fopen(inFileName, "r")) == NULL) {
      errMsg("opening (for reading)", inFileName);
    }
  } else {
    inFileName = "stdin";
    inFile = stdin;
  }

  if (argc >= 3) {
    outFileName = argv[2];
    if ((outFile = fopen(outFileName, "w")) == NULL) {
      errMsg("opening (for writing)", outFileName);
    }
  } else {
    outFileName = "stdout";
    outFile = stdout;
  }

  line_t *lines;            // Pointer auf den Anfang des dynamischen Arrays
                            // mit den einzelnen Zeilen-struct's

  // size_t ist der Standard-int-Typ für Längen (meist unsigned long int)
  size_t lineCnt;           // Anzahl der belegten Zeilen in lines
  size_t lineSize;          // Allokierte Größe von lines

  lineSize = FIRST_MALLOC;
  lines = (line_t *) checkMalloc(malloc(lineSize * sizeof(line_t)));

  // Input zeilenweise verarbeiten bis der File zu Ende ist, mitzählen
  for (lineCnt = 0; ; ++lineCnt) {
    char *line = readLine(inFile);
    // Lesefehler oder File zu Ende?
    if (!line) break;

    if (lineCnt == lineSize) {
      // kein freies Element mehr in lines ==> größer machen!
      // (nicht jedesmal um eine Zeile, sondern gleich doppelt so groß)
      lineSize *= 2;
      lines = (line_t *) checkMalloc(realloc(lines, lineSize * sizeof(line_t)));
    }

    // line ist schon dynamisch angelegt, nicht noch einmal kopieren!
    lines[lineCnt].text = line;
    lines[lineCnt].lineNr = lineCnt + 1;  // "Menschliche" Zeilennummern ab 1
  }

  // Hat das fgets NULL geliefert,
  // weil das File-Ende erreicht wurde,
  // oder weil ein Fehler aufgetreten ist?
  if (ferror(inFile)) {
    errMsg("reading", inFileName);
  }
  if (fclose(inFile) == EOF) {
    errMsg("closing", inFileName);
  }

  // sortieren, Elementgröße = Größe einer Struktur
  qsort(lines, lineCnt, sizeof(line_t), lineCmp);

  // zeilenweise ausgeben, Schleife läuft mit Pointer über das Array lines
  for (line_t *p = lines; p < lines + lineCnt; ++p) {
    // p zeigt auf eine Struktur
    // ==> die Member ausgeben
    if (fprintf(outFile, "%08d: %s", p->lineNr, p->text) < 0) {
      errMsg("writing", outFileName);
    }
  }

  if (fclose(outFile) == EOF) {
    errMsg("closing", outFileName);
  }
  
  exit(EXIT_SUCCESS);
}