#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <math.h>
#include <time.h>
#include <assert.h>

#include <X11/Xlib.h>
#include <X11/Xutil.h>
#include <X11/keysym.h>

/* The name of the program, for error messages. */
const char *progname;

/* The size of the image, and a pointer to the dynamically allocated memory
 * which holds the pixel values (0 for background, 1 for crystal).  They
 * are only global to save the bother of passing them around. */
int width, height;
char *img;

/* X window things. */
Display *x_dpy = 0;
int x_screennum;
GC x_gc;
Window x_wd;
XImage *x_img;


/* Convert a pixel value to the three color components. */
void
pixel_to_color (int *r, int *g, int *b, int value)
{
   if (value) {
      *r = 0.5 * value;
      *g = value;
      *b = 255 - value;
   }
   else
      *r = *g = *b = 0;
}

/* Turn RGB color components into a single X colour value. */
unsigned long
x_make_pixel (int r, int g, int b)
{
   return ((unsigned long) r * 0x10000) +
          ((unsigned long) g * 0x100) +
          ((unsigned long) b);
}

/* Mark a pixel as part of the crystal. */
void
plot (int x, int y, int color)
{
   int r, g, b;

   assert (x >= 0);
   assert (x < width);
   assert (y >= 0);
   assert (y < height);

   img[x + y * width] = color;

   pixel_to_color(&r, &g, &b, color);
   XSetForeground(x_dpy, x_gc, x_make_pixel(r, g, b));
   XDrawPoint(x_dpy, x_wd, x_gc, x, y);
   XFlush(x_dpy);
}

/* Return the value of the pixel at the specified position. */
int
pixel (int x, int y)
{
   assert (x >= 0);
   assert (x < width);
   assert (y >= 0);
   assert (y < height);

   return img[x + y * width];
}

/* Write the image data to the filehandle 'f', in the binary variant of the
 * PPM format - three bytes per pixel. */
void
write_ppm (FILE *f)
{
   int x, y;
   int r, g, b;

   /* Write the header. */
   fprintf(f, "P6\n%d %d\n255\n", width, height);

   /* Write the binary image data. */
   for (y = 0; y < height; ++y) {
      for (x = 0; x < width; ++x) {
         pixel_to_color(&r, &g, &b, pixel(x, y));
         fputc(r, f);
         fputc(g, f);
         fputc(b, f);
      }
   }
}

/* Return a random number in the range 0 to n-1. */
int
rand_over_range (int n)
{
   double dummy;
   return (int) (modf((double) rand() / RAND_MAX, &dummy) * n);
}

/* Set the values pointed to by 'x' and 'y' to a random location along the
 * side of the image. */
void
random_start_position (int *x, int *y)
{
   /* Decide which side to put the new particle on.  The value of 'side'
    * is 0 for the top of the image, 1 for the right, 2 for the bottom
    * or 3 for the left. */
   int side = rand_over_range(4);

   *x = (side == 0 || side == 2) ? rand_over_range(width)
                                 : (side == 1) ? width - 1 : 0;
   *y = (side == 1 || side == 3) ? rand_over_range(height)
                                 : (side == 2) ? height - 1 : 0;
}

/* Return a true value if the specified point is adjacent to any part of the
 * growing crystal. */
int
next_to_crystal (int x, int y)
{
   return (x > 0 && pixel(x - 1, y)) ||
          (x < width - 1 && pixel(x + 1, y)) ||
          (y > 0 && pixel(x, y - 1)) ||
          (y < height - 1 && pixel(x, y + 1));
}

/* Randomly change the position given by one pixel in any of the four
 * cardinal directions.  For simplicity (and because it shouldn't affect
 * the crystal's growth) we allow particles to wrap around to the other side
 * of the image. */
void
shift_point (int *x, int *y)
{
   int dir = rand_over_range(4);

   if (dir == 0)
      --*y;
   else if (dir == 1)
      ++*x;
   else if (dir == 2)
      ++*y;
   else
      --*x;

   if (*x < 0)
      *x = width - 1;
   else if (*x == width)
      *x = 0;
   else if (*y < 0)
      *y = height - 1;
   else if (*y == height)
      *y = 0;
}

/* Simulate a single particle starting at the edge of the image and moving
 * about randomly until it bumps into part of the crystal. */
void
do_particle (int color)
{
   int x, y;

   random_start_position(&x, &y);

   while (!next_to_crystal(x, y))
      shift_point(&x, &y);

   plot(x, y, color);
}

/* Set up X, open a window and initialize it with the current image. */
void
init_x (void)
{
   Screen *screen;
   XWMHints wmhints;
   char *data;

   /* Open the display. */
   if (!(x_dpy = XOpenDisplay(NULL))) {
      fprintf(stderr, "%s: error opening display '%s'.\n",
              progname, XDisplayName(NULL));
      exit(2);
   }

   x_screennum = DefaultScreen(x_dpy);
   x_gc = DefaultGC(x_dpy, x_screennum);

   /* Create the window. */
   screen = DefaultScreenOfDisplay(x_dpy);
   x_wd = XCreateSimpleWindow(x_dpy, RootWindowOfScreen(screen), 0, 0,
                              width, height, 0, 0,
                              BlackPixel(x_dpy, x_screennum));
   if (!x_wd) {
      fprintf(stderr, "%s: error opening window on display '%s'.\n",
              progname, XDisplayName(NULL));
      exit(2);
   }

   /* Tell the window manager that this window might want keyboard input. */
   wmhints.flags = InputHint;
   wmhints.input = True;
   XSetWMHints(x_dpy, x_wd, &wmhints);

   /* Create an image object we can use to draw to the window. */
   if (!(data = malloc(width * height * 4))) {
      fprintf(stderr, "%s: error allocating X image memory: %s\n",
              progname, strerror(errno));
      exit(2);
   }

   x_img = XCreateImage(x_dpy, DefaultVisual(x_dpy, x_screennum), 24,
                        ZPixmap, 0, data, width, height, 8,
                        width * 4);
   XInitImage(x_img);

   /* Open the window. */
   XSelectInput(x_dpy, x_wd, ExposureMask | KeyPressMask | KeyReleaseMask);
   XMapWindow(x_dpy, x_wd);
   XFlush(x_dpy);
}

/* Set the title of the winodw to show progress. */
void
x_window_title (int so_far, int total)
{
   char buf[256];

   sprintf(buf, "Done %d/%d particles (%d%%)",
           so_far, total, (int) ((so_far * 100.0) / total + 0.5));

   XStoreName(x_dpy, x_wd, buf);
}

/* Redraw part of the window. */
void
x_redraw (int x1, int y1, int x2, int y2)
{
   int x, y;
   int r, g, b;

   if (x1 != x2 && y1 != y2) {
      for (y = y1; y < y2; ++y) {
         for (x = x1; x < x2; ++x) {
            pixel_to_color(&r, &g, &b, pixel(x, y));
            XPutPixel(x_img, x, y, x_make_pixel(r, g, b));
         }
      }

      XPutImage(x_dpy, x_wd, x_gc, x_img, x1, y1, x1, y1, x2 - x1, y2 - y1);
      XFlush(x_dpy);
   }
}

/* Process any pending X events (key presses or window exposures).  Returns
 * a true value if the program should terminate now. */
int
x_process_events (void)
{
   XEvent ev;

   while (XCheckWindowEvent (x_dpy, x_wd, ExposureMask | KeyPressMask, &ev)) {
      switch (ev.type)
      {
       case Expose:
         {
            int x1 = ev.xexpose.x;
            int y1 = ev.xexpose.y;
            int x2 = x1 + ev.xexpose.width;
            int y2 = y1 + ev.xexpose.height;
            x_redraw(x1, y1, x2, y2);
         }
         break;

       case KeyPress:
         {
            KeySym key;
            char buf[32];
            XComposeStatus compose;
            XLookupString((XKeyEvent *) &ev, buf, 32, &key, &compose);

            if (!IsModifierKey(key) && key != XK_Tab)
            {
               if (key == XK_Escape || key == XK_q || key == XK_Q)
                  return 1;
            }
         }
         break;

       case KeyRelease:
         break;
      }
   }

   return 0;
}

/* Close the window and clear up resuorces. */
void
clean_up_x (void)
{
   XDestroyWindow(x_dpy, x_wd);
   XDestroyImage(x_img);
}


int
main (int argc, char **argv)
{
   int iterations;
   int i;

   /* Make sure we get different random numbers each time we run this. */
   srand(time(0));

   /* Check and decode the command line arguments. */
   progname = argv[0];
   if (argc != 4) {
      fprintf(stderr, "Usage: %s WIDTH HEIGHT ITERATIONS > out.ppm\n",
              progname);
      return 1;
   }

   width = atoi(argv[1]);
   height = atoi(argv[2]);
   iterations = atoi(argv[3]);

   /* Allocate memory to store the image in. */
   img = malloc(width * height);
   if (!img) {
      fprintf(stderr, "%s: error allocating memory for image: %s\n",
              progname, strerror(errno));
      return 2;
   }

   /* Clear out the image memory, setting it all to black. */
   for (i = 0; i < width * height; ++i)
      img[i] = 0;

   /* Open an X window. */
   init_x();
   x_window_title(0, iterations);

   /* Start with a single pixel set in the middle of the image. */
   plot(width / 2, height / 2, 1);

   /* Simulate the particles as many times as requested. */
   for (i = 0; i < iterations; ++i) {
      do_particle(i * 254 / iterations + 1);

      if (i && (iterations < 100 || i % (iterations / 100) == 0))
         x_window_title(i, iterations);

      if (x_process_events())
         break;
   }

   write_ppm(stdout);

   clean_up_x();
   free(img);
   return 0;
}