//------------------------------------------------------------------------------------------
// COOL-LEX GRAY CODE FOR FIXED DENSITY NECKLACES or LYNDON WORDS IN CONSTANT AMORTIZED TIME
// and FIXED DENSITY DE BRUIJN CYCLES IN CONSTANT TIME PER N BITS
// Research by: Aaron Williams, Joe Sawada
// Programmed by: Joe Sawada -- August 2010
//------------------------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#define MAX 63
#define TRUE 1
#define FALSE 0
#define Max(a,b) ( (a>b) ? a : b )

int N, D, c, total=0, PSEUDO=0, NECK=0, LYN=0, DB=0, to, from, type, ONE=1, ZERO=0, old_from=0;
int STRING=0, BLOCK=0, SWAP=0, SHIFT=0, NONE=0, COLEX=0;
int a[MAX], S[MAX], T[MAX];

//--------------------------------------------------------------------------------
void Input() {
    int output;
    
    printf("\n  Lex Smallest Representative                Lex Largest Representative\n");
    printf("  ---------------------------                --------------------------\n");
    printf("  1.  Necklaces                              5. Necklaces\n");
    printf("  2.  Lyndon words                           6. Aperiodic necklaces\n");
    printf("  3.  Pseudo necklaces                       7. Pseudo necklaces\n");
    printf("  4.  Fixed density de Bruijn cycles         8. Fixed density de Bruijn cycles\n");
    
    printf("\nENTER object #: ");    scanf("%d", &type);
    
    if (type == 1 || type == 5) NECK = 1;
    if (type == 2 || type == 6) LYN = 1;
    if (type == 3 || type == 7) PSEUDO = 1;
    if (type == 4 || type == 8) DB = NECK =  1;
    
    if (!DB) {
        printf("\n  Cool-lex Gray code order                    Co-lex order:\n");
        printf("  --------------------------                  ------------------------\n");
        printf("  1.  String                                  7. String\n");
        printf("  2.  Run length blocks                       8. Run length blocks\n");
        printf("  3.  Swaps                                   9. Both string and blocks \n");
        printf("  4.  Shifts \n");
        printf("  5.  ALL the above cool-lex outputs \n\n");
        printf("  6.  No output (just counts)\n");
        
        printf("\nENTER output choice #: ");    scanf("%d", &output);
        
        if (output == 1 || output == 5 || output == 7 || output == 9) STRING = 1;
        if (output == 2 || output == 5 || output == 8 || output == 9) BLOCK = 1;
        if (output == 3 || output == 5 ) SWAP = 1;
        if (output == 4 || output == 5 ) SHIFT = 1;
        if (output == 6) NONE = 1;
        if (output > 6) COLEX = 1;
    }
    
    printf("ENTER length n: ");    scanf("%d", &N);
    if (type != 4  && type != 8 && (output !=3 && output != 4)) printf("ENTER density d (-1 for all densities): ");
    else printf("ENTER density d: ");
    scanf("%d", &D);
    
    if (type < 5) {
        ZERO = 1; ONE = 0;
        if (D != -1) D = N-D;  // updated in main loop instead
    }
    printf("\n");
}
//--------------------------------------------------
void SetBlock(int j, int z, int d) {
    S[j] = z;
    T[j] = d;
}
//--------------------------------------------------
void Swap(int i, int j) {
    int tmp;
    
    tmp = a[i];    a[i] = a[j];     a[j] = tmp;
}
//---------------------------------------------------------------------------------------
// Returns 0 if not a necklace, otherwise returns the length of the longest Lyndon prefix
//---------------------------------------------------------------------------------------
int TestNecklace(int r) {
    int i, p=0;
    
    if (D==0 || D == N) return(1);
    for (i=0; i<c; i++) {
        if (r-i <= 0) r += c;
        if (r < c || c == 1) p += S[r-i] + T[r-i];
        if (S[c-i] < S[r-i] || S[c-i] == S[r-i] && T[c-i] > T[r-i]) return(0);
        if (S[c-i] > S[r-i] || S[c-i] == S[r-i] && T[c-i] < T[r-i]) return(N);
    }
    return(p);
}
//--------------------------------------------------
int TestSuffix(int r) {
    int i;
    
    for (i=0; i<r; i++) {
        if (c-1-i == r) return(1);
        if (S[c-1-i] < S[r-i] || S[c-1-i] == S[r-i] && T[c-1-i] > T[r-i]) return(0);
        if (S[c-1-i] > S[r-i] || S[c-1-i] == S[r-i] && T[c-1-i] < T[r-i]) return(1);
    }
    return(0);
}
//--------------------------------------------------
void Visit(int r) {
    int i, p;
    
    if (DB) {
        p = TestNecklace(r);
        for (i=p; i>=1; i--) printf("%d ", a[i]);
    }
    if (STRING) {
        for (i=1; i<=N; i++) printf("%d ", a[i]);
    }
    if (BLOCK) {
        for (i=c; i>0; i--) printf(" (%d %d)", S[i], T[i]);
    }
    if (SHIFT) {
        printf("  shift(%2d,%2d)  ", from, to);
    }
    if (SWAP) {
        if (a[to] == ONE || total == 0) printf("  swap(%2d,%2d)", to, from);
        else if (a[to+1] == ONE) printf("  swap(%2d,%2d) and swap(%2d,%2d)", from-1, from, to, to+S[c-1]);
        else printf("  swap(%2d,%2d)", from-1, from);
    }
    if (!NONE && !DB) printf("\n");
    total++;
}
//--------------------------------------------------
void Update(int s, int t, int i) {
    
    if (i == 0) {
        SetBlock(c-1, S[c-1]+1, T[c-1]);
        SetBlock(c, S[c]-1, T[c]);
    }
    else {
        SetBlock(c, 1, i);
        SetBlock(c+1, s-1, t-i);
        c = c+1;
    }
}
//--------------------------------------------------
void Restore(int s, int t, int i) {
    
    if (i == 0) {
        SetBlock(c-1, S[c-1]-1, T[c-1]);
        SetBlock(c, S[c]+1, T[c]);
    }
    else {
        c = c-1;
        SetBlock(c, s, t);
    }
}
//--------------------------------------------------
int PseudoOracle(int s, int t, int r) {
    
    if (s == 1) return t;
    if (c == 1) {
        if (s==2) return (N-1)/2;
        return 1;
    }
    if (s-1 > S[r]+1) return 0;
    if (s-1 == S[r]+1) {
        if (s-1 == S[c-1]+1 && t >  T[c-1]) return 1;
        return  0;
    }
    if (s-1 == S[r]) {
        if (s==2) return Max(t-T[r], (t+1)/2);
        if ((s-1 > S[c-1]+1) || (s-1 == S[c-1]+1 && t <= T[c-1])) return Max(t-T[r], 0);
        return Max(t-T[r], 1);
    }
    if (s-1 == S[r]-1) return t;
}
//--------------------------------------------------
int NeckOracle(int s, int t, int r) {
    int j,p;
    
    j = PseudoOracle(s,t,r);
    Update(s,t,j);
    if (TestSuffix(r)) p = TestNecklace(c-1);
    else p = TestNecklace(r);
    Restore(s,t,j);
    if ((NECK && p > 0) || (LYN && p == N)) return j;
    return j+1;
}
//--------------------------------------------------
int Gen(int s, int t, int r) {
    int i,j;
    
    if (COLEX) Visit(r);
    if (s > 0 && t > 0) {
        if (PSEUDO) j = PseudoOracle(s,t,r);
        else j = NeckOracle(s,t,r);
        for (i=t-1; i>= j; i--) {
            if (i < t-1) from = s+t-i;
            to = s;
            
            Update(s,t,i);
            Swap(s, t+s-i);
            
            if (TestSuffix(r)) Gen(s-1, t-i, c-1);
            else Gen(s-1, t-i, r);
            
            Swap(s, t+s-i);
            Restore(s,t,i);
            
            from = s+t-i;
            to = s;
        }
    }
    if (!COLEX) Visit(r);
}
//--------------------------------------------------
void Init() {
    int i;
    
    c = 1;
    from = D+1; 
    SetBlock(1,D,N-D);
    for (i=1; i<=D; i++)   a[i] = ONE;
    for (i=D+1; i<=N; i++) a[i] = ZERO;
}
//--------------------------------------------------
int main(int argc, char *argv[]) {
    int i;
    
    Input();	
    
    // PRODUCE DE BRUIJN CYCLE or  FIXED DENSITY NECKLACES/LYNDON WORDS
    if (DB == 1 || D >= 0) {
        Init();
        Gen(D,N-D,1);
        if (DB) printf("\n");
        else printf("Total = %8d\n", total);
    }
    // LIST ALL NECKLACES/LYNDON WORDS 
    else {
        for (i=0; i<=N; i++) {
            D = i;
            if (type < 5) D = N-D;
            Init();
            Gen(D,N-D,1);
        }			
        printf("Total = %8d\n", total);
    }
}