// Prim's Algorithmus: Minimum Cost Spanning Tree, grafisch
// für eine gegebene Anzahl zufällig innerhalb eines Rechtecks erzeugter Städte
// mit Heap zur Ermittlung der minimalen Kante
//
// Aufruf: prim anzahl
//
// Klaus Kusche, 2012

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
#include "sdlinterf.h"

// Größe des "Landes" in x- und y-Richtung
// Rundherum lassen wir 10 Pixel Rand
#define PIXEL_OFFSET 10
#define X_SIZE (SDL_X_SIZE - 2 * PIXEL_OFFSET)
#define Y_SIZE (SDL_Y_SIZE - 2 * PIXEL_OFFSET)

// für die Grafik-Ausgabe: Farb-Komponenten für Städte und die Linien
#define CITY_R 255
#define CITY_G 0
#define CITY_B 255
#define LINE_R 0
#define LINE_G 255
#define LINE_B 0

// Wartezeit (Millisekunden) pro angezeigter Verbindung
#define SLEEP_PER_LINE 30

// Typ einer Stadt
typedef struct _city_t {
  int x, y;                  // Pixel-Koordinaten der Stadt
  double dist;               // Länge der kürzesten Verbindung zur Stadt
  struct _city_t *from;      // Von woher kommt die kürzeste Verbindung?
} city_t;

// berechne die Entfernung zwischen a und b
double getDist(city_t *a, city_t *b);
// Schieb das Element i im Heap wenn nötig nach rechts
void shiftRight(int father);
// Schieb das Element i im Heap wenn nötig nach links
void shiftLeft(int son);
// Stelle die richtige Ordnung im Heap wieder her
void heapify(void);
// Entnimm und returniere das kleinste Element des Heaps,
// bring den Heap wieder in Form
city_t *getMin(void);

// berechne die Entfernung zwischen a und b
inline double getDist(city_t *a, city_t *b)
{
  int dx, dy;             // x- und y-Abstand von a und b
  
  dx = b->x - a->x;
  dy = b->y - a->y;
  return sqrt(dx * dx + dy * dy);
}

city_t **heap;             // Pointer auf den Heap
int heapSize;              // aktuelle Anzahl der Städte im Heap

// Schieb das Element i im Heap wenn nötig nach rechts
void shiftRight(int father)
{
  int son;
  city_t *tmp;

  // a[father]..."Vater", a[2*father] und a[2*father+1]..."Söhne"
  // tausche den Vater mit dem kleineren der beiden Söhne
  // bis der Vater kleiner als beide Söhne ist oder kein Sohn mehr im Heap ist
  for ( ; (son = 2 * father) <= heapSize; father = son) {
    // Wenn es 2 Söhne gibt: stelle son auf den kleineren der beiden Söhne
    if ((son + 1 <= heapSize) && (heap[son + 1]->dist < heap[son]->dist)) {
      ++son;
    }
    // vergleiche den kleineren Sohn mit dem einzusickernden Vater
    if (heap[father]->dist <= heap[son]->dist) {
      // Vater ist kleiner, fertig!
      break;
    }
    // Sohn ist kleiner, mit Vater tauschen
    tmp = heap[father];
    heap[father] = heap[son];
    heap[son] = tmp;
  }
}

// Schieb das Element i im Heap wenn nötig nach links
void shiftLeft(int son)
{
  int father;
  city_t *tmp;

  // tausche den Sohn mit dem Vater,
  // bis der Vater kleiner als der Sohn ist
  for ( ;
       ((father = son / 2) >= 1) && (heap[father]->dist > heap[son]->dist);
       son = father) {
    // Sohn ist kleiner, mit Vater tauschen
    tmp = heap[father];
    heap[father] = heap[son];
    heap[son] = tmp;
  }
}

// Stelle die richtige Ordnung im Heap wieder her:
// * Die hintere Hälfte eines Heaps besteht nur aus Blättern
// und ist daher immer ein korrekter Heap, egal, wie sie geordnet ist.
// * Die Werte in der vorderen Hälfte muss man von hinten nach vorne
// an die richtige Stelle "einsickern lassen".
void heapify(void)
{
  int i;

  for (i = heapSize / 2; i >= 1; --i) {
    shiftRight(i);
  }
}

// Entnimm und returniere das kleinste Element des Heaps,
// bring den Heap wieder in Form
city_t *getMin(void)
{
  city_t *min = heap[1];  // vorderstes Element = kleinstes Element
  // Heap wird kürzer
  --heapSize;
  if (heapSize != 0) {
    // entnommenes Element im Heap durch hinterstes ersetzen,
    heap[1] = heap[heapSize + 1];
    // ... und Element einsickern lassen
    shiftRight(1);
  }
  return min;
}


int main(int argc, const char *argv[])
{
  int cityCnt;               // Anzahl der Städte
  city_t *cities;            // Pointer auf das Array der Städte
  city_t *a, *b;             // Pointer darin
  city_t **h;                // Pointer im Heap
  int x, y;                  // Pixel-Koordinaten einer Stadt
  // Heap mit Pointern auf alle Städte, die noch nicht in der Lösung sind
  // (so sortiert, dass die kleinste Stadt vorne ist)
  // Element 0 ist unbenutzt!
  double dist;               // Länge einer Verbindung
  double totalLen;           // Gesamtlänge aller bisherigen Verbindungen
  int i;

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

  sdlInit();

  // Städte erzeugen
  // und Heap aufbauen (alle Städte außer der der ersten)
  cities = (city_t *) (malloc(cityCnt * sizeof (city_t)));
  if (cities == NULL) {
    fprintf(stderr, "%s: Out of memory\n", argv[0]);
    exit(EXIT_FAILURE);
  }
  heap = (city_t **) (malloc(cityCnt * sizeof (city_t)));
  if (heap == NULL) {
    fprintf(stderr, "%s: Out of memory\n", argv[0]);
    exit(EXIT_FAILURE);
  }
  srand((unsigned int)(time(NULL)));
  for (a = cities, h = heap; a < cities + cityCnt; ++a, ++h) {
    x = a->x = rand() % X_SIZE + PIXEL_OFFSET;
    y = a->y = rand() % Y_SIZE + PIXEL_OFFSET;
    if (a == cities) {
      // Erste Stadt in die Lösung geben
      cities->from = NULL;
      cities->dist = 0;
    } else {
      // Anfangsdistanz berechnen
      a->from = cities;
      a->dist = getDist(cities, a);
      *h = a;
    }
    sdlDrawLine(x - 2, y - 2, x + 2, y + 2, CITY_R, CITY_G, CITY_B);
    sdlDrawLine(x - 2, y + 2, x + 2, y - 2, CITY_R, CITY_G, CITY_B);
  }
  sdlUpdate();
  heapSize = cityCnt - 1;
  heapify();

  totalLen = 0;
  // Baum erstellen:
  // Immer die "nächstgelegenste" Stadt (im Heap vorne) zur Lösung nehmen
  // bis der Heap leer ist
  for (;;) {
    a = getMin();
    b = a->from;
    totalLen += a->dist;
    sdlDrawLine(a->x, a->y, b->x, b->y, LINE_R, LINE_G, LINE_B);
    sdlUpdate();
    sdlMilliSleep(SLEEP_PER_LINE);
    if (heapSize == 0) break; // das war die letzte Stadt ==> fertig
    // Distanzen aller Städte im Heap korrigieren
    for (i = 1; i <= heapSize; ++i) {
      b = heap[i];
      dist = getDist(a, b);
      if (dist < b->dist) {
        b->from = a;
        b->dist = dist;
        shiftLeft(i);
      }
    }
  }
  printf("\n%d Verbindungen, Gesamtlänge %g\n", cityCnt - 1, totalLen);
  
  // periodisches sdlMilliSleep, damit periodisch auf Close-Events geprüft wird
  for (;;) {
    sdlMilliSleep(100);
  }
  
  sdlExit();
  
  exit(EXIT_SUCCESS);
}