/***************           MOTZKIN    WORDS            *****************/

#include <SDL/SDL.h>
#include <SDL/SDL_ttf.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define step 9
void drawing(void);
void mountain(int N,int P);
void motzkin(int N,int P);
void combi(int N,int P);
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 linewithwidth(int x1, int y1, int x2, int y2, int width,Uint32 c);
int a[100],b[100],aa[100],count[2],xorig, yorig,NN; int countc;
SDL_Surface * screen; Uint32 white,blue;
SDL_Surface *texte;  SDL_Rect position;TTF_Font *police=NULL;char chiffre[2000];

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

   NN=7;    /** can be changed */

   xorig=10;yorig=NN*step;
   countc=1;

   if (NN%2==0)
   for(kk=0;kk<=NN;kk+=2)  combi(NN,kk);
   else if (NN%2==1)
   for(kk=1;kk<=NN;kk+=2)  combi(NN,kk);

   TTF_Init();
   police=TTF_OpenFont("times.ttf",20);
    SDL_Color couleurnoire={0,0,0};
    sprintf( chiffre," %d  Motzkin words of length %d",countc,NN);
    texte=TTF_RenderText_Solid(police,chiffre,couleurnoire);
    position.x=10; position.y=yorig+10;
    SDL_BlitSurface(texte,NULL,screen,&position);
   SDL_Flip(screen);pause();return 0;
}

void combi(int N,int P)
{ int i,count0,n,j,pospivot;
   for(i=0;i<P;i++) a[N-1-i]=2; for(i=0;i<N-P;i++) a[i]=0;
   if (P==0)  mountain(N,0);
   else if (P==N) { for(i=0;i<N;i++) aa[i]=2; drawing(); }
   else
   for(;;)
     { mountain(N,P);
        i=N-1; count0=0;
       while (a[i]!=2 || a[i-1]!=0 && i>0)   { if (a[i]==0) count0++; i--;}
       pospivot=i-1;   if (pospivot==-1) break;
       a[pospivot]=2; a[pospivot+1]=0;
       n=0;
       for(j=pospivot+2;j<N;j++){ n++; if (n<=count0) a[j]=0;else a[j]=2;}
     }
}

void mountain(int N,int P)      /** N and P even, P!=N, mountains  of length N-P  */
{ int i,q,t,k,j,pospivot;
   for(i=0;i<N-P;i++) if (i<(N-P)/2) b[i]=0; else b[i]=1;
   for(;;)
     { q=0;
        for(t=0;t<N;t++) aa[t]=a[t];
        for(t=0;t<N;t++) if (aa[t]==0) aa[t]=b[q++];
        drawing(); countc++;
        if (N-P==2) break;
        if (N-P>2)
          { count[0]=0; count[1]=1; count[b[N-P-2]]++;  i=N-P-3;
            while (i>=0 && (b[i]!=0 || b[i+1]!=1 || b[i+2]!=1))
              { count[b[i]]++;  i--;  }
             if (i==-1) break;
            pospivot=i; b[pospivot]=1; b[pospivot+1]=0; count[1]--;
            k=1;
            for(j=pospivot+2;j<N-P;j++)
             { if (k<=count[0]) b[j]=0; else b[j]=1; k++; }
          }
     }
}

void drawing(void)
{ int i; int x,y,oldx,oldy;
   x=xorig;y=yorig;
   for(i=0;i<NN;i++)
     { oldx=x;oldy=y;  x+=step;
        if (aa[i]==0) y-=step;  else if (aa[i]==1) y+=step;
        linewithwidth(oldx,oldy,x,y,1,blue); linewithwidth(x,y,x,yorig,0,blue);
     }
    linewithwidth(xorig,yorig,xorig+NN*step,yorig,0,blue);
   xorig+=NN*step+10; if (xorig>800-(NN+1)*step) { xorig=10;yorig+=NN*step/2+7;}
   if (yorig>600-NN*step/2) {SDL_Flip(screen);pause();SDL_FillRect(screen,0,white);
                                            xorig=10;yorig=50;}
}

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

void linewithwidth(int x1, int y1, int x2, int y2, int width,Uint32 c)
{
int dx,dy;
float k,xf1,yf1,xf2,yf2,d,dx1,dy1,ndx1,ndy1,ndx2,ndy2,angle=M_PI/2.;
line(x1,y1,x2,y2,c);
dx=x2-x1; dy=y2-y1;       d=sqrt(dx*dx+dy*dy);
if (d!=0.)
{ dx1=(float)width*(float)dx/d; dy1=(float)width*(float)dy/d;
   ndx1=dx1*cos(angle)-dy1*sin(angle);
   ndy1=dx1*sin(angle)+dy1*cos(angle);
   ndx2=dx1*cos(-angle)-dy1*sin(-angle);
   ndy2=dx1*sin(-angle)+dy1*cos(-angle);
   for(k=0;k<=1.;k+=0.1/d)
   {
   xf1=(1.-k)*x1+k*x2; yf1=(1.-k)*y1+k*y2;
   xf2=xf1-ndx1; yf2=yf1-ndy1;  line(xf1,yf1,xf2,yf2,c);
   xf2=xf1-ndx2; yf2=yf1-ndy2;    line(xf1,yf1,xf2,yf2,c);
   }
}
}

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;  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;
                                                    putpixel(x,y,c); }
else if(dy==0) for(i=0;i<absdx;i++){ x+=stepx;
                                                         putpixel(x,y,c);  }
else if (absdx==absdy)
   for(i=0;i<absdx;i++) {x+=stepx; y+=stepy;
                                     putpixel(x,y,c);
                                     }
else if (absdx>absdy)
          for(i=0;i<absdx;i++)
			  { x+=stepx; residu+=absdy;
			     if(residu >= absdx) {residu -=absdx; y+=stepy;}
			     putpixel(x,y,c);
			  }
else for(i=0;i<absdy;i++)
             {y+=stepy; residu +=absdx;
              if (residu>=absdy)   {residu -= absdy;x +=stepx;}
              putpixel(x,y,c);
             }
}



