/*
 *  File:    GetDiagonals.cpp
 *  Author:  S Harry White
 *  Created: 2020-08-01
 *  Updated: 2021-05-20
 *    Improve store allocation. 
 *    Remove .txt from in-file name to use name in out-file name.
 *    Add 1 or 2 to out-file name to indicate which diagonal.
 *  Updated: 2022-01-02
 *    Replace & with && and | with || where necessary.
 *  Updated: 2023-01-28
 *    Change to compile with g++ for macOS.
 */

/*
 *  Gets \ or / diagonals and sorts them in ascending order removing duplicates.
 */

//#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>

int N, // order of the squares
    M, // N-1
    **iSquare=NULL, **Diags=NULL, *diag=NULL,
    allocatedSize, allocatedDiagsSize, squareNumber, fieldWidth, Sindex;
const int startSize=10, startDiagsSize=10000, maxDiagsIncr=1000000, bufSize=1024, outSize=bufSize+50;
const bool F=false, T=true; bool bell; //bool readError;

void initGlobals() { bell=T; squareNumber=0; fieldWidth=0, Sindex=0; M=N-1; } //readError=F;
//   -----------
//============================================== allocate store =============================================

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

void freeInts(int **a) { if (*a!=NULL) { free(*a); *a=NULL; }}
//   ---------

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

void freeStore() {
//   ---------
  freeIntArray(&iSquare, allocatedSize); allocatedSize=0;
  freeIntArray(&Diags, allocatedDiagsSize); allocatedDiagsSize=0; freeInts(&diag);
} // freeStore

bool allocateInts(int **l, const int n) { *l=(int*)malloc(n*sizeof(int)); return *l!=NULL; }
//   ------------

bool allocateIntArray(int ***a, const int n1, const int n2) {
//   ----------------
  bool ok=((*a=(int**) malloc(n1*sizeof(int*)))!=NULL);
  if (ok) {
    int numAllocated=n1;
    for (int i=0; i<n1; i++) {
      int *p=(int*) malloc(n2*sizeof(int)); if (p==NULL) { numAllocated=i; ok=F; break; } (*a)[i]=p;
    }
    if (!ok) freeIntArray(a, numAllocated);
  }
  return ok;
} // allocateIntArray

bool allocateStore(int size) {
//   -------------
  bool ok=T; if (size<startSize) size=startSize;
  if (size>allocatedSize) {
    freeStore();
    if ((ok=allocateIntArray(&iSquare, size, size))) {
      if ((ok=allocateIntArray(&Diags, startDiagsSize, size))) ok=allocateInts(&diag, size);
    }
    if (ok) { allocatedSize=size, allocatedDiagsSize=startDiagsSize; }
    else { freeStore(); reportError(storeAllocFail); }
  }
  return ok;
} //allocateStore

bool increaseDiags() {
//   -------------
  bool ok; int incr=(allocatedDiagsSize>maxDiagsIncr)?maxDiagsIncr:allocatedDiagsSize;
  int length=allocatedSize, size=allocatedDiagsSize+incr, **t=(int**) malloc(size*sizeof(int*));
  if ((ok=(t!=NULL))) {
    for (int i=0; i<allocatedDiagsSize; i++) t[i]=Diags[i]; free(Diags); Diags=t;
    int numAllocated=size;
    for(int i=allocatedDiagsSize; i<size; i++) {
      int *p=(int*) malloc(length*sizeof(int)); Diags[i]=p;
      if (p==NULL) { numAllocated=i; ok=F; break; }
    }
    if (!ok) freeIntArray(&Diags, numAllocated);
  }
  if (ok) { allocatedDiagsSize=size; printf("increase store to %d diags\n", size); }
  else reportError(storeAllocFail);
  return ok;
} // increaseDiags
//=============================================== 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');
} // getY

bool getYorOrder() { // Y, N, or 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

int getInt(const char *s) {
//  ------
  printf("%s? ", s); int n=0; scanf("%d", &n); clearLine(getchar()); return n;
}

bool getFileName(char *buf, 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; }
  while ( (*--s==' ')||(*s=='\t') )
    ; /* strip trailing whitespace */ *++s='\0'; return T;
} // getFileName

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 *fin) {
//    ---------
  FILE *rfp=NULL; char buf[bufSize]; strcpy(buf, fin); 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);
  } else printf("Input file is %s\n", buf);
  return rfp;
} // openInput

const int maxFieldWidth=10;
int getWidth(int i) {
//  --------
  const bool isSigned=i<0; int width=1; if (isSigned) i=-i;
  while ((i=i/10)!=0) ++width; if (isSigned) ++width;
  if (width>maxFieldWidth) width=maxFieldWidth; return width;
} // getWidth

bool readSquare(FILE *rfp, const int diag) {
//   ----------
  int smallest=INT_MAX, biggest=INT_MIN, width;
  for (int r=0; r<N; r++) {
    for (int c=0; c<N; c++) {
	    int tmp, rv;
      if ((rv=fscanf(rfp, "%d", &tmp))==1) {
        iSquare[r][c]=tmp;
        if (((diag==1)&(r==c))|((diag==2)&(r==(M-c)))) {
          if (tmp<smallest) smallest=tmp; if (tmp>biggest) biggest=tmp;
        }
      } else {
        if ( (rv!=EOF)|(r!=0)|(c!=0) ) { printf("\a\nError reading square from file.\n"); } //readError=T;
        return F;
      }
    }
  }
  int sWidth=getWidth(smallest), bWidth=getWidth(biggest); width=sWidth>bWidth ? sWidth : bWidth;
  if (width>fieldWidth) fieldWidth=width; ++squareNumber; return T;
} // readSquare
//================================================= output ===============================================

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

char outFile[outSize];
FILE *openOutput(char inFname[bufSize], const int d, const char *tag) {
//    ----------
  int sub=0; FILE *wfp=NULL; const int baseSize=bufSize+25;
  char baseName[baseSize], buf[outSize]; stripName(inFname, buf);
  snprintf(baseName, baseSize, "./%s-%d%s", buf, d, tag); snprintf(buf, outSize, "%s.txt", baseName);
  do {
    if (access(buf, F_OK)!=0) break; else snprintf(buf, outSize, "%s_%d.txt", baseName, ++sub);
  } while (T);
  if ((wfp=fopen(buf, "w"))==NULL) {
    char msg[outSize+50]; snprintf(msg, outSize+50, "\a\nCan't open for write %s", buf); perror(msg);
  } else { printf(".. writing squares to file %s\n", buf); strcpy(outFile, buf); }
  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; }
bool fprintFWb(FILE *fp, const int i) { return fprintf(fp, "%11d", i)>0; }

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

bool outputDiags(const int n, FILE *wfp) {
//   -----------
  const int fw0=fieldWidth, fw=fw0+1;

  for (int i=0; i<Sindex; i++) {
    int *x=Diags[i]; int c=1; if (!fprintFW[fw0](wfp, x[0])) return F;
    while (c<N) { if (!fprintFW[fw](wfp, x[c])) return F; ++c; }
    if (fputc('\n', wfp)==EOF) return F; 
  }
  return T;
} // outputDiags
//====================================== get diagonals ====================================

int cmpDiags(int *key, int *s) {
//  ----------
  int i=0; while(i++<N) if (*key<*s) return -1; else if (*key++>*s++) return 1; return 0;
} // cmpRowPerms

int findDiag(int *key, int *insertPoint) {
//  ----------
  int first=0, last=Sindex-1, middle;
  while (first<=last) {
    middle=(first+last)/2; int cmp=cmpDiags(key,Diags[middle]);
    if (cmp<0) last=middle-1; else if (cmp>0) first=middle+1; else return T;
  }
  *insertPoint=first; return F;
} // findDiag

void insertDiag(const int insertPoint, bool *storeFail) {
//   ----------
  if (Sindex==allocatedDiagsSize) if (!increaseDiags()) { *storeFail=T;  return; }
  int *p=Diags[Sindex]; for (int i=Sindex; i>insertPoint; --i) Diags[i]=Diags[i-1];
  for (int i=0; i<N; ++i) p[i]=diag[i]; Diags[insertPoint]=p; ++Sindex;
} // insertDiag

void pushDiag(bool *storeFail) {
//   --------
  int insertPoint=0;
  if ((Sindex==0)||!findDiag(diag, &insertPoint)) insertDiag(insertPoint, storeFail);
} // pushDiag
//========================================== main ==========================================

bool validOrder(const int n) {
//   ----------
  if (n<=0) { printf("\aERROR: N must be a positive integer.\n"); return F; } return T;
} // validOrder

int main() {
//  ----
  bool another=T, inputSize=T, writeError=F, ok=F;
  do {     
    if (inputSize) N=getInt("Order");
    if (validOrder(N)&&allocateStore(N)) {
      initGlobals(); char buf[bufSize]; printf("File? "); getFileName(buf, bufSize-6);
      int which=getInt("Which \\ 1 or / 2");
      if (which<1) which=1; else if (which>2) which=2; FILE *rfp=openInput(buf);
      if (rfp!=NULL) {
        FILE *wfp=openOutput(buf,which,"Diags");
        if (wfp!=NULL) { ok=T;
          while (readSquare(rfp, which)) {
            int **i=iSquare; bool storeFail=F;
            if (which==1) for (int r=0; r<N; ++r) diag[r]=i[r][r];
            else          for (int r=0; r<N; ++r) diag[r]=i[r][M-r];
            pushDiag(&storeFail); if (storeFail) { ok=F; break; }
          }
          if (ok) {
            writeError=!outputDiags(N, wfp);
            if (writeError) ok=F; else printf("squares %d diags %d\n", squareNumber, Sindex);
          }
          fclose(wfp); if (Sindex==0) remove(outFile);
        }
        fclose(rfp); 
      }
      if (writeError) {
        perror("\a\nError writing file"); ok=F; another=F; remove(outFile);
      } else if (ok) {
        printf("\nContinue? y (yes) or n (no) or the order: ");
        if (getYorOrder()) inputSize=(N==0); else another=F;
      } else another=F;
    }
  } while (another);
  freeStore(); printf("\nHit return to close the console.");
  while (T) if (getchar()=='\n') break; return ok ? EXIT_SUCCESS : EXIT_FAILURE;
} // main