/**------------------------------------------------------------------------
 * @file
 *
 * Copyright 2001 by the University of Toronto (UT).
 *
 *                       All Rights Reserved
 * 
 * Permission to copy and modify this software and its documentation 
 * only for internal use in your organization is hereby granted, 
 * provided that this notice is retained thereon and on all copies.  
 * UT makes no representations as to the suitability and operability 
 * of this software for any purpose.  It is provided "as is" without 
 * express or implied warranty.
 *
 * UT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
 * SHALL UT BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA
 * OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 *
 * No other rights, including for example, the right to redistribute 
 * this software and its documentation or the right to prepare 
 * derivative works, are granted unless specifically provided in a 
 * separate license agreement.
 *
 * Author: Diego Macrini
 * 
 * $Log: ApproxPoly.h,v $
 *
 *-----------------------------------------------------------------------*/

#ifndef __APROX_POLY_H__
#define __APROX_POLY_H__

#include <math.h>
#include "SmartArray.h"

namespace dml {

struct POINT {
	double x, y;
	POINT() {x = -1; y = -1; }
	POINT(const double& xx, const double& yy)    { x = xx; y = yy; }
	void Set(const double& xx, const double& yy) { x = xx; y = yy; }

	friend std::ostream& operator<<(std::ostream& os, const POINT& p)
	{
		//os << "(x:" << p.x << ", y:" << p.y << ")";
		return os << p.x << ", " << p.y;
	}

	POINT& operator=(const POINT& rhs)
	{
		x = rhs.x;
		y = rhs.y;

		return *this;
	}
	
	bool operator==(const POINT& rhs) const { return x == rhs.x && y == rhs.y; }
	bool operator!=(const POINT& rhs) const { return !operator==(rhs); }
	
	double L2() const { return sqrt(x * x + y * y); }
	double L2(const POINT& p1) const
	{
		double dx = x - p1.x;
		double dy = y - p1.y;
		return sqrt(dx * dx + dy * dy);
	}
	
	double Dot(const POINT& b) const { return x * b.x + y * b.y; }
};

typedef SmartArray<POINT> POINTS;

struct SEGMENT
{
    double m;	//<! slope
    double b;	//<! y-intercept
    POINT p0;	//<! point 0 (eg, an endpoint of a line or a ctrl point of a curve)
    POINT p1;	//<! point 1 (eg, an endpoint of a line or a ctrl point of a curve)
 		
    SEGMENT() { m = 0; b = 0; }
    
	/*!
		THIS FUNCTION CANNOT BE VIRTUAL. USE A VIRTUAL SET AT THE LEVEL OF APPROXPOLY
	*/
    SEGMENT& Set(const SEGMENT& s)
    {
    	m = s.m;
    	b = s.b;
    	p0 = s.p0;
    	p1 = s.p1;
	
	return *this;
    }
    
    SEGMENT& operator=(const SEGMENT& rhs)
    {
    	return Set(rhs);
    }
    
    /*void Set(const double& slope, const double& y_intercept,
    	const POINT& startPt, const POINT& endPt)
    {
    	m = slope;
    	b = y_intercept;
    	p0 = startPt;
    	p1 = endPt;
    }*/

    double GetLen() const { return p0.L2(p1); }
    double Y(const double& x) const { return m * x + b; }
    double Y0() const { return Y(p0.x); }
    double Y1() const { return Y(p1.x); }
	
	POINT GetP0() const { return POINT(p0.x, Y(p0.x)); }
	POINT GetP1() const { return POINT(p1.x, Y(p1.x)); }

    std::istream& Read(std::istream& is)
    {
	is.read((char*)this, sizeof(*this));
	return is;
    }

    std::ostream& Write(std::ostream& os) const
    {
	os.write((char*)this, sizeof(*this));
	return os;
    }
	
	std::ostream& Print(std::ostream& os) const
    {
    	return os << "[" << p0 << "," << p1 << "] "
    		<< m << " x + " << b;
    }

	friend std::ostream& operator<<(std::ostream& os, const SEGMENT& s) 	{ return s.Print(os); }
	//friend std::istream& operator>>(std::istream& is, SEGMENT& s)			{ return s.Read(is); }
};

typedef SmartArray<SEGMENT> SEGMENTS;

class MEMDATA
{
	int ptIdx;
	double dMinError;
	bool bEmpty;
	
public:	
	MEMDATA() { bEmpty = true; ptIdx = -1; dMinError = 0; }
	bool IsEmpty() const { return bEmpty; }
	int GetIdx() const { return ptIdx; }
	double GetMinError() const { return dMinError; }
	
	void Set(const double& e, int i)
	{
		ASSERT(i >= 0);
		bEmpty = false;
		ptIdx = i;
		dMinError = e;
	}
	double operator+(const MEMDATA& rhs) const
	{
		ASSERT(!bEmpty && !rhs.bEmpty);
		
		return dMinError + rhs.dMinError;
	}
	
	friend std::ostream& operator<<(std::ostream& os, const MEMDATA& d)
	{
		return os << "(" << d.dMinError << ", " << d.ptIdx << ")";
	}
};

typedef SmartArray< SmartMatrix<MEMDATA> > MEMORY;

struct SLOPE
{
	double m;

	bool bRelSmall;
	
	friend std::ostream& operator<<(std::ostream& os, const SLOPE& s)
	{
		return os << "(" << s.m << ", " << s.bRelSmall << ")";
	}
};

typedef SmartArray<SLOPE> SlopesArray;

class ApproxPoly
{
public:	
	struct KNOT
	{
		int nIndex;
		SEGMENT seg;
		double dError;
		int dir;

		KNOT() { nIndex = 0; }
		KNOT(int idx, double slope) { Set(idx, slope); }
		KNOT(int idx, const SEGMENT& s, const double& err) { Set(idx, s, err); }
		void Set(int idx, const SEGMENT& s, const double& err) { nIndex = idx; seg = s; dError = err; }
		void Set(int idx, double slope) { nIndex = idx; seg.m = slope; }
		
		friend std::ostream& operator<<(std::ostream& os, const KNOT& p)
		{
			return os << "Knot at " << p.nIndex << ", line segment " << p.seg
				<< ", fit error: " << p.dError;
		}
	};

	double m_dMinError, m_dMinSlope, m_dMaxSegments, m_dMaxYDiff;
	bool m_bDbgMode;
	double m_ymin, m_ymax;
	
	SmartArray<KNOT> m_knots;
	POINTS m_points;
	SmartMatrix<SEGMENT> m_segments;
	MEMORY m_minerrors;

public:
	ApproxPoly(double dMinError, double dMinSlope, double dMaxSegments, double dMaxYDiff);
	ApproxPoly(const ApproxPoly& poly);
	virtual ~ApproxPoly();
	
	virtual double LeastSquares(const POINT* vertices, int n, SEGMENT& s);
	virtual double LeastSquares(const POINT* vertices, int fromIdx, int toIdx, SEGMENT& s);
	virtual void Fit(const POINTS vertices);
	virtual double FindMaxYDiff(int seg_num, int s, int e) const;
	
	/*!
		@brief Returns a pointer to a SEGMENT. Must call delete to free the allocated memory.
		
		Derived classes must overload this function to return a different set of parameters 
		for a curve segment.
	*/
	virtual SEGMENT* NewSegment() { return new SEGMENT; }

	virtual bool IsRelativeSmall(double x0, double xn, double m, double b);	
	
	void Test();
	
	MEMDATA Min(int seg_num, int s, int e);
	int AddKnots(int seg_num, int s, int e);
	void PlotKnots(int seg_num);
	void SetDbgMode(bool bOn) { m_bDbgMode = bOn; }
	void SetYMinMax();
	double CompAcuteAngle(int seg1, int seg2) const;
	double CompObtuseAngle(int seg1, int seg2) const;
	
private:
	void FindMaxYDiff(int seg_num, int s, int e, const SEGMENT*& pFirstSeg, const SEGMENT*& pLastSeg, double& dMaxYDiff) const;
};

typedef SmartMatrix< SmartMatrix<MEMDATA> > MEMORY2;

struct MINMAX
{
	int min, max;
	MINMAX(int mi, int ma) { min = mi; max = ma; }
};

class ModelFit
{
	MEMORY2 m_minerrors;
	SEGMENTS m_segments;
	POINTS m_points;
	SmartArray<double> m_minLineLen;
	SmartArray<double> m_minDataLen;
	double m_minLenCoeff, m_totalMinLineLen, m_totalMaxLineLen, m_totalDataLen;
	
public:	
	ModelFit(double minLenCoeff) { m_minLenCoeff = minLenCoeff; }
	
	double Fit(const POINTS& vertices, const SEGMENTS& segs);
	MEMDATA Min(int ls, int le, int ps, int pe);
	void UpdateSegments(int ls, int le, int ps, int pe);
	double CompLSError(int ls, int ps, int pe) const;
	MINMAX GetMinMaxLen(int ls, int li, int le, int ps, int pe) const;
	void GetSegmentError(int s, double* error, double* scaleFactor) const;
	void Plot(std::ostream& os, const POINTS& points2, const SEGMENTS& segments2) const;
};

} //namespace dml

#endif //__APROX_POLY_H__
