/*
 *  File:    CopySquaresByPondCount.cpp
 *  Author:  S Harry White
 *  Created: 2020-01-08
 *  Updated: 2021-12-28
 *    Tidy code.
 *  Updated: 2023-01-25
 *    Tidy code with check_txt. Fix perror message in openOutput.
 *  Updated: 2023-02-01
 *    Fix (R==C) ? "rectangle" : "square". Improve openInput.
 */

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

const bool F=false, T=true; const int startSize=25, bufSize=1024;
int R, C,           // The order of the rectangle.
    N,              // R==C ? R : sqrt(RC)
    Rm1,            // R-1
    Cm1,            // C-1
    RC,             // R*C
    maxNumber,            // Biggest number in the rectangle.
    inputRectNumber,      // Counts rectangles input from a .txt file.
    **xRectangle=NULL, **water=NULL, **pond, *numPonds, maxPonds, squaresOut,
    allocatedR, allocatedC, allocatedQueueSize, qIndex;

struct t_Cell { int priority, row, col; }; t_Cell *Queue=NULL;

void initGlobals() {
//   -----------
  Rm1=R-1; Cm1=C-1; RC=R*C; N=R==C? R : (int)sqrt((double)RC);
  inputRectNumber=0; squaresOut=0; maxPonds=0; for (int i=0; i<RC; ++i) numPonds[i]=0;
} // initGlobals
//============================================= store ===============================================

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

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

void freeQueue() { if (Queue!=NULL) { free(Queue); Queue=NULL; allocatedQueueSize= 0; } }
//   ---------

void freeStore() {
//   ---------
  freeRectangle(&water, allocatedR); freeRectangle(&xRectangle, allocatedR);
  freeRectangle(&pond, allocatedR);
  if (numPonds!=NULL) { free(numPonds); numPonds=NULL; } allocatedR=0; allocatedC=0; freeQueue();
} // freeStore

bool allocateRectangle(int*** rectangle, const int nR, const int nC) {
//   -----------------
  bool ok; *rectangle=(int**) malloc(nR*sizeof(int*)); ok=(*rectangle!=NULL);
  if (ok) {
    int numAllocated=0;
    for(int i=0; i<nR; i++) {
      int* p=(int*) malloc(nC*sizeof(int)); (*rectangle)[i]=p;
      if (p==NULL) { numAllocated=i; ok=F; break; }
    }
    if (!ok) freeRectangle(rectangle, numAllocated);
  }
  return ok;
} // allocateRectangle 

bool allocateQueue(const int size) {
//   -------------
  bool ok=T;
  if (allocatedQueueSize<size) {
   	freeQueue(); Queue=(t_Cell *) malloc(size*sizeof(t_Cell));
	  if (ok=(Queue!=NULL)) allocatedQueueSize=size;
  }
  return ok;
} // allocateQueue

bool increaseQueue() {
//   -------------
  const int size=allocatedQueueSize+allocatedQueueSize;

  t_Cell *tmp=(t_Cell *) malloc(size*sizeof(t_Cell));
  if (tmp==NULL) { reportError(storeAllocFail); return F; }
  for (int i=0; i<qIndex; i++) tmp[i]=Queue[i];
  freeQueue(); Queue=tmp; allocatedQueueSize=size; return T;
} // increaseQueue;

bool allocateStore() {
//   -------------
  bool ok=T; int nR=R, nC=C;
  if (nR<startSize) nR=startSize; if (nC<startSize) nC=startSize;
  if ((nR>allocatedR)|(nC>allocatedC)) {
    const int nRnC=nR*nC; freeStore();
    if (ok=allocateRectangle(&xRectangle, nR, nC))
	     if (ok=allocateRectangle(&water, nR, nC))
         if (ok=allocateRectangle(&pond, nR, nC))
           if (ok=allocateQueue(nRnC)) {
             numPonds=(int*) malloc(nRnC*sizeof(int)); ok=(numPonds!=NULL);
             if (ok) { allocatedR=nR; allocatedC=nC; }
           }
    if (!ok) { reportError(storeAllocFail); 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');
} // getY

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

bool getInts(int *p, int *q, int c) {
//   -------
  bool ok=F; *p=*q=0; if (c<0) do { c=getchar(); } while ((c==' ')|(c=='\t'));
  if ( ('1'<=c)&(c<='9') ) {
    int i=c-'0'; while ( ('0'<=(c=getchar()))&&(c<='9') ) i=i*10+c-'0'; *p=i;
    if ((c==' ')|(c=='\t')) {
      do { c=getchar(); } while ((c==' ')|(c=='\t'));
      if ( ('1'<=c)&(c<='9') ) { int i=c-'0'; while ( ('0'<=(c=getchar()))&&(c<='9') ) i=i*10+c-'0'; *q=i; }
    }
    if (*q==0) *q=*p; ok=T;
  } 
  clearLine(c); if (!ok) return reportError("Invalid input"); return T;
} // getInts

bool getYorInts(int *p, int *q) {
//   ----------
  bool ok=F; int c; *p=-1; do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n') );
  if ( (c=='Y')|(c=='y') ) ok=T; else if ( (c!='N')&(c!='n') ) return getInts(p, q, c);  
  clearLine(c); return ok;
} // getYorInts

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

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 %ss file: ", (R==C)?"square":"rectangle");
    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, rFname, "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(int n) {
//  --------
  const bool isSigned=n<0; int width=1; while ((n/=10)!=0) ++width; return isSigned ? width+1 : width;
} // getWidth

bool inputRectangle(FILE *rfp) {
//   --------------
  int smallest=LONG_MAX, biggest=LONG_MIN;
  for (int r=0; r<R; r++)  for (int c=0; c<C; c++) {
   	int rv, tmp;

	  if ( (rv=fscanf_s(rfp, "%d", &tmp))!=1) {
      if ( (rv!=EOF)|(r!=0)|(c!=0) ) return reportError("Reading from file"); return F;
    } else {
      xRectangle[r][c]=tmp; if (tmp<smallest) smallest=tmp; if (tmp>biggest) biggest=tmp;
    } 
  }
  const int sWidth=getWidth(smallest), bWidth=getWidth(biggest);
  fieldWidth=sWidth>bWidth?sWidth:bWidth; ++inputRectNumber; maxNumber=biggest;return T; 
} // inputRectangle
//============================================ output ===========================================

const int outSize=bufSize+50;
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

char outFile[outSize];
FILE *openOutput(char *inFname, const int outponds) {
//    ----------
  FILE *wfp=NULL; int sub=0; const int baseSize=bufSize+25; char baseName[baseSize], buf[outSize];
  sprintf_s(baseName, baseSize, "%s-%dpond%s", inFname, outponds, outponds==1?"":"s");
  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) {
    char msg[outSize+50];
    sprintf_s(msg, outSize+50, "\a\nCan't open for write %s", buf); perror(msg);
  } else strcpy_s(outFile, outSize, buf);
  return wfp;
} // openOutput

//FILE *Qfp=NULL;
//void printQueue() {
////   ----------
//  int i=0;
//  while (i<qIndex) {
//	  t_Cell *q=&Queue[i];
//    fprintf(Qfp,"priority %d row %d col %d\n",	q->priority, q->row, q->col); i++;
//  }
//  fprintf(Qfp,"\n");
//} // printQueue

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; }
bool fprintFWc(FILE *fp, const int i) { return fprintf(fp, "%12d", i)>0; }

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

bool printSquare(int **X, FILE *wfp) {
//   -----------
  const int fw0=fieldWidth, fw=fw0+1;
  for (int r=0; r<R; r++) {
    if (!fprintFW[fw0](wfp, X[r][0])) return F;
    for (int c=1; c<C; c++) if (!fprintFW[fw](wfp, X[r][c])) return F;
    if (fputc('\n', wfp)==EOF) return F;
  }
  return fputc('\n', wfp)!=EOF;
} // printSquare
//========================================== copy squares ============================================

void initBounds() {
//   ----------
  const int mR=Rm1, mC=Cm1; int **x=xRectangle;
  for (int r=0; r<R; r++) { water[r][0]=x[r][0]; water[r][mC]=x[r][mC]; }
  for (int c=1; c<mC; c++) {	water[0][c]=x[0][c]; water[mR][c]=x[mR][c]; }
  for (int r=1; r<mR; r++) for (int c=1; c<mC; c++) water[r][c]=maxNumber; qIndex=0;
} // initBounds

void pushQueue(const int priority, const int row, const int col) {
//   ---------
  t_Cell cell; cell.priority=priority; cell.row=row; cell.col=col; Queue[qIndex++]=cell;
} //  pushQueue

bool insertQueue(const int priority, const int row, const int col) {
//   -----------
  if ((qIndex>=allocatedQueueSize)&&!increaseQueue()) return F;
  t_Cell cell; cell.priority=priority; cell.row=row; cell.col=col;
  int i=qIndex-1;
  while (Queue[i].priority<priority) { Queue[i+1]=Queue[i]; if (--i<0) break; }
  Queue[++i]=cell; ++qIndex; /*printQueue(); */ return T;
} // insertQueue

void popQueue(t_Cell *cell) { *cell=Queue[--qIndex]; }
//   --------

bool queueBorder() {
//   -----------
  const int mR=Rm1, mC=Cm1; pushQueue(water[1][0], 1, 0);
  if (!insertQueue(water[1][mC], 1, mC)) return F;
  for (int r=2; r<mR; r++) {
	  if (!insertQueue(water[r][0], r, 0)) return F; if (!insertQueue(water[r][mC], r, mC)) return F;
  }
  for (int c=1; c<mC; c++) {
	  if (!insertQueue(water[0][c], 0, c)) return F; if (!insertQueue(water[mR][c], mR, c)) return F;
  }
  return T;
} // queueBorder

bool computeBounds(const int p, const int r, const int c) {
//   -------------
  const int mR=Rm1, mC=Cm1;
  if ( ( (0<r)&(r<mR) )&( (0<c)&(c<mC) ) ) {
    int *bp=&water[r][c]; const int tmp=max(xRectangle[r][c],p);
	   if (tmp<*bp) { *bp=tmp; if (!insertQueue(tmp, r, c)) return F; }
  }
  return T;
} // computeBounds

/*
 *  Based on an algorithm of Gareth McCaughan supplied by Craig Knecht.
 */
bool getWater() {
//   --------
  initBounds(); if (!queueBorder()) return F;
  while (qIndex!=0) {
   	t_Cell cell; popQueue(&cell);	const int p=cell.priority, r=cell.row, c=cell.col;
	  if (!computeBounds(p, r-1, c)) return F; if (!computeBounds(p, r+1, c)) return F;
   	if (!computeBounds(p, r, c-1)) return F; if (!computeBounds(p, r, c+1)) return F;
  }
  return T;
} // getWater

bool checkPonds(const int p, const int r, const int c) {
//   ----------
  const int mR=Rm1, mC=Cm1;
  if ( ( (0<r)&(r<mR) )&( (0<c)&(c<mC) ) ) {
    const bool wet=water[r][c]>xRectangle[r][c], visited=pond[r][c]!=0;
    if (wet&!visited) {
      if (qIndex==0) pushQueue(p, r, c); else if (!insertQueue(p, r, c)) return F; pond[r][c]=p;
    }
  }
  return T;
} // checkPonds

bool getSquares(FILE *wfp, const int outPonds, bool *writeError) {
//   ----------
  for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) pond[r][c]=0;
  if (getWater()) {
    int pnum=0;
    for (int r=1; r<Rm1; ++r) for (int c=1; c<Cm1; ++c) {
      const bool wet=water[r][c]>xRectangle[r][c], visited=pond[r][c]!=0;
      if (wet&!visited) {
        pushQueue(++pnum, r, c); pond[r][c]=pnum;
        while (qIndex!=0) {
   	      t_Cell cell; popQueue(&cell); const int p=cell.priority, r=cell.row, c=cell.col;
          if (wet) {
	          if (!checkPonds(p, r-1, c)) return F; if (!checkPonds(p, r+1, c)) return F;
   	        if (!checkPonds(p, r, c-1)) return F; if (!checkPonds(p, r, c+1)) return F;
          }
        }
      }
    }
    if (pnum>maxPonds) maxPonds=pnum; ++numPonds[pnum];
    if (pnum==outPonds) {
      if (!printSquare(xRectangle, wfp)) { *writeError=T; return F; }  ++squaresOut;
    }
  }
  return T;
} // getSquares
//============================================== main ===============================================

void outputLocalTime() {
//   --------------
  time_t startTime=time(NULL); 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 *inputOrder, const bool writeError) {
//   ---------
  if (writeError) return F;
  printf("\nContinue? input y (yes) or n (no) or the order: ");
  if (getYorInts(&R, &C)) { *inputOrder=(R<0); return T; } else { freeStore(); return F; }
} // doAnother

int main() {
//  ----
  outputLocalTime(); bool another=T, inputOrder=T, ok=F;
  allocatedR=0; allocatedC=0; allocatedQueueSize=0; qIndex=0;
  do {
    bool writeError=F;
    if (inputOrder) { printf("\nOrder? "); if (!getInts(&R, &C, -1)) break;}
    if (allocateStore()) {
      initGlobals(); char ibuf[bufSize], obuf[outSize];
      FILE *rfp=openInput(ibuf); stripName(ibuf, obuf);
      if (rfp!=NULL) {
        time_t startTime=time(NULL); int outPonds=0;
        printf("\nGet %ss with how many ponds ? ", (R==C) ? "square" : "rectangle"); outPonds=getInt();
        FILE *wfp=NULL; if (outPonds>=0) wfp=openOutput(obuf, outPonds);
        if ((outPonds<0)|(wfp!=NULL)) {
          while (inputRectangle(rfp)) if (!getSquares(wfp, outPonds, &writeError)) break;
          if (writeError) printf("\aError writing file\n"); 
          else {
            ok=T; printf("\nmax ponds %d\n", maxPonds);
            for (int i=0; i<=maxPonds; ++i) printf("ponds %6d count %10d\n", i, numPonds[i]);
          }
          if (wfp!=NULL) { fclose(wfp); if (writeError|(squaresOut==0)) remove(outFile); }
        } // (wfp!=NULL
        fclose(rfp); reportElapsedTime(startTime);
      } // (rfp!=NULL
    } // allocateStore()
    another=doAnother(&inputOrder, writeError);
  } while (another);

  printf("\nPress a key to close the console.");
  while (!_kbhit()) Sleep(250); return ok ? EXIT_SUCCESS : EXIT_FAILURE;
} // main