// Übung zu Listen: Radixsort mit einfach verketteten Listen
//
// Aufruf: radixsort
//
// Klaus Kusche, 2018

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// wir sortieren NR_ELEMS viele Elemente mit je NR_DIGITS vielen Ziffern
const int NR_ELEMS = 20;
const int NR_DIGITS = 7;

// Klasse für ein einzelnes Element
class Elem
{
  // "Elem" soll nur innerhalb von "Bucket" verwendbar sein
  // wir machen daher alles in Elem privat (==> keiner kann darauf zugreifen)
  // und erklären Bucket zum Freund (==> aber Bucket darf alles)
  friend class Bucket;

  private:
    // Konstruktor:
    // Das neue Element bekommt die nächste fortlaufende Nummer
    // und hat vorläufig keinen Nachfolger
    Elem() : elem_nr(next_nr++), next(nullptr) {
      // speichere in allen Ziffern zufällige Werte von 0 bis 9
      for (int i = 0; i < NR_DIGITS; ++i) {
        key[i] = rand() % 10;
      }
    }

    // gib das Element aus
    void print() {
      cout << elem_nr << ":\t";
      for (int i = 0; i < NR_DIGITS; ++i) {
        cout << key[i];
      }
      cout << endl;
    }

    // klassenweites Member für die automatische Nummerierung:
    // Welche Nummer bekommt das nächste Element?
    static int next_nr;

    // Sortierschlüssel: NR_DIGITS einzeln gespeicherte Ziffern 0...9
    short int key[NR_DIGITS]; 
    int elem_nr;  // Nutzdaten: Fortlaufende Nummer des Elementes
    Elem *next;   // die Listen-Verkettung (Zeiger auf das nächste Element)
};

// Speicher für das klassenweite Member anlegen und initialisieren
int Elem::next_nr = 1;

// Klasse für einen Bucket (eine Liste)
class Bucket
{
  public:
    // Konstruktor:
    // Ein neuer Bucket wird auf "leer" initialisiert
    // (keine Elemente ==> head und tail sind beide der Nullpointer)
    Bucket() : head(nullptr), tail(nullptr) {}

    // removeFirst:
    // entfernt das erste Element aus unserer Liste (ohne es zu löschen)
    // und liefert einen Pointer auf das entfernte Element als Returnwert
    // bei leerer Liste liefert es nullptr
    Elem *removeFirst() {
      Elem *elem = head;
      if (elem != nullptr) {
        // der Nachfolger des entnommenen Elementes wird neuer head
        head = elem->next;  
      }
      return elem;
    }

    // append:
    // hänge das Element, auf das elem zeigt, hinten an die Liste
    void append(Elem *elem) {
      if (head == nullptr) {
        // die Liste war bisher leer
        // ==> elem wird neues erstes Element
        head = elem;
      } else {
        // die Liste hat schon Elemente
        // ==> elem wird Nachfolger des bisher letzten Elementes
        tail->next = elem;
      }
      // in beiden Fällen ist elem das neue letzte Element
      tail = elem;
      // ... und hat daher keinen Nachfolger
      elem->next = nullptr;
    }

    // append:
    // hänge alle Elemente von buck hinten an die eigene Liste an
    // (in der Reihenfolge, die sie in buck haben)
    // und setze buck dann auf "leer"
    void append(Bucket &buck) {
      // das könnte man mit einer Schleife elementweise machen
      // (mit removeFirst und dem append für einzelne Elemente)
      // aber das ist viel zu viel Arbeit
      // Wir hängen daher die Liste von buck als Ganzes um, nicht elementweise
      if (buck.head == nullptr) { // die Liste von buck ist leer
        return;                   // ==> nichts zu tun
      }
      if (head == nullptr) {
        // wenn unsere eigene Liste leer ist
        // wird das erste Element der Liste von buck unser erstes Element
        head = buck.head;
      } else {
        // sonst wird das erste Element von buck
        // der Nachfolger unseres letzten Elementes
        tail->next = buck.head;
      }
      // in beiden Fällen wird das letzte Element von buck unser letztes Element
      tail = buck.tail;
      // alle Elemente von buck hängen jetzt in unserer Liste
      // ==> die Liste von buck auf "leer" setzen
      buck.head = buck.tail = nullptr;
    }

    // sort:
    // sortiere unsere Liste mittels Radixsort
    void sort() {
      // unsere einzelnen Ziffern können Wert 0 bis 9 haben,
      // also brauchen wir 10 Hilfs-Buckets
      // zum Verteilen unserer Elemente nach Ziffern
      Bucket buck[10];
      int buck_num;
      // mach einen Sortier-Durchlauf pro Stelle bzw. Ziffer des Schlüssels,
      // und zwar von hinten (letzte Ziffer) nach vorn
      for (int pos = NR_DIGITS - 1; pos >= 0; --pos) {
        // Schritt 1: Verteilen unserer Elemente auf die Hilfs-Buckets
        for (;;) {
          // nimm das erste Element aus unserer Liste
          Elem *elem = removeFirst();
          // wenn keines mehr da ==> Schritt 1 fertig 
          if (elem == nullptr) break;
          // Ziffer im Element an Stelle pos = Nummer des zuständigen Bucket
          buck_num = elem->key[pos];
          // häng das Element hinten an diesen Hilfs-Bucket an
          buck[buck_num].append(elem);
        }
        // Schritt 2: Hilfs-Buckets wieder einsammeln
        // unsere eigene Liste ist jetzt leer
        // hänge die zehn Hilfs-Buckets der Reihe nach
        // (in aufsteigender Reihenfolge) an unsere eigene Liste an
        for (buck_num = 0; buck_num < 10; ++buck_num) {
          append(buck[buck_num]);
        }
        // jetzt sind wieder alle Elemente in unserer eigenen Liste,
        // sortiert nach der Ziffer an Stelle pos,
        // und die Hilfs-Buckets sind wieder alle leer
        // ==> bereit für den nächsten Durchlauf mit der Ziffer davor
      }
    }

    // fill:
    // füllt unsere Liste mit cnt vielen neu erzeugten Elementen
    // (diese bekommen beim Erzeugen zufällige Werte)
    void fill(int cnt) {
      for (int i = 0; i < cnt; ++i) {
        append(new Elem());
      }
    }

    // print:
    // Ausgabe aller Elemente
    void print() {
      // ... mit der üblichen Listen-Durchlauf-Schleife
      for (Elem *elem = head; elem != nullptr; elem = elem->next) {
        elem->print();
      }
      cout << endl;
    }

  private:
    Elem *head;  // Zeiger auf das erste Element
    Elem *tail;  // Zeiger auf das letzte Element
};

int main()
{
  // damit rand bei jedem Programmlauf andere Zahlen liefert
  srand(time(nullptr));  

  Bucket buck;

  buck.fill(NR_ELEMS);
  buck.print();
  
  buck.sort();
  buck.print();

  return 0;
}