//  Deductor.cpp -- Analysis of 1D Mondrian scenes with integer values using an interval approach
//
//
// DESCRIPTION
//
// Copyright © Tim Bahls, Daniel Scharstien 2003.
//
///////////////////////////////////////////////////////////////////////////



#pragma once

#include "Error.h"
#include "Image.h"
#include "Color.h"
#include "Deductor.h"



#ifndef UNKNOWN
#define UNKNOWN -9876
#define UNKNOWNF -9876.5f
#define MAX 1234.5f
#define MIN -1234.5f
#ifndef WIN32
#define __max(a,b)  (((a) > (b)) ? (a) : (b))
#define __min(a,b)  (((a) < (b)) ? (a) : (b))
#endif
#endif

#define MINVEL -4
#define MAXVEL 4
#define MINLEN 6
#define MAXLEN 299


///////////////////////////////////////////////////////////////////////////
// class CRegion - a single region

CRegion::CRegion(int iid, int inFrames)
{
	id = iid;
	minVel=MINVEL;
	maxVel=MAXVEL;
	minLen=MINLEN;
	maxLen=MAXLEN;
	nFrames=inFrames;
	xmins=new int[nFrames];
	for(int i=0; i<nFrames;i++){
		xmins[i]=UNKNOWN;
	}
	xmaxes=new int[nFrames];
	for(int i=0; i<nFrames;i++){
		xmaxes[i]=UNKNOWN;
	}
	leftIDs=new int[nFrames];
	for(int i=0; i<nFrames;i++){
		leftIDs[i]=UNKNOWN;
	}
	rightIDs=new int[nFrames];
	for(int i=0; i<nFrames;i++){
		rightIDs[i]=UNKNOWN;
	}
	minmax=new float[nFrames];
	for(int i=0; i<nFrames; i++){
		minmax[i]=MIN;
	}
	maxmin=new float[nFrames];
	for(int i=0; i<nFrames; i++){
		maxmin[i]=MAX;
	}
	minmin=new float[nFrames];
	for(int i=0; i<nFrames; i++){
		minmin[i]=MIN;
	}
	maxmax=new float[nFrames];
	for(int i=0; i<nFrames; i++){
		maxmax[i]=MAX;
	}
}

bool CRegion::limitV(int f1, int f2, float*minA, float*maxA){
	bool a=false;
	float minV=(maxA[f1]-minA[f2])/(float)(f1-f2);
	float maxV=(minA[f1]-maxA[f2])/(float)(f1-f2);
	a |= max(minVel,minV);
	a |= min(maxVel,maxV);
	return a;
}



bool CRegion::restrictVel(){
	if(minVel==maxVel)
		return false;
	bool change=false;

	for(int f1=0; f1<nFrames-1;f1++){
		for(int f2=f1+1; f2<nFrames;f2++){
			change|=limitV(f1,f2,minmin,maxmin);//restrict velocity by position
			change|=limitV(f1,f2,minmax,maxmax);
		}
	}

	return change;
}

bool CRegion::restrictLen(){
	if(minLen==maxLen)
		return false;
	bool change=false;
	for(int f=0; f<nFrames;f++){
		if(maxmin[f]!=MAX&&minmax[f]!=MAX)
			change|=max(minLen,minmax[f]-maxmin[f]);//restrict length by position
		if(maxmax[f]!=MAX&&minmin[f]!=MAX)
			change|=min(maxLen,maxmax[f]-minmin[f]);
	}

	return change;
}

bool CRegion::limitP(int f1, int f2, float*&minA, float*&maxA){
	bool a=false;
	float minX1=minA[f2]+maxVel*(f1-f2);
	float maxX1=maxA[f2]+minVel*(f1-f2);
	float minX2=minA[f1]+minVel*(f2-f1);
	float maxX2=maxA[f1]+maxVel*(f2-f1);
	a|=max(minA[f1],minX1);
	a|=min(maxA[f1],maxX1);
	a|=max(minA[f2],minX2);
	a|=min(maxA[f2],maxX2);
	return a; 
}


bool CRegion::restrictPosition(){
	bool change=false;
	for(int f=0; f<nFrames;f++){	
		if(maxLen!=MAX&&maxmin[f]!=MAX)
			change|=min(maxmax[f],maxmin[f]+maxLen);//restrict position by length
		if(maxLen!=MAX&&minmax[f]!=MIN)
			change|=max(minmin[f],minmax[f]-maxLen);
		if(minmin[f]!=MIN)
			change|=max(minmax[f],minmin[f]+minLen);
		if(maxmax[f]!=MAX)
			change|=min(maxmin[f],maxmax[f]-minLen);
		for(int f2=f+1; f2<nFrames;f2++){
			change|=limitP(f,f2,minmin,maxmin);//restrict position by velocity
			change|=limitP(f,f2,minmax,maxmax);
		}
	}
	return change;
}



bool CRegion::operator == (CRegion param) {
	return (param.id==id);
}



///////////////////////////////////////////////////////////////////////////
// class CDeductor - all regions



// destructor
CDeductor::~CDeductor()
{
	for (int i = 0; i <=maxID; i++) {
		if (&region[i]!=0) {
			//delete &region[i];
		}
	}
}


void CDeductor::p(int id){
	if(verbose)
		CCol(id).printName();
}


int CDeductor::compare(int a,int b)   
{
	if(a==-1){//everything is below the boundary
		return 2;
	}
	if(b==-1){
		return -2;
	}
	return relative[a][b];
}

//sets high priority closer
bool CDeductor::setCloser(int c, int f)
{

	if(c==f){

		printf("Whoops: highSetCloser(%d,%d)\n",c,f);
		return false;
	}

	switch(compare(c,f)){

		case -2:
			verbose=true;
			printf("WARNING: setCloserThan(");
			p(c);
			printf(",");
			p(f);
			printf(") when the opposite is recorded\n");

			throw CError("setCloserThan(%d)", f);
			return false;
			break;
		case 0:
			relative[c][f]=2;
			relative[f][c]=-2;
			if(verbose){
				printf("     ");
				p(c);
				printf(" closer than ");
				p(f);
				printf("\n");
			}
			return true;
			break;
		case 2:
			return false;
			break;
		default:
			printf("Screwy value--compare(%d,%d)=%d\n",c,f,compare(c,f));
			relative[c][f]=2;
			relative[f][c]=-2;
			return true;
	}
	return false;
}




//Goes about extending and copying maxID, relative, minmax, and found.

void CDeductor::addid(int a){

	int oldMax=maxID;
	maxID=a;

	CRegion * b=new CRegion[maxID+1];
	for(int i=0;i<=maxID;i++){
		if(i<=oldMax){
			b[i]=region[i];
		}else{
			b[i]=null;
		}
	}
	region=b;


	int ** c=new int*[maxID+1];
	for(int i=0;i<=maxID;i++){
		c[i]=new int[maxID+1];
	}
	for(int i=0;i<=maxID;i++){
		for(int j=0;j<=maxID;j++){

			if(i<=oldMax&&j<=oldMax){
				c[i][j]=relative[i][j];
			}else{
				if(i==j){
					c[i][j]=0;
				}else{
					c[i][j]=0;
				}
			}

		}
	}
	//if(oldMax>0){
	//delete [] relative;
	//}
	relative=c;
}


//returns the id of the color
int CDeductor::getPixID(int row, int col){
	CCol *c=(CCol*)&im.Pixel(col,row,0);     //notice switch
	CCol cc=*c;
	int a= cc.getId();

	if (a>maxID){
		addid(a);
	}

	if(region[a]==null){
		region[a]=CRegion(a,nFrames);
		nRegions++;
	}
	return a;
}



// create new region if necessary, add a new component, and record its left edge
void CDeductor::startRegion(int id, int frame, int x, int prevID)
{
	if(region[id].xmins[frame]==UNKNOWN){
		region[id].xmins[frame]=x;
		region[id].leftIDs[frame]=prevID;
		region[id].maxmin[frame]=(float)x;
	}
}

// record right boundary of current region
void CDeductor::endRegion(int id, int frame, int x, int nextID)
{
	region[id].xmaxes[frame]=x;
	region[id].rightIDs[frame]=nextID;
	region[id].minmax[frame]=(float)x;
}


// read a frame: look at all pixels in center scanline and initialize / update
// regions and their edges


void CDeductor::readFrame(CByteImage iim, int frame)
{
	im=iim;
	CShape sh = im.Shape();
	int w = sh.width, h = sh.height;
	maxWidth=w;
	data[frame]=new int[w];
	int row=h/2;
	int oldid = getPixID(row,0);
	startRegion(oldid, frame, 0, -1);
	data[frame][0]=oldid;
	for (int x = 1; x < w; x++) {
		int newid = getPixID(row,x);
		data[frame][x]=newid;
		if(newid!=oldid){      
			endRegion(oldid, frame, x-1, newid);
			startRegion(newid, frame, x, oldid);
			oldid = newid;
		}
	}
	//update last extent:
	endRegion(oldid, frame, w-1, -1);
}

void CDeductor::printData()
{
	printf("%d regions observed\n", nRegions);
	for (int i=0; i <= maxID; i++) {
		if (region[i]==null)
			continue;
		printf("     ");
		p(i);
		printf(":");
		CRegion r = region[i]; 
		for (int f=0; f < nFrames; f++) {

			printf("  f%d:", f);        
			if(r.xmins[f]==UNKNOWN)
				continue;
			printf("%d-%d,", r.xmins[f],r.xmaxes[f]);
		}
		printf("\n");

	}
}

void CDeductor::checkTripletForQuadT(int i, int f1, int f2,int f3, int *minmax,int*rightleft)
{
	int x1=minmax[f1];
	int x2=minmax[f2];
	int x3=minmax[f3];
	// check if motion is consistent over three frames
	int x21 = x2-x1;
	int x31 = x3-x1;
	int f21 = f2-f1;
	int f31 = f3-f1;
	if (f21*x31 != f31*x21)
		return;
	int edgeVel = x21/f21;
	int id1=rightleft[f1];
	int id2=rightleft[f2];
	int id3=rightleft[f3];
	if (id1 < 0 || id2 < 0 || id3 < 0)
		return;

	if (id1 == id2 && id2 != id3){
		for(int f4=f3+1;f4<nFrames;f4++){
			int id4=rightleft[f4];
			if (id4<0)
				continue;
			if (id4!=id3)
				continue;
			int x4=minmax[f4];
			int x41 = x4-x1;
			int f41 = f4-f1;
			if (f21*x41 != f41*x21)
				continue;

			if(setCloser(i,id1)){
				change=true;
				//times++;
			}
			if(setCloser(i,id3)){
				change=true;
				//times++;
			}

			return;
		}	
	}
}

void CDeductor::quadT()
{
	if(verbose)
		printf("Edge Velocities and T-Junctions\n");
	for (int i=0; i <= maxID; i++) {
		if (region[i]==null)
			continue;
		CRegion r=region[i];
		for (int f1=0; f1 < nFrames; f1++) {
			for (int f2=f1+1; f2 < nFrames; f2++) {				
				for (int f3=f2+1; f3 < nFrames; f3++) {																								checkTripletForQuadT(i,f1,f2,f3,r.xmins,r.leftIDs);  
				checkTripletForQuadT(i,f1,f2,f3,r.xmaxes,r.rightIDs);					
				}
			}
		}
	}
}


//Okay, this is based on the idea that if 
//you see two colors adjacent through two
//frames, then you have found the velocity 
//of the closer one.  So suppose we track 
//region A and region B through two frames. 
//Since two points define a line, we can 
//predict which two pixels would define the
//edge in all frames.  Thus if we see color
//C on both pixels, then either A<B, so we
//are tracking A's edge and C<A and thus C<B
//by the transitive property, or B<A and then
//C<B, so C<A.  Either way we know that C<A
//and C<B.

void CDeductor::extendedT()
{
	if(verbose)
		printf("Extended T:\n");
	for (int i=0; i <= maxID; i++) {
		CRegion r1=region[i];
		if (r1==null)
			continue;
		for (int j=0; j <= maxID; j++) {
			CRegion r2=region[j];
			if (r2==null||i==j)
				continue;
			int f1=0;
			for(; f1<nFrames;f1++){
				if(r1.leftIDs[f1]==j)
					break;
			}
			int f2=f1+1;
			for(; f2<nFrames;f2++){
				if(r1.leftIDs[f2]==j)
					break;
			}
			if(f2>=nFrames||r2.rightIDs[f1]!=i||r2.rightIDs[f2]!=i)
				continue;
			float edgeVel=(float)(r1.xmins[f2]-r1.xmins[f1])/(float)(f2-f1);
			int pos=r1.xmins[f1];

			for(int f=0;f<nFrames; f++){
				int 
					loc=(int)(pos+edgeVel*(f-f1));
				if(loc<=0||loc>=maxWidth)// so both x2 and x2-1 are on image
					continue;
				int id1=data[f][loc-1];
				int id2=data[f][loc];
				if(id1==id2&&id2!=i){
					change|=setCloser(id1,i);
					change|=setCloser(id1,j);
				}
			}
		}

	}
}


void CDeductor::possibilityElimination(){
	//if(verbose)
	//printf("Possibility Elimination:\n");
	for (int i=0; i <= maxID; i++) {
		CRegion r=region[i];
		if (r==null)
			continue;
		bool change2=true;
		while(change2==true){
			change2=false;
			change2|=region[i].restrictPosition();
			change2|=region[i].restrictVel();
			change2|=region[i].restrictLen();
			change|=change;
		}
	}
}

void CDeductor::occlusionDetection(){
	if(verbose)
		printf("Occlusion Detection:\n");
	for (int i=0; i <= maxID; i++) {
		CRegion r=region[i];
		if (r==null)
			continue;
		for(int f=0; f<nFrames;f++){
			int start1=(int)r.maxmin[f];
			start1=__min(start1,maxWidth-1);
			start1=__min(start1,(int)(r.minmax[f]));
			int end1=(int)r.minmin[f];
			end1=__max(end1,0);
			for(int x=start1;x>=end1;x--){
				if(compare(i,data[f][x])==2){
					r.minmin[f]=(float)(x+1);//if i extended this far, it would've been found.  Thus it doesn't.
					change=true;
					break;
				}
			}
			int start2=(int)r.minmax[f];
			start2=__max(start2,0);
			start2=__max(start2,(int)r.maxmin[f]);
			int end2=(int)r.maxmax[f];
			end2=__min(end2,(int)maxWidth-1);
			for(int x=start2;x<=end2;x++){
				if(compare(i,data[f][x])==2){
					r.maxmax[f]=(float)(x-1);//if i extended this far, it would've been found.  Thus it doesn't.
					change=true;
					break;
				}
			}
			if(r.maxmin[f]==MAX||r.maxmin[f]==MIN)
				continue;
			for(int x=__max(0,(int)(r.maxmin[f]));x<=__min((int)(r.minmax[f]),maxWidth-1);x++){
				int id=data[f][x];
				if(id!=i){
					change|=setCloser(id,i);	
				}
			}
		}
	}
}






//like it sounds
void CDeductor::transitiveClosure()
{
	if(verbose)
		printf("Computing Transitive closure:\n");
	bool newEdge = true;
	while (newEdge) {
		newEdge = false;
		for (int i=0; i <= maxID; i++) {
			if (region[i]==null)
				continue;
			for (int j=0; j <= maxID; j++) {
				if(compare(i,j)==2){//definite
					for (int k=0; k <= maxID; k++) {
						if(compare(j,k)==2&&i!=k){//definite
							newEdge |= setCloser(i,k);//definite
							change |=newEdge;
						}
					}
				}
			}
		}
	}
}


void CDeductor::reportResults()
{
	printf("\nResults: %d regions observed\n", nRegions);
	for (int i=0; i <= maxID; i++) {
		CRegion r=region[i];
		if (r==null)
			continue;
		printf("   ");
		p(i);
		printf(": v");
		if(r.minVel==r.maxVel){
			printf(":%2d=%2d", (int)r.minVel,(int)r.maxVel);
		}else{
			printf(":%2d~%2d",(int)r.minVel,(int)r.maxVel);
		}
		printf(" l");
		if(r.minLen==r.maxLen){

			printf(":%3d=%3d", (int)r.minLen,(int)r.maxLen);

		}else{
			printf(":%3d~%3d",(int)r.minLen,(int)r.maxLen);
		}		
		printf(" Over: ");
		for (int j=0; j <= maxID; j++) {
			if(compare(i,j)==2){
				p(j);
				printf(" ");
			}         
		}
		printf("\n");
	}
}


// infer depth ordering, lengths and motion
int CDeductor::goGoGo()
{

	times=0;
	quadT();
	extendedT();
	while (change) {
		change = false;
		occlusionDetection();
		possibilityElimination();
		transitiveClosure();
	}
	for (int i=0; i <= maxID; i++) {
		for (int j=0; j <= maxID; j++) {
			if(compare(i,j)==2)
				times++;
		}
	}
	if(verbose)
		reportResults();
	return times;
}

void CDeductor::checkAccuracy(CScene scene)
{
	for (int i=1; i <= maxID; i++) {
		CRegion reg=region[i];
		if (reg==null)
			continue;
		CRect rect=scene.getByID(i);
		if(rect.vel.x>reg.maxVel||rect.vel.x<reg.minVel){
			printf("i=%d rect=%d\n",i,rect.color.getId());
			printf("ERROR! This velocity is false: %d <= %d <= %d\n",(int)reg.minVel,(int)rect.vel.x,(int)reg.maxVel);
			throw CError("Velocity incorrect: %d",(int)rect.vel.x);
		}
		if(rect.diag.x>reg.maxLen||rect.diag.x<reg.minLen){
			printf("ERROR! This length is false: %d <= %d <= %d\n",(int)reg.minLen,(int)rect.vel.x,(int)reg.maxLen);
			throw CError("Length incorrect: %f",(int)rect.vel.x);
		}
		for(int j=1; j<=maxID;j++){
			CRect rect2=scene.getByID(j);
			if(compare(i,j)==-2&&rect.z<rect2.z){
				verbose=true;
				printf("ERROR! ");
				p(i);
				printf(" not behind ");
				p(j);
				printf("!\n");
				throw CError("Relative Distances incorrect");
			}
			if(compare(i,j)==2&&rect.z>rect2.z){
				verbose=true;
				printf("ERROR! ");
				p(i);
				printf(" doesn't beat ");
				p(j);
				printf("!\n");
				throw CError("Relative Distances incorrect");
			}
		}
		if(compare(0,i)==2){
			verbose=true;
			printf("ERROR! ");
			p(i);
			printf(" doesn't beat ");
			p(0);
			throw CError("Nothing behind white");
		}
	}
	if(verbose)
		printf("All true\n");
}