// Topologisches Sortieren, grafisch
// Null-Knoten hinten statt vorne anhängen
//
// Aufruf: topsort knotenzahl kantendichte
// (kantendichte in Prozent)
//
// Klaus Kusche, 2012

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

#include "sdlinterf.h"

// maximale Knoten-Anzahl (mehr lassen sich schlecht darstellen)
#define MAX_NODES (SDL_Y_SIZE / 10)

// Struktur für einen Knoten des Graphen
typedef struct {
  // die Knoten haben keine Nutzdaten,
  // jeder Knoten repräsentiert eine Nummer (sein Index im Knoten-Array)
  int pos;   // Position des Knotens im topologisch sortierten Output
  int cnt;   // Für Topsort: Anzahl der Vorgänger
  int next;  // Für Topsort: Array-Index des nächsten Knotens
             // in der Liste aller Knoten ohne Vorgänger
} node_t;

int nodeCnt;                       // Anzahl der Knoten
int edgePcnt;                      // Prozent Kantendichte
node_t nodes[MAX_NODES];           // unser Knoten-Array
bool edges[MAX_NODES][MAX_NODES];  // unsere Kanten (gerichtete Adjazenzmatrix,
                                   // Zeile = von-Knoten, Spalte = nach-Knoten

// zeichne das Array
void paint(void);
// gib dem Knoten mit der Nummer oldPos schrittweise die Nummer newPos
// zeichne jeden Zwischenschritt
void animate(int oldPos, int newPos);
// fülle Knotenarray und Kanten-Matrix
void init(void);
// topologisches Sortieren
void topsort(void);

// zeichne das Array
void paint(void)
{
  // Abstand zwischen Knoten
  int xDist = SDL_X_SIZE / nodeCnt;
  int yDist = SDL_Y_SIZE / nodeCnt;
  // Abstand des ersten Knotens vom Rand
  int xOffs = (SDL_X_SIZE - xDist * (nodeCnt - 1)) / 2;
  int yOffs = (SDL_Y_SIZE - yDist * (nodeCnt - 1)) / 2;

  int i, j, pi, pj, k;

  sdlSetBlack();
  
  // zeichne die Knoten
  for (i = 0; i < nodeCnt; ++i) {
    if (nodes[i].cnt == 0) {
      sdlDrawCirc(xOffs + i * xDist, yOffs + nodes[i].pos * yDist,
                  3, 3, 0, 255, 255);
    } else {
      sdlDrawCirc(xOffs + i * xDist, yOffs + nodes[i].pos * yDist,
                  3, 3, 255, 0, 0);
    }
  }
  
  // zeichne die Kanten
  for (i = 0; i < nodeCnt; ++i) {
    pi = nodes[i].pos;
    for (j = 0; j < nodeCnt; ++j) {
      if (edges[i][j]) {
        pj = nodes[j].pos;
        // Kante geht von i nach j!
        if (i < j) {
          if (pi < pj) {
            sdlDrawCircPart(xOffs + i * xDist, yOffs + pj * yDist,
                            (j - i) * xDist, (pj - pi) * yDist,
                            0, 255, 0, SDL_CIRC_UPPER_RIGHT);
            for (k = -3; k <= 3; ++k) {
              sdlDrawLine(xOffs + j * xDist, yOffs + pj * yDist,
                          xOffs + j * xDist - k, yOffs + pj * yDist - 6,
                          0, 255, 0);
            }
          } else {
            sdlDrawCircPart(xOffs + i * xDist, yOffs + pj * yDist,
                            (j - i) * xDist, (pi - pj) * yDist,
                            255, 255, 0, SDL_CIRC_LOWER_RIGHT);
            for (k = -3; k <= 3; ++k) {
              sdlDrawLine(xOffs + j * xDist, yOffs + pj * yDist,
                          xOffs + j * xDist - k, yOffs + pj * yDist + 6,
                          255, 255, 0);
            }
          }
        } else {
          if (pi < pj) {
            sdlDrawCircPart(xOffs + i * xDist, yOffs + pj * yDist,
                            (i - j) * xDist, (pj - pi) * yDist,
                            0, 255, 0, SDL_CIRC_UPPER_LEFT);
            for (k = -3; k <= 3; ++k) {
              sdlDrawLine(xOffs + j * xDist, yOffs + pj * yDist,
                          xOffs + j * xDist - k, yOffs + pj * yDist - 6,
                          0, 255, 0);
            }
          } else {
            sdlDrawCircPart(xOffs + i * xDist, yOffs + pj * yDist,
                            (i - j) * xDist, (pi - pj) * yDist,
                            255, 255, 0, SDL_CIRC_LOWER_LEFT);
            for (k = -3; k <= 3; ++k) {
              sdlDrawLine(xOffs + j * xDist, yOffs + pj * yDist,
                          xOffs + j * xDist - k, yOffs + pj * yDist + 6,
                          255, 255, 0);
            }
          }
        }
      }
    }
  }

  sdlUpdate();
}

// gib dem Knoten mit der Nummer oldPos schrittweise die Nummer newPos
// newPos muss kleinergleich oldPos sein, d.h. der Knoten muss aufsteigen
// zeichne jeden Zwischenschritt
void animate(int oldPos, int newPos)
{
  int p, i;

  paint();
  for (p = oldPos; p > newPos; --p) {
    for (i = 0; i < nodeCnt; ++i) {
      if (nodes[i].pos == p) {
        nodes[i].pos = p - 1;
      } else if (nodes[i].pos == p - 1) {
        nodes[i].pos = p;
      }
    }
    sdlMilliSleep(50);
    paint();
  }
  sdlMilliSleep(300);
}

// fülle Knotenarray und Kanten-Matrix
void init(void)
{
  int i, j;
  
  for (i = 0; i < nodeCnt; ++i) {
    nodes[i].pos = i;
    nodes[i].cnt = -1;
  }

  for (i = 0; i < nodeCnt; ++i) {
    for (j = 0; j < nodeCnt; ++j) {
      // keine Kante zu sich selbst!
      if (j == i) edges[i][j] = false;
      // der folgende Vergleich ergibt
      // mit edgePcnt Prozent Wahrscheinlichkeit true
      else edges[i][j] = (rand() % 100 < edgePcnt);
    }
  }
}

// topologisches Sortieren
void topsort(void)
{
  int headIdx;   // Array-Index des ersten Knotens
                 // der Liste der Knoten ohne Vorgänger
  int tailIdx;   // Index des letzten Knotens in der Liste
  int cnt;       // Anzahl der schon sortierten Knoten
  int i, j;

  // 1. Schritt: Setze bei jedem Knoten die Anzahl der Vorgänger auf 0
  for (i = 0; i < nodeCnt; ++i) {
    nodes[i].cnt = 0;
  }

  // 2. Schritt: Geh für jeden Knoten alle seine Nachfolger durch,
  // erhöhe bei jedem Nachfolger die Anzahl der Vorgänger um 1
  for (i = 0; i < nodeCnt; ++i) {
    for (j = 0; j < nodeCnt; ++j) {
      if (edges[i][j]) {
        ++(nodes[j].cnt);
      }
    }
  }

  // 3. Schritt: Gehe nochmal alle Knoten durch.
  // Hänge alle Knoten, bei denen die Anzahl der Vorgänger 0 ist,
  // in eine einfach verkettete Liste.
  // Die Liste ist nicht mit Pointern, sondern mittels Array-Index verkettet
  // (d.h. in .next steht der Index des nächsten Knotens in der Liste,
  // -1 steht statt dem NULL-Pointer).
  // Der Listenkopf (Array-Index des ersten Elementes der Liste) ist headIdx,
  // der Tail ist tailIdx.
  headIdx = -1;
  for (i = 0; i < nodeCnt; ++i) {
    if (nodes[i].cnt == 0) {
      nodes[i].next = -1;
      if (headIdx == -1) headIdx = i;
      else nodes[tailIdx].next = i;
      tailIdx = i;
    }
  }

  // 4. Schritt: Ermittle die Knoten in topologisch sortierter Reihenfolge
  cnt = 0; // Anzahl der Knoten, die schon topologisch sortiert sind
           // = Nummer des nächsten Knotens, der sortiert wird 
  while (headIdx != -1) {
    // solange es noch Knoten ohne Vorgänger in der Liste gibt ...
    // ... nimm den vordersten Knoten der Liste (cur ist der Index des Knotens)
    i = headIdx;
    // ... entferne ihn aus der Liste
    headIdx = nodes[headIdx].next;
    // ... lass ihn an die richtige Stelle wandern und zähle ihn
    animate(nodes[i].pos, cnt);
    ++cnt;
    // ... und lösche alle von diesem Knoten ausgehenden Kanten,
    // d.h. zähle bei allen Nachfolgern die Anzahl der Vorgänger um 1 herunter.
    for (j = 0; j < nodeCnt; ++j) {
      if (edges[i][j]) {
        --(nodes[j].cnt);
        if (nodes[j].cnt == 0) {
          // Wenn die Anzahl der Vorgänger von j 0 wird:
          // füge j hinten in die Liste der Knoten mit 0 Vorgängern ein
          nodes[j].next = -1;
          if (headIdx == -1) headIdx = j;
          else nodes[tailIdx].next = j;
          tailIdx = j;
        }
      }
    }
  }

  // Wenn die Liste der Knoten ohne Vorgänger leer ist,
  // aber noch nicht alle Knoten topologisch sortiert sind:
  // Die restlichen Knoten enthalten einen Zyklus!
  // (d.h. jeder der restlichen Knoten hat mindestens 1 Vorgänger!)
  if (cnt != nodeCnt) {
    printf("Zyklus nach %d von %d Knoten.\n", cnt, nodeCnt);
  } else {
    printf("%d Knoten erfolgreich sortiert.\n", nodeCnt);
  }
}

int main(int argc, const char *argv[])
{
  if (argc != 3) {
    fprintf(stderr, "Usage: %s node_count edge_percent\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  nodeCnt = atoi(argv[1]);
  if ((nodeCnt < 1) || (nodeCnt > MAX_NODES)) {
    fprintf(stderr, "%s: node_count must be between 1 and %d\n",
            argv[0], MAX_NODES);
    exit(EXIT_FAILURE);
  }
  edgePcnt = atoi(argv[2]);
  if ((edgePcnt < 1) || (edgePcnt > 100)) {
    fprintf(stderr, "%s: edge_percent must be between 1 and 100\n", argv[0]);
    exit(EXIT_FAILURE);
  }
  
  srand(time(NULL));
  sdlInit();

  init();
  paint();
  sdlMilliSleep(500);
  topsort();
  
  // periodisches sdlMilliSleep, damit periodisch auf Close-Events geprüft wird
  for (;;) {
    sdlMilliSleep(100);
  }
  sdlExit();
 
  exit(EXIT_SUCCESS);
}