/***********        SCHROEDER    WORDS   OF  LENGTH   N       ***********/

#include <SDL/SDL.h>
#include <SDL/SDL_ttf.h>
#include <stdio.h>
#include <math.h>
#define N 10         /**  N even  */
#define pas 8
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);
SDL_Surface * screen; Uint32 white,blue;
SDL_Surface *texte;  SDL_Rect position;TTF_Font *police=NULL;char chiffre[2000];
int a[N],xorig,yorig,count;
void drawing(void);

int main(int argc, char ** argv)
{  int i, j,k,pospivot,nb1,nb2,flag;
   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);

   xorig=10; yorig=pas*N/2-6;
   for(i=0;i<N;i++) a[i]=0;
   for(;;)
    { drawing();  count++;
       flag=0;
       for(i=0;i<N;i+=2) if (! (a[i]==1 && a[i+1]==2)) { flag=1; break;}
       if (flag==0) break;
        i=N-1;
       while (! ((a[i]==0 && a[i-1]==0 && i>=1)
	    || (a[i]==2 && a[i-1]==2 && a[i-2]==1 && i>=2))) i--;
       if (a[i]==0 && a[i-1]==0)
         { pospivot=i-1;  a[pospivot]=1;
            nb1=0; nb2=0;
            for(j=N-1;j>pospivot;j--)
	           { if (a[j]==1) nb1++ ;
	              if (a[j]==2) nb2++;
	           }
            if (nb1==0)  for(j=pospivot+1;j<N;j++) a[j]=2;
            else
               { for(j=N-1;j>N-1-(nb2-nb1+1);j--) a[j]=2;
                  for(k=pospivot+1;k<=j;k++) a[k]=0;
	           }
          }
       else
         { pospivot=i-2;  a[pospivot]=2;
            nb1=0; nb2=0;
            for(j=N-1;j>pospivot;j--)
	           { if (a[j]==1) nb1++ ;
	              if (a[j]==2) nb2++;
	           }
            for(j=pospivot+1;j<N;j++) a[j]=0;
            for(j=N-1;j>N-1-(nb2-nb1-2);j--) a[j]=2;
         }
      }
   TTF_Init();
    police=TTF_OpenFont("times.ttf",20);
    SDL_Color couleurnoire={0,0,0};
    sprintf( chiffre," %d  Schroeder words of length %d",count,N);
    texte=TTF_RenderText_Solid(police,chiffre,couleurnoire);
    position.x=10; if (yorig<570) position.y=yorig+10;  else position.y=20;
    SDL_BlitSurface(texte,NULL,screen,&position);
    SDL_Flip(screen);pause();TTF_CloseFont(police); TTF_Quit(); return 0;
}


void drawing(void)
{ int x,y,i;
   x=xorig;y=yorig;
   line(xorig,yorig,xorig+N*pas,yorig,blue);
   for(i=0;i<N;i++)
      { line (x,y,x,yorig,blue);
         if (a[i]==0) {x+=pas; linewithwidth (x,y,x-pas,y,1,blue); }
         else if (a[i]==1) {x+=pas;y-=pas; linewithwidth(x,y,x-pas,y+pas,1,blue);}
         else if (a[i]==2) {x+=pas;y+=pas; linewithwidth (x,y,x-pas,y-pas,1,blue);}
      }
   xorig+=N*pas+20; if (xorig>800-N*pas) {yorig+=N*pas/2+5;xorig=10;}
   if (yorig>600-N*pas) { SDL_Flip(screen);pause();SDL_FillRect(screen,0,white);
                                       xorig=10; yorig=pas*N/2-6;
                                    }
}

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

