/*************       TILINGS OF HALF AZTRC DIAMOND         *************/
/*************                                                                                   *************/
#include <SDL/SDL.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define step 8
void drawing(void);
void mountain(int P);
void combi(void);
void pause(void);
void putpixel(int xe, int ye, Uint32 couleur);
Uint32 getpixel(int xe, int ye);
void line(int x0,int y0, int x1,int y1, Uint32 c);
void rectangle(int x1,int y1, int x2, int y2, Uint32 cb,Uint32 cr);
void floodfill( int x,int y, Uint32 cr,Uint32 cb);
int a[100],b[100],aa[100],m[100],count[2],N,LH,LB,xorig,yorig;
long int c,countc;
SDL_Surface * screen; Uint32 white,red,yellow,lightblue,blue;

int main(int argc, char ** argv)
{  SDL_Init(SDL_INIT_VIDEO);
    screen=SDL_SetVideoMode(800,600,32, SDL_HWSURFACE|SDL_DOUBLEBUF);
    white=SDL_MapRGB(screen->format,255,255,255);
    red=SDL_MapRGB(screen->format,255,0,0);
    yellow=SDL_MapRGB(screen->format,255,255,0);
    lightblue=SDL_MapRGB(screen->format,70,70,255);
    blue=SDL_MapRGB(screen->format,0,0,255);
    SDL_FillRect(screen,0,white);

    N=5;      /** length of the base : 2*N  */

   xorig=20;yorig=(N+1)*step;
   combi();
   SDL_Flip(screen);pause();return 0;
}

void combi(void)
{ int i,pospivot,nb0;
   for(i=0;i<2*N;i++) aa[i]=0;
   for(;;)
     { c++;
        for(i=0;i<2*N-1;i++)  a[i]=aa[i+1];  a[2*N-1]=0;
        for(i=0;i<2*N-1;i++) if (a[i]==1) { a[i]=2; a[i+1]=2;}
        nb0=0; for(i=0;i<2*N;i++) if (a[i]==0) nb0++;
        if (nb0==0)
  	      { for(i=0;i<2*N;i++) m[i]=a[i];
	         countc++; printf("%3.d",countc);
	         drawing();
	       }
       else mountain(nb0/2);
       i=2*N-1;
       if (aa[i]==0 && aa[i-1]==0) pospivot=2*N-1;
       else
        { while( i>=1 && (aa[i]==1 || (aa[i]==0 && aa[i-1]==1))) i--;
           pospivot=i;
        }
      if (pospivot==0) break;
      aa[pospivot]=1;
      for(i=pospivot+1;i<2*N;i++) aa[i]=0;
    }
}

void mountain(int P)     /** mountain of length 2P with P>0 */
{
int i,k,count0,pospivot;
for(i=0;i<2*P;i++) if (i<P) b[i]=0; else b[i]=1;
for(;;)
 {
  countc++;  k=0;
  for(i=0;i<2*N;i++) if(a[i]==0) m[i]=b[k++]; else m[i]=2;
  drawing(); xorig+=2*N*step+15; if (xorig>750) {yorig+=(2*N-1)*step;xorig=20; }
  if (yorig>600-N*step) { SDL_Flip(screen);pause();SDL_FillRect(screen,0,white);
                           xorig=20;yorig=(N+1)*step;}

  i=2*P-3; count0=0;
  while(i>=0 && !(b[i]==0 && b[i+1]==1 && b[i+2]==1))
    { if (b[i+2]==0) count0++;  i--; }
  pospivot=i; if (pospivot==-1) break;
  b[pospivot]=1; b[pospivot+1]=0;  k=0;
  for(i=pospivot+2;i<2*P;i++)
    { if (k<count0) b[i]=0; else b[i]=1;  k++; }
 }
}

void drawing(void)
{ int i,j,x,y,xx,yy;
   x=xorig,y=yorig; LH=N;LB=N;
   for(i=0;i<2*N;i++)
   if (m[i]==2)
     { rectangle(x-step/2,y-step/2,x+step+step/2,y+step/2,blue,yellow);
        xx=x;yy=y-step;
        for(j=0;j<LH;j++)
          { rectangle(xx-step/2,yy-step/2,xx+step+step/2,yy+step/2,blue,yellow);
	         xx+=step;yy-=step;
          }
        xx=x;yy=y+step;
        while(yy<=yorig)
          { rectangle(xx-step/2,yy-step/2,xx+step+step/2,yy+step/2,blue,yellow);
             xx+=step;yy+=step;
          }
        LH--;  x=x+2*step;  i=i+1;
     }
   else if (m[i]==0)
     { rectangle(x-step/2,y+step/2,x+step/2,y-step-step/2,blue,red);
        xx=x;yy=y+step;
        while(yy<=yorig)
          { rectangle(xx-step/2,yy-step/2,xx+step+step/2,yy+step/2,blue,yellow);
	         xx+=step;yy+=step;
          }
        LH--;  x=x+step;y=y-step;
      }
    else if (m[i]==1)
      { rectangle(x-step/2,y-step/2,x+step/2,y+step+step/2,blue,lightblue);
         xx=x;yy=y-step;
         for(j=0;j<LH;j++)
           { rectangle(xx-step/2,yy-step/2,xx+step+step/2,yy+step/2,blue,yellow);
         	 xx+=step;yy-=step;
           }
         x=x+step;y=y+step;
      }
}

void floodfill( int x,int y, Uint32 cr,Uint32 cb)
{   int xg,xd,xx;
    if (getpixel(x,y) !=cb && getpixel(x,y) !=cr)
    { putpixel(x,y,cr);
    xg=x-1;
    while(xg>0 && getpixel(xg,y)!=cb)  {putpixel(xg,y,cr); xg--;}
    xd=x+1;
    while(xd<800 && getpixel(xd,y)!=cb)  {putpixel(xd,y,cr); xd++ ;}
    for(xx=xg; xx<xd;xx++)
    { if (y>1 ) {floodfill(xx,y-1,cr,cb);}
       if (y<599 ) {floodfill(xx,y+1,cr,cb);}

    }
    }
}

void pause(void)
{
    SDL_Event evenement;
    do   SDL_WaitEvent(&evenement);
    while(evenement.type != SDL_QUIT && evenement.type != SDL_KEYDOWN);
}


void putpixel(int xe, int ye, Uint32 couleur)
{ Uint32 * numerocase;
numerocase= (Uint32 *)(screen->pixels)+xe+ye*screen->w;    *numerocase=couleur;
}

Uint32 getpixel(int xe, int ye)
{ Uint32 * numerocase;
   numerocase= (Uint32 *)(screen->pixels)+xe+ye*screen->w;   return (*numerocase);
}

/**  stair line */
void line(int x0,int y0, int x1,int y1, Uint32 c)
{
int dx,dy,x,y,residu,absdx,absdy,stepx,stepy,i;
dx=x1-x0; dy=y1-y0;  residu=0;       x=x0;y=y0;  if (x>=0 && x<800 && y>=0 && y<600) putpixel(x,y,c);
if (dx>0) stepx=1;else stepx=-1; if (dy>0) stepy=1; else stepy=-1;
absdx=abs(dx);absdy=abs(dy);
if (dx==0) for(i=0;i<absdy;i++) { y+=stepy;
                                                    if (x>=0 && x<800 && y>=0 && y<600) putpixel(x,y,c); }
else if(dy==0) for(i=0;i<absdx;i++){ x+=stepx;
                                                         if (x>=0 && x<800 && y>=0 && y<600) putpixel(x,y,c);  }
else if (absdx==absdy)
   for(i=0;i<absdx;i++) {x+=stepx; if (x>=0 && x<800 && y>=0 && y<600) putpixel(x,y,c);
                                     y+=stepy;
                                     if (x>=0 && x<800 && y>=0 && y<600) putpixel(x,y,c);
                                     }
else if (absdx>absdy)
          for(i=0;i<absdx;i++)
			  { x+=stepx; if (x>=0 && x<800 && y>=0 && y<600) putpixel(x,y,c);
			     residu+=absdy;
			     if(residu >= absdx) {residu -=absdx; y+=stepy;
	                              		        if (x>=0 && x<800 && y>=0 && y<600) putpixel(x,y,c);
			                                    }
			  }
else for(i=0;i<absdy;i++)
             {y+=stepy; if (x>=0 && x<800 && y>=0 && y<600) putpixel(x,y,c);
               residu +=absdx;
              if (residu>=absdy)   {residu -= absdy;x +=stepx;
                                              if (x>=0 && x<800 && y>=0 && y<600) putpixel(x,y,c);
                                             }
             }
}

void rectangle(int x1,int y1, int x2, int y2, Uint32 cb,Uint32 cr)
{
    line(x1,y1,x2,y1,cb);line(x1,y2,x2,y2,cb);line(x1,y1,x1,y2,cb);line(x2,y2,x2,y1,cb);
    floodfill((x1+x2)/2,(y1+y2)/2,cr,cb);
}

