#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>


#include "crochB7.hpp"

#define StSIZE 36
#define SqSIZE StSIZE/2
//#define _aaa


// last character in the alphabet starting with 'a'
#define lchar 'b'

int rho[36] = {0,0,1,1,2,2,3,4,5,5,6,7,8,8,10,10,11,12,13,14,15,15,16,17,
               18,19,20,21,22,23,24,25,26,27,27,28};

CROCH c;

class SQUARE {
public:
    char* gen;
    int start;
    int p;
    SQUARE *prev, *next;
    SQUARE(char* gen,int start,int p) {
        this->gen=new char[p+1];
        strcpy(this->gen,gen);
        this->start=start;
        this->p=p;
        next=prev=0;
    }
    SQUARE(SQUARE *s) {
        gen = new char[s->p+1];
        strcpy(gen,s->gen);
        start=s->start;
        p = s->p;
        next=prev=0;
    }
    ~SQUARE() { 
        if (gen) delete[] gen; 
        gen=0;
    }
    SQUARE& operator=(SQUARE& s) {
        if (gen) delete[] gen;
        gen=new char[s.p+1];
        strcpy(gen,s.gen);
        start=s.start;
        p=s.p;
        next=prev=0;
        return *this;
    }
    void Delete() {
        if (next) 
            next->Delete();
        delete this;
    }
};

class SQUARES {
public:
    SQUARE *first, *last;
    int cut;
    SQUARES() { first=last=0; }
    ~SQUARES() { 
        if (first) 
            first->Delete(); 
        first=last=0;
    }
    void Reset() {
        if (first) 
            first->Delete();
        first=last=0;
    }
    SQUARES& operator=(SQUARES& squares) {
        if (first) first->Delete();
        first=last=new SQUARE(squares.first);
        for(SQUARE* q=squares.first->next; q != 0; q=q->next) {
            last->next = new SQUARE(q);
            last->next->prev = last;
            last=last->next;
        }
        return *this;
    }
    void Add(char* gen,int start,int p,int cut) {
        this->cut=cut;
        if (first==0) {
            first=last=new SQUARE(gen,start,p);
        }else{
            last->next = new SQUARE(gen,start,p);
            last->next->prev = last;
            last=last->next;
        }
    }
    void show(FILE* fp=stdout) {
        SQUARE* q;
        for(q = first; q!=0; q=q->next) {
            for(int i=0; i < q->start; i++) fputc('.',fp);
            fprintf(fp,"%s%s\n",q->gen,q->gen);
        }
    }
    char* makeString() {
        static char string[StSIZE+1];
        for(SQUARE* q=first; q!=0; q=q->next) {
            string[q->start]='\0';
            strcat(string,q->gen);
            strcat(string,q->gen);
        }
        return string;
    }
};


bool next_square(int round,SQUARES& squares,FILE* fp);


int get_cut(char* s,int len,int from) { // return first position where the density check fails
    int j;

    int fullcount = c.Process(s);
    for(j=from; j < len; j++) {
        int count = c.Process(&s[j]);
        int lost = fullcount-count; // we lost so many runs due to cutting off s[0..j-1]
        if (lost < rho[j]) {
            return j;
        }
    }
    return j;
}


bool primitive(char* gen,int len) {
    int i, p, l, e, e1;
    bool q1;

    l = len/2;
    for(p=1; p <= l; p++) {
        if ((len % p) != 0)
            continue;
        // so p is a possible period of the repetition
        e = len / p;
        // check if it is a period
        q1 = true;
        for(i=0; q1 && i < p; i++) {
            for(e1=1; q1 && e1 < e; e1++) {

                if (gen[i]!=gen[i+p*e1]) 
                    q1 = false;
            }
        }
        if (q1)   // gen is a repetition of period p
            return false; 
    }
    return true;
}
    
bool nextGen(char* gen,int len) {
    int i;
A:
    for(i=len-1; i >= 0 && gen[i]==lchar; i--);
    // gen[i] is the first from end that is not lchar
    if (i < 0) return false; // the whole string consists of lchar
    gen[i++]++;
    for( ; i < len; gen[i++]='a');
    // is it primitive
    if (! primitive(gen,len))
        goto A;

    return true;
}

bool nextString(char* s,int len) {
    int i;
    for(i=len-1; i >= 0 && s[i]==lchar; i--);
    // s[i] is the first from end that is not lchar
    if (i < 0) return false; // the whole string consists of lchar
    s[i++]++;
    for( ; i < len; s[i++]='a');
    return true;
}

void good(char* string,int len) {
    // check reverse density
    char t[50];
    char *s = string;
    int i;
    for(i=len-1; i>=0; i--,s++)
        t[i] = *s;
    t[len]='\0';
    int cut = get_cut(t,len,0);
    if (cut < len) 
        return;

    FILE* fp;
    char infile[100];
    sprintf(infile,"G%d",len);
//#define _check_duplicates
#ifdef _check_duplicates
    fp = fopen(infile,"r");
    if (fp==0) {
        fp=fopen(infile,"w");
        fprintf(fp,"%s\n",string);
        fclose(fp);
        return;
    }
    char line[StSIZE+1];
    while(fgets(line,StSIZE+1,fp)!=0) {
        if (strncmp(line,string,len)==0) {
            printf("duplication \"%s\"\n",string);
            getchar();
            break;
        }
    }
    fclose(fp);
#endif
    fp = fopen(infile,"a");
    fprintf(fp,"%s\n",string);
    fclose(fp);
}

void first_square(FILE* fp=stdout) {
    int i;
    SQUARES squares;

    squares.Add("a",0,1,2);
    next_square(2,squares,fp);
    
    char gen[SqSIZE+1] = "aa";
    char square[StSIZE+1];
    int p=2;
    while(true) {
        while( nextGen(gen,p)) {
            if (gen[0]!='a') continue;
            strcpy(square,gen);
            strcat(square,gen);
            int cut = get_cut(square,2*p,0);
            if (cut >= 2*p-1)
                good(square,2*p);
            squares.Reset();
            squares.Add(gen,0,p,cut);
            next_square(2,squares,fp);
        }
        p++;
        if (p > SqSIZE) 
            break;
        for(i=0; i < p; gen[i++]='a');
        gen[i]='\0';
    }
}

bool check_periodicity(char* square1,int len1,int start2,int p2) {
    for(int i=0; i < p2; i++) {
        if (start2+i+p2 >= len1) break;
        if (square1[i+start2]!=square1[start2+i+p2])
            return false;
    }
    return true;
}

bool compatible(char* s1,int p1,int s,char* s2) {
    int end1 = 2*p1-1;
    for(int i=0; i <= end1; i++)
        if (s1[i] != s2[s+i])
            return false;
    return true;
}



// check if adding of a new square2 to squares creates an undesirable inter_square
bool creates_inter_square(SQUARES& squares,char* square2,int start2,int p2) {
    int i, start, end, end1, p;
    bool found, ok;
    char* string;

    string = squares.makeString();
    string[start2]='\0';
    strcat(string,square2);

    for(start=0; start < start2; start++) {
        end1 = squares.last->start+2*squares.last->p-1;  // end of last sqaure
        for(end=start2+2*p2-1; end > end1; end--) {
            p = end-start+1;
            if ((p%2)!=0) 
                continue;
            p = p/2;
            found=true;
            for(i=0; i<p; i++) {
                if (string[start+i] != string[start+i+p]) { 
                    found=false;
                    break;
                }
            }
            if (found) {
                // so there is an inter-square from start to end with period p
                // we have to check if it is not a right shift of a square from squares
                //we also have to check it is is not a right shift of a square that is
                //covered by one of the squares
                //so, shift this square as much left as possible
                int nstart = start;
                while(nstart>0 && string[nstart-1]==string[nstart-1+p])
                    nstart--;
                ok=false;
                for(SQUARE* q=squares.first; q!=0; q=q->next) {
                    if (q->start <= nstart && nstart+2*p <= q->start+2*q->p) {
                        ok=true; 
                        break;
                    }
                }
                if (!ok) 
                    return true; // found true inter-square
            }
        }
    }
    return false;
}


void show_square(char* s,int start,FILE* fp=stdout) {
    int i;
    for(i=0; i<start; i++) fputc(' ',fp);
    fprintf(fp,"%s\n",s);
}
int last_round=0;
int last_p=0;

bool next_square(int round,SQUARES& squares,FILE* fp=stdout) {
    int k, end1, start2, p2, end2;
    char square1[2*SqSIZE+1];
    char gen2[SqSIZE+1];
    char tail[SqSIZE+1];
    char square2[2*SqSIZE+1];
    char *us;
    bool done_something=false;

    if (round!=last_round || last_p!=squares.last->p) {
        last_round=round; 
        last_p=squares.last->p;
        for(int i=2; i < round; i++) putchar('.');
            printf("%d\n",last_p);
    }

     strcpy(square1,squares.last->gen);
    strcat(square1,squares.last->gen);
    end1 = squares.last->start+2*squares.last->p-1;    // end of the first square

    // so the second square may start at any position 1..cut1
    for(start2 = squares.last->start+1; start2 <= squares.cut; start2++) {
        // generate all possible periods
        for(p2=1; p2 <= SqSIZE; p2++) {
            end2 = start2+2*p2-1;  // end of square 2
            if (end2 <= end1) // too short
                continue;
            // hence end2 is the end of the whole string
            if (end2 >= StSIZE)
                break;
            end2 = start2+p2-1;  // end of the gen2
            if (end2 <= end1) { // the generator of the second square fully covered
                if (end2 < end1) 
                    if (!check_periodicity(square1,2*squares.last->p,start2-squares.last->start,p2))
                        continue;
                // so it fits
                for(k=0; k < p2; k++)
                    gen2[k]=square1[start2-squares.last->start+k];
                gen2[k]='\0';
                if (! primitive(gen2,p2))
                    continue;
                // so we have gen2, check if it can be moved left
                strcpy(square2,gen2);
                strcat(square2,gen2);
                if (square1[start2-1-squares.last->start]==square2[p2-1])  // left shift
                    continue;
                if (creates_inter_square(squares,square2,start2,p2))
                    continue;
                us = squares.makeString();
                us[start2]='\0';
                strcat(us,square2);
                int cut2 = get_cut(us,start2+2*p2,squares.last->start);
                if (cut2 < start2)
                    continue;
                if (cut2 >= start2+2*p2-1)
                    good(us,start2+2*p2);
                done_something=true;
                SQUARES squares1;
                squares1 = squares;
                squares1.Add(gen2,start2,p2,cut2);
#ifdef _aaa
                printf("type a\n");
                squares1.show();
                //getchar();
#endif
                
                next_square(round+1,squares1,fp);
                continue;
            }else{ // the generator of the second square not fully covered
                // how much do I need to add ?
                if (start2 == end1+1) { // need to generate full generator
                    for(k=0; k<p2; gen2[k++]='a');
                    gen2[k]='\0';
                    do {
                        strcpy(square2,gen2);
                        strcat(square2,gen2);
                        if (square1[start2-1-squares.last->start]==square2[p2-1])  // left shift
                            continue;
                        if (creates_inter_square(squares,square2,start2,p2))
                            continue;
                        us = squares.makeString();
                        us[start2]='\0';
                        strcat(us,square2);
                        int cut2 = get_cut(us,start2+2*p2,squares.last->start);
                        if (cut2 < start2)
                            continue;
                        if (cut2 >= start2+2*p2-1) 
                            good(us,start2+2*p2);
                        done_something=true;
                        SQUARES squares1;
                        squares1 = squares;
                        squares1.Add(gen2,start2,p2,cut2);
#ifdef _aaa
                        printf("type b\n");
                        squares1.show();
                        //getchar();
#endif
                        next_square(round+1,squares1,fp);
                    }while(nextGen(gen2,p2));
                }else{                 // need to generate tail 
                    // covered squares start2 .. end1
                    int x;
                    for(x=0, k=start2; k <= end1; x++, k++)
                        gen2[x]=square1[k-squares.last->start];
                    gen2[x]='\0'; // x is th elength of the covered squares
                    // uncovered squares end1+1..end2
                    int y = end2-end1; // size of uncovered squares
                    for(k=0; k < y; tail[k++]='a');
                    tail[k]='\0';
                    do {
                        gen2[x]='\0';
                        strcat(gen2,tail);
                        if (primitive(gen2,p2)) {
                            strcpy(square2,gen2);
                            strcat(square2,gen2);
                            if (square1[start2-1-squares.last->start]==square2[p2-1])  // left shift
                                continue;
                            if (creates_inter_square(squares,square2,start2,p2))
                                continue;
                            us=squares.makeString();
                            us[start2]='\0';
                            strcat(us,square2);
                            int cut2 = get_cut(us,start2+2*p2,squares.last->start);
                            if (cut2 < start2)
                                continue;
                            if (cut2 >= start2+2*p2-1)
                                good(us,start2+2*p2);
                            done_something=true;
                            SQUARES squares1;
                            squares1=squares;
                            squares1.Add(gen2,start2,p2,cut2);
#ifdef _aaa
                            printf("type c\n");
                            squares1.show();
                            //getchar();
#endif
                            next_square(round+1,squares1,fp);
                        }
                    }while(nextString(tail,y));
                }//end else
            }//end else
        }//end for
    }//end for
    
    return done_something;
}//end next_square

int getN(char* line) {
    if (*line!='M')
        return 0;
    while(*line != 'N')
        line++;
    line++; // eat N
    line++; // eat = 
    int N = atoi(line);
    return N;
}

char* NextStored(int n,bool first) {
    static FILE* fp=0;

    if (fp==0)
        fp=fopen("maxrun_2_35.asc","r");
    static char line[100];

    if (first) {
        while(true) {
            if (fgets(line,100,fp)==0)
                return 0;
            line[strlen(line)-1]='\0';
            if (getN(line) < n)
                continue;
            if (getN(line) > n) {
                printf("problem\n");
                exit(0);
            }
            if (fgets(line,100,fp)==0)
                return 0;
            line[strlen(line)-1]='\0';
            return line;
        }
    }else{
        while(true) {
            if (fgets(line,100,fp)==0)
                return 0;
            if (line[0]=='(') continue;
            if (line[0]=='-') return 0;
            line[strlen(line)-1]='\0';
            return line;
        }
    }
}

void removeG() {
    char infile[100];
    for(int i=4; i <= 36; i++) {
        sprintf(infile,"G%d",i);
        remove(infile);
    }
    printf("all G's removed\n");
}

bool isIn(char* string,char* infile) {
    FILE* fp;
    char line[100];

    fp = fopen(infile,"r");
    if (fp==0) {
        printf("no file %s\n",infile);
        return false;
    }
    while(fgets(line,100,fp) != 0) {
        line[strlen(line)-1]='\0';
        if (strcmp(string,line)==0) {
            fclose(fp);
            return true;
        }
    }
    fclose(fp);
    return false;
}


void checkG() {
    char infile[100];
    char* s;
    int x = StSIZE;
    if (x > 35)
        x = 35;

    for(int i=4; i <= x; i++) {
        sprintf(infile,"G%d",i);
        s = NextStored(i,true);
        if (s==0) continue;
        if (! isIn(s,infile))
            printf("string \"%s\" not in %s\n",s,infile);
        while((s = NextStored(i,false)) != 0) {
            if (! isIn(s,infile))
                printf("string \"%s\" not in %s\n",s,infile);
        }
    }
}

void checkDouble() {
    char infile[100];
    FILE *fp1, *fp2;
    char line1[100], line2[100];
    int c1, c2;

    for(int i=4; i <= StSIZE; i++) {
        sprintf(infile,"G%d",i);
        fp1 = fopen(infile,"r");
        if (fp1==0) continue;
        c1=0;
        while(fgets(line1,100,fp1)!=0) {
            c1++;
            fp2=fopen(infile,"r");
            c2=0;
            while(fgets(line2,100,fp2)!=0) {
                c2++;
                if (c1==c2) continue;
                if (strncmp(line1,line2,i)==0) {
                    printf("G%d duplication row %d and %d\n",i,c1,c2);
                    printf("%s",line1);
                    return;
                }
            }
            fclose(fp2);
        }
        fclose(fp1);
    }    
}

int main() {
    time_t t1, t2;
    t1 = time(NULL);

    removeG();
    first_square();

    //checkG();
    //checkDouble();
    t2 = time(NULL);
    int lapsed_seconds = (int) t2- (int) t1;
    int lapsed_minutes = lapsed_seconds / 60;
    lapsed_seconds = lapsed_seconds % 60;
    int lapsed_hours = lapsed_minutes / 60;
    lapsed_minutes = lapsed_minutes % 60;
    printf("DONE in %d hours %d minutes and %d seconds",lapsed_hours,lapsed_minutes,lapsed_seconds);
    getchar();
    return 0;
}