/*
 *  File:    ReversibleToAssociative.cpp
 *  Author:  S Harry White
 *  Created: 2014-04-06
 *  Updated: 2022-01-20
 *    Tidy code.
 * Updated: 2023-02-21
 *   Improve openInput and openOutput.
 */

#include "stdafx.h"
#include <conio.h>
#include <direct.h>
#include <errno.h>
#include <io.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <Windows.h>

int N,             // The order of the square.
    Nm1,           // N-1
    Nm2,           // N-2
    Nd2,           // N/2
    Nd2m1,         // N/2-1 
    N3d4,          // 3*N/4
    N3m2d2,        // (3*N-2)/2
    NN,            // N*N
    NNm1,          // NN-1
    NNp1,          // NN+1

    magicConstant, // 1 .. NN
    magicSum,      // 0 .. NN-1 or 1 .. NN
    Sum2,          //           "
    Sum4,          //           "
    startSize=32,
    **xSquare=NULL, **tSquare=NULL, allocatedSize, squareNum;
const bool F=false, T=true; bool zeroBase, *numberUsed=NULL;

void initGlobals() {
//  -----------
  Nm1=N-1; Nm2=N-2; Nd2=N/2; Nd2m1=Nd2-1; N3d4=3*N/4; N3m2d2=(3*N-2)/2;
  NN=N*N; NNm1=NN-1; NNp1=NN+1; magicConstant=Nd2*(NN+1); squareNum=0;
} // initGlobals
//================================================= store =====================================================

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

void freeUsed() { if (numberUsed!=NULL) { free(numberUsed); numberUsed=NULL; }}
//   --------

void freeStore() {
//   --------- 
  freeSquare(&xSquare, allocatedSize); freeSquare(&tSquare, allocatedSize); freeUsed(); 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=size;
    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 allocateUsed(const int size) { return ((numberUsed=(bool*) malloc(size*sizeof(bool)))!=NULL); }
//   ------------

bool allocateStore(int size) {
//   -------------
  bool ok=T; if (size<startSize) size=startSize;
  if (size>allocatedSize) {
    freeStore(); if (ok=allocateSquare(&tSquare, size)) if (ok=allocateSquare(&xSquare, size))
    if (ok=allocateUsed(size*size+1))  allocatedSize=size; if (!ok) freeStore();
  }
  return ok;
} //allocateStore
//================================================= 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 getYorInt(int *n) { // Yes or No or integer
//   ---------
  bool result=F; int c; *n=-1; do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n') );
  if ( (c=='Y')|(c=='y') ) result=T;
  else if ( (c!='N')&(c!='n') )
    if ( ('0'<=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;
} // getYorInt

int getInt() { int n=0; scanf_s("%d", &n); clearLine(getchar()); return n; }
//  ------
  
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;
void check_txt(char *buf) {
//   ---------
  char *s=buf; bool txt=F; while (*s++!='\0');
  while (--s!=buf) if (*s=='.') { txt=(*++s=='t')&&(*++s=='x')&&(*++s=='t')&&(*++s=='\0'); break; }
  if (!txt) strcat_s(buf, bufSize, ".txt");
} // check_txt

FILE *openInput(char buf[bufSize]) {
//    ---------
  char *rFname=NULL; FILE *rfp=NULL;
  do {
    printf("\nEnter the name of the squares file: ");
    if (getFileName(buf, bufSize-4)) { 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) {
    check_txt(buf);  
    if (fopen_s(&rfp, buf, "r")!=0) {
      const int msgSize=bufSize+50; char msg[msgSize];
      sprintf_s(msg, msgSize, "\a\nCan't open for read %s", buf); perror(msg);
    }
  }
  return rfp;
} // openInput

int fieldWidth;
int getWidth(const int number) { int width=1, i=number; while ((i=i/10)!=0) ++width; return width; }
//  --------

void assignGlobals() {
//   -------------
  if (zeroBase) { fieldWidth=getWidth(NNm1); magicSum=magicConstant-N; Sum2=NNm1; }
  else { fieldWidth=getWidth(NN); magicSum=magicConstant; Sum2=NNp1; } Sum4=Sum2+Sum2;
} // assignGlobals

bool allNumbersUsed(int **x) {
//   --------------
  for (int i=0; i<=NN; ++i) numberUsed[i]=F;
  for (int r=0; r<N; ++r) for (int c=0; c<N; ++c) { const int t=x[r][c]; if ((t>=0)&(t<=NN)) numberUsed[t]=T; }
  for (int i=1; i<NN; ++i) if (!numberUsed[i]) return F; if (numberUsed[0]==numberUsed[NN]) return F; return T;
} // allNumbersUsed

bool isReversible(int **x) {
//   ------------
  if (!allNumbersUsed(x)) return F;
  // Check reverse similarity of half rows.
  for (int r=0; r<N; ++r) {
    const int t=x[r][0]+x[r][Nm1]; for (int c=1; c<Nd2; ++c) if ((x[r][c]+x[r][Nm1-c])!=t) return F;
  }
  // Check reverse similarity of half columns.
  for (int c=0; c<N; ++c) {
    const int t=x[0][c]+x[Nm1][c]; for (int r=1; r<Nd2; ++r) if ((x[r][c]+x[Nm1-r][c])!=t) return F;
  }
  // Check cross-corner sum equality.
  for (int r=0; r<N; ++r) for (int c=0; c<N; ++c) for (int i=0; i<(N-r); ++i)
    for (int j=0; j<(N-c); ++j) if ((x[r][c]+x[r+i][c+j])!=(x[r][c+j]+x[r+i][c])) return F; return T;
} // isReversible

bool checkSquare(const int smallest, const int biggest) {
//   -----------
  if ((smallest<0)|(biggest>NN)) {
    printf("\a\nError: Invalid number %d in square %d.\n\n", (smallest<0) ? smallest : biggest, squareNum);
    return F;
  } else {
    if (!isReversible(xSquare)) { printf("\a\nError: Square %d is not reversible.\n\n", squareNum); return F; }
  }
  return T;
} // checkSquare

bool readSquare(FILE *rfp) {
//   ----------
  const int n=N; int smallest=LONG_MAX, biggest=LONG_MIN;
  for (int r=0; r<n; r++) {
    for (int c=0; c<n; c++) {
	    int tmp, rv;
      if ( (rv=fscanf_s(rfp, "%d", &tmp))==1) {
        if (tmp<smallest) smallest=tmp; if (tmp>biggest) biggest=tmp; xSquare[r][c]=tmp;
      } else {
        if ( (rv!=EOF)|(r!=0)|(c!=0) ) printf("\a\nError reading square %d from file.\n", squareNum+1);
        return F;
      }
    }
  }
  ++squareNum; zeroBase=(smallest==0); assignGlobals(); return checkSquare(smallest, biggest);
} // readSquare
//==================================================== output ===================================================

const int outSize=bufSize+50; bool bell=T; char fmt[bufSize];
bool programError(char *s) {
//   ------------
  sprintf_s(fmt, bufSize, "%sProgram error: %s.\nPlease report by e-mail.\n", bell ? "\a" : "", s); 
  printf(fmt, squareNum); return bell=F;
} // programError

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

FILE *openOutput(char *inFname) {
//    ----------
  const int baseSize=bufSize+25; char baseName[baseSize], buf[outSize]; FILE *wfp=NULL; int sub=0;
  sprintf_s(baseName, baseSize, "%sA", inFname); sprintf_s(buf, outSize, "%s.txt", baseName);
  do {
    if (_access_s(buf, 00)==ENOENT) break; sprintf_s(buf, outSize, "%s_%d.txt", baseName, ++sub);
  } while (T);
  if (fopen_s(&wfp, buf, "w")==0) printf("Output file is %s.\n", buf);
  else {
    char msg[outSize+50];
    sprintf_s(msg, outSize+50, "\a\nCan't open for write %s", buf); perror(msg);
  }
  return wfp;
} // openOutput

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 writeSquare(FILE *wfp, int **x) {
//   -----------
  const int n=N, fw0=fieldWidth, fw=fw0+1; if (fw>maxFieldWidth) return F;
  for (int r=0; r<n; r++) {
    if (!fprintFW[fw0](wfp, x[r][0])) return F;
    for (int c=1; c<n; c++) if (!fprintFW[fw](wfp, x[r][c])) return F;
    if (fputc('\n', wfp)==EOF) return F;
  }
  return fputc('\n', wfp)!=EOF;
} // writeSquare
//===================================================== check =====================================================

enum magicType { notMagic, normalSemiMagic, otherSemiMagic, normalMagic, otherMagic };
const magicType basicType[2][2]={ {otherSemiMagic, normalSemiMagic}, {otherMagic, normalMagic} };
magicType isNormal(int **x) {
//        --------
  int sumX, sumY, sumXY=0, sumYX=0, chkSum;
  for (int r=0; r<N; ++r) {
    sumX=0; sumY=0; for (int c=0; c<N; ++c) { sumX+=x[r][c]; sumY+=x[c][r]; }
    if (r==0) chkSum=sumX; if ((sumX!=chkSum)|(sumY!=chkSum)) return notMagic; sumXY+=x[r][Nm1-r]; sumYX+=x[r][r];
  }
  return basicType[(sumXY==chkSum)&(sumYX==chkSum)][allNumbersUsed(x)&(chkSum==magicSum)];
} // isNormal

bool isAssociative(int **x) {
//   -------------
  if (isNormal(x)!=normalMagic) return F;
  for (int r=0; r<Nd2; ++r) for (int c=0; c<N; ++c) if (x[r][c]+x[Nm1-r][Nm1-c]!=Sum2) return F; return T;
} // isAssociative

bool checkSquareA(int **x) {
//   -------------
  if (!isAssociative(x))  return programError("Output square %d is not associative"); return T;
} // checkSquareA
//===================================================== make =====================================================

void reverseRowsRightHalf(int **x) {
//    -------------------
  for (int r=0; r<N; ++r) for (int c=Nd2; c<N3d4; ++c) {
    const int t=x[r][c]; x[r][c]=x[r][N3m2d2-c]; x[r][N3m2d2-c]=t;
  }
} // reverseRowsRightHalf

void  reverseColumnsBottomHalf(int **x) {
//    ------------------------
  for (int c=0; c<N; ++c) for (int r=Nd2; r<N3d4; ++r) {
    const int t=x[r][c]; x[r][c]=x[N3m2d2-r][c]; x[N3m2d2-r][c]=t;
  }
} // reverseColumnsBottomHalf

#define xForm(iX, jX) for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) t[iX][jX]=x[i][j]
#define xCopy() for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) x[i][j]=t[i][j]

void applyTransform(int **x) { int **t=tSquare, k=Nd2, l=k+1; xForm((i+k*j)%N, (k*i+l*j)%N); xCopy(); }
//   --------------

void putInFrenicleForm(int **x) {
//   -----------------
  bool inFrenicleForm=F; int **t=tSquare; const int minC=min(min(x[0][0], x[0][Nm1]), min(x[Nm1][0], x[Nm1][Nm1]));
  if (x[0][0]==minC) {
    if (x[0][1]<x[1][0]) inFrenicleForm=T;
    else xForm(j,i);                                 // YX
  } else if (x[0][Nm1]==minC) {
    if (x[1][Nm1]<x[0][Nm2]) xForm(Nm1-j,i);         // -90
    else xForm(i,Nm1-j);                             // Y   
  } else if (x[Nm1][Nm1]==minC) {
    if (x[Nm1][Nm2]<x[Nm2][Nm1]) xForm(Nm1-i,Nm1-j); // 180
    else xForm(Nm1-j,Nm1-i);                         // XY
  } else { // x[Nm1][0]==minC
    if (x[Nm2][0]<x[Nm1][1]) xForm(j,Nm1-i);         // 90
    else xForm(Nm1-i,j);                             // X
  }
  if (!inFrenicleForm) xCopy();
} // putInFrenicleForm

// In the square below:
//
//   a, b, c, d are the square corners, e is (N/2-1, N/2), f is (N/2-1, N/2-1)
//
//            a . . b
//            . f e .
//            . . . .
//            c . . d
//
// Orients the square corners as above where a<b<c<d.
// Then, if a>e and b>f inverts the square,
// else, if a>e and b<f mirrors the square.
//
void orientRSquare(int **x) {
//   -------------
  bool change=T; int **t=tSquare; const int minC=min(min(x[0][0], x[0][Nm1]), min(x[Nm1][0], x[Nm1][Nm1]));
  if (x[0][0]==minC) {
    if (x[0][Nm1]<x[Nm1][0]) change=F;
    else xForm(j,i);                             // YX
  } else if (x[0][Nm1]==minC) {
    if (x[Nm1][Nm1]<x[0][0]) xForm(Nm1-j,i);     // -90
    else xForm(i,Nm1-j);                         // Y   
  } else if (x[Nm1][Nm1]==minC) {
    if (x[Nm1][0]<x[0][Nm1]) xForm(Nm1-i,Nm1-j); // 180
    else xForm(Nm1-j,Nm1-i);                     // XY
  } else { // x[Nm1][0]==minC
    if (x[0][0]<x[Nm1][Nm1]) xForm(j,Nm1-i);     // 90
    else xForm(Nm1-i,j);                         // X
  }
  if (change) xCopy();
  if (x[0][0]>x[Nd2m1][Nd2]) {
    if (x[0][Nm1]>x[Nd2m1][Nd2m1]) xForm(Nm1-i,j); // X
    else xForm(i,Nm1-j);                           // Y
    xCopy();
  }
}  // orientRSquare

bool getAssociative(FILE *wfp) {
//   --------------
  int **x=xSquare; bool good=F, write=F;
  orientRSquare(x); reverseRowsRightHalf(x); reverseColumnsBottomHalf(x);
  applyTransform(x); reverseRowsRightHalf(x); reverseColumnsBottomHalf(x);
  putInFrenicleForm(x); good=checkSquareA(x); write=writeSquare(wfp, x); return good&write;
} // getAssociative
//===================================================== main ========================================================

bool checkN() {
//   ------
  if ((N<=0)|((N&3)!=0)) { printf("\aOrder %d is not a positive doubly even order.\n\n", N); return F; } return T;
} // checkN

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

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

bool doAnother(bool getError, bool *inputSize) {
//   ---------
  if (!getError) {
    printf("\nContinue? input y (yes) or n (no) or the order of the squares: ");
    if (getYorInt(&N)) { *inputSize=(N<0); return T; }
  }
  freeStore(); return F;
} // doAnother

int main() {
//  ----
  outputLocalTime(); bool another=T, inputSize=T, getError=F, ok=F;
  do { // for each input file
    if (inputSize) { printf("\nInput the order of the squares: "); N=getInt(); }
    if (checkN()) {
      initGlobals();
      if (allocateStore(N)) {
        char ibuf[bufSize], obuf[bufSize]; FILE *rfp=openInput(ibuf);
        if (rfp!=NULL) {
          time_t startTime=time(NULL); stripName(ibuf, obuf); FILE *wfp=openOutput(obuf);
          if (wfp!=NULL) {
            squareNum=0; bell=T;
            while (readSquare(rfp)) { if (getError=!getAssociative(wfp)) break; } fclose(wfp); 
          } // if (wfp!=NULL)       
          reportElapsedTime(startTime); if (!getError) ok=T; fclose(rfp);
        } // (rfp!=NULL)
      } // (allocateStore())
    } // (checkN
    another=doAnother(getError, &inputSize);
  } while (another);
  printf("\nPress a key to close the console");
  while (!_kbhit()) Sleep(250); return ok ? EXIT_SUCCESS : EXIT_FAILURE;
} // main