#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>
#include <assert.h>

#define STB_IMAGE_WRITE_IMPLEMENTATION
#include "stb/stb_image.h"
#include "stb/stb_image_write.h"

#include "primitives.h"
#include "point.h"
#include "stack.h"

// convertit les coordonnées dans l'espace du dessin
double cX(int x)
{
    return 0.1+x / 15.;
}

double cY(int y)
{
    return -0.1+1-(1+y) / 15.;
}

/*** Correction ***/

/* Question 1 */

int plus_bas(point *tab, int n)
{
  int bas = 0;
  for (int i = 1; i < n; i++)
  {
    if (tab[i].y < tab[bas].y || (tab[i].y == tab[bas].y && tab[i].x < tab[bas].x))
    {
      bas = i;
    }
  }
  return bas;
}

/* Question 4 */

int orient(point *tab, int i, int j, int k)
{
  int aire = (tab[k].y - tab[i].y) * (tab[j].x - tab[i].x)
    - (tab[k].x - tab[i].x) * (tab[j].y - tab[i].y);
  if (aire > 0)
  {
    return 1;
  }
  else if (aire < 0)
  {
    return -1;
  }
  else
  {
    return 0;
  }
}

/* Question 6 */

int prochain_point(point *tab, int n, int i)
{
  int j = 0;
  if (i == 0) // il ne faut jamais avoir i == j
  {
    j = 1;
  }
  for (int k = 0; k < n; k++)
  {
    if (k != i && k != j) // trois points distincts
    {
      if (orient(tab, i, j, k) <= 0)
      {
        j = k;
      }
    }
  }
  return j;
}

/* Question 8 */

int conv_jarvis(point *tab, int n, int *env)
{
  int i = plus_bas(tab, n); // O(n)
  int j = prochain_point(tab, n, i); // O(n)
  int nb = 0;
  env[nb] = i;
  nb++;
  while (j != i) // On passe au plus n fois dans cette boucle
  {              // donc complexité en O(n^2)
    env[nb] = j;
    nb++;
    j = prochain_point(tab, n, j); // O(n)
  }
  return nb;
}

/* Question 10 */

void maj_es(point *tab, stack es, int i)
{
  int s1 = pop(es);
  if (!is_empty(es))
  {
    int s2 = top(es);
    while (!is_empty(es) && orient(tab, i, s1, s2) < 0)
    {
      s1 = pop(es);
      if (!is_empty(es)) { s2 = top(es); }
    }
  }
  push(s1, es);
  push(i, es);
}

/* Question 11 */

void maj_ei(point *tab, stack ei, int i)
{
  int s1 = pop(ei);
  if (!is_empty(ei))
  {
    int s2 = top(ei);
    while (!is_empty(ei) && orient(tab, i, s1, s2) > 0) // et pas < 0 cette fois !
    {
      s1 = pop(ei);
      if (!is_empty(ei)) { s2 = top(ei); }
    }
  }
  push(s1, ei);
  push(i, ei);
}

/* Question 12 */

stack conv_graham(point *tab, int n)
{
  stack es = new_stack();
  stack ei = new_stack();
  push(0, es);
  push(0, ei);
  for (int i = 1; i < n; i++)
  {
    maj_es(tab, es, i);
    maj_ei(tab, ei, i);
  }
  /* fusion de es et ei :
     on vide es dans ei, sauf son premier et dernier élément */
  pop(es); // on enlève le dernier élément
  while (!is_empty(es)) // on vide es dans ei
  {
    push(pop(es), ei);
  }
  pop(ei); // on enlève le premier élément de es
  return ei;
}

int main(int argc, char **argv)
{
    int W = 1000;
    int H = 500;

    point tab[] = {
        { 0, 0 }, { 1, 4 }, { 1, 8 }, { 4, 1 }, { 4, 4 }, { 5, 9 },
        { 5, 6 }, { 7, -1 }, { 7, 2 }, { 8, 5 }, { 11, 6 }, { 13, 1 }
    };
    int n = 12;

    int env[12];
    int t = conv_jarvis(tab, n, env);

    for(int i = 0; i < t; i++)
        printf("%d ", env[i]);
    printf("\n");

    stack s_env = conv_graham(tab, n);
    print_stack(s_env);

    initialise(W, H);
    clear();
    fenetre(0, 0, W/2-1, H-1);
    for (int i = 0; i < n; i++)
        cercle_plein(cX(tab[i].x), cY(tab[i].y), 0.01, rgb(0,0,0));
    for(int i = 0; i < t; i++)
        ligne(cX(tab[env[i]].x), cY(tab[env[i]].y),
              cX(tab[env[(i+1)%t]].x), cY(tab[env[(i+1)%t]].y),
              rgb(255, 0, 0));
    fenetre(W/2, 0, W-1, H-1);
    for (int i = 0; i < n; i++)
        cercle_plein(cX(tab[i].x), cY(tab[i].y), 0.01, rgb(0,0,0));

    int dernier = top(s_env);
    while(!is_empty(s_env))
    {
        int i = pop(s_env);
        int j;
        if(is_empty(s_env)) 
        {
            j = dernier;
        }
        else
        {
            j = top(s_env);
        }

        ligne(cX(tab[i].x), cY(tab[i].y),
              cX(tab[j].x), cY(tab[j].y),
              rgb(0, 0, 255));
    }

    stbi_write_png("dm01.png", W, H, 4, get_pixels(), 0);
    detruit();
}