/* Generates animation of ordering rational 2D coordinates. By drummyfish,
  released under CC0 1.0, public domain. */

#include <cairo.h>

#define W 512
#define H 512
#define S 10.0         // scale
#define LW 0.1         // line width
#define C1 0.5,0.5,0.5 // color 1
#define C2 1.0,0,0
#define C3 0.7,0.7,0.8
#define N 20           // number of coords to plot

cairo_surface_t *s;
cairo_t *c;

int isSimplified(int nom, int den)
{
  int divisor = 2;

  while (divisor <= nom && divisor <= den)
  {
    if (nom % divisor == 0 && den % divisor == 0)
      return 0;

    divisor++;
  }

  return 1;
}

void nThPair(int n, int *a, int *b, int skipSimplified)
{
  *a = 0;
  *b = 1;

  if (n == 0)
    return;

  n--;

  int state = 0;

  *a = 1;
  
  while (n > 0)
  {
    switch (state)
    {
      case 0: (*a)++; state = 1; break;
      case 1:
        (*a)--;
        (*b)++; 

        if (*a == 1)
          state = 2;

        break;
      case 2: (*b)++; state = 3; break;
      case 3:
        (*a)++;
        (*b)--; 

        if (*b == 1)
          state = 0;
        break;

      default: break;
    }

    if (!skipSimplified || isSimplified(*a,*b))
      n--;
  }
}

void nThRational(int n, int *nom, int *den)
{
  nThPair(n,nom,den,1);
}

void nThCoord(int n, int *xNom, int *xDen, int *yNom, int *yDen)
{
  int a, b;

  nThPair(n + 1,&a,&b,0);

  nThRational(a - 1,xNom,xDen);
  nThRational(b - 1,yNom,yDen);
}

void line(double x1, double y1, double x2, double y2, double w,
  double r, double g, double b)
{
  cairo_set_operator(c,CAIRO_OPERATOR_DARKEN);
  cairo_set_source_rgb(c,r,g,b);
  cairo_set_line_width(c,w);
  cairo_move_to(c,x1,S - y1);
  cairo_line_to(c,x2,S - y2);
  cairo_stroke(c);
  cairo_set_operator(c,CAIRO_OPERATOR_OVER);
}

void point(double x, double y, double rad, double r, double g, double b)
{
  cairo_set_source_rgb(c,r,g,b);
  cairo_arc(c,x,S - y,rad,0,2 * 3.1415);
  cairo_fill(c);
}

int main(void)
{

  s = cairo_image_surface_create(CAIRO_FORMAT_RGB24,W,H);
  c = cairo_create(s);

  cairo_scale(c,W / S,H / S);

  cairo_set_source_rgb(c, 1, 1, 1);
  cairo_paint(c);

  line(0,0,0,S,LW,C1);
  line(0,0,S,0,LW,C1);

  for (int i = 0; i < S; ++i)
  {
    line(i,0,i,0.2,LW,C1);
    line(0,i,0.2,i,LW,C1); 
  }

  double xPrev = 0, yPrev = 0;

  for (int i = 0; i < 1000; ++i)
  {
    char fileName[] = "frames/frame0000.png";   
 
    fileName[12] += (i / 1000) % 10;
    fileName[13] += (i / 100) % 10;
    fileName[14] += (i / 10) % 10;
    fileName[15] += i % 10;

    cairo_surface_write_to_png(s,fileName);

    int x1, y1, x2, y2;

    nThCoord(i,&x1,&y1,&x2,&y2);

    double x = ((double) x1) / ((double) y1),
      y = ((double) x2) / ((double) y2);
 

    line(xPrev,yPrev,x,y,LW / 4,C3);

    point(xPrev,yPrev,0.05,C2);
    point(x,y,0.05,C2);

    xPrev = x;
    yPrev = y;
  }

  cairo_destroy(c);
  cairo_surface_destroy(s);

  return 0;
}