#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "devoir1.h"

struct _Arete {
  float x, dx;
  int ymax;
  Arete * suivante;
};

struct _TGA {
  int hauteur;
  Arete ** table;
};

struct _TAA {
  Arete * ligne_courante;
  int compte_courant;
  Arete * ligne_suivante;
  int compte_suivant;
};


TGA * nouvelle_TGA(int largeur, int hauteur)
{
  TGA * tga = (TGA *) malloc(sizeof(TGA));
  tga->table = (Arete **) calloc(sizeof(Arete *), hauteur);
  tga->hauteur = hauteur;
  return tga;
}

void detruire_TGA(TGA * tga)
{
  int y;
  Arete * a, *b;

  for (y = 0; y < tga->hauteur; y++) {
    for (a = tga->table[y]; a != NULL; a = b) {
      b = a->suivante;
      free(a);
    }
  }
  free(tga->table);
  free(tga);
}

void insert_arete(TGA * tga, int x0, int y0, int x1, int y1)
{
  Arete * arete;
  float x, dx;

  /* On degage les aretes horizontales */
  if (y0 == y1) return;
  if (y0 > y1) {
    int tmp = x0; x0 = x1; x1 = tmp;
    tmp = y0; y0 = y1; y1 = tmp;
  }

  x = x0;
  dx = (x1 - x0) / (float)(y1 - y0);

  arete = (Arete *) malloc(sizeof(Arete));
  arete->x = x;
  arete->dx = dx;
  arete->ymax = y1;
  arete->suivante = tga->table[y0];
  tga->table[y0] = arete;
}

TAA * nouvelle_TAA()
{
  TAA * taa = (TAA *) malloc(sizeof(TAA));

  taa->ligne_courante = NULL;
  taa->compte_courant = 0;
  taa->ligne_suivante = NULL;
  taa->compte_suivant = 0;
  return taa;
}

void detruire_TAA(TAA * taa)
{
  Arete * a, *b;

  for (a = taa->ligne_courante; a != NULL; a = b) {
    b = a->suivante;
    free(b);
  }
  for (a = taa->ligne_suivante; a != NULL; a = b) {
    b = a->suivante;
    free(a);
  }
  free(taa);
}

static void
calcul_ligne_suivante(TAA * taa, int y)
{
  Arete * a;
  Arete ** prec;

  /* enleve les aretes qui ont depassees la limite en y de la taa */
  for (prec = &taa->ligne_courante; *prec != NULL; ) {
    a = *prec;
    if (a->ymax <= y) {
      *prec = a->suivante;
      free(a);
      taa->compte_courant--;
    } else
      prec = &a->suivante;
  }
}

static int compare_arete(const void * p1, const void * p2)
{
  const Arete ** a1 = (const Arete **)p1;
  const Arete ** a2 = (const Arete **)p2;

  return (*a1)->x - (*a2)->x;
}

static void ordonne_aretes(TAA * taa)
{
  Arete ** table;
  int i;
  Arete * a;

  if (taa->compte_courant == 0) return;
  table = (Arete **) malloc(sizeof(Arete *) * taa->compte_courant);
  for (a = taa->ligne_courante, i = 0; a != NULL; a = a->suivante, i++)
    table[i] = a;
  qsort(table, taa->compte_courant, sizeof(Arete *), compare_arete);
  for (i = 0; i < (taa->compte_courant-1); i++)
    table[i]->suivante = table[i+1];
  table[taa->compte_courant-1]->suivante = NULL;
  taa->ligne_courante = table[0];
  free(table);
}

void transfert_aretes_et_ordonne(TGA * tga, TAA * taa, int y)
{
  Arete * a, *b;

  calcul_ligne_suivante(taa, y);
  for (a = tga->table[y]; a != NULL; a = b) {
    b = a->suivante;
    a->suivante = taa->ligne_courante;
    taa->ligne_courante = a;
    taa->compte_courant++;
  }
  tga->table[y] = NULL;
  ordonne_aretes(taa);
}

int segment_suivant(TAA * taa, int * x0, int * x1)
{
  Arete * a;

  if (taa->ligne_courante == NULL) {
    taa->ligne_courante = taa->ligne_suivante;
    taa->compte_courant = taa->compte_suivant;
    taa->ligne_suivante = NULL;
    taa->compte_suivant = 0;
    return 0;
  }

  a = taa->ligne_courante;
  taa->ligne_courante = a->suivante;

  *x0 = (int)ceil(a->x);
  /* Insere l'arete dans la ligne suivante */
  a->x += a->dx;
  a->suivante = taa->ligne_suivante;
  taa->ligne_suivante = a;
  taa->compte_courant--;
  taa->compte_suivant++;

  if (taa->ligne_courante == NULL) { /* erreur */
    return segment_suivant(taa, x0, x1);
  }
  a = taa->ligne_courante;
  taa->ligne_courante = a->suivante;

  *x1 = (int)floor(a->x);
  a->x += a->dx;
  a->suivante = taa->ligne_suivante;
  a->x += a->dx;
  a->suivante = taa->ligne_suivante;
  taa->ligne_suivante = a;
  taa->compte_courant--;
  taa->compte_suivant++;
  return 1;
}

void
dessine_segment(int x0, int x1, int y, Couleur c)
{
  int x;

  for (x = x0; x < x1; x++) {
    image[y][x] = c;
  }
}

void
remplir_polygone(Polygone* poly, Couleur c, int largeur, int hauteur)
{
  TAA* taa;
  TGA* tga;
  int x0, y0, x1, y1, y;
  int i;
  
  tga = nouvelle_TGA(largeur, hauteur);
  /* debut de remplissage de la TGA */
  x0 = poly->sommet[0].x;
  y0 = poly->sommet[0].y;
  for (i = 1; i < poly->longueur; i++) {
    x1 = poly->sommet[i].x;
    y1 = poly->sommet[i].y;
    insert_arete(tga, x0, y0, x1, y1);
    x0 = x1;
    y0 = y1;
  }
  x1 = poly->sommet[0].x;
  y1 = poly->sommet[0].y;
  insert_arete(tga, x0, y0, x1, y1);
  /* fin du remplissage de la TGA */

  taa = nouvelle_TAA();
  /* debut du dessin du polygone rempli */  
  for (y = 0; y != hauteur; y++) {
    transfert_aretes_et_ordonne(tga, taa, y);
    while (segment_suivant(taa, &x0, &x1)) {
      dessine_segment(x0, x1, y, c);
    }
  }
  /* fin du dessin du polygone rempli */
  detruire_TAA(taa);  
  detruire_TGA(tga);
}