#tuentiContest Solución al Challenge 15 . Reto del artista en C

/**
*************************************************************
* @file artist.c
* @brief Challenge 15
*
* @author Gaspar Fernández <blakeyed@totaki.com>
* @version
* @date 17 jun 2011
* Historial de cambios:
*
*************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/* Huge string */
#define STRSIZE 1000
/* #define debug */

typedef struct TRect
{
  int lx, ly, ux, uy, color;
} TRect;

int extrae_argumentos_dd(char *orig, char *delim, char ***args);
void fill_image(int *img, int width, int color, int x1, int y1, int x2, int y2);
void new_rect(int *img, int width, int height, int color, int lx, int ly, int ux, int uy);
void see_image(int *img, int width, int height);
char *trim2(char *s, const char *trimChars);
void define_rect(TRect *r, int lx, int ly, int ux, int uy, int color);
void draw_rect(int *img, int width, int height, const TRect *r);
void swap(TRect* a, TRect* b);
void quicksort(TRect* izq, TRect* der);
int count_color(int *img, int width, int height, int color);

int main(int argc, char *argv[])
{
  char **args;
  int control;
  char bigstr[STRSIZE];
  int width;
  int height;
  int colors;
  int c;
  unsigned *img;        /* Lots of colors available */
  TRect *rectangles;
 
  int i;
  /* Read until EOF in stdin */
  while (fgets(bigstr, STRSIZE, stdin)!=NULL)
    {
      control=extrae_argumentos_dd(trim2(bigstr,"\n\r "), " ", &args);
      if (control<=3)
    continue;

      width=atoi(args[0]);
      height=atoi(args[1]);
      colors=atoi(args[2]);
     
      if (control!=colors*5+3)
    {
      printf("Wrong number of parameters: %d; colors=%d\n", control, colors);
      /* for (c=0; c<control; c++) */
      /*   printf("P%d=%s\n", c, args[c]); */
      continue;
    }

      /* Everything's ok */

      img=malloc(sizeof(int)*height*width);
      fill_image(img, width, 1, 0,0, width-1, height-1);
      rectangles=malloc(sizeof(TRect)*colors);
      /* control=(control-3)/5; */
      for (c=3, i=0; c<control; c+=5, i++)
          {
      define_rect(&rectangles[i], atoi(args[c+0]),atoi(args[c+1]),atoi(args[c+2]),atoi(args[c+3]),atoi(args[c+4]));
          }
      quicksort(&rectangles[0], &rectangles[colors-1]);
      for (i=0; i<colors; i++)
    {
      draw_rect(img, width, height, &rectangles[i]);
    }

#ifdef debug
      see_image(img, width, height);
#endif
      printf ("%d %d", 1, count_color(img, width, height, 1));

      for (i=0; i<colors; i++)
    {
      control=count_color(img, width, height, rectangles[i].color);
      if (control>0)
        printf (" %d %d", rectangles[i].color, control);
    }
      printf("\n");

      free(rectangles);
      free(img);
    }

 
  return EXIT_SUCCESS;
}


int count_color(int *img, int width, int height, int color)
{
  int i, j;
  int s=0;
  for (i=0; i<height; i++)
    {
      for (j=0; j<width; j++)
    {
      if (img[i*width+j]==color)
        s++;
    }
    }
  return s;
}


void define_rect(TRect *r, int lx, int ly, int ux, int uy, int color)
{
  r->lx=lx;
  r->ly=ly;
  r->ux=ux;
  r->uy=uy;
  r->color=color;
}

void draw_rect(int *img, int width, int height, const TRect *r)
{
  new_rect(img, width, height, r->color, r->lx, r->ly, r->ux, r->uy);
}

void new_rect(int *img, int width, int height, int color, int lx, int ly, int ux, int uy)
{

#ifdef debug
  printf("LI: %d,%d | UR: %d, %d\n", lx, ly, ux, uy);
#endif

  fill_image(img, width, color, lx, height-uy, ux-1, height-ly-1);
 
}

void fill_image(int *img, int width, int color, int x1, int y1, int x2, int y2)
{
  int i, j;
#ifdef debug
   printf("%d,%d -> %d,%d\n", x1,y1, x2,y2);
#endif
  for (i=y1; i<=y2; i++)
    {
      for (j=x1; j<=x2; j++)
    {
      img[i*width+j]=color;
    }
    }
 
}

void see_image(int *img, int width, int height)
{
  int i, j;

  for (i=0; i<height; i++)
    {
      for (j=0; j<width; j++)
    {
      printf("%2d ", img[i*width+j]);
    }
      printf("\n");
    }
}

/* An old function I made */
int extrae_argumentos_dd(char *orig, char *delim, char ***args)
{
  char *tmp;
  int num=0;
  /* Reservamos memoria para copiar la candena ... pero la memoria justa */
  char *str= malloc(strlen(orig)+1);
  char **aargs;

  strcpy(str, orig);

  aargs=malloc(sizeof(char**));

  tmp=strtok(str, delim);
  do
    {
      aargs[num]=malloc(sizeof(char*));

      /*       strcpy(aargs[num], tmp); */
      aargs[num]=tmp;
      num++;

      /* Reservamos memoria para una palabra más */
      aargs=realloc(aargs, sizeof(char**)*(num+1));

      /* Extraemos la siguiente palabra */
      tmp=strtok(NULL, delim);
    } while (tmp!=NULL);

  *args=aargs;
  return num;
}

char *trim2(char *s, const char *trimChars)
{
  char *start = s;

  /* Nos comemos los caracteres al principio */
  while(*start && strpbrk((const char*)start, trimChars)==start)
    ++start;

  char *i = start;
  char *end = start;

  /* Nos comemos los caracteres al final */
  while(*i)
  {
    if( strpbrk(i++, trimChars)!=i-1 )
      end = i;
  }

  /* Coloramos el perminador */
  *end = 0;

  return start;
}

/* to order colors */
void quicksort(TRect* izq, TRect* der)
{
        if(der<izq) return;
        TRect pivot=*izq;
        TRect* ult=der;
        TRect* pri=izq;
 
        while(izq<der)
        {
                while(izq->color<=pivot.color && izq<der+1) izq++;
                while(der->color>pivot.color && der>izq-1) der--;
                if(izq<der) swap(izq,der);
        }
        swap(pri,der);
        quicksort(pri,der-1);
        quicksort(der+1,ult);
}
 
void swap(TRect* a, TRect* b)
{
        TRect temp=*a;
        *a=*b;
        *b=temp;
}