#include <stdio.h>
#include <stdlib.h>
#include "btree.h"

/*
 * Fußnotensortierprogramm optimiert auf die Aufgabe aus dem Linux-Magazin
 * Ausgabe 10/08 Seite 30ff
 *
 * Beschränkungen: max. 2^32 Fußnoten, größte max. Nummerierung: 2^32.
 *                 Je nach Vorsortierung max. 2^32 bytes Fußnoten oder mehr, 
 *                 bzw. beschränkt durch RAM.
 *
 * Funktionsweise:
 * Gelesen wird von stdin, ausgegeben auf stdout. Es gibt keine Hilfe oder
 * sonstige sinnvolle Ausgaben.
 *
 * Ich bin kein Programmierer und daher... öhm, sieht der Code
 * etwas Grauenhaft aus?? k.A.
 * Nach fast einem Tag Arbeit (ich wollte halt nur mal ein wenig C lernen, da
 * war mir das ganze hier Recht) hab ich jetzt auch keine Lust mehr, nochmal
 * drüberzugucken und noch Teile in Funktionen auszulagern etc.
 *
 * Meinen Teil hab ich mal (denke ich) auf geringen Speicherverbrauch
 * optimiert. Daher Langsamer durch häufiges freigeben
 * auch kleiner nicht benötigter Speicherbereiche(?). Speicherverbrauch ohne
 * b-Baum(*altzuneu) im ungünstigsten Fall etwas mehr als der untere Teil der
 * Eingabedatei, oder?
 * Die Verwendete btree Implementierung ist nicht von mir und daher u.U. 
 * deutlich Speicherintensiver. k.A., hab keine Lust mehr noch selber was zu
 * implementieren ;-)
 *
 * Lizenz dieser Datei: Public Domain
 * Lizenz btree.c und btree.h: GPL v2.
 *
 * BUGs: Ich nutze eine btree-implementierung, die ich auf der LKML gefunden
 *       habe. Diese steht unter der GPL v2. Ich musste eine Zeile hinzufügen,
 *       da diese sonst nachvollziehbar Segfaults bei btree_search() lieferte.
 *
 *       Wenn im Text irgendwo ein [XXX] auftaucht, wo XXX eine beliebige Zahl
 *       ist, aber [XXX] keinen Verweis auf eine Fußnote darstellt, wird dafür
 *       ein Verweis angelegt (die Zahl XXX also geändert), und in der
 *       Fußnotenliste dafür die originale Zahl wieder angegeben.
 */

//globale Variablen
int alloziierterspeicher = 0;
int *neuzualt; //flacher speicher für mapping neu->alt
int laufendenummer = 0;
btree *altzuneu; //btree für mapping alt->neu
char **fussnoten;

//funktionen für die btree-lib
unsigned int value(void * key)
{
  return *(int *)key;
}
unsigned int keysize(void * key)
{
  return sizeof(int);
}
unsigned int datasize(void * data)
{
  return sizeof(int);
}

/*
 * fehler ausgeben und programm beenden
 */
fehler(char * fehlermeldung)
{
  printf(fehlermeldung);
  exit(1);
}

/*
 * Es wurde eine Fußnote im Text gefunden. Diese sollte eine neue Nummer 
 * bekommen und in die Korrespondenztabelle der alten eingefügt werden.
 */
int fn_einfuegen(char* altenummer_s)
{
  int altenummer,i,neuenummer;
  bt_key_val * kv = NULL;

  //falls Speicher knapp wird, neuen alloziieren.
  if (alloziierterspeicher<(laufendenummer+1))
  {
    if (alloziierterspeicher==0)
    {
      neuzualt=(int *)malloc(64*sizeof(int));
      if (neuzualt==NULL) fehler("malloc: zu wenig speicher");
      alloziierterspeicher=64;
    }
    else
    {
      alloziierterspeicher=alloziierterspeicher+(alloziierterspeicher);
      neuzualt=(int *)
                   realloc(neuzualt,alloziierterspeicher*sizeof(int));
      if (neuzualt==NULL) fehler("realloc: zu wenig speicher");
    }
  }

  altenummer = atoi(altenummer_s);

  //alte nummer schon aufgetreten?
  if (laufendenummer>0)
  {
    kv = btree_search(altzuneu, &altenummer);
  }
  if (kv!=NULL)
  { //schon da -> vorhandene neue ausgeben
    return *(int *) kv->val;
  }
  else 
  { //noch nicht da -> anfügen
    neuenummer = ++laufendenummer;
    kv = (bt_key_val*)malloc(sizeof(*kv));
    kv->key = malloc(sizeof(int));
    *(int *)kv->key = altenummer;
    kv->val = malloc(sizeof(int));
    *(int *)kv->val = neuenummer;
    btree_insert_key(altzuneu,kv);
 
    neuzualt[neuenummer]=altenummer;

    return neuenummer; //TODO: neuenummer->laufendenummer
  }
  //return 100; unreachable
}

/*
 * Eine Klammer wurde im Text erkannt. Nun wird geprüft, ob dies auch eine
 * Fußnote ist und diese ggf. aufgenommen.
 */
void klammer_im_text()
{
  char fussnotennummer[10];
  int i = 0, neuenummer; char c;
  c=getchar();
  while (c>=48 && c<=57 && i<10)
  {
    fussnotennummer[i]=c;
    i++;
    c=getchar();
  }
  fussnotennummer[i]=0;
  if (c==93 && i>0)
  {
    neuenummer = fn_einfuegen(fussnotennummer);
    printf("[%i]",neuenummer);
    return; //neue Nummer eingefügt und ausgegeben.
  }

  // ist keine Fußnote, der hier eingelesene Text wird ausgegeben
  printf("[%s",fussnotennummer);
  putchar(c);
  
}

int fussnoten_folgen()
{
  char trenntext[10] = "footnotes:";
  char c; int i,j;
  for (i=0; i<10; i++)
  {
    c=getchar();
    if (c!=trenntext[i])
    {
      putchar('@');
      for (j=0; j<i; j++)
        putchar(trenntext[j]);
      putchar(c);
      return 0;
    }
  }
  return 1;
}

int main()
{
  char c;
  int i,infussnote=0,altenummer,aktuellefussnotenmaxlaenge=0;
  int aktuellefussnote=0,aktuellefussnotenlaenge=0,maxausgegebenefn=0;
  char fussnotennummer[10];
  bt_key_val * kv; //für btree_search

  //btree lib initialisieren
  altzuneu = btree_create(3);
  altzuneu->value = value;
  altzuneu->key_size = keysize;
  altzuneu->data_size = datasize;

  //ab hier der obere Teil (Textmodus)
  while ((c=getchar())!=EOF)
  {
    if (c==91) klammer_im_text();
    else if (c==64) {if (fussnoten_folgen()) break;}
    else putchar(c);
  }

  //neuzualt-Speicher aufs nötigte schrumpfen
  neuzualt=(int *)realloc(neuzualt,laufendenummer*sizeof(int));
  //Speicher für die Zeiger auf die Fußnoten alloziieren.
  fussnoten=(char **)malloc(laufendenummer*sizeof(char*));
  //TODO:hier wird 1*sizeof(int) verschenkt, da fussnoten[0] nie vorkommen wird

  //ab hier der untere Teil (Fußnotenmodus)
  printf("@footnotes:");

  alloziierterspeicher = 0;

  while ((c=getchar())!=EOF)
  {
    if (c==91) 
    {
      i=0;
      c=getchar();
      while (c>=48 && c<=57 && i<10)
      {
        fussnotennummer[i]=c;
        i++;
        c=getchar();
      }
      fussnotennummer[i]=0;
      if (c==93 && i>0) //fussnotenanfang gefunden
      {
        if (aktuellefussnote) //string beenden
          fussnoten[aktuellefussnote][aktuellefussnotenlaenge++]=0;
        if (aktuellefussnotenmaxlaenge>aktuellefussnotenlaenge
            && aktuellefussnote) //TODO: schrumpfen könnte man auch nach ausg.
        { //platz für alte fußnote zurechtschrumpfen
	  fussnoten[aktuellefussnote]=(char *)realloc(
             fussnoten[aktuellefussnote],aktuellefussnotenlaenge*sizeof(char));
        }
        //prüfen, ob vor dieser fn schon alle anderen ausgegeben wurden
        if (maxausgegebenefn==aktuellefussnote-1)
        { //ja, es können weitere fussnoten ausgegeben werden
          while (fussnoten[aktuellefussnote])
          {
            printf("[%i]%s",aktuellefussnote,fussnoten[aktuellefussnote]);
            free(fussnoten[aktuellefussnote]);
            fussnoten[aktuellefussnote]=NULL;
            maxausgegebenefn++;
            aktuellefussnote++;
          }
        }
        aktuellefussnotenlaenge=0;
        aktuellefussnotenmaxlaenge=0;
        altenummer = atoi(fussnotennummer);
        kv = btree_search(altzuneu, &altenummer);
	if (kv==NULL)
	{
	  printf("[unreferenziert]");
          aktuellefussnote = 0;
	} else //kv!=NULL
	{
          aktuellefussnote = *(int *) kv->val;
	}
      } else
      {
        //TODO: schon gelesene nicht-fußnoten-nummer wieder ausgeben
        printf("TODO");
      }
    }
    else if (aktuellefussnote)
    { //in fussnote: gelesenes zeichen laden
      if (aktuellefussnotenmaxlaenge==0)
      {
	aktuellefussnotenmaxlaenge=256;
        fussnoten[aktuellefussnote]=(char *)
                  malloc(aktuellefussnotenmaxlaenge*sizeof(char));
      } else if (aktuellefussnotenmaxlaenge<aktuellefussnotenlaenge+1)
      {
        aktuellefussnotenmaxlaenge=aktuellefussnotenmaxlaenge+256;
	fussnoten[aktuellefussnote]=(char *) realloc(
          fussnoten[aktuellefussnote],aktuellefussnotenmaxlaenge*sizeof(char));
      }
      fussnoten[aktuellefussnote][aktuellefussnotenlaenge]=c;
      aktuellefussnotenlaenge++;
    }
    else putchar(c); //wenn nicht in einer referenzierten Fußnote
  }
  if (aktuellefussnote) //string beenden
    fussnoten[aktuellefussnote][aktuellefussnotenlaenge++]=0;
  for (i=maxausgegebenefn+1;i<=laufendenummer;i++)
    if (fussnoten[i]==NULL)
      printf("[%i] Alte Zahl: %i\n",i,neuzualt[i]);
    else
      printf("[%i]%s",i,fussnoten[i]);

  return 0;
}