/*
 *  File:    NFR_NBD.cpp
 *  Author:  S Harry White
 *  Created: 2018-11-17
 *  Updated: 2020-09-27
 *    Fix open_input when file name includes .txt.
 *  Updated: 2022-01-12
 *    Replace & with && where necessary. Tidy code.
 *  Updated: 2023-01-26
 *    Open output files in the current folder.
 *  Updated: 2023-01-28
 *    Change to compile with g++ for macOS.
 *  Updated: 2023-03-28
 *    Fix store allocation. Remove allocatedSize=0 from initGlobals().
 */

/*
 *  Converts Latin squares to natural order first row, (nfr), or natural order \diagonal, (nbd).
 *  Squares are converted to nbd only if the \diagonal is a transversal.
 */

//#include <ctype.h>
#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 int writeSize=100000000, startSize=32, reportLimit=10;
int N, M, NN, **Q, *X, fieldWidth, allocatedSize, notLatin, notBD, squareNumber, squareBytes, outBytes;
char outBuffer[writeSize], *outPointer;
const bool F=false, T=true; bool *numUsed=NULL, isLatin, nfrOption, bd, zeroBase, readError, writeError;

void initGlobals() {
//   -----------
  NN=N*N; M=N-1; fieldWidth=0; notLatin=0; notBD=0; squareNumber=0; squareBytes=0;
  outBytes=0; outPointer=outBuffer; isLatin=F; nfrOption=F; bd=F; zeroBase=F; readError=F; writeError=F;
} // initGlobals
//============================================== store ==================================================

const char *storeAllocFail="Storage allocation failed"; bool bell=T;
bool reportError(const char *msg) {
//   -----------
  printf("%sError: %s.\n", bell?"\a\n":"",  msg); if (bell) bell=F; return F;
} // reportError

void freeSquare(int*** square, const int size) {
//   ----------
  if (*square!=NULL) { for(int i=0; i<size; i++) free((*square)[i]); free(*square); *square=NULL; }
} // freeSquare

void freeStore() {
//   ---------
   freeSquare(&Q, allocatedSize); free(X); X=NULL; free(numUsed); numUsed=NULL; allocatedSize=0;
} // freeStore

bool allocateSquare(int*** square, const int size) {
//   --------------
  bool ok; *square=(int**) malloc(size*sizeof(int*)); ok=(*square!=NULL);
  if (ok) {
    int numAllocated=0;
    for(int i=0; i<size; i++) {
      int *p=(int*) malloc(size*sizeof(int)); (*square)[i]=p;
      if (p==NULL) { numAllocated=i; ok=F; break; }
    }
    if (!ok) freeSquare(square, numAllocated);
  }
  return ok;
} // allocateSquare

bool allocateT(const int size) { return ((X=(int*) malloc(size*sizeof(int)))!=NULL); }
//   ---------

bool allocateUsed(const int size) { return ((numUsed=(bool*) malloc(size*sizeof(bool)))!=NULL); }
//   ------------

bool allocateStore() {
//   -------------
  bool ok=T; int size=N; if (size<startSize) size=startSize;
  if (size>allocatedSize) {
    freeStore();
    if ((ok=allocateSquare(&Q,size))) if ((ok=allocateT(size+1)))
      if ((ok=allocateUsed(size+1))) allocatedSize=size;
    if (!ok) { reportError(storeAllocFail); freeStore(); }
  }
  return ok;
} // allocateStore
//============================================== input ==================================================

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

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

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

bool getYorOrder(int *n) {
//   -----------
  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

bool getFileName(char *buf, const int size) {
//   -----------
  int c, i=0; char *s=buf; do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n') ); *s=c;
  while (i++<size) if ( (*++s=getchar())=='\n') break;
  if (*s!='\n') { printf("\nFile name too long.\n"); clearLine(*s); return F; } *s='\0'; return T;
} // getFileName

const int bufSize=1024, outSize=bufSize+50;
void adjustName(char *buf) {
//   ----------
  char *s=buf; bool txt=F;
  if ((*s!='.')&(*s!='/')) { // Assume in current folder.
    char tmp[bufSize]; snprintf(tmp, bufSize, "./%s", buf); strcpy(buf, tmp);
  }
  if (access(buf, R_OK)!=0) {
    while (*s++!='\0')
      ; --s;  if ((strlen(buf)>6)&&(*s--=='t')&&(*s--=='x')&&(*s--=='t')&&(*s=='.')) txt=T;
    if (!txt) strcat(buf, ".txt"); // no .txt entered, add it
  }
} // adjustName

FILE *openInput(char buf[bufSize]) {
//    ---------
  char *rFname=NULL; FILE *rfp=NULL;
  do {
    printf("\nEnter the name of the squares file: ");
    if (getFileName(buf, bufSize-6)) { rFname=buf; break; }
    printf("\a\nCan't read the file name. Try again? y (yes) or n (no) "); if (!getY()) break;
  } while (T);
  if (rFname!=NULL) {
    adjustName(buf);
    if ((rfp=fopen(buf, "r"))==NULL) {
      const int msgSize=bufSize+50; char msg[msgSize];
      snprintf(msg, msgSize, "\a\nCan't open for read %s", buf); perror(msg);
    }
  }
  return rfp;
} // openInput

void checkLatin(int **x, const int n) {
//   -----------
  const int min=zeroBase?0:1, max=n+min-1, m=n-1; bool ls=T, dls=T;
  for (int r=0; r<n; ++r) {
    for (int i=min; i<=max; i++) numUsed[i]=F; for (int c=0; c<n; ++c) numUsed[x[r][c]]=T;
    for (int i=min; i<=max; ++i) if (!numUsed[i]) { ls=F; break; } if (!ls) break;
  }
  if (ls) for (int c=0; c<n; ++c) {
    for (int i=min; i<=max; i++) numUsed[i]=F; for (int r=0; r<n; ++r) numUsed[x[r][c]]=T;
    for (int i=min; i<=max; ++i) if (!numUsed[i]) { ls=F; break; } if (!ls) break;
  }
  if (ls&!nfrOption) {
    bd=T; for (int i=min; i<=max; i++) numUsed[i]=F; for (int r=0; r<n; ++r) numUsed[x[r][r]]=T;
    for (int i=min; i<=max; ++i) if (!numUsed[i]) { bd=F; break; }
  }
  isLatin=ls;
} // checkLatin

int getWidth(int i) {
//  --------
  int width=1; while ((i/=10)!=0) ++width; if (width>10) width=10; /* limited by sprintFW11 */ return width;
} // getWidth

bool readSquare(FILE *rfp) {
//   ----------
  int smallest=INT_MAX, biggest=INT_MIN;
  for (int r=0; r<N; r++) for (int c=0; c<N; c++) {
	  int tmp, rv;
    if ( (rv=fscanf(rfp, "%d", &tmp))==1) {
      if (tmp<smallest) smallest=tmp; if (tmp>biggest) biggest=tmp; Q[r][c]=tmp;
    } else {
      if ( (rv!=EOF)|(r!=0)|(c!=0) ) { readError=T; printf("\a\nError reading square from file.\n"); } return F;
    }
  }
  ++squareNumber; zeroBase=(smallest==0);
  if ((zeroBase&(biggest==M))|((smallest==1)&(biggest==N))) checkLatin(Q, N); else isLatin=F;
  if (isLatin) {
    if (!nfrOption&!bd) {
      if (notBD<reportLimit) printf("Square %d, \\diagonal is not a transversal.\n", squareNumber); ++notBD;
    }
  } else { if (notLatin<reportLimit) printf("Square %d is not Latin.\n", squareNumber); ++notLatin; }
  fieldWidth=(zeroBase)?getWidth(M):getWidth(N); squareBytes=NN*(fieldWidth+1)+1; return T;
} // readSquare
//================================================= output ====================================================

void stripName(char *inFname, char *obuf) {
//   ---------
  char *s=inFname; while (*s++!='\0');
  while (--s!=inFname)
    if (*s=='.') *s='\0';                          // Remove .txt
    else if ((*s=='/')|(*s=='\\')) { ++s; break; } // Remove any directory path
  strcpy(obuf, s); 
} // stripName

char outputFile[outSize];
int openOutput(char inFname[bufSize], bool nfr) {
//  ----------
  int sub=0, wfd=-1; const int baseSize=bufSize+25; 
  char baseName[baseSize], buf[outSize]; stripName(inFname, buf);
  snprintf(baseName, baseSize, "./%sTo%s", buf, nfr?"NFR":"NBD");
  snprintf(buf, outSize, "%s.txt", baseName);
  do {
    if (access(buf, F_OK)!=0) break; snprintf(buf, outSize, "%s_%d.txt", baseName, ++sub);
  } while (T);
  if ((wfd=open(buf, O_CREAT|O_WRONLY, 0644))==-1) {
    char msg[bufSize+50]; snprintf(msg, bufSize+50, "\a\nCan't open for write %s", buf); perror(msg);
  } else {
    printf(".. output file is %s\n", buf); snprintf(outputFile, outSize, "%s", buf);
  }
  return wfd;
} // openOutput

typedef void (*t_sprintFW)(char *s, const int i);
void sprintFW1 (char *s, const int i) { snprintf(s,  2, "%1d",  i); }
void sprintFW2 (char *s, const int i) { snprintf(s,  3, "%2d",  i); }
void sprintFW3 (char *s, const int i) { snprintf(s,  4, "%3d",  i); }
void sprintFW4 (char *s, const int i) { snprintf(s,  5, "%4d",  i); }
void sprintFW5 (char *s, const int i) { snprintf(s,  6, "%5d",  i); }
void sprintFW6 (char *s, const int i) { snprintf(s,  7, "%6d",  i); }
void sprintFW7 (char *s, const int i) { snprintf(s,  8, "%7d",  i); }
void sprintFW8 (char *s, const int i) { snprintf(s,  9, "%8d",  i); }
void sprintFW9 (char *s, const int i) { snprintf(s, 10, "%9d",  i); }
void sprintFW10(char *s, const int i) { snprintf(s, 11, "%10d", i); }
void sprintFW11(char *s, const int i) { snprintf(s, 12, "%11d", i); }
static t_sprintFW sprintFW[]=
  {
    NULL,      sprintFW1, sprintFW2, sprintFW3, sprintFW4, sprintFW5,
    sprintFW6, sprintFW7, sprintFW8, sprintFW9, sprintFW10, sprintFW11
  };

void printLSany(int **Q, const int wfd) {
//   ----------
  char *s=outPointer; const int fw=fieldWidth, fw1=fieldWidth+1;
  for (int r=0; r<N; ++r) {
    sprintFW[fw](s, Q[r][0]); s+=fw;
    for (int c=1; c<N; ++c) { sprintFW[fw1](s, Q[r][c]); s+=fw1;} *s++='\n';
  }
  *s++='\n'; outPointer=s; outBytes+=squareBytes;  
} // printLSany

void printLSLT40(int **Q, const int wfd) {
//   -----------
  char *s=outPointer;
  for (int r=0; r<N; ++r) {
    for (int c=0; c<N; ++c) { const int v=Q[r][c];
      if (v<10) { *s++=' '; *s++='0'+v; } else if (v<20) { *s++='1'; *s++='0'-10+v; }
      else if (v<30) { *s++='2'; *s++='0'-20+v; } else { *s++='3'; *s++='0'-30+v; }
      if (c==M) *s++='\n'; else *s++=' ';
    }
  }
  *s++='\n'; outPointer=s; outBytes+=squareBytes;
} // printLSLT40

void printLSLT30(int **Q, const int wfd) {
//   -----------
  char *s=outPointer;
  for (int r=0; r<N; ++r) {
    for (int c=0; c<N; ++c) { const int v=Q[r][c];
      if (v<10) { *s++=' '; *s++='0'+v; } else if (v<20) { *s++='1'; *s++='0'-10+v; }
      else { *s++='2'; *s++='0'-20+v; } if (c==M) *s++='\n'; else *s++=' ';
    }
  }
  *s++='\n'; outPointer=s; outBytes+=squareBytes;
} // printLSLT30

void printLSLT20(int **Q, const int wfd) {
//   -----------
  char *s=outPointer;
  for (int r=0; r<N; ++r) {
    for (int c=0; c<N; ++c) { const int v=Q[r][c];
      if (v<10) { *s++=' '; *s++='0'+v; } else { *s++='1'; *s++='0'-10+v; }
      if (c==M) *s++='\n'; else *s++=' ';
    }
  }
  *s++='\n'; outPointer=s; outBytes+=squareBytes;
} // printLSLT20

void printLT10(int **Q, const int wfd) {
//  ---------
  char *s=outPointer;
  for (int r=0; r<N; ++r) {
    *s++='0'+Q[r][0]; for (int c=1; c<N; ++c) { *s++=' '; *s++='0'+Q[r][c]; } *s++='\n';
  }
  *s++='\n'; outPointer=s; outBytes+=squareBytes;  
} // printLT10

bool printLS(int **Q, const int wfd) {
//   -------
  if ((outBytes+squareBytes)>=writeSize) {
    if (write(wfd, outBuffer, outBytes)!=outBytes) { writeError=T; return F; }
    outBytes=0; outPointer=outBuffer;
  }
  switch (fieldWidth) {
    case 1: printLT10(Q,wfd); break;
    case 2: {
      const int big=zeroBase?M:N;
      if (big<20) printLSLT20(Q,wfd); else if (big<30) printLSLT30(Q,wfd);
      else if (big<40) printLSLT40(Q,wfd); else printLSany(Q,wfd);
    } break;
    default: printLSany(Q,wfd); break;
  }
  return T;
} // printLS

void outputLast(const int wfd) { if ((outBytes!=0)&&(write(wfd, outBuffer, outBytes)!=outBytes)) writeError=T; }
//   ----------
//=================================================== permute ===================================================

bool permuteToNFR(int **Q, int *X, const int wfd) { // natural order first row
//   ------------
  bool nfr=T;
  if (zeroBase) {
    for (int C=0; C<N; ++C) if (Q[0][C]!=C) { nfr=F; break; }
    if (!nfr) for (int C=0; C<N; ++C) { X[Q[0][C]]=C; Q[0][C]=C; }
  } else {
    for (int C=0; C<N; ++C) if (Q[0][C]!=(C+1)) { nfr=F; break; }
    if (!nfr) for (int C=0; C<N; ++C) { X[Q[0][C]]=C+1; Q[0][C]=C+1; }
  }
  if (!nfr) for (int r=1; r<N; ++r) for (int c=0; c<N; ++c) Q[r][c]=X[Q[r][c]]; return printLS(Q,wfd);
} // permuteToNFR

bool permuteToNBD(int **Q, int *X, const int wfd) { // natural order \diagonal
//   ------------
  bool nbd=T;
  if (zeroBase) {
    for (int C=0; C<N; ++C) if (Q[C][C]!=C) { nbd=F; break; }
    if (!nbd) for (int C=0; C<N; ++C) X[Q[C][C]]=C;
  } else {
    for (int C=0; C<N; ++C) if (Q[C][C]!=(C+1)) { nbd=F; break; }
    if (!nbd) for (int C=0; C<N; ++C) X[Q[C][C]]=C+1;
  }
  if (!nbd) for (int r=0; r<N; ++r) for (int c=0; c<N; ++c) Q[r][c]=X[Q[r][c]]; return printLS(Q,wfd);
} // permuteToNBD
//================================================== 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\0", local); printf("\n%s", dateTime);
  }
} // outputLocalTime

void printElapsedTime(time_t startTime, const char c) {
//   ---------------- 
  int et=(int)difftime(time(NULL), startTime);
  if (et>0) printf("%celapsed time %d:%02d:%02d\n", c, et/3600, et%3600/60, et%60);
} // printElapsedTime

int main() {
//  ----
  bool ok=F, inputSize=T; allocatedSize=0; outputLocalTime();
  do {
    if (inputSize) { printf("order? "); N=getInt(); }
    if (N<=0) printf("\aOrder must be a positive integer.\n\n");
    else {
      if (allocateStore()) {
        initGlobals(); char buf[bufSize]; FILE *rfp=openInput(buf);
        if (rfp!=NULL) {
          printf("Enter 1 for nfr or 2 for nbd: "); nfrOption=(getInt()==1);
          const int wfd=openOutput(buf, nfrOption);
          if (wfd!=-1) {
            time_t startTime=time(NULL);
            if (nfrOption) while (readSquare(rfp)) { if (isLatin&&!permuteToNFR(Q, X, wfd)) break; }
            else while (readSquare(rfp)) { if (isLatin&bd) if (!permuteToNBD(Q, X, wfd)) break; }
            if (!writeError) { outputLast(wfd); ok=T; } close(wfd);
            if (ok) {
              if ((notLatin==0)&(notBD==0)) printf("Squares %d\n", squareNumber);
              else { printf("Squares in: %d", squareNumber);
                if (notLatin!=0) printf(", not Latin: %d", notLatin);
                if (notBD!=0) printf(", \\diagonal not transversal: %d", notBD);
                printf(", out: %d\n", squareNumber-notLatin-notBD);
              }
            }
            if ((!ok)|((squareNumber-notLatin-notBD)==0)) remove(outputFile); printElapsedTime(startTime, '\n');
          }
          fclose(rfp);
        }
      }
    }
    printf("Continue? input Y or the square order for yes, N for no: ");
    if (getYorOrder(&N)) inputSize=(N==0); else break;
  } while (T);
  freeStore(); printf("\nHit return to close the console.");
  while (T) if (getchar()=='\n') break; return ok ? EXIT_SUCCESS : EXIT_FAILURE;
} // main