/*
								+----------------------------------+
								|                                  |
								|  *** Common spline template ***  |
								|                                  |
								|   Copyright © -tHE SWINe- 2008   |
								|                                  |
								|             Spline.h             |
								|                                  |
								+----------------------------------+
*/

#pragma once
#ifndef __GENERIC_SPLINE_TEMPLATE_INCLUDED
#define __GENERIC_SPLINE_TEMPLATE_INCLUDED

/**
 *	@file dev/Spline.h
 *	@date 2008
 *	@author -tHE SWINe-
 *	@brief Common spline template
 *
 *	@date 2009-01-15
 *
 *	fixed error in CSpline::ErasePoints() where cached lengths
 *	were erased instead of the points themselves
 *
 *	@date 2009-05-23
 *
 *	removed all instances of std::vector::reserve and replaced them by stl_ut::Reserve_*
 *
 *	@date 2009-10-20
 *
 *	fixed some warnings when compiling under VC 2005, implemented "Security
 *	Enhancements in the CRT" for VC 2008. compare against MyProjects_2009-10-19_
 *
 *	@date 2012-06-19
 *
 *	Moved multiple inclusion guard before file documentation comment.
 *
 */

#include "../NewFix.h"
#include "../CallStack.h"
#include "../StlUtils.h"

#include <vector>
#include "Numerical.h"

/*
 *	template <class CPointClass>
 *	class CSpline
 *		- simple generic spline template
 */
template <class CPointClass>
class CSpline {
protected:
	/*
	 *	class CSpline::CTangentMag
	 *		- tangent magnitude adaptor for integrator (gives arc length)
	 */
	class CTangentMag {
	protected:
		const CSpline *m_p_spline;
		int m_n_arc;
	public:
		inline CTangentMag(const CSpline *p_spline, int n_arc)
			:m_p_spline(p_spline), m_n_arc(n_arc)
		{}

		inline float operator ()(float f_t) const
		{
			return m_p_spline->v_Arc_Derivative(f_t, m_n_arc).f_Length();
		}
	};

	std::vector<CPointClass> m_point_list;
	mutable float m_f_length, m_f_length_precission; // total spline length, max length error
	mutable std::vector<float> m_arc_length_list; // segment lengths (erased on change)

public:
	/*
	 *	CSpline::CSpline()
	 *		- default constructor
	 *		- creates empty spline; points must be inserted before calling v_* functions
	 */
	CSpline()
	{
		InvalidateCachedLengths();
	}

	/*
	 *	CSpline::CSpline(const std::vector<CPointClass> &r_point_list)
	 *		- constructor
	 *		- r_point_list is list of curve points, it's duplicated here
	 *		  (it is recommended to check if number of points in curve is
	 *		  equal to number of points in r_point_list to see wheter
	 *		  there was enough memory)
	 */
	CSpline(const std::vector<CPointClass> &r_point_list)
	{
		if(stl_ut::Reserve_N(m_point_list, r_point_list.size()))
			m_point_list.insert(m_point_list.end(), r_point_list.begin(), r_point_list.end());
		// copy points

		InvalidateCachedLengths();
	}

	/*
	 *	inline int CSpline::n_Point_Num() const
	 *		- returns number of spline points
	 */
	inline int n_Point_Num() const
	{
		return m_point_list.size();
	}

	/*
	 *	inline const CPointClass &CSpline::t_Point(int n_index) const
	 *		- returns const reference to point with zero-based index n_index
	 */
	inline const CPointClass &t_Point(int n_index) const
	{
		return m_point_list[n_index];
	}

	/*
	 *	inline CPointClass &CSpline::r_Point(int n_index)
	 *		- returns reference to point with zero-based index n_index
	 *		- note this resets cached spline segment lengths
	 */
	inline CPointClass &r_Point(int n_index)
	{
		InvalidateCachedLengths();
		// caller is about to change point data - lengths will change

		return m_point_list[n_index];
	}

	/*
	 *	inline void CSpline::ErasePoints(int n_begin = 0, int n_end = -1)
	 *		- erases points with zero-based indices in range [n_begin, n_end)
	 *		- note if n_end is negative number, it is replaced with number of points
	 */
	inline void ErasePoints(int n_begin = 0, int n_end = -1)
	{
		if(n_end >= 0) {
			m_point_list.erase(m_point_list.begin() + n_begin,
				m_point_list.begin() + n_end);
		} else {
			m_point_list.erase(m_point_list.begin() + n_begin,
				m_point_list.end());
		}
		// erase points

		InvalidateCachedLengths();
		// lengths just changed
	}

	/*
	 *	bool CSpline::Insert(int n_insert_before, const CPointClass *p_point, int n_count)
	 *		- inserts n_count points from array p_point and places them before spline
	 *		  point with zero-based index n_insert_before
	 *		- returns true on success, false on failure
	 */
	bool Insert(int n_insert_before, const CPointClass *p_point, int n_count)
	{
		if(!stl_ut::Reserve_NMore(m_point_list, n_count))
			return false;
		// make sure there's enough space in the list

		m_point_list.insert(m_point_list.begin() + n_insert_before, p_point, p_point + n_count);
		// add new points

		InvalidateCachedLengths();
		// lengths just changed

		return true;
	}

	/*
	 *	bool CSpline::PushBack(const CPointClass *p_point, int n_count)
	 *		- inserts n_count points from array p_point and
	 *		  places them on the end of spline point list
	 *		- returns true on success, false on failure
	 */
	bool PushBack(const CPointClass *p_point, int n_count)
	{
		if(!stl_ut::Reserve_NMore(m_point_list, n_count))
			return false;
		// make sure there's enough space in the list

		m_point_list.insert(m_point_list.end(), p_point, p_point + n_count);
		// add new points

		InvalidateCachedLengths();
		// lengths just changed

		return true;
	}

	/*
	 *	inline bool CSpline::Insert(int n_insert_before, CPointClass t_point)
	 *		- inserts a single point t_point before point with zero-based index n_insert_before
	 *		- returns true on success, false on failure
	 */
	inline bool Insert(int n_insert_before, CPointClass t_point)
	{
		return InsertPoints(n_insert_before, &t_point, 1);
	}

	/*
	 *	inline bool CSpline::PushBack(CPointClass t_point)
	 *		- inserts a single point t_point to the end of spline point list
	 *		- returns true on success, false on failure
	 */
	inline bool PushBack(CPointClass t_point) // t_odo - document this, create subdivision functions minimal, cheap length, precise length, curvature
	{
		return PushBack(&t_point, 1);
	}

	/*
	 *	virtual int CSpline::n_Arc_Num() const = 0
	 *		- returns number of spline arcs
	 *		- note this function is supposed to be implemented by final spline class
	 */
	virtual int n_Arc_Num() const = 0;

	/*
	 *	float CSpline::f_Length(float f_max_error = 1e-3f) const
	 *		- returns curve length with maximal relative error f_max_error
	 */
	float f_Length(float f_max_error = 1e-3f) const
	{
		if(m_f_length_precission < f_max_error)
			return m_f_length;

		int n_arc_num;
		if((n_arc_num = n_Arc_Num()) <= 0)
			return 0;

		f_max_error /= n_arc_num;
		// error multiplies with number of arcs

		m_arc_length_list.clear();
		if(!stl_ut::Reserve_N(m_arc_length_list, n_arc_num))
			return -1;
		// reserve space in arc length list

		float f_length = 0;
		for(int i = 0, n = n_arc_num; i < n; ++ i) {
			float f_arc_length = f_Arc_Length(i, f_max_error);
			m_arc_length_list.push_back(f_arc_length);
			f_length += f_arc_length;
		}
		// sum up arc lengths

		m_f_length_precission = f_max_error;
		m_f_length = f_length;
		// cache results

		return f_length;
	}

	/*
	 *	float CSpline::f_Arc_Length(int n_arc, float f_max_error = 1e-3f) const
	 *		- return length of arc n_arc with maximal relative error f_max_error
	 */
	float f_Arc_Length(int n_arc, float f_max_error = 1e-3f) const
	{
		_ASSERTE(n_arc >= 0);
		if(m_arc_length_list.size() > unsigned(n_arc) &&
		   m_f_length_precission < f_max_error)
			return m_arc_length_list[n_arc];
		// use cached arc length

		return f_Integrate_s(CTangentMag(this, n_arc), 0, 1, f_max_error);
		// can't cache arc length here, because of list insertion policy
	}

	/*
	 *	int CSpline::n_Arc(float f_t, float &r_f_local_t, float f_max_error = 1e-3f) const
	 *		- returns index of arc at position f_t along the curve
	 *		- r_f_local_t is local t for that particular arc
	 *		- f_max_error is maximal relative length error
	 *		- both f_t and r_f_local_t are in range [0, 1]
	 */
	int n_Arc(float f_t, float &r_f_local_t, float f_max_error = 1e-3f) const
	{
		int n_arc_num;
		if((n_arc_num = n_Arc_Num()) <= 0)
			return -1;

		if(f_t <= 0) {
			r_f_local_t = 0;
			return 0;
		} else if(f_t >= 1) {
			r_f_local_t = 1;
			return n_arc_num - 1;
		}
		// clamp t to range [0, 1]

		float f_dist = f_t * f_Length(f_max_error);
		for(int i = 0, n = n_arc_num; i < n; ++ i) {
			float f_arc_len = f_Arc_Length(i, f_max_error);
			if(f_dist < f_arc_len) {
				r_f_local_t = f_dist / f_arc_len;
				return i;
			}
			f_dist -= f_arc_len;
		}
		// find arc by curve length

		r_f_local_t = 1;
		return n_arc_num - 1;
		// last arc was hit
	}

	/*
	 *	virtual CPointClass CSpline::v_Arc_Position(float f_t, int n_arc) const = 0
	 *		- returns point at position f_t along curve arc n_arc
	 *		- note this function is supposed to be implemented by final spline class
	 */
	virtual CPointClass v_Arc_Position(float f_t, int n_arc) const = 0;

	/*
	 *	virtual CPointClass CSpline::v_Arc_Derivative(float f_t, int n_arc) const = 0
	 *		- returns tangent at position f_t along curve arc n_arc
	 *		- note this function is supposed to be implemented by final spline class
	 */
	virtual CPointClass v_Arc_Derivative(float f_t, int n_arc) const = 0;

	/*
	 *	CPointClass CSpline::v_Position(float f_t) const
	 *		- returns point at position f_t along the curve
	 *		- note this doesn't use any kind or approximation of constant
	 *		  speed subdivision, each spline segment is considered unit length
	 */
	CPointClass v_Position(float f_t) const
	{
		int n_arc_num = n_Arc_Num();
		int n_arc = (f_t > 0)? ((f_t < 1)? int(f_t * n_arc_num) : n_arc_num - 1) : 0;
		float f_arc_t = f_t * n_arc_num - n_arc;
		return v_Arc_Position(f_arc_t, n_arc);
	}

	/*
	 *	CPointClass CSpline::v_Derivative(float f_t) const
	 *		- returns tangent at position f_t along the curve
	 *		- note this doesn't use any kind or approximation of constant
	 *		  speed subdivision, each spline segment is considered unit length
	 */
	CPointClass v_Derivative(float f_t) const
	{
		int n_arc_num = n_Arc_Num();
		int n_arc = (f_t > 0)? ((f_t < 1)? int(f_t * n_arc_num) : n_arc_num - 1) : 0;
		float f_arc_t = f_t * n_arc_num - n_arc;
		return v_Arc_Derivative(f_arc_t, n_arc);
	}

	/*
	 *	CPointClass CSpline::v_Position_SCS(float f_t, float f_max_error = 1e-3f) const
	 *		- returns point at position f_t along the curve (semi-constant speed subdivision)
	 *		- f_max_error is maximal relative length error
	 *		- note semi-constant speed means arc lengths are used to determine spline arc
	 *		  on position f_t, but arc itself is subdivided with constant time
	 */
	CPointClass v_Position_SCS(float f_t, float f_max_error = 1e-3f) const
	{
		float f_arc_t;
		int n_arc = n_Arc(f_t, f_arc_t, f_max_error);
		return v_Arc_Position(f_arc_t, n_arc);
	}

	/*
	 *	CPointClass CSpline::v_Derivative_SCS(float f_t, float f_max_error = 1e-3f) const
	 *		- returns tangent at position f_t along the curve (semi-constant speed subdivision)
	 *		- f_max_error is maximal relative length error
	 *		- note semi-constant speed means arc lengths are used to determine spline arc
	 *		  on position f_t, but arc itself is subdivided with constant time
	 */
	CPointClass v_Derivative_SCS(float f_t, float f_max_error = 1e-3f) const
	{
		float f_arc_t;
		int n_arc = n_Arc(f_t, f_arc_t, f_max_error);
		return v_Arc_Derivative(f_arc_t, n_arc);
	}

protected:
	inline void InvalidateCachedLengths() const
	{
		m_f_length_precission = 3.402823466e38f;
		m_arc_length_list.clear();
		// invalidate cached lengths
	}
};

#endif // __GENERIC_SPLINE_TEMPLATE_INCLUDED
