//------------------------------------------------------
// COOL-LEX GRAY CODE FOR BUBBLE LANGUAGES (and colex) 
// Research by: Aaron Williams, Joe Sawada, Frank Ruskey
// Programmed by: Joe Sawada April 2010
//------------------------------------------------------
#include <stdio.h>
#include <string.h>
#define MIN(a,b) ((a < b) ? a : b)
#define MAX(a,b) ((a > b) ? a : b)
#define MAX_N 63
#define MAX_INT 10000

int a[MAX_N], S[MAX_N], T[MAX_N], N, D, K, K2, type, c, to, from, total=0;
int ZERO=0, ONE=1;

int BALANCED=0, NECKLACE=0, LYNDON=0, DYCK=0, FORB=0, INVERSION=0, BPOSET=0, LARGER=0, SORT = 0;
int LARGEST=0, REVERSAL=0, STRICT_REVERSAL=0, COMP_REVERSAL=0, INTERVAL=0, COMBINATIONS=0, KNAPSACK=0;
int STRING=0, BLOCK=0, SWAP=0, SHIFT=0, NONE=0, COLEX=0;

int mb[MAX_N];											     // Reversals, complemented reversals
int pos[MAX_N];                                              // B-POSET
int b[MAX_N];                                                // k-largest
int w[MAX_N], choose[MAX_N][MAX_N], u=0,v=0,y=0,z=0;         // Larger, k-largest
int item[MAX_N], CAP;                                        // Knapsack
//---------------------------------
int Binom(int n, int m) {

    if (choose[n][m] > 0) {}
    else if (m==0 || n<=m) choose[n][m] =  1;
    else choose[n][m] = Binom(n-1,m) + Binom(n-1,m-1);
    return choose[n][m];
}
//---------------------------------
void FindW(int n, int d, int v) {

    if (d == 0) return;
    if (Binom(n-1,d) >= v && n>d) FindW(n-1,d,v);
    else {
            w[N-n+1] = 1;
            FindW(n-1,d-1,v - Binom(n-1,d));
    }
}
//---------------------------------
void DetermineW() {
int i,j;

    if (D != -1) {
        if (ONE) K = Binom(N,D)-K+1;
        if (K < 1) K = 1;
        if (ONE) FindW(N,D,K);
        else FindW(N,N-D,K);
    }
    else {
        for (i=1; i<=N; i++) w[i] = ONE;
        if (ONE) {
            j = 1;
            i = N;
            while (j < K) {
                w[i--] = ZERO;
                j = j*2;
            }
            K = j-K;
        }
        else K--;            
        
        j=N;
        while (K > 0) {
            if (K%2 == 1) w[j] = 1;            // 1 for both smaller and larger
            K = K/2;
            j--;
        }
    }        
}
//---------------------------------
int CompareStrings() {
int i;
    for (i=1; i<=N; i++) {
        if (!ONE && a[i] < w[i]) return 1;
        if (!ONE && a[i] > w[i]) return 0;
        if (ONE && a[i] < w[i]) return 0;
        if (ONE && a[i] > w[i]) return 1;
    }
    return 1;
}
//---------------------------------
void Input() {
int i, j, output;

    printf("\n  1-BUBBLE (ends 1..10..0)                    0-BUBBLE (ends 0..01..1)\n");
    printf("  ------------------------                    ------------------------\n");
    printf("  1.  Combinations                            21. Combinations \n");
    printf("  2.  Forbidden 01^k                          22. Forbidden 10^k\n");
    printf("  3.  <= k (1-0) inversions                   23. <= k (0-1) inversions\n");
    printf("  4.  >= string w                             24. <= string w \n");
    printf("  5.  k largest strings                       25. k smallest strings \n");
    printf("  6.  >= reversal                             26. <= reversal \n");
    printf("  7.  > reversal                              27. < reversal \n");
    printf("  8.  >= complemented reversal (d > n/2)      28. <= complemented reversal (d < n/2)\n");
    printf("  9.  Necklaces (lex largest rep)             29. Necklaces (lex smallest rep) \n");
    printf(" 10.  Aperiodic necklaces (lex largest)       30. Lyndon words \n"); 
    printf(" 11.  <= k transpositions to sort             31.  <= k transpositions to sort \n");
    printf(" 12.  k-ary Dyck words (k=n/d)          \n"); 
    printf(" 13.  Linear extenstions of B-poset \n");
    printf(" 14.  Connected unit interval graphs \n");
    printf(" 15.  Balanced parentheses strings with <= k balanced prefixes (ordered forests with <= k trees) \n"); 
    printf(" 16.  Knapsack holding exactly d items with integer weights (with feasible capacity)     \n"); 

    printf("\nENTER language #: ");    scanf("%d", &type);
    
    if (type == 1 || type == 21) COMBINATIONS = 1;
    if (type == 2 || type == 22) FORB = 1;
    if (type == 3 || type == 23) INVERSION = 1;
    if (type == 4 || type == 24) LARGER = 1;
    if (type == 5 || type == 25) LARGEST = 1;
    if (type == 6 || type == 26) REVERSAL = 1;
    if (type == 7 || type == 27) REVERSAL = STRICT_REVERSAL = 1;
    if (type == 8 || type == 28) COMP_REVERSAL = 1;
    if (type == 9 || type == 29) NECKLACE = 1;
    if (type == 10 || type == 30) NECKLACE = LYNDON = 1;
    if (type == 11 || type == 31) SORT = 1;
    if (type == 12 ) DYCK = 1;
    if (type == 13 ) BPOSET = 1;
    if (type == 14 ) INTERVAL = 1;
    if (type == 15 ) BALANCED = 1;
    if (type == 16 ) KNAPSACK = 1;
    
    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("\nENTER length n: ");    scanf("%d", &N);
    if (INTERVAL || BALANCED) {
        D = N; 
        N = 2*D;
    }
    else if (DYCK || COMP_REVERSAL || BPOSET || output == 3 || output == 4) {  printf("ENTER density d: ");    scanf("%d", &D);  }
    else {  printf("ENTER density d (-1 for all densities): ");    scanf("%d", &D);  }

    
    if (INVERSION || LARGEST || FORB || SORT) {   printf("ENTER k: ");    scanf("%d", &K);  }
    if (DYCK || INTERVAL) K = N/D;
    if (INTERVAL) K2 = 1;
    if (BALANCED) {
        K = 2;
        printf("ENTER k: ");    scanf("%d", &K2); 
    }
    //---------------------------------------
    if (type > 20) { 
        ONE = 0; 
        ZERO = 1; 
        if (D != -1) D = N-D;   // Updated in main for loop instead
    }
    //---------------------------------------    
    if (KNAPSACK) {
        printf("ENTER weights of the %d items sorted in increasing order of weight: ", N);
        for (i=1; i<=N; i++) scanf("%d", &item[i]);
        printf("ENTER capacity of knapsack: ", CAP);     scanf("%d", &CAP); 
    }
    if (BPOSET) {
        printf("ENTER %d-element maximum positions (with spaces): ", D);
        for (i=1; i<=D; i++) scanf("%d", &pos[i]);
    }
    if (LARGER) {
        printf("ENTER the length %d comparison string (with spaces between bits): ", N);
        for (i=1; i<=N; i++) scanf("%d", &w[i]);
    }
    if (LARGEST) DetermineW();
    if (LARGER || LARGEST) {
        j = b[N] = 1;
        for (i=N-1; i> 0; i--) {
                if (w[i] == ZERO && w[i+1] == ONE) j++;
                b[i] = j;
        }
        i = 1;
        while (w[i] == ONE  && i <=N) { u++; i++; }
        while (w[i] == ZERO && i <=N) { v++; i++; }
        while (w[i] == ONE  && i <=N) { y++; i++; }
        while (w[i] == ZERO && i <=N) { z++; i++; }    
    }
    printf("\n");
}
//---------------------------------
void Visit() {
int 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) printf("\n");    

    total++;
}
//---------------------------------
void SetBlock(int j, int s, int t) {
    
    S[j] = s;     T[j] = t;
}
//---------------------------------
void Swap(int i, int j) {
int tmp;
    
    tmp = a[i];    a[i] = a[j];     a[j] = tmp;
}
//--------------------------------------------------
void Update_Blocks(int s, int t, int i) {

    if (i == 0 && c > 1) {
        S[c-1]++;
        S[c]--;
    }
    else {
        SetBlock(c, 1, i);
        SetBlock(c+1, s-1, t-i);
        c++;
    }
}
//--------------------------------------------------
void Restore_Blocks(int s, int t, int i) {

    if (i == 0 && (c>2 || S[1] > 1 || T[1] > 0) ) {
        S[c-1]--;
        S[c]++;
    }
    else {
        c--;
        SetBlock(c,s,t);    
    }
}
//---------------------------------
// ORACLE SUBROUTINES
//---------------------------------
TestJ (int j, int rev_flag, int ones, int zeros) {

    if (j < 0 || (j==0 && rev_flag)) return 0;                
    if (ones == 1 && zeros >= j  && rev_flag) return j;
    return j+1;
}
//--------------------------------------------------
int TestNecklace(int r) {
int i;

    for (i=0; i<c; i++) {
        if (r-i <= 0) r += c;
        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(1);
    }
    if (LYNDON) return(0);
    return(1);
}
//--------------------------------------------------
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);
}
//---------------------------------
// SPECIFIC ORACLES
//---------------------------------
int Oracle_Necklace(int s, int t, int r) {
int j,tmp;

    if (s == 1) return t;
    if (c == 1) {
        if (s==2 && LYNDON) return N/2;
        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;
        if (s-1 == S[c-1]+1 && t == T[c-1] && LYNDON && c == 2) return 1;
        return  0;
    }            
    if (s-1 == S[r]) {
        tmp = t-T[r];
        if (s==2 && tmp < (s+t-1)/2) return (s+t-1)/2;
        if (tmp <= 0 && (s-1 == S[c-1] || (s-1 == S[c-1]+1 && t > T[c-1])) ) return 1;
        if (tmp <  0) return 0;              
        
        Update_Blocks(s,t,tmp); 

        if (TestNecklace(r)) j=tmp;
        else j= tmp+1;
        
        Restore_Blocks(s,t,tmp);
        return j;
    }        
    if (s-1 == S[r]-1) return t;
}
//---------------------------------
int Oracle_Reversal(int s, int t, int rev_flag) {

    if (T[1] == 0) {    
        if (c == 2 && s-1 == S[1]+1 && STRICT_REVERSAL) return 1;
        if (s-1 > S[1]) return 0;    
        if (s-1 < S[1]) return t;
        if (c == 2 && STRICT_REVERSAL) return t/2+1;   
        if (c == 2) return (t+1)/2;
        return TestJ(t-T[2], rev_flag, S[2], T[3]); 
    } 
    if (c == 1 && s == 2 && STRICT_REVERSAL) return 1;   
    if (s > 1) return 0;
    if (c == 1 && STRICT_REVERSAL) return (N+1)/2;
    if (c == 1) return N/2;
    return TestJ(t-T[1], rev_flag, S[1], T[2]);   
}
//---------------------------------
int Oracle_Comp_Reversal(int s, int t, int comp_rev_flag) {

    if (c == 1 || s-1 > T[1]) return 0;
    if (s-1 < T[1]) return t;
    if (c == 2 && t-1 <= S[1]) return 0;
    return TestJ(t-S[1], comp_rev_flag, T[2], S[2]);
}
//---------------------------------
int Oracle_Larger(int s, int t, int larger_flag) {

    if (s-1 < u) return t;
    if (s-1 > u || t < v) return 0; 
    if ((t==v || (y==1 && t-v <= z)) && larger_flag) return t-v;    
    return t-v+1;
}
//---------------------------------
int Oracle_Inversion(int s, int t, int inv) {

    return MAX(0, t-(K-inv));
}
//---------------------------------
int Oracle_Dyck(int s, int t) {

    return MAX(0, t-(s-1)*(K-1) );
}
//---------------------------------
int Oracle_Bposet(int s, int t) {

    return MAX(0, s+t - pos[s]);
}
//---------------------------------
int Oracle_Forb(int s, int t, int k) {

    if (k+1 == K) return 1;
    return 0;
}
//---------------------------------
int Oracle_Balanced(int s, int t, int bal) {

    if (bal == K2 && s == t && s>1) return 2;
    if (bal == K2 && s == t+1) return 1;
    return MAX(0, t-s+1);
}
//---------------------------------
int Oracle_Knapsack(int s, int t, int avail) {
int j;
            
    j = t;
    while (j > 0 && (avail >= item[s+t-j+1] - item[s]) ) j--;
    return j;
}
//---------------------------------
int Oracle_Sort(int s, int t, int sort) {
            
    if (sort == K) return MAX(0, s+t-D);
    return 0;
}
//---------------------------------
//---------------------------------
int Oracle(int s, int t, int r, int rev_flag, int comp_rev_flag, int larger_flag, int k, int inv, int sort, int bal, int avail) {

    if (COMBINATIONS)    return 0;
    if (REVERSAL)        return Oracle_Reversal(s, t, rev_flag);
    if (COMP_REVERSAL)   return Oracle_Comp_Reversal(s, t, comp_rev_flag);
    if (LARGER)          return Oracle_Larger(s, t, larger_flag);
    if (LARGEST)         return Oracle_Larger(s, t, larger_flag);
    if (INVERSION)       return Oracle_Inversion(s, t, inv);
    if (DYCK)            return Oracle_Dyck(s, t);
    if (BPOSET)          return Oracle_Bposet(s, t);
    if (FORB)            return Oracle_Forb(s, t, k);
    if (BALANCED)        return Oracle_Balanced(s,t,bal);
    if (INTERVAL)        return MAX( Oracle_Comp_Reversal(s,t,comp_rev_flag), Oracle_Balanced(s,t,bal));
    if (NECKLACE)        return Oracle_Necklace(s, t, r);
    if (KNAPSACK)        return Oracle_Knapsack(s, t, avail);
    if (SORT)            return Oracle_Sort(s, t, sort);
}
//---------------------------------
int Gen(int s, int t, int r, int rev_flag, int comp_rev_flag, int larger_flag, int k, int inv, int sort, int bal, int avail) {
int i, j, p, q, rflag, newk, newr, crflag, lflag, newb, news;
    
    if (COLEX) Visit();
    if (s > 0 && t > 0) {
        j = Oracle(s,t,r, rev_flag, comp_rev_flag, larger_flag, k, inv, sort, bal, avail);   
        for (i=t-1; i>= j; i--) {
            if (i < t-1) from = s+t-i;
            to = s;
            Update_Blocks(s,t,i);
            Swap(s, t+s-i);
            //------------------------------------
            // UPDATE LANGUAGE SPECIFIC PARAMETERS
            //------------------------------------
            p = s+t-i;
            q = N-p+1;   
            mb[ p ] = c-1;      
            //--------------------------
            if (p >  N/2 && STRICT_REVERSAL) rflag = 0;
            else if (p > N/2 || a[q] == ZERO) rflag = 1;    
            else if (i == 0 || (a[q-1] == ZERO && T[ mb[q]+1 ] >= i))  rflag = rev_flag;
            else rflag=0;             
            //------------------------------------
            if (p >= N/2 || a[q] == ONE) crflag = 1;
            else if (i == 0 || (a[q-1] == ONE && S[ mb[q-1] ]  >= i)) crflag = comp_rev_flag; 
            else crflag = 0;
            //------------------------------------
            if (w[s+t-i] == ZERO) lflag = 1;
            else if (i==0 || (w[s+t-i+1] == ZERO && b[s+t-i+1] == b[s+t])) lflag = larger_flag;
            else lflag = 0;
            //--------------------------
            if (i==0) newk = k+1;
            else newk = 1;
            //--------------------------
            if (TestSuffix(r)) newr = c-1;
            else newr = r;    
            //--------------------------
            if (s-1 == t-i) newb = bal+1;
            else newb = bal;    
            //--------------------------
            if (s+t-i > D) news = sort+1;
            else news = sort;    
            //--------------------------
                        
            Gen(s-1, t-i, newr, rflag, crflag, lflag, newk, inv+t-i, news, newb, avail - item[p] + item[s]);
            
            //--------------------------
            Swap(s, t+s-i);
            Restore_Blocks(s,t,i);
            from = s+t-i;
            to = s;
        }    
    } 
    if (!COLEX) Visit();
}    
//--------------------------------------------------
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, j, cap;

    Input();
        
    if (D == -1) {
        for (i=0; i<=N; i++)  {
			D = i;
			if (type > 20) D = N-D;
            cap = CAP;
            if (KNAPSACK) for (j=1; j<=D; j++) cap = cap - item[j];
            if (!((D==0 || D==N) && (LYNDON || STRICT_REVERSAL)) && !(KNAPSACK && cap< 0)) {
                Init();
                if ((!LARGER && !LARGEST) || CompareStrings()) Gen(D,N-D,1,1,1,1,0,0,0,1,cap); 
            }
        }
    }
    else {
        cap = CAP;
        if (KNAPSACK) for (i=1; i<=D; i++) CAP = CAP - item[i];
        if (!((D==0 || D==N) && LYNDON) && !(KNAPSACK && cap< 0)) {
			Init();
            Gen(D,N-D,1,1,1,1,0,0,0,1,cap);
        }
    }
    printf("Total = %8d\n", total);
}