// Radix-Sort auf zufälligen Strings
//
// Aufruf: radix anzahl
// 
// Klaus Kusche, 2011

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Länge des Sortierschlüssels (Anzahl der Zeichen ohne \0)
#define TEXTLEN 7
// Wertebereich pro Zeichen des Sortierschlüssels:
// 0-127 (nur ASCII, keine Umlaute)
// eigentlich nur 32-126 (druckbare Zeichen),
// aber die Elemente 0-31 und 127 bleiben einfach leer
#define CHOICES 128

const char *progName;

// Ein zu sortierendes Element
typedef struct _entry {
  struct _entry *next;      // Listenverkettung
  char data[TEXTLEN + 1];   // Sortierschlüssel: Text fixer Länge
} entry;

// Kopf der einfach verketteten Liste aller Elemente
entry *head = NULL;

// speichere eine zufällig generierte Liste mit anzahl Elementen in head 
void createData(int anzahl);
// sortiere die Liste in head
void sortData(void);
// gib die Liste in head aus
void printData(void);

void createData(int anzahl)
{
  // Liste der Zeichen, aus denen wir zufällig unsere Daten zusammenbauen
  const char chars[] = " 0123456789abcdefghijklmnopqrstuvwxyz";
  entry *p;
  int pos;
  
  srand((unsigned int)(time(NULL)));

  head = NULL;
  for ( ; anzahl > 0; --anzahl) {
    p = (entry *) (malloc(sizeof(entry)));
    if (p == NULL) {
      fprintf(stderr, "%s: Cannot allocate %lu bytes of memory\n",
              progName, sizeof(entry));
      exit(EXIT_FAILURE);
    }
    // String zufällig füllen und terminieren
    for (pos = 0; pos < TEXTLEN; ++pos) {
      p->data[pos] = chars[rand() % (sizeof(chars) - 1)];
                     // - 1, damit das '\0' am Ende von chars nicht gewählt wird
    }
    p->data[TEXTLEN] = '\0';
    p->next = head;
    head = p;
  }
}

void sortData(void)
{
  // Eine Liste pro möglichem Zeichen
  entry *heads[CHOICES], *tails[CHOICES];

  int c;
  int pos;
  entry *p, *tail;

  // Ein Umlauf pro Stelle des Sortierschlüssels, von hinten nach vorne!
  for (pos = TEXTLEN - 1; pos >= 0; --pos) {
    // Listen pro Buchstabe auf "leer" initialisieren
    for (c = 0; c < CHOICES; ++c) {
      heads[c] = tails[c] = NULL;
    }

    // Hauptliste auf Listen pro Buchstabe aufteilen
    for (p = head; p != NULL; p = p->next) {
      c = (p->data)[pos];
      if (heads[c] == NULL) {
        heads[c] = tails[c] = p;
      } else {
        tails[c] = tails[c]->next = p;
      }
    }

    // Listen pro Buchstabe zu neuer Hauptliste zusammenhängen
    head = NULL;
    for (c = 0; c < CHOICES; ++c) {
      if (heads[c] != NULL) {   // nur nichtleere Listen berücksichtigen!
        if (head == NULL) {     // Erste Liste wird Anfang der Hauptliste
          head = heads[c];
          tail = tails[c];
        } else {                // Liste hinten an Hauptliste anhängen
          tail->next = heads[c];
          tail = tails[c];
        }
      }
    }
    // Ende der Hauptliste markieren
    if (head != NULL) {
      tail->next = NULL;
    }
  }
}

void printData(void)
{
  entry *p;

  for (p = head; p != NULL; p = p->next) {
    fputs(p->data, stdout);
    putchar('\n');
  }
}

int main(int argc, const char *argv[])
{
  int anzahl;

  if ((argc != 2) || ((anzahl = atoi(argv[1])) < 0)) {
    fprintf(stderr, "Usage: %s anzahl\n", argv[0]);
    exit(EXIT_FAILURE);
  }
  progName = argv[0];

  createData(anzahl);
  sortData();
  printData();

  exit(EXIT_SUCCESS);
}