#include <stack></stack>

#include <time.h></time.h>

#include "stdfx.h"

#include "tsystem.h"

#include "tconvert.h"

#include "trop.h"

/* Riferimenti:

[1] "Filling a region in a frame buffer", Ken Fishkin, su Graphics Gems vol.1, pag 278;

*/

// TODO

// v integrare in zcomp

// v aggiungere: selezioni multiple, antialias, feather, .

// v aggiungere: gestione del mouse, indicatore del colore del pixel selezionato, media sui vicini del pixel selezionato

// . maglass

// . verifiche ed ottimizzazioni

namespace

{

} // anonymous namespace

static int invocazioni = 0; // tmp: numero di invocazioni della MagicWand

// Shadow Segment

// "Ombra" proiettata da una riga di pixel idonei sulle righe adiacenti superiore ed inferiore; vedi [1].

class ShadowSegment

{

public:

	ShadowSegment(int Lx, int Rx, int pLx, int pRx, int y, int dir) : m_lx(Lx), m_rx(Rx), m_pLx(pLx), m_pRx(pRx), m_y(y), m_dir(dir) {}

	int m_rx,  // Right endpoint

		m_lx,  // Left endpoint

		m_pRx, // parent Right endpoint

		m_pLx, // parent Left endpoint

		m_y,   // this segment line

		m_dir; // upward, downward

};

// Stack per la memorizzazione dei segmenti.

typedef std::stack<shadowsegment> ShadowSegmentStack;</shadowsegment>

class MagicWandFx : public TStandardRasterFx

{

	FX_PLUGIN_DECLARATION(MagicWandFx)

	TRasterFxPort m_input;

	TDoubleParamP m_tolerance;  // tolleranza

	TDoubleParamP m_blurRadius; // ampiezza del campione per il SEED

	TPointParamP m_point;		  // coordinate del SEED (passate da zviewer)

	TBoolParamP m_contiguous;	 // selezione di regioni non connesse alla regione contentente il SEED

	TBoolParamP m_antialiased;	// applicazione dell'antialiasing

	TBoolParamP m_euclideanD;	 // funzione alternativa per il calcolo della "similitudine" tra punti

	TBoolParamP m_preMolt;		  // premoltiplicazione

	TBoolParamP m_isShiftPressed; // per le selezioni multiple: SUB

	TBoolParamP m_isAltPressed;   // per le selezioni multiple: ADD

public:

	MagicWandFx()

		: m_tolerance(15.0), m_blurRadius(0.0), m_point(TPointD(0, 0))

	{

		m_contiguous = TBoolParamP(true);

		m_antialiased = TBoolParamP(true);

		m_euclideanD = TBoolParamP(true);

		m_preMolt = TBoolParamP(true);

		m_isShiftPressed = TBoolParamP(false);

		m_isAltPressed = TBoolParamP(false);

		addParam("Tolerance", m_tolerance);

		addParam("Feather", m_blurRadius);

		addParam("Point", m_point);

		addParam("Contiguous", m_contiguous);

		addParam("Antialias", m_antialiased);

		addParam("EuclideanD", m_euclideanD);

		addParam("PreMultiply", m_preMolt);

		addParam("isShiftPressed", m_isShiftPressed);

		addParam("isAltPressed", m_isAltPressed);

		addInputPort("Source", m_input);

		m_tolerance->setValueRange(0, 255);

		m_blurRadius->setValueRange(0, 100);

	}

	~MagicWandFx(){};

	TRect getInvalidRect(const TRect &max);

	void doCompute(TTile &tile, double frame, const TRasterFxRenderInfo *ri);

	void doMagicWand(TTile &tile, double frame, const TRasterFxRenderInfo *ri);

	void EnqueueSegment(int num, int dir, int pLx, int pRx, int Lx, int Rx, int y);

	bool pixelProcessor(TPixel32 *testPix, TPixelGR8 *maskPix);

	bool getBBox(double frame, TRectD &rect, TPixel32 &bgColor)

	{

		return m_input->getBBox(frame, rect, bgColor);

	}

	TRasterGR8P m_maskGR8; // maschera

	TPixel32 *m_pickedPix; // puntatore al pixel SEED

	TPixelGR8 *m_maskPickedPix;

	int m_imageHeigth; // altezza del raster

	int m_imageWidth;  // larghezza del raster

	double m_tol;	  // le uso per evitare di dover richiamare la funzione getValue per ogni punto: sistemare?

	int m_cont;		   // le uso per evitare di dover richiamare la funzione getValue per ogni punto: sistemare?

	bool m_antial;	 // le uso per evitare di dover richiamare la funzione getValue per ogni punto: sistemare?

	bool m_euclid;	 // le uso per evitare di dover richiamare la funzione getValue per ogni punto: sistemare?

	bool m_add;

	bool m_sub;

	int m_id_invocazione;		  // contatore delle invocazioni

	ShadowSegmentStack m_sSStack; // stack dei segmenti shadow

};

const int EmptyPixel = 0;

const int FullPixel = 255;

//--------------------------------------

// tmp: per l'analisi delle prestazioni

int pixelProcessed;

int pixelMasked;

int shadowEnqueued;

int pixelReprocessed;

int shadowOutOfBorder;

bool maskValue;

bool MagicWandFx::pixelProcessor(TPixel32 *testPix, TPixelGR8 *maskPix)

{

	pixelProcessed++;

	unsigned int maskValue = 0;

	double diff = 0;

	// valuto la distanza tra il testPix ed il SEED e la metto in diff

	if (m_euclid) {

		// calcolo la Distanza Euclidea tra i punti nello spazio RGB

		diff = sqrt((m_pickedPix->r - testPix->r) * (m_pickedPix->r - testPix->r) + (m_pickedPix->g - testPix->g) * (m_pickedPix->g - testPix->g) + (m_pickedPix->b - testPix->b) * (m_pickedPix->b - testPix->b));

	} else {

		// GIMP-like: confronto la tolleranza con il massimo tra gli scarti delle componenti

		diff = abs(m_pickedPix->r - testPix->r);

		double diffNext = abs(m_pickedPix->g - testPix->g);

		if (diffNext >= diff)

			diff = diffNext;

		diffNext = abs(m_pickedPix->b - testPix->b);

		if (diffNext >= diff)

			diff = diffNext;

	}

	if (diff <= m_tol)

		maskValue = FullPixel;

	else

		maskValue = EmptyPixel;

	if (maskValue) {

		// il pixel soddisfa il criterio di compatibilita

		if (m_add) {

			// sto aggiungendo selezioni

			if (testPix->m != EmptyPixel) {

				pixelReprocessed++;

				return false;

			} // gia' trattato

			//* DECIDERE SE VOGLIO CHE LA SELEZIONE INTERESSI AREE GIA' SELEZIONATE IN PRECEDENZA

			//      if (maskPix->value == EmptyPixel) { //pixel c-compatibile, non gia' mascherato

			testPix->m = maskValue;		// set(mV)m

			maskPix->value = maskValue; // set(mV)a

			pixelMasked++;

			//      } else { // pixel c-compatibile gia' mascherato precedentemente

			//               testPix->m = maskValue;  // set(mV)m

			//     }

		} else if (m_sub) {

			// sto togliendo selezioni

			if (testPix->m != EmptyPixel)

				return false;			 // gia' trattato

			testPix->m = maskValue;		 // set(mV)m

			maskPix->value = EmptyPixel; // set(0)a

		} else {						 // prima selezione

			if (testPix->m != EmptyPixel)

				return false;			// gia' trattato

			testPix->m = maskValue;		// set(mV)m

			maskPix->value = maskValue; // set(mV)a

			pixelMasked++;

		}

		return true;

	} else

		return false;

} // pixelProcessor

// [1]: aggiunge le ombre necessarie alla pila.

void MagicWandFx::EnqueueSegment(int num, int dir, int pLx, int pRx, int Lx, int Rx, int y)

{

	int pushRx = Rx + 1;

	int pushLx = Lx + 1;

	//  TSystem::outputDebug("[MWfx("+toString(m_id_invocazione)+":"+toString(num)+")<push 1="">]\tStack Size:"+toString((int) m_sSStack.size())+"\tLx:"+toString(Lx)+"\tRx:"+toString(Rx)+"\tpLx:"+toString(pushLx)+"\tpRx:"+toString(pushRx)+"\ty:"+toString(y)+"\tdir:"+toString(dir)+"\n");</push>

	assert((Lx <= Rx) && (pushLx <= pushRx) && (Lx >= 0));

	m_sSStack.push(ShadowSegment(Lx, Rx, pushLx, pushRx, (y + dir), dir));

	shadowEnqueued++;

	if (Rx > pRx) { // U-turn a destra

					//  TSystem::outputDebug("[MWfx("+toString(m_id_invocazione)+":"+toString(num)+")<push 2="">]\tStack Size:"+toString((int) m_sSStack.size())+"\tLx:"+toString(pRx+1)+"\tRx:"+toString(Rx)+"\tpLx:"+toString(pushLx)+"\tpRx:"+toString(pushRx)+"\ty:"+toString(y-dir)+"\tdir:"+toString(dir)+"\n");</push>

		assert(((pRx + 1) <= (Rx)) && (pushLx <= pushRx) && ((pRx + 1) >= 0));

		m_sSStack.push(ShadowSegment((pRx + 1), Rx, pushLx, pushRx, (y - dir), (-dir)));

		shadowEnqueued++;

	}

	if (Lx < pLx) { // U-turn a sinistra

					//    TSystem::outputDebug("[MWfx("+toString(m_id_invocazione)+":"+toString(num)+")<push 3="">]\tStack Size:"+toString((int) m_sSStack.size())+"\tLx:"+toString(Lx)+"\tRx:"+toString(pLx-1)+"\tpLx:"+toString(pushLx)+"\tpRx:"+toString(pushRx)+"\ty:"+toString(y-dir)+"\tdir:"+toString(dir)+"\n");</push>

		assert(((Lx) <= (pLx - 1)) && (pushLx <= pushRx) && (Lx >= 0));

		m_sSStack.push(ShadowSegment(Lx, (pLx - 1), pushLx, pushRx, (y - dir), (-dir)));

		shadowEnqueued++;

	}

	// W-Turn = 2 U-Turn

} // EnqueueSegment

void MagicWandFx::doMagicWand(TTile &tile, double frame, const TRasterFxRenderInfo *ri)

{

	clock_t start_time = clock(); // debug

	clock_t stop_time;

	invocazioni++;

	m_id_invocazione = invocazioni;

	m_tol = m_tolerance->getValue(frame);

	m_antial = m_antialiased->getValue();

	m_euclid = m_euclideanD->getValue(); // temporaneo?

	m_cont = m_contiguous->getValue();   // selezione di aree cromaticamente compatibili ma non contigue: Selezione ByColor

	m_add = m_isShiftPressed->getValue();

	m_sub = m_isAltPressed->getValue();

	tile.getRaster()->lock();

	TRaster32P ras32 = tile.getRaster();

	TPixel32 vPixel;

	TPixel32 *tmpPix;

	TPixel32 *rowStart;

	TPixelGR8 *maskRowStart;

	TPixelGR8 *maskPix;

	if (ras32) {

		pixelProcessed = 0;

		pixelMasked = 1;

		shadowEnqueued = 2;

		pixelReprocessed = 0;

		shadowOutOfBorder = 0;

		m_imageWidth = ras32->getLx();

		m_imageHeigth = ras32->getLy();

		//assert(m_imageWidth == 800);

		assert(m_imageHeigth <= 600);

		int lx = m_imageWidth;

		int ly = m_imageHeigth;

		if (!m_maskGR8) {

			// prima esecuzione creo il raster gr8 x la maschera e azzero gli alpha

			TRectD bBoxD;

			TPixel32 bgColor;

			bool getBBoxOk = getBBox(frame, bBoxD, bgColor);

			assert(getBBoxOk);

			TRect bBoxI = convert(bBoxD);

			m_maskGR8 = TRasterGR8P(bBoxI.getLx(), bBoxI.getLy());

			m_maskGR8->clear();

		}

		m_maskGR8->lock();

		// sono arrivato qui: sto verificando se serve davvero il gr8.

		for (int iy = 0; iy < m_imageHeigth; iy++) { // y

			tmpPix = ras32->pixels(iy);

			for (int ix = 0; ix < m_imageWidth; ix++) { // x

				tmpPix->m = EmptyPixel;

				tmpPix++;

			} // x

		}	 // y

		if (m_add) { // ho premuto Shift sto aggiungendo alla selezione

		} else if (m_sub) {

			// ho premuto Alt sto sottraendo dalla selezione

		} else {

			// non ho premuto niente nuova selezione

			// ripulisco il canale alpha dell'immagine e la maschera

			for (int iy = 0; iy < m_imageHeigth; iy++) {

				tmpPix = ras32->pixels(iy);

				maskPix = m_maskGR8->pixels(iy);

				for (int ix = 0; ix < m_imageWidth; ix++) {

					tmpPix->m = 0;

					maskPix->value = EmptyPixel;

					tmpPix++;

					maskPix++;

				} // x

			}	 // y

		}

		// trovo il pixel in X,Y soluzione temporanea in attesa della gestione del mouse.

		// converto le coordinate mondo (-500;+500) in coordinate raster (0;m_imageWidth);

		TPointD point = m_point->getValue(frame);

		// coordinate dagli sliders

		//    int x = (int) (500+point.x)*m_imageWidth/1000; if (x>0) x--;

		//    int y = (int) (500+point.y)*m_imageHeigth/1000; if (y>0) y--;

		// coordinate dalla ZViewer:leftButtonClick

		int x = tcrop((int)(point.x + m_imageWidth / 2), 0, (m_imageWidth - 1));

		int y = tcrop((int)(point.y + m_imageHeigth / 2), 0, (m_imageHeigth - 1));

		TSystem::outputDebug("\n[MWfx(" + toString(m_id_invocazione) + ")<begin>]\nSize:" + toString(m_imageWidth) + "x" + toString(m_imageHeigth) + "\tx:" + toString(x) + "\ty:" + toString(y) + "\tToll:" + toString(m_tol) + /*      "\tRadius:" + toString(radius) +*/ ((m_cont) ? "\tContiguous" : "\tNon Contiguous") + ((m_antial) ? "\tAnti Aliased" : "\tAliased") + ((m_euclid) ? "\tEuclidean\n" : "\tNon Euclidean\n"));</begin>

		lx = m_imageWidth;

		ly = m_imageHeigth;

		m_pickedPix = ras32->pixels(y) + x;

		m_maskPickedPix = m_maskGR8->pixels(y) + x;

		pixelProcessed = 1;

		if (m_cont) { // seleziono esclusivamente i pixel connessi al pixel SEED

			//- ALGORITMO FLOOD FILL: GRAPHICS GEM 1 p.280 ----------------------------------------

			int xAux, yAux, lxAux, rxAux, dirAux, pRxAux, pLxAux;

			bool inSpan = true;

			// trova Rx e Lx dello span contentente il SEED point

			int xCont = x;

			tmpPix = m_pickedPix;	  // puntatore al SEED

			maskPix = m_maskPickedPix; //******

			// cerco Lx

			maskValue = pixelProcessor(tmpPix, maskPix);

			bool tmpMv = maskValue;

			while ((xCont >= 0) && (maskValue)) {

				tmpPix--;

				maskPix--;

				xCont--;

				if (xCont >= 0)

					maskValue = pixelProcessor(tmpPix, maskPix);

			}

			if (tmpMv)

				lxAux = xCont + 1;

			else

				lxAux = xCont;

			// cerco Rx

			tmpPix = m_pickedPix;

			maskPix = m_maskPickedPix; //******

			xCont = x;

			maskValue = tmpMv;

			while ((xCont < m_imageWidth) && (maskValue)) {

				tmpPix++;

				maskPix++;

				xCont++;

				if (xCont < m_imageWidth)

					maskValue = pixelProcessor(tmpPix, maskPix);

			}

			if (tmpMv)

				rxAux = xCont - 1;

			else

				rxAux = xCont;

			assert((lxAux <= rxAux) && (lxAux >= 0));

			// metto nella pila delle ombre la riga sopra e sotto quella contentente il seed.

			//            TSystem::outputDebug("[MWfx("+toString(m_id_invocazione)+")]\tStack Size:"+toString((int) m_sSStack.size())+"\tLx:"+toString(lxAux)+"\tRx:"+toString(rxAux)+"\tpLx:"+toString(lxAux)+"\tpRx:"+toString(rxAux)+"\ty:"+toString(y+1)+"\tdir:"+toString(1)+"\n");

			m_sSStack.push(ShadowSegment(lxAux, rxAux, lxAux, rxAux, y + 1, +1)); // cerca in alto

																				  //            TSystem::outputDebug("[MWfx("+toString(m_id_invocazione)+")]\tStack Size:"+toString((int) m_sSStack.size())+"\tLx:"+toString(lxAux)+"\tRx:"+toString(rxAux)+"\tpLx:"+toString(lxAux)+"\tpRx:"+toString(rxAux)+"\ty:"+toString(y-1)+"\tdir:"+toString(-1)+"\n");

			m_sSStack.push(ShadowSegment(lxAux, rxAux, lxAux, rxAux, y - 1, -1)); // cerca in basso

			while (!m_sSStack.empty()) {

				ShadowSegment sSegment = m_sSStack.top();

				m_sSStack.pop();

				//        TSystem::outputDebug("[MWfx("+toString(m_id_invocazione)+":0)<pop>]\tStack Size:"+toString((int) m_sSStack.size())+"\tLx:"+toString(sSegment.m_lx)+"\tRx:"+toString(sSegment.m_rx)+"\tpLx:"+toString(sSegment.m_pLx)+"\tpRx:"+toString(sSegment.m_pRx)+"\ty:"+toString(sSegment.m_y)+"\tdir:"+toString(sSegment.m_dir)+"\n");</pop>

				dirAux = sSegment.m_dir;

				pRxAux = sSegment.m_pRx;

				pLxAux = sSegment.m_pLx;

				lxAux = sSegment.m_lx;

				rxAux = sSegment.m_rx;

				yAux = sSegment.m_y;

				if ((yAux < 0) || (yAux >= m_imageHeigth)) {

					shadowOutOfBorder++;

					continue; // questo segmento sta fuori dal raster oppure l'ho gia' colorato: lo salto

				}

				assert((lxAux <= rxAux) && (pLxAux <= pRxAux));

				assert((m_sSStack.size() <= 1000));

				xAux = lxAux + 1;

				rowStart = ras32->pixels(yAux);

				maskRowStart = m_maskGR8->pixels(yAux); //**

				tmpPix = rowStart + lxAux;

				maskPix = maskRowStart + lxAux;

				maskValue = pixelProcessor(tmpPix, maskPix);

				inSpan = (maskValue);

				if (maskValue) { // il punto e' cromaticompatibile

					lxAux--;

					if (lxAux >= 0) {

						tmpPix--;

						maskPix--;

						maskValue = pixelProcessor(tmpPix, maskPix);

					}

					while ((maskValue) && (lxAux >= 0)) { // sto nello span E nell'immagine

						lxAux--;

						if (lxAux >= 0) {

							tmpPix--;

							maskPix--;

							maskValue = pixelProcessor(tmpPix, maskPix);

						}

					} // sto nello span E nell'immagine

				}	 // il punto e' cromaticompatibile

				lxAux++;

				//        rowStart = ras32->pixels(yAux);

				while (xAux < m_imageWidth) { // mi sposto a destra lungo la X

					if (inSpan) {

						tmpPix = rowStart + xAux;

						maskPix = maskRowStart + xAux; //***

						maskValue = pixelProcessor(tmpPix, maskPix);

						if (maskValue) { // case 1

										 // fa tutto nella pixel processor

						}				 // case 1

						else {			 // case 2

							EnqueueSegment(1, dirAux, pLxAux, pRxAux, lxAux, (xAux - 1), yAux);

							inSpan = false;

						}  // case 2

					}	  // inSpan

					else { // non ero nello span

						if (xAux > rxAux)

							break;

						tmpPix = rowStart + xAux;

						maskPix = maskRowStart + xAux;

						maskValue = pixelProcessor(tmpPix, maskPix);

						if (maskValue) { // case 3

							inSpan = true;

							lxAux = xAux;

						}	  // case 3

						else { // case 4

						}

					} // non ero nello span

					xAux++;

					//          TSystem::outputDebug("[MWfx("+toString(m_id_invocazione)+")]\tStack Size:"+toString((int) m_sSStack.size())+"\txAux:"+toString(xAux)+"\ty:"+toString(yAux)+"\n");

				} // mi sposto a destra lungo la X: endloop 1

				if (inSpan) {

					EnqueueSegment(2, dirAux, pLxAux, pRxAux, lxAux, (xAux - 1), yAux);

				}

			}  // finche' la pila non e' vuota: endloop 2

		}	  // if m_cont

		else { // anche le regioni simili NON contigue: questo rimane anche in caso di modifica della parte m_cont

			for (int iy = 0; iy < m_imageHeigth; iy++) {

				tmpPix = ras32->pixels(iy);

				maskPix = m_maskGR8->pixels(iy);

				for (int ix = 0; ix < m_imageWidth; ix++) {

					maskValue = pixelProcessor(tmpPix, maskPix);

					//                 if (maskValue) { } // if// il colore e' simile => va incluso nella selezione // fa tutto nella pixel processor

					tmpPix++;

					maskPix++;

				} // ix

			}	 // iy

		}		  // else m_cont

		int blurRadius = (int)(m_blurRadius->getValue(frame));

		if ((m_antial) && (blurRadius < 2))

			blurRadius = 1;

		if (blurRadius > 0)

			TRop::blur(m_maskGR8, m_maskGR8, (blurRadius + 1), 0, 0);

		// copio la maschera sull'alpha channel dell'immagine

		// lo faccio a mano chiedere se esiste una funziona apposita

		for (iy = 0; iy < m_imageHeigth; iy++) {

			tmpPix = ras32->pixels(iy);

			maskPix = m_maskGR8->pixels(iy);

			for (int ix = 0; ix < m_imageWidth; ix++) {

				tmpPix->m = maskPix->value;

				tmpPix++;

				maskPix++;

			} //ix

		}	 //iy

		if (m_preMolt->getValue())

			TRop::premultiply(ras32);

		stop_time = clock();

		double durata = (double)(stop_time - start_time) / CLOCKS_PER_SEC;

		TSystem::outputDebug("\n#Pixel:\t" + toString(m_imageWidth * m_imageHeigth) + "\nProc:\t" + toString(pixelProcessed) + "\t[" + toString((pixelProcessed * 100 / (m_imageWidth * m_imageHeigth))) + "%t]" + "\nMask:\t" + toString(pixelMasked) + "\t[" + toString((pixelMasked * 100 / (m_imageWidth * m_imageHeigth))) + "%t]" + "\t[" + toString((pixelMasked * 100 / (pixelProcessed))) + "%p]" + "\nEnqu:\t" + toString(shadowEnqueued) + "\nRepr:\t" + toString(pixelReprocessed) + "\t[" + toString((pixelReprocessed * 100 / (m_imageWidth * m_imageHeigth))) + "%t]" + "\t[" + toString((pixelReprocessed * 100 / (pixelProcessed))) + "%p]" + "\nOutB:\t" + toString(shadowOutOfBorder) + "\t[" + toString((shadowOutOfBorder * 100 / (shadowEnqueued))) + "%t]" + "\nTime:\t" + toString(durata, 3) + " sec\n[MagicWandFX <end>]\n");</end>

	} // if (ras32)

	else {

		TRasterGR8P rasGR8 = tile.getRaster();

		if (rasGR8) {

		}

	}

	tile.getRaster()->unlock();

	m_maskGR8->unlock();

} // doMagicWand

void MagicWandFx::doCompute(TTile &tile, double frame, const TRasterFxRenderInfo *ri)

{

	if (!m_input.isConnected())

		return;

	m_input->compute(tile, frame, ri);

	doMagicWand(tile, frame, ri);

}

//------------------------------------------------------------------

TRect MagicWandFx::getInvalidRect(const TRect &max)

{

	return max;

}

//------------------------------------------------------------------

FX_PLUGIN_IDENTIFIER(MagicWandFx, magicWandFx);