/***************************    anagrams      **************************/
/***************************                    **************************/
#include <SDL/SDL.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define N 4   /**   2*N: length of increased aztec diamond  */

#define step 10
void reverse (int i, int j);void swap( int i, int j);
void drawing(int k,int xo, int yo);long int fact (int n);void anagrams(int k);
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],N2,NB[3],pospivot,posQ,count;
int i,letter,q,xorig,yorig,LH,LB;
SDL_Surface * screen; Uint32 white,red,yellow,lightblue,blue;

int main(int argc, char ** argv)
{  int k;
    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);

    k=1;  count=0; xorig=10; yorig= N*step+10;
    for(k=0;k<=N;k++)
    anagrams(k); /**  of length N+k, with k  0, k  1, and N-k  2 */
    SDL_Flip(screen);pause();return 0;
}

void anagrams (int k)
{
int j;    NB[0]=k; NB[1]=k;  NB[2]=N-k;  q=0;
for(letter=0;letter<3;letter++) for(i=0;i<NB[letter];i++) a[q++]=letter;

for(;;)
  {
   LB=N;LH=N;
   drawing(k,xorig,yorig); xorig+=2*N*step +20;
   if (xorig>800-2*N*step) {yorig+=2*N*step+20; xorig=10;}
   if (yorig>600-2*N*step) {SDL_Flip(screen);pause(); SDL_FillRect(screen,0,white);
                           xorig=10;yorig=N*step+10;}
   j=N+k-1;  while (j>=1 && a[j]<=a[j-1]) j--;    pospivot=j-1;
   if (pospivot==-1) break;
   j=N+k-1;  while(a[j]<=a[pospivot]) j--;  posQ=j;
   swap(pospivot,posQ);    reverse(pospivot+1,N+k-1);
  }
}

void reverse (int i, int j)
{ int g,d;
   g=i;d=j; while(g<d) swap(g++,d--);
}

void swap( int i, int j)
  {int aux;   aux=a[i]; a[i]=a[j]; a[j]=aux;}

void drawing(int k,int xo,int yo)
{int i,j,x,y,xx,yy;
 x=xo,y=yo;
 for(i=0;i<N+k;i++)
 if (a[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;
     for(j=0;j<LB;j++)
       { rectangle(xx-step/2,yy-step/2,xx+step+step/2,yy+step/2,blue,yellow);
          xx+=step;yy+=step;
       }
     LB--;LH--;
     x=x+2*step;
   }
 else if (a[i]==0)
   { rectangle(x-step/2,y+step/2,x+step/2,y-step-step/2,blue,red);
      xx=x;yy=y+step;
      for(j=0;j<LB;j++)
       { 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 (a[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;
       }
     LB--;
     x=x+step;y=y+step;
   }
}


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);
}

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);}

    }
    }
}
