#include "tmachine.h"

#include "tmathutil.h"

#include "tstrokeutil.h"

#include "tstrokeoutline.h"

#include "tcurves.h"

#include "tbezier.h"

#include "tzerofinder.h"

#include "tcurveutil.h"

#include <limits></limits>

#include "tstroke.h"

//=============================================================================

#define USE_NEW_3D_ERROR_COMPUTE 1

//=============================================================================

// Some using declaration

using namespace TConsts;

using namespace std;

// Some useful typedefs

typedef std::vector<double> DoubleArray;</double>

typedef DoubleArray::iterator DoubleIt;

typedef std::vector<tthickquadratic *=""> QuadStrokeChunkArray;</tthickquadratic>

static int numSaved = 0;

void detectCorners(const std::vector<t3dpointd> &points,</t3dpointd>

				   int minSampleNum,

				   int minDist,

				   int maxDist,

				   double maxAngle,

				   std::vector<int> &corners);</int>

namespace

{

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

void extractStrokeControlPoints(const QuadStrokeChunkArray &curves,

								vector<tthickpoint> &ctrlPnts)</tthickpoint>

{

	const TThickQuadratic *prev = curves[0];

	assert(prev);

	const TThickQuadratic *curr;

	ctrlPnts.push_back(prev->getThickP0());

	ctrlPnts.push_back(prev->getThickP1());

	for (UINT i = 1; i < curves.size(); ++i) {

		curr = curves[i];

		assert(curr);

		TThickPoint middlePnt = (prev->getThickP2() + curr->getThickP0()) * 0.5;

		ctrlPnts.push_back(middlePnt);

		ctrlPnts.push_back(curr->getThickP1());

		prev = curr;

	}

	ctrlPnts.push_back(prev->getThickP2());

}

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

inline TThickPoint adapter(const TThickPoint &tp)

{

	return tp;

}

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

inline TThickPoint adapter(const TPointD &p)

{

	return TThickPoint(p);

}

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

template <typename t=""></typename>

void buildChunksFromControlPoints(QuadStrokeChunkArray &tq,

								  const vector<t> &v)</t>

{

	TThickQuadratic *chunk;

	T temp;

	switch (v.size()) {

	case 0:

		tq.push_back(new TThickQuadratic);

		break;

	case 1:

		temp = adapter(v.front());

		chunk = new TThickQuadratic(temp, temp, temp);

		tq.push_back(chunk);

		break;

	case 2: {

		TThickSegment s(adapter(v.front()), adapter(v.back()));

		chunk = new TThickQuadratic(s.getThickP0(), s.getThickPoint(0.5), s.getThickP1());

		tq.push_back(chunk);

	} break;

	default:

		assert(v.size() & 1); //  v.size() == 2 * chunk + 1

		for (UINT i = 0; i < v.size() - 1; i += 2) {

			chunk = new TThickQuadratic(adapter(v[i]), adapter(v[i + 1]), adapter(v[i + 2]));

			tq.push_back(chunk);

		}

		break;

	}

}

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

// WARNING  duplicata in tellipticbrush

//  dovrebbe essere eliminata da tellipticbrush perche' qui

//  viene usata per  eliminare le strokes a thickness negativa

//  evitandone la gestione in tellip...

inline bool pairValuesAreEqual(const DoublePair &p)

{

	return p.first == p.second;

}

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

// WARNING  duplicata in tellipticbrush

//  dovrebbe essere eliminata da tellipticbrush perche' qui

//  viene usata per  eliminare le strokes a thickness negativa

//  evitandone la gestione in tellip...

void analyzeSolution(const vector<double> &coeff, vector<doublepair> &interval)</doublepair></double>

{

	//  risolve la disequazione  coeff[2]*t^2 + coeff[1]*t + coeff[0] >= 0  in [0, 1] ritornando le soluzioni

	//  come sotto-intervalli chiusi di [0, 1] (gli intervalli degeneri [s, s] isolati vengono eliminati)

	vector<double> sol;</double>

	//int numberOfIntervalSolution = 0;

	rootFinding(coeff, sol);

	if (isAlmostZero(coeff[2])) {

		//  disequazione di 1^ grado

		if (isAlmostZero(coeff[1])) {

			if (coeff[0] >= 0)

				interval.push_back(DoublePair(0.0, 1.0));

			return;

		}

		double singleSol = -coeff[0] / coeff[1];

		if (coeff[1] > 0) {

			if (singleSol < 1)

				interval.push_back(DoublePair(std::max(0.0, singleSol), 1.0));

		} else {

			if (singleSol > 0)

				interval.push_back(DoublePair(0.0, std::min(1.0, singleSol)));

		}

		return;

	}

	//  disequazione di 2^ grado effettivo

	//double delta = sq(coeff[1]) - 4*coeff[2]*coeff[0];

	sort(sol.begin(), sol.end());

	if (coeff[2] > 0) {

		switch (sol.size()) {

		case 0:

			interval.push_back(DoublePair(0.0, 1.0));

			break;

		case 1:

			interval.push_back(DoublePair(0.0, 1.0));

			break;

		case 2:

			interval.push_back(DoublePair(0.0, std::min(std::max(sol[0], 0.0), 1.0)));

			interval.push_back(DoublePair(std::max(std::min(sol[1], 1.0), 0.0), 1.0));

			break;

		}

	} else if (coeff[2] < 0 && sol.size() == 2)

		interval.push_back(DoublePair(std::min(std::max(sol[0], 0.0), 1.0),

									  std::max(std::min(sol[1], 1.0), 0.0)));

	// eat not valid interval

	std::vector<doublepair>::iterator it = std::remove_if(interval.begin(),</doublepair>

														  interval.end(),

														  pairValuesAreEqual);

	interval.erase(it, interval.end());

}

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

void floorNegativeThickness(TThickQuadratic *quad)

{

	assert(quad);

	double val = quad->getThickP0().thick;

	if (val < 0 && isAlmostZero(val))

		quad->setThickP0(TThickPoint(quad->getP0(), 0.0));

	val = quad->getThickP1().thick;

	if (val < 0 && isAlmostZero(val))

		quad->setThickP1(TThickPoint(quad->getP1(), 0.0));

	val = quad->getThickP2().thick;

	if (val < 0 && isAlmostZero(val))

		quad->setThickP2(TThickPoint(quad->getP2(), 0.0));

}

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

// potrebbe essere realizzata come unary function da usare in una transform

void roundNegativeThickess(QuadStrokeChunkArray &v)

{

	QuadStrokeChunkArray

		protoStroke,

		tempVectTQ;

	TThickQuadratic

		*tempTQ = 0,

		*tempTQ_1 = 0;

	int chunkCount = v.size();

	vector<double> coeff;</double>

	double alpha,

		beta,

		gamma;

	vector<doublepair></doublepair>

		positiveIntervals;

	for (int i = 0; i < chunkCount; ++i) {

		const TThickQuadratic &ttq = *v[i];

		alpha = ttq.getThickP0().thick - 2 * ttq.getThickP1().thick + ttq.getThickP2().thick;

		beta = 2.0 * (ttq.getThickP1().thick - ttq.getThickP0().thick);

		gamma = ttq.getThickP0().thick;

		coeff.push_back(gamma);

		coeff.push_back(beta);

		coeff.push_back(alpha);

		//  return sotto-intervalli non degeneri di [0, 1] in cui coeff[2]*t^2 + coeff[1]*t + coeff[0] >= 0

		analyzeSolution(coeff, positiveIntervals);

		//  il caso isAlmostZero(r(t)) per t in [0, 1] e' gestito direttamente da computeOutline

		switch (positiveIntervals.size()) {

		case 0: //  r(t) <= 0 per t in [0, 1]

			tempTQ = new TThickQuadratic(ttq);

			tempTQ->setThickP0(TThickPoint(tempTQ->getP0(), 0.0));

			tempTQ->setThickP1(TThickPoint(tempTQ->getP1(), 0.0));

			tempTQ->setThickP2(TThickPoint(tempTQ->getP2(), 0.0));

			protoStroke.push_back(tempTQ);

			break;

		case 1:

			if (positiveIntervals[0].first == 0.0 &&

				positiveIntervals[0].second == 1.0)

				protoStroke.push_back(new TThickQuadratic(ttq));

			else if (positiveIntervals[0].first == 0.0) {

				tempTQ = new TThickQuadratic;

				tempTQ_1 = new TThickQuadratic;

				ttq.split(positiveIntervals[0].first,

						  *tempTQ,

						  *tempTQ_1);

				tempTQ_1->setThickP0(TThickPoint(tempTQ_1->getP0(), 0.0));

				tempTQ_1->setThickP1(TThickPoint(tempTQ_1->getP1(), 0.0));

				tempTQ_1->setThickP2(TThickPoint(tempTQ_1->getP2(), 0.0));

				floorNegativeThickness(tempTQ);

				protoStroke.push_back(tempTQ);

				protoStroke.push_back(tempTQ_1);

			} else if (positiveIntervals[0].second == 1.0) {

				tempTQ = new TThickQuadratic;

				tempTQ_1 = new TThickQuadratic;

				ttq.split(positiveIntervals[0].first,

						  *tempTQ,

						  *tempTQ_1);

				tempTQ->setThickP0(TThickPoint(tempTQ->getP0(), 0.0));

				tempTQ->setThickP1(TThickPoint(tempTQ->getP1(), 0.0));

				tempTQ->setThickP2(TThickPoint(tempTQ->getP2(), 0.0));

				protoStroke.push_back(tempTQ);

				floorNegativeThickness(tempTQ_1);

				protoStroke.push_back(tempTQ_1);

			} else {

				coeff.clear();

				coeff.push_back(positiveIntervals[0].first);

				coeff.push_back(positiveIntervals[0].second);

				split<tthickquadratic>(ttq, coeff, tempVectTQ);</tthickquadratic>

				assert(tempVectTQ.size() == 3);

				tempVectTQ[0]->setThickP0(TThickPoint(tempVectTQ[0]->getP0(), 0.0));

				tempVectTQ[0]->setThickP1(TThickPoint(tempVectTQ[0]->getP1(), 0.0));

				tempVectTQ[0]->setThickP2(TThickPoint(tempVectTQ[0]->getP2(), 0.0));

				// controllo che i valori prossimi a zero siano in ogni caso positivi

				floorNegativeThickness(tempVectTQ[1]);

				tempVectTQ[2]->setThickP0(TThickPoint(tempVectTQ[2]->getP0(), 0.0));

				tempVectTQ[2]->setThickP1(TThickPoint(tempVectTQ[2]->getP1(), 0.0));

				tempVectTQ[2]->setThickP2(TThickPoint(tempVectTQ[2]->getP2(), 0.0));

				copy(tempVectTQ.begin(), tempVectTQ.end(), back_inserter(protoStroke));

				tempVectTQ.clear(); // non serve una clearPointerArray perchè il possesso

									// va alla protoStroke

			}

			break;

		case 2:

			assert(positiveIntervals[0].first == 0.0);

			assert(positiveIntervals[1].second == 1.0);

			coeff.clear();

			coeff.push_back(positiveIntervals[0].second);

			coeff.push_back(positiveIntervals[1].first);

			split<tthickquadratic>(ttq, coeff, tempVectTQ);</tthickquadratic>

			assert(tempVectTQ.size() == 3);

			floorNegativeThickness(tempVectTQ[0]);

			tempVectTQ[1]->setThickP0(TThickPoint(tempVectTQ[1]->getP0(), 0.0));

			tempVectTQ[1]->setThickP1(TThickPoint(tempVectTQ[1]->getP1(), 0.0));

			tempVectTQ[1]->setThickP2(TThickPoint(tempVectTQ[1]->getP2(), 0.0));

			floorNegativeThickness(tempVectTQ[2]);

			copy(tempVectTQ.begin(), tempVectTQ.end(), back_inserter(protoStroke));

			tempVectTQ.clear(); // non serve una clearPointerArray perchè il possesso

			break;

		}

		positiveIntervals.clear();

		coeff.clear();

	}

	swap(protoStroke, v);

	clearPointerContainer(protoStroke);

}

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

// Some usefuf constant

// used in printContainer to set number of row to print

const int MAX_ROW = 10;

inline void changeTQDirection(TThickQuadratic *tq)

{

	TThickPoint p = tq->getThickP2();

	tq->setThickP2(tq->getThickP0());

	tq->setThickP0(p);

}

/*

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

  double getTQDistance2(const TThickQuadratic& tq, 

    const TPointD& p, 

    double maxDistance2, 

    double& currT)

  {

    TRectD rect = tq.getBBox();

    if (!rect.contains(p))

    {

      double dist21 = tdistance2(p, rect.getP00());

      double dist22 = tdistance2(p, rect.getP01());

      double dist23 = tdistance2(p, rect.getP10());

      double dist24 = tdistance2(p, rect.getP11());

      if (std::min(dist21, dist22, dist23, dist24)>=maxDistance2)

        return maxDistance2;

    }

    currT = tq.getT(p);

    double dist2 = tdistance2(tq.getPoint(currT), p); 

    return (dist2

  }

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

  template <class class="" k,="" t=""> </class>

    void clearMap(std::map<k,t>& v)</k,t>

  {

    typedef std::map<k,t>::iterator TypeIt;</k,t>

    TypeIt it = v.begin();

    for( ;it!=v.end(); ++it)

      delete it->second;

    v.clear();

  }

  */

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

/*

  Local binary function to find approx values in a vector.

  */

bool bfAreAlmostEqual(double x, double y)

{

	double x_y = (x > y) ? x - y : y - x;

	return x_y < TConsts::epsilon;

}

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

/*

  Sends values of a container in standard input.

  */

template <class t=""></class>

void printContainer(const T &c, int maxRow = MAX_ROW)

{

	/*  DA DECOMMENTARE SE NECESSARIO!!!!! 

	    //(commentato per non avere dipendenze da tsystem.lib 7/1/2004)

    if (maxRow <=0 ) maxRow = MAX_ROW;

    typename T::const_iterator cit;

    cit = c.begin();

    ostrstream  oss1;

    oss1<<'['<

    TSystem::outputDebug( oss1.str() );

    oss1.freeze(false);

    int counter = 0;

    for( ; cit != c.end(); ++cit)

    {

      ostrstream  oss;

      if( ++counter == maxRow-1)

      {

        oss<<'\n';

        counter = 0;

      }

      oss<<(*cit)<<'\n'<<'\0';

      TSystem::outputDebug( oss.str() );

      oss.freeze(false);

    }

		*/

}

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

template <class t=""></class>

void printContainer(ostream &os, const T &c, int maxRow = MAX_ROW)

{

	if (maxRow <= 0)

		maxRow = MAX_ROW;

	typename T::const_iterator cit;

	cit = c.begin();

	os << '[' << c.size() << ']' << "=\n";

	int counter = 0;

	for (; cit != c.end(); ++cit) {

		if (++counter == maxRow - 1) {

			os << '\n';

			counter = 0;

		}

		os << (*cit) << ' ';

	}

}

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

template <class t=""></class>

void printContainerOfPointer(ostream &os, const T &c, int maxRow = MAX_ROW)

{

	if (maxRow <= 0)

		maxRow = MAX_ROW;

	typename T::const_iterator cit;

	cit = c.begin();

	os << '[' << c.size() << ']' << " - ";

	int counter = 0;

	for (; cit != c.end(); ++cit) {

		if (++counter == maxRow - 1) {

			os << '\n';

			counter = 0;

		}

		os << **cit << ' ';

	}

}

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

/*

  Compute a proportion of type x:a=b:c

  */

template <class t=""></class>

T proportion(T a, T b, T c)

{

	assert(c != T(0));

	return a * b / c;

}

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

/*

  Compute a proportion of type x-off:a-off=b:c

  */

template <class t=""></class>

T proportion(T a, T b, T c, T offset)

{

	assert(c != T(0));

	return (a - offset) * b / c + offset;

}

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

/*!

    backinserter

   */

template 

		  typename container_>

class TBackInserterPointer

{

	container_ &m_c;

public:

	explicit TBackInserterPointer(container_ &c)

		: m_c(c){};

	TBackInserterPointer &operator=(const type_ *value)

	{

		m_c.push_back(new type_(*value));

		return *this;

	}

	TBackInserterPointer &operator=(const type_ &value)

	{

		m_c.push_back(new type_(value));

		return *this;

	};

#ifdef MACOSX

	typedef type_ value_type;

	typedef type_ &reference;

	typedef type_ *pointer;

	typedef output_iterator_tag iterator_category;

	typedef ptrdiff_t difference_type;

#endif

	/* SIC */

	TBackInserterPointer &operator*() { return *this; }

	TBackInserterPointer &operator++() { return *this; }

	TBackInserterPointer operator++(int val) { return *this; }

};

typedef TBackInserterPointer<tthickquadratic, quadstrokechunkarray=""> TThickQuadraticArrayInsertIterator;</tthickquadratic,>

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

/*!

  simple adapter for find zero algorithm

  */

struct computeOffset_ {

	TQuadraticLengthEvaluator m_lengthEval;

	double m_offset;

	computeOffset_(const TThickQuadratic *ttq,

				   double offset)

		: m_lengthEval(*ttq), m_offset(offset)

	{

	}

	double operator()(double par)

	{

		return m_lengthEval.getLengthAt(par) - m_offset;

	}

};

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

/*!

  simple adapter for find zero algorithm

  */

struct computeSpeed_ {

	const TThickQuadratic *ref_;

	computeSpeed_(const TThickQuadratic *ref)

		: ref_(ref)

	{

	}

	double operator()(double par)

	{

		return norm(ref_->getSpeed(par));

	}

};

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

} // end of unnamed namespace

//=============================================================================

const BYTE TStroke::c_selected_flag = 0x1;

const BYTE TStroke::c_changed_region_flag = 0x2;

const BYTE TStroke::c_dirty_flag = 0x4;

//=============================================================================

//

// TStroke::Imp

//

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

struct TStroke::Imp {

	//Geometry-related infos

	BYTE m_flag;

	//! This flag checks if changes occurs and if it is neccessary to update lenght.

	bool m_isValidLength;

	//! This flag checks if changes occurs and if it is neccessary to update outline.

	bool m_isOutlineValid;

	//! Control calculus of cache vector.

	bool m_areDisabledComputeOfCaches;

	//! Bounding Box of a stroke

	TRectD m_bBox;

	//! This vector contains length computed for  each control point of stroke.

	DoubleArray m_partialLenghtArray;

	//! This vector contains parameter computed for each control point of stroke.

	DoubleArray m_parameterValueAtControlPoint;

	//! This vector contains outline of stroke.

	QuadStrokeChunkArray m_centerLineArray;

	bool m_selfLoop;

	int m_negativeThicknessPoints;

	double m_averageThickness;

	double m_maxThickness;

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

	//Not-geometrical vars (style infos)

	int m_id;

	int m_styleId;

	TStrokeProp *m_prop;

	TStroke::OutlineOptions m_outlineOptions;

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

	Imp();

	Imp(const vector<tpointd> &v);</tpointd>

	Imp(const vector<tthickpoint> &v);</tthickpoint>

	~Imp()

	{

		delete m_prop;

		clearPointerContainer(m_centerLineArray);

		//delete m_style;

	}

	void init();

	// void  computeOutlines( double pixelSize );

	inline double getW(int index) { return ((int)m_parameterValueAtControlPoint.size() > index) ? m_parameterValueAtControlPoint[index] : m_parameterValueAtControlPoint.back(); }

	TRectD computeCenterlineBBox();

	/*! 

  It computes the bounding box of the subStroke in the parameter range w0-w1.

  */

	void computeMaxThickness();

	TRectD computeSubBBox(double w0, double w1) const;

	inline QuadStrokeChunkArray &getTQArray()

	{

		return m_centerLineArray;

	}

	/*! 

    Swaps the geometrical infos only

  */

	void swapGeometry(TStroke::Imp &other) throw();

	//! compute cache vector

	void computeCacheVector();

	/*!

  Set value in m_parameterValueAtControlPoint

  */

	void computeParameterInControlPoint();

	/*! 

  Update parameter in m_parameterValueAtControlPoint 

  after insert of control point in stroke.

  */

	void updateParameterValue(double w,

							  UINT chunk,

							  TThickQuadratic *tq1,

							  TThickQuadratic *tq2);

	/*!

    From parameter w retrieves chunk and its parameter ( t in [0,1] ).

    Return 

    true  ->  error (parameter w out of range, etc)

    false ->  ok

  */

	bool retrieveChunkAndItsParamameter(double w, int &chunk, double &t);

	/*!

  From lenght s retrieves chunk and its parameter ( t in [0,1] ).

  Return 

  true  ->  error (parameter w out of range, etc)

  false ->  ok

  */

	bool retrieveChunkAndItsParamameterAtLength(double s, int &chunk, double &t);

	/*!

  Retrieve chunk which contains the n-th control point of stroke.

  If control point is between two chunks return the left point.

  */

	int retrieveChunkFromControlPointIndex(int n)

	{

		assert(0 <= n && n < getControlPointCount());

		if (n & 1)

			++n;

		n >>= 1;

		return n ? n - 1 : n;

	};

	/*!

  Retrieve range for a chunk.

  */

	DoublePair retrieveParametersFromChunk(UINT chunk)

	{

		DoublePair outPar;

		int nFirst, nSecond;

		nFirst = chunk * 2;

		nSecond = (chunk + 1) * 2;

		outPar.first = getW(nFirst);

		outPar.second = getW(nSecond);

		return outPar;

	}

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

	void print(ostream &os);

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

	inline int getChunkCount() const

	{

		return m_centerLineArray.size();

	}