/*
 *  File:    Reversible.cpp
 *  Author:  S Harry White
 *  Created: 2014-01-05
 *  Updated: 2022-01-20
 *    Fix checkRange when only one number entered. Tidy code.
 *  Updated: 2023-01-07
 *    Change to compile with g++ for macOS.
 */

/*
 *  Makes principal reversible squares.
 */

#include <curses.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/stat.h>
//#include <sys/types.h>
#include <time.h>
#include <unistd.h>

const bool F=false, T=true;
int N, Nd2, **xSquare=NULL, squareSize, list1Size, list2Size, listSize, listIndex, fieldWidth;
typedef unsigned int Uint; typedef unsigned short int Ushort;
typedef struct { Ushort x, y; } t_format; t_format *list1=NULL, *list2=NULL, *list=NULL;

int getFieldWidth(int n) { if (n<=1) return 1; int width=1; while ((n=n/10)!=0) ++width; return width; }
//  -------------

void initGlobals(const int origin, const bool fw) {
//   -----------
  Nd2=N/2; listIndex=0; if (fw) { int NN=N*N; fieldWidth=getFieldWidth(origin==0 ? NN-1 : NN); }
} // initGlobals
//==================================================== store ====================================================

void freeSquare(int size) {
//   ----------
  if (xSquare!=NULL) { for (int i=0; i<size; i++) free(xSquare[i]); free(xSquare); xSquare=NULL; squareSize=0; }
} // freeSquare

void freeStore() {
//   ----------
  freeSquare(squareSize); free(list1); list1=NULL; list1Size=0;
  free(list2); list2=NULL; list2Size=0; list=NULL; listSize=0;
}

void printAllocFail() { printf("\a\nERROR: Storage allocation failed.\n"); }
//  ---------------

bool allocateSquare() {
//   --------------
  bool ok=T;
  if (N>squareSize) {
    freeSquare(squareSize); xSquare=(int**) malloc(N*sizeof(int*)); ok=(xSquare!=NULL);
    if (ok) {
      int numAllocated=N;
      for (int i=0; i<N; i++) {
        int *p=(int*) malloc(N*sizeof(int)); xSquare[i]=p; if (p==NULL) { numAllocated=i; ok=F; break; }
      }
      if (ok) squareSize=N; else freeSquare(numAllocated); 
    }
  }
  if (!ok) printAllocFail(); return ok;
} // allocateSquare

bool allocateLists() {
//   -------------
  int size=10000; bool ok=T;
  if (size>list1Size) {
    free(list1); ok=(list1=(t_format *) malloc(size*sizeof(t_format)))!=NULL;
    if (ok) list1Size=size; else { list1Size=0; free(list2); list2=NULL; list2Size=0; }
  }
  if (ok&(size>list2Size)) {
    free(list2); ok=(list2=(t_format *) malloc(size*sizeof(t_format)))!=NULL;
    if (ok) list2Size=size; else { list2Size=0; free(list1); list1=NULL; list1Size=0; }
  }
  listSize=list1Size; list=list1; if (!ok) printAllocFail(); return ok;
} // allocateLists

bool increaseList(t_format **list) {
//   ------------
  bool ok=F;
  if (*list==list1) {
   int size=list1Size+list1Size/2; t_format *tmp; ok=(tmp=(t_format *) malloc(size*sizeof(t_format)))!=NULL;
   if (ok) {
     for (int i=0; i<list1Size; ++i) tmp[i]=list1[i];
     free(list1); list1=tmp; *list=list1; list1Size=size; listSize=size;
   }
  } else {
    int size=list2Size+list2Size/2; t_format *tmp; ok=(tmp=(t_format *) malloc(size*sizeof(t_format)))!=NULL;
    if (ok) {
      for (int i=0; i<list2Size; ++i) tmp[i]=list2[i];
      free(list2); list2=tmp; *list=list2; list2Size=size; listSize=size;
    }
  }
  if (!ok) printAllocFail(); return ok;
} // increaseList

bool allocateStore(const bool square) { if (allocateLists()) return square ? allocateSquare() : T; return F; }
//   -------------
//================================================= input =====================================================

void clearLine(int c) { while (c!='\n') c=getchar(); }
//   ---------

bool getY() {
//   ----
  int c; do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n'));
  clearLine(c); return (c=='Y')|(c=='y');
}

bool getYorOrder() { // Y, N, or the order
//   -----------
  bool result=F; int c; N=0; do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n') );
  if ( (c=='Y')|(c=='y') ) result=T;
  else if ( (c!='N')&(c!='n') )
    if ( ('1'<=c)&(c<='9') ) {
      int i=c-'0'; while ( ('0'<=(c=getchar()))&&(c<='9') ) i=i*10+c-'0'; N=i; result=T;
    }   
  clearLine(c); return result;
} // getYorOrder

void getInt(int *n) { *n=0; scanf("%d", n); clearLine(getchar()); }
//   ------

bool validOrder(const int n) {
//   ----------
  if (n<=0) { printf("\aERROR: %d is not a positive integer.\n", n); return F; }
  if (n>USHRT_MAX) { printf("\aERROR: %d exceeds implementation limit of %d.\n", n, USHRT_MAX); return F; }
  return T;
} // validOrder

bool checkRange(int *p, int *q) {
//   ----------
  if (*q<*p) { const int t=*p; *p=*q; *q=t; } if (*p==0) *p=*q; return validOrder(*p)&&validOrder(*q);
} // checkRange

bool getInts(int c, int *p, int *q) {
//   -------
  bool chs=F, result=F; *p=*q=0; if (c==' ') do { c=getchar(); } while ((c==' ')|(c=='\t'));
  if (c=='-') { chs=T; c=getchar(); }
  if ( ('0'<=c)&(c<='9') ) {
    int i=c-'0'; while ( ('0'<=(c=getchar()))&&(c<='9') ) i=i*10+c-'0'; if (chs) i=-i; *p=i; chs=F;
    if ((c==' ')|(c=='\t')) {
      do { c=getchar(); } while ((c==' ')|(c=='\t')); if (c=='-') { chs=T; c=getchar(); }
      if ( ('0'<=c)&(c<='9') ) {
        int i=c-'0'; while ( ('0'<=(c=getchar()))&&(c<='9') ) i=i*10+c-'0'; if (chs) i=-i; *q=i;
      }
    }
    result=checkRange(p,q);
  }   
  clearLine(c); return result;
} // getInts
//================================================ output =======================================================

const int bufSize=1024;
bool openDir() {
//   -------
  int sub=0; char buf[bufSize], msg[bufSize+50];
  const char *baseName="./ReversibleSquares"; strcpy(buf, baseName);
  do {
    if (mkdir(buf, 0775)==0) break;
    if (errno!=EEXIST) {
      snprintf(msg, bufSize+50, "Can't make folder %s", buf); perror(msg); return F;
    }
    snprintf(buf, bufSize, "%s_%d", baseName, ++sub);
  } while (T); 
  if (chdir(buf)!=0) {
    snprintf(msg, bufSize+50, "Can't open folder %s", buf); perror(msg); return F;
  }
  printf("Output files are in folder %s\n", buf); return T;
} // openDir

FILE *openFile(const int n1, const int n2) {
//    --------
  int sub=0; FILE *wfp=NULL; char buf[bufSize], baseName[bufSize];
  if (n1==n2) snprintf(baseName, bufSize, "./Order%d", n1);
  else snprintf(baseName, bufSize, "./Order%dto%d", n1,n2);
  snprintf(buf, bufSize, "%s.txt", baseName);
  do {
    if (access(buf, F_OK)!=0) break;
    snprintf(buf, bufSize, "%s_%d.txt", baseName, ++sub);
  } while (T);
  if ((wfp=fopen(buf, "w"))==NULL) {
    char msg[bufSize+50]; snprintf(msg, bufSize+50, "\a\nCan't open for write %s", buf); perror(msg); }
  else printf("\nOutput file is %s\n", buf); return wfp;
} // openFile

typedef bool (*t_fprintFW)(FILE *fp, const int i);

bool fprintFW1(FILE *fp, const int i) { return fprintf(fp, "%1d",  i)>0; }
bool fprintFW2(FILE *fp, const int i) { return fprintf(fp, "%2d",  i)>0; }
bool fprintFW3(FILE *fp, const int i) { return fprintf(fp, "%3d",  i)>0; }
bool fprintFW4(FILE *fp, const int i) { return fprintf(fp, "%4d",  i)>0; }
bool fprintFW5(FILE *fp, const int i) { return fprintf(fp, "%5d",  i)>0; }
bool fprintFW6(FILE *fp, const int i) { return fprintf(fp, "%6d",  i)>0; }
bool fprintFW7(FILE *fp, const int i) { return fprintf(fp, "%7d",  i)>0; }
bool fprintFW8(FILE *fp, const int i) { return fprintf(fp, "%8d",  i)>0; }
bool fprintFW9(FILE *fp, const int i) { return fprintf(fp, "%9d",  i)>0; }
bool fprintFWa(FILE *fp, const int i) { return fprintf(fp, "%10d", i)>0; }

static t_fprintFW fprintFW[]={ NULL,
  fprintFW1, fprintFW2, fprintFW3, fprintFW4, fprintFW5,
  fprintFW6, fprintFW7, fprintFW8, fprintFW9, fprintFWa
};
const int maxFieldWidth=10;

bool printSquare(FILE *wfp) {
//   -----------
  const int fw0=fieldWidth, fw=fw0+1; if (fw>maxFieldWidth) return F;
  for (int i=0; i<N; i++) {
    if (!fprintFW[fw0](wfp, xSquare[i][0])) return F;
    for (int j=1; j<N; j++) if (!fprintFW[fw](wfp, xSquare[i][j])) return F;
    if (fputc('\n', wfp)==EOF) return F;
  }
  return fputc('\n', wfp)!=EOF;
} // printSquare

double factorial(const int n) { double x=1.; for (int i=2; i<=n; ++i) x*=(double)i; return x; }
//     ---------

void outputNumbers(const int n, const int principal, FILE *wfp) {
//   -------------
  const double factNd2=factorial(n/2), variations=pow(2., (double)(n<2?0:n-2))*factNd2*factNd2,
    reversible=variations*principal; char fmt[bufSize]; const char *s=N<10 ? "%1.0f" : "%1.2e";
  snprintf(fmt, bufSize, "\nPrincipal Squares: %s  Variations: %s  Reversible Squares: %s\n", "%d", s, s);
  printf(fmt, principal, variations, reversible);
} // outputNumbers
//================================================= make =====================================================

bool putFormat(const int x, const int y) {
//   ---------
  if ((listIndex<listSize)||increaseList(&list)) { t_format *q=&list[listIndex++]; q->x=x; q->y=y; return T; }
  return F;
} // putFormat

bool putFirstLevelFormats(bool *moreFormats) {
//   --------------------
  bool more=F; printf("\nput unnested formats\n");
  if (!putFormat(0, 0)) return F; // separator
  if (!putFormat(N, N)) return F; // full square
  if (!putFormat(0, 0)) return F; // separator
  for (int x=Nd2; x>=2; --x) if ((N%x)==0) { // col
    for (int m=2; m<(N/x); ++m) { const int mx=m*x; if ((mx<N)&((N%mx)==0)) { more=T; break; } }
    for (int y=2; y<=N; ++y) if ((N%y)==0) { // row
      if (!putFormat(x, y)) return F; // sub-square rectangle
      if (!putFormat(0, 0)) return F; // separator
    }
  }
  *moreFormats=more; return T;
} // putFirstLevelFormats

bool putNestedFormats(const int l, bool *moreFormats) {
//   ----------------
  printf("put nested %d formats\n", l); t_format *oldList=list; bool more=F;
  if (list==list1) { list=list2; listSize=list2Size; } else { list=list1; listSize=list1Size; }
  const int oldIndex=listIndex; int count=0; listIndex=0;
  for (int i=0; i<oldIndex; ++i) {
    t_format *p=&oldList[i]; if (!putFormat(p->x, p->y)) return F; ++count;
    if (p->x==0) { 
      if (count==(l+1)) {
        p=&oldList[i-1]; const int x1=p->x;
        if ((x1+x1)<N) {
          const int i1=i-l, i2=i1+l, y1=p->y; int x=N-x1, y=y1+y1;
          while (x>x1) {
            if (N%x==0) {
              for (int m=2; m<(N/x); ++m) { const int mx=m*x; if ((mx<N)&((N%mx)==0)) { more=T; break; }}
              while (y<=N) {
                if (N%y==0) {
                  for (int j=i1; j<i2; ++j) { // copy the format
                    p=&oldList[j]; if (!putFormat(p->x, p->y)) return F;
                  }
                  if (!putFormat(x, y)) return F; // nest rectangle
                  if (!putFormat(0, 0)) return F; // separator
                }
                y+=y1;
              } // while (y<=N)
            }
            x-=x1; y=y1+y1;
          } // while (x<N)
        }
      }
      count=0;
    } // if (p->x==0)
  } // for (int i
  *moreFormats=more; return T;
} // putNestedFormats

bool putFormats() {
//   ----------
  bool moreFormats=F, ok=putFirstLevelFormats(&moreFormats);
  if (ok) { int l=1; while (moreFormats) { if (!(ok=putNestedFormats(l++, &moreFormats))) break; }} return ok;
} // putFormats

void fillRectangle(const int ra, const int ca, const int rb, const int cb, int *pv, int i) {
//   -------------
  int v=*pv; t_format *q=&list[--i];
  if (q->x==0) { int **p=xSquare; for (int r=ra; r<rb; ++r) for (int c=ca; c<cb; ++c) p[r][c]=v++; }
  else {
    const int x=q->x, y=q->y;
    for (int r=ra; r<rb; r+=y) { for (int c=ca; c<cb; c+=x) { fillRectangle(r, c, r+y, c+x, &v, i); }}
  }
  *pv=v;
} // fillRectangle

bool writeError;
bool makeSquares(const int origin, FILE *wfp) {
//   -----------
  int count=0; writeError=F;
  if (putFormats()) {
    for (int i=1; i<listIndex; ++i) {
      t_format *q=&list[i];
      if (q->x==0) {
        q=&list[i-1]; const int x=q->x, y=q->y; int v=origin; 
        for (int r=0; r<N; r+=y) for (int c=0; c<N; c+=x) fillRectangle(r, c, r+y, c+x, &v, i-1);
        if (!printSquare(wfp)) { writeError=T; return F; } ++count;
        if ((count&0x3ff)==0) printf("... %d\n", count);
      }
    }
    outputNumbers(N&1?N-1:N, count, wfp); return T;
  }
  return F;
} // makeSquares

bool putNestedCountFormats(Uint *countp, bool *moreFormats) {
//   ---------------------
  t_format *oldList=list; Uint count=*countp; bool more=F;
  if (list==list1) { list=list2; listSize=list2Size; } else { list=list1; listSize=list1Size; }
  const int oldIndex=listIndex; listIndex=0;
  for (int i=0; i<oldIndex; ++i) {
    t_format *p=&oldList[i]; p=&oldList[i]; const int x1=p->x;
    if ((x1+x1)<N) { const int y1=p->y; int x=N-x1, y=y1+y1;
      while (x>x1) {
        if (N%x==0) {
          for (int m=2; m<(N/x); ++m) { const int mx=m*x; if ((mx<N)&((N%mx)==0)) { more=T; break; }}
          while (y<=N) { if (N%y==0) { if (!putFormat(x, y)) return F; /* nest rectangle */ ++count; } y+=y1; }
        }
        x-=x1; y=y1+y1;
      } // while (x<N)
    } // if ((x1+x1)<N)
  } // for (int i
  *countp=count; *moreFormats=more; return T;
} // putNestedCountFormats

bool putCountFormats(Uint *countp) {
//   ---------------
  bool more=F;
  for (int x=Nd2; x>=2; --x) if ((N%x)==0) { // col
    for (int m=2; m<(N/x); ++m) { const int mx=m*x; if ((mx<N)&((N%mx)==0)) { more=T; break; } }
    for (int y=2; y<=N; ++y) if ((N%y)==0) { // row
      listIndex=0; if (!putFormat(x, y)) return F; // sub-square rectangle
      ++*countp; more=T; while (more) if(!putNestedCountFormats(countp, &more)) return F;
    }
  }
  return T;
} // putCountFormats

bool countSquares(FILE *wfp) {
//   ------------
  Uint count=1; // full square
  if (putCountFormats(&count)) {
    printf("%u %u\n", N, count); writeError=(fprintf(wfp, "%u %u\n", N, count)<=0); return !writeError;
  }
  return F;
} // countSquares
//============================================== main ====================================================

void outputLocalTime() {
//   --------------
  time_t startTime=time(NULL); struct tm *local=localtime(&startTime);
  if (local!=NULL) {
    char dateTime[100];
    size_t slen=strftime(dateTime, 100, "%A %Y-%m-%d %X %Z\n\n\0", local); printf("\n%s", dateTime);
  }
} // outputLocalTime

void printElapsedTime(FILE *wfp, time_t startTime) {
//   ----------------
  const int et=(int)difftime(time(NULL), startTime);
  if (et>0) fprintf(wfp, "\nelapsed time %d:%02d:%02d\n", et/3600, et%3600/60, et%60);
} // printElapsedTime

bool mainCount() {
//   ---------
  bool ok=F; printf("Only counting squares.\n");
  do {  
    printf("Square order or order range: "); int n1=0, n2=0;
    if (getInts(' ', &n1, &n2)) {
      if (allocateStore(F)) {
        FILE *wfp=NULL;
        if ( (wfp=openFile(n1,n2))!=NULL) {
          time_t startTime=time(NULL);
          for (N=n1; N<=n2; ++N) {
            initGlobals(0,F); if (!(ok=countSquares(wfp))) break;
            if (writeError) { perror("\a\nError writing file"); break; }
          }
          printElapsedTime(stdout, startTime); fclose(wfp);
	}
      } // if (allocateStore())
    } // if (getInts
    if (ok) { printf("\nContinue? y (yes) or n (no)? "); if (!getY()) break; } else break;
  } while (T);
  freeStore(); return ok;
} // mainCount

bool mainMake() {
//   --------
  int origin=0; printf("\nInput the start number, (0 or 1): "); getInt(&origin);
  if ((origin<0)|(origin>1)) origin=1; bool inputSize=T, countOnly=F, ok=F;
  do {  
    if (inputSize) { printf("Input the order of the squares: "); getInt(&N); }
    if (validOrder(N)) {
      if (N>100) { printf("Only counting squares.\n"); countOnly=T; }
      if (allocateStore(!countOnly)) {
        initGlobals(origin, !countOnly); FILE *wfp=NULL;
        if ( (wfp=openFile(N,N))!=NULL) {
          time_t startTime=time(NULL); ok=countOnly?countSquares(wfp):makeSquares(origin, wfp);
          printElapsedTime(stdout, startTime);
          if (writeError) { perror("\a\nError writing file"); break; } fclose(wfp);
        }
      } // if (allocateStore())
    } // if (validOrder())
    if (ok) {
      printf("\nContinue? input y (yes) or n (no) or the order of the squares: ");
      if (getYorOrder()) inputSize=(N==0); else break;
    } else break;
  } while (T);
  freeStore(); return ok;
} // mainMake

int main() {
//  ----
  bool ok=F; outputLocalTime();
  if (openDir()) {
    bool countOnly=F; printf("Count only, y (yes) or n (no)? "); countOnly=getY();
    ok=countOnly ? mainCount() : mainMake();
  }
  printf("\nHit return to close the console.");
  while (T) if (getchar()=='\n') break; return ok ? EXIT_SUCCESS : EXIT_FAILURE;
} // main