// Topologisches Sortieren, grafisch
// Rahmenprogramm zum Fertigstellen
//
// 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)
{
  // schreiben!!!
}

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);
}