#ifdef _DEBUG

#define _STLP_DEBUG 1

#endif

#include <tcurves.h></tcurves.h>

#include <tstroke.h></tstroke.h>

#include <tmathutil.h></tmathutil.h>

#include <tcurveutil.h></tcurveutil.h>

#include <tgl.h></tgl.h>

#include <set></set>

#include <iterator></iterator>

// please do not move, it is necessary to be the last

// to work properely with DVAPI macro

#include "ext/ExtUtil.h"

// just to override assert

#ifdef _DEBUG

#define EXT_NORMALIZE(a) norm2(a) != 0.0 ? normalize(a) : a

#define DEBUG_EXPORT DVAPI

#else

#define EXT_NORMALIZE(a) normalize(a)

#define DEBUG_EXPORT static

#endif

namespace

{

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

inline bool

isWGood(double first,

		double w,

		double second,

		const TStroke *s)

{

	if (!ToonzExt::isValid(first) ||

		!ToonzExt::isValid(second) ||

		!ToonzExt::isValid(w))

		return false;

	if (s) {

		if (s->isSelfLoop())

			if (first > second) {

				if ((first < w && w <= 1.0) ||

					(0.0 <= w && w < second))

					return true;

			} else if (first == second) {

				if (areAlmostEqual(w, first))

					return true;

			}

	}

	if (first < w && w < second)

		return true;

	return false;

}

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

inline int normalizeAngle(int angle)

{

	if (angle < 0)

		angle = -angle;

	return angle %= 181;

}

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

int getStrokeId(const TStroke *s,

				const TVectorImageP &vi)

{

	if (!ToonzExt::isValid(s) ||

		!vi)

		return -1;

	int

		count = vi->getStrokeCount();

	if (!count)

		return -1;

	while (count--) {

		if (s == vi->getStroke(count))

			return count;

	}

	return -1;

}

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

/**

   * Verify if a curve is a "almost" point.

   */

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

bool isImproper(const T *tq)

{

	TPointD

		v1 = tq->getP0() - tq->getP1(),

		v2 = tq->getP2() - tq->getP1();

	if (isAlmostZero(norm2(v1)) &&

		isAlmostZero(norm2(v2)))

		return true;

	return false;

}

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

bool areParallel(const TPointD &v1,

				 const TPointD &v2)

{

	double

		res = cross(EXT_NORMALIZE(v1), EXT_NORMALIZE(v2));

	if (isAlmostZero(res))

		return true;

	return false;

}

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

bool areInSameDirection(const TPointD &v1,

						const TPointD &v2)

{

	if (v1 * v2 >= 0)

		return true;

	return false;

}

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

/**

   * Verify if a curve is a straight line.

   */

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

bool curveIsStraight(const T *tq,

					 double &t)

{

	t = -1;

	assert(tq);

	if (!tq)

		return false;

	TPointD v1 = tq->getP1() - tq->getP0();

	TPointD v2 = tq->getP2() - tq->getP1();

	double

		res = cross(v1, v2);

	if (isAlmostZero(res)) {

		if (v1 * v2 < 0) {

			t = tq->getT(tq->getP1());

		}

		return true;

	}

	return false;

}

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

/**

   * Verify if junction between two curves, is smooth.

   */

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

bool corner(const T *q1,

			const T *q2,

			double tolerance)

{

	if (!q1 ||

		!q2 ||

		!areAlmostEqual(q1->getP2(),

						q2->getP0()))

		return false;

	// really near to the extremes

	TPointD

		//pnt = q1->getP2(),

		v1 = q1->getSpeed(1.0), //q1->getPoint(1.0-TConsts::epsilon) - pnt,

		v2 = q2->getSpeed(0.0); //q2->getPoint(TConsts::epsilon) - pnt;

	v1 = EXT_NORMALIZE(v1);

	v2 = EXT_NORMALIZE(v2);

	double

		res = cross(v1, v2);

	if (!isAlmostZero(res, tolerance))

		return true;

	return false;

}

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

int detectStraightIntervals_(const TThickQuadratic *ttq,

							 ToonzExt::Intervals &intervals,

							 double tolerance)

{

	if (!ttq)

		return 0;

	TPointD

		v0 = ttq->getP1() - ttq->getP0(),

		v1 = ttq->getP2() - ttq->getP1();

	double

		v0_norm2 = norm(v0),

		v1_norm2 = norm(v1);

	if (v0_norm2 != 0.0)

		v0 = v0 * (1.0 / v0_norm2);

	if (v1_norm2 != 0.0)

		v1 = v1 * (1.0 / v1_norm2);

	double

		v0xv1 = v0 * v1;

	if (v0xv1 == 0.0 &&

		v0_norm2 == 0.0 &&

		v1_norm2 == 0.0) // null value with all zero

		return 0;

	if (isAlmostZero(cross(v0, v1) /*,tolerance*/)) {

		if (v0xv1 >= 0) {

			intervals.push_back(ToonzExt::Interval(0.0, 1.0));

			return 1;

		} else {

			double

				t = ttq->getT(ttq->getP1());

			intervals.push_back(ToonzExt::Interval(0.0, t));

			intervals.push_back(ToonzExt::Interval(t, 1.0));

			return 2;

		}

	}

#if 0

    // need to be analysed

    else

    {

      double

        pixelSize = 1.0;

#ifndef _DEBUG

      pixelSize = sqrt(tglGetPixelSize2());

#endif

      double

        step = computeStep(*ttq,

        pixelSize);

      //assert( step < 1.0 );

      if( step > 1.0 )

        return 0;

      double 

        t = 0.0;

      TPointD

        pnt ,

        p0 = ttq->getP0(),

        pn;

      ToonzExt::Interval

        last_interval(-1,-1),

        curr_interval;

      pnt = ttq->getPoint(step);

      v0 = pnt - p0;

      if( t+step < 1.0)

        pn = ttq->getPoint( step+step );

      else

        pn = ttq->getP2();

      v1 = pn - pnt;

      v0 = EXT_NORMALIZE(v0);

      v1 = EXT_NORMALIZE(v1);

      if( isAlmostZero( cross(v0,v1), tolerance ) )

      {

        assert( v0*v1 >0);

        last_interval.first = ttq->getT(p0);

        last_interval.second= ttq->getT(pn);

      }

      p0 = pn;

      for(t=2.0*step;

      t<1.0;

      t+=2.0*step)

      {

        pnt = ttq->getPoint(t);

        v0 = pnt - p0;

        if( t+step < 1.0)

          pn = ttq->getPoint( t+step );

        else

          pn = ttq->getP2();

        v1 = pn - pnt;

        v0 = EXT_NORMALIZE(v0);

        v1 = EXT_NORMALIZE(v1);

        if( isAlmostZero( cross(v0,v1), tolerance ) )

        {

          //assert( v0 * v1 > 0 );

          curr_interval.first  = ttq->getT(p0);

          curr_interval.second = ttq->getT(pn);

          if( curr_interval.first != last_interval.second ||

            v0 * v1 < 0)

          {

            intervals.push_back(last_interval);

            last_interval.first =

              last_interval.second = curr_interval.second;

          }

          else

          {

            last_interval.second = curr_interval.second;

          }

        }

        // for quadratic is not possible

        std::swap(p0,pn);

      }

      pn=ttq->getP2();

      v1 = pn - pnt;

      if( isAlmostZero( cross(v0,v1), tolerance ) )

      {

        if( v0 * v1 > 0 )

        {

          curr_interval.first  = ttq->getT(p0);

          curr_interval.second = ttq->getT(pn);

          if( curr_interval.first == last_interval.second )

            last_interval.second = curr_interval.second;

          intervals.push_back(last_interval);

        }

      }

      return intervals.size();

    }

#endif

	return 0;

}

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

/*

  int

  detectStraightIntervals_(const TThickQuadratic* ttq,

                           std::set<double>& values)</double>

  {

    if(!ttq ||

       isImproper( ttq ))

      return 0;

    TPointD

      v0 = ttq->getP1() - ttq->getP0(),

      v1 = ttq->getP2() - ttq->getP1();

    if( isAlmostZero( cross(v0,v1) ) )

    {

      values.insert(0.0);

      values.insert(1.0);

      if(v0 * v1 > 0 )

      {

        return values.size()-1;

      }

      else

      {

        double

          t = ttq->getT(ttq->getP1());

        values.insert( t );

        return values.size()-1;

      }

    }

    else

    {

      double

        pixelSize = 1.0;

#ifndef  _DEBUG

      pixelSize = sqrt(tglGetPixelSize2());

#endif

      double

        step = computeStep(*ttq,

                           pixelSize);

      double 

        t = 0.0;

      TPointD

        pnt ,

        p0 = ttq->getP0(),

        pn;

      for(t=step;

          t<1.0;

          t+=2.0*step)

      {

        pnt = ttq->getPoint(t);

        v0 = pnt - p0;

        if( t+step < 1.0)

          pn = ttq->getPoint( t+step );

        else

          pn = ttq->getP2();

        v1 = pn - pnt;

        if( isAlmostZero( cross(v0,v1) ) )

        {

          assert( v0 * v1 > 0 );

          values.insert(ttq->getT(p0));

          values.insert(ttq->getT(pn));

        }

        // for quadratic is not possible

        std::swap(p0,pn);

      }

      pn=ttq->getP2();

      v1 = pn - pnt;

      if( isAlmostZero( cross(v0,v1) ) )

      {

        assert( v0 * v1 > 0 );

        values.insert(ttq->getT(p0));

        values.insert(ttq->getT(pn));

      }

    }

    return values.size()-1;

  }

  */

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

bool mapValueInStroke(const TStroke *stroke,

					  const TThickQuadratic *ttq,

					  double value,

					  double &out)

{

	assert(ttq);

	if (!ttq ||

		!ToonzExt::isValid(stroke) ||

		!ToonzExt::isValid(value))

		return false;

	if (value == 1.0) {

		if (ttq->getPoint(1.0) ==

			stroke->getPoint(1.0)) {

			if (!stroke->isSelfLoop())

				out = 1.0;

			else

				out = 0.0;

			return true;

		}

	}

	out = stroke->getW(ttq->getPoint(value));

	return true;

}

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

bool mapIntervalInStroke(const TStroke *stroke,

						 const TThickQuadratic *ttq,

						 const ToonzExt::Interval &ttq_interval,

						 ToonzExt::Interval &stroke_interval)

{

	if (!ttq ||

		!ToonzExt::isValid(stroke))

		return false;

	if (ttq_interval.first > ttq_interval.second ||

		0.0 > ttq_interval.first ||

		ttq_interval.second > 1.0)

		return false;

	bool

		check = mapValueInStroke(stroke,

								 ttq,

								 ttq_interval.first,

								 stroke_interval.first);

	assert(check);

	if (!check)

		return false;

	check = mapValueInStroke(stroke,

							 ttq,

							 ttq_interval.second,

							 stroke_interval.second);

	assert(check);

	if (!check)

		return false;

	return true;

}

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

bool addQuadraticIntervalInStroke(const TStroke *stroke,

								  ToonzExt::Intervals &stroke_intervals,

								  const TThickQuadratic *ttq,

								  ToonzExt::Intervals &ttq_intervals)

{

	if (!ttq ||

		!ToonzExt::isValid(stroke))

		return false;

	const int

		size = ttq_intervals.size();

	if (size == 0)

		return false;

	int

		i = 0;

	for (i = 0;

		 i < size;

		 ++i) {

		const ToonzExt::Interval

			&tmp = ttq_intervals[i];

		if (tmp.first > tmp.second ||

			0.0 > tmp.first ||

			tmp.second > 1.0)

			return false;

	}

	for (i = 0;

		 i < size;

		 ++i) {

		const ToonzExt::Interval

			&ttq_interval = ttq_intervals[i];

		ToonzExt::Interval

			stroke_interval;

		// start to add interval in stroke

		if (mapIntervalInStroke(stroke,

								ttq,

								ttq_interval,

								stroke_interval)) {

			stroke_intervals.push_back(stroke_interval);

		}

	}

	return true;

}

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

bool addQuadraticSetInStroke(const TStroke *stroke,

							 ToonzExt::Intervals &stroke_intervals,

							 const TThickQuadratic *ttq,

							 const std::set<double> &ttq_set)</double>

{

	if (!ttq ||

		!ToonzExt::isValid(stroke))

		return false;

	const int

		size = ttq_set.size();

	if (size < 1)

		return false;

	std::set<double>::const_iterator</double>

		cit,

		cit_end = ttq_set.end();

	for (cit = ttq_set.begin();

		 cit != cit_end;

		 ++cit) {

		if (0.0 > *cit ||

			*cit > 1.0)

			return false;

	}

	cit = ttq_set.begin();

	std::set<double>::const_iterator</double>

		next_cit = cit;

	std::advance(next_cit, 1);

	for (;

		 next_cit != cit_end;

		 ++next_cit) {

		ToonzExt::Interval

			stroke_interval;

		bool

			check = mapValueInStroke(stroke,

									 ttq,

									 *cit,

									 stroke_interval.first);

		assert(check);

		if (!check)

			return false;

		check = mapValueInStroke(stroke,

								 ttq,

								 *next_cit,

								 stroke_interval.second);

		assert(check);

		if (!check)

			return false;

		assert(stroke_interval.first <= stroke_interval.second);

		if (stroke_interval.first > stroke_interval.second)

			return false;

		stroke_intervals.push_back(stroke_interval);

		cit = next_cit;

	}

	return true;

}

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

bool isThere(double value,

			 const ToonzExt::Intervals &intervals)

{

	ToonzExt::Intervals::const_iterator

		cit = intervals.begin(),

		cit_end = intervals.end();

	while (cit != cit_end) {

		if (cit->first == value ||

			cit->second == value)

			return true;

		++cit;

	}

	return false;

}

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

bool isThere(double value,

			 const std::set<double> &mySet)</double>

{

	std::set<double>::const_iterator</double>

		cit_end = mySet.end();

	if (cit_end == mySet.find(value))

		return false;

	return true;

}

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

bool isCorner(const ToonzExt::Intervals &values,

			  double w,

			  double tolerance)

{

	ToonzExt::Interval

		prev = values[0],

		curr = prev;

	// first point

	if (areAlmostEqual(prev.first,

					   w,

					   tolerance))

		return true;

	const int

		size = values.size();

	for (int i = 1;

		 i < size;

		 ++i) {

		curr = values[i];

		if (areAlmostEqual(prev.second,

						   curr.first) &&

			areAlmostEqual(w,

						   curr.first,

						   tolerance))

			return true;

		prev = curr;

	}

	// last point

	if (areAlmostEqual(curr.second,

					   w,

					   tolerance))

		return true;

	return false;

}

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

} // end of unnamed namespace

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

DEBUG_EXPORT bool

isThereACornerMinusThan(double minCos,

						double minSin,

						const TThickQuadratic *quad1,

						const TThickQuadratic *quad2)

{

	if (!quad1 ||

		!quad2 ||

		!ToonzExt::isValid(fabs(minCos)) ||

		!ToonzExt::isValid(fabs(minSin)))

		return false;

	TPointD

		//speed1,

		//speed2,

		tan1,

		tan2;

	//speed1 = quad1->getSpeed(1);

	//speed2 = -quad2->getSpeed(0);

	tan1 = quad1->getSpeed(1);

	tan2 = -quad2->getSpeed(0);

	if (norm2(tan1) == 0.0 ||

		norm2(tan2) == 0.0)

		return false;

	tan1 = normalize(tan1);

	tan2 = normalize(tan2);

	// move cos value to compare just positive values

	minCos += 1.0;

	double

		cosVal = 1.0 + (tan1 * tan2); //, sinVal = fabs(cross(tan1,tan2));

	assert(minCos >= 0.0);

	if (cosVal >= minCos)

		return true;

	return false;

}

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

DEBUG_EXPORT double

degree2cos(int degree)

{

	int tmp = degree < 0 ? -degree : degree;

	tmp %= 360;

	degree = degree < 0 ? 360 - tmp : degree;

	if (degree == 0)

		return 1.0;

	if (degree == 180)

		return -1.0;

	if (degree == 90 ||

		degree == 270)

		return 0.0;

	return cos(degree * TConsts::pi_180);

}

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

DEBUG_EXPORT double

degree2sin(int degree)

{

	return degree2cos(degree - 90);

}

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

DVAPI bool

ToonzExt::findNearestSpireCorners(const TStroke *stroke,

								  double w,

								  ToonzExt::Interval &out,

								  int cornerSize,

								  const ToonzExt::Intervals *const cl,

								  double tolerance)

{

	if (!ToonzExt::isValid(stroke) ||

		!ToonzExt::isValid(w))

		return false;

	const ToonzExt::Intervals

		*values = cl;

	ToonzExt::Intervals

		tmpValues;

	if (!cl) {

		cornerSize = normalizeAngle(cornerSize);

		if (!ToonzExt::detectSpireIntervals(stroke,

											tmpValues,

											cornerSize))

			return false;

		values = &tmpValues;

	}

	if (!values ||

		values->empty()) {

		return false;

	}

	return findNearestCorners(stroke,

							  w,

							  out,

							  *values,

							  tolerance);

}

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

DVAPI bool

ToonzExt::isASpireCorner(const TStroke *s,

						 double w,

						 int cornerSize,

						 const ToonzExt::Intervals *const cl,

						 double tolerance)

{

	if (!ToonzExt::isValid(s) ||

		!ToonzExt::isValid(w))

		return false;

	ToonzExt::Intervals

		tmpValues;

	const ToonzExt::Intervals

		*values = cl;

	if (!cl) {

		if (!ToonzExt::detectSpireIntervals(s,

											tmpValues,

											cornerSize))

			return false;

		values = &tmpValues;

	}

	if (!values ||

		values->empty()) {

		return false;

	}

	return isCorner(*values,

					w,

					tolerance);

}

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

DVAPI bool

ToonzExt::detectStraightIntervals(const TStroke *stroke,

								  ToonzExt::Intervals &intervals,

								  double tolerance)

{

	if (!ToonzExt::isValid(stroke))

		return false;

	assert(tolerance > 0.0 &&

		   tolerance < 1.0 &&

		   "Strange tolerance are you sure???");

	intervals.clear();

	// first step:

	//  store information about chunk and straight interval

	typedef std::pair<const *,="" toonzext::intervals="" tthickquadratic=""> ChunkStraights;</const>

	std::map<int, chunkstraights=""></int,>

		arrayOfChunkIntervals;

	int

		chunkCount = stroke->getChunkCount();

	int

		counter = 0;

	for (int i = 0;

		 i < chunkCount;

		 ++i) {

		ToonzExt::Intervals

			values;

		const TThickQuadratic *

			chunk = stroke->getChunk(i);

		if (chunk->getLength() == 0.0)

			continue;

		int

			howMany = detectStraightIntervals_(chunk,

											   values,

											   tolerance);