/**
 * This file describes the template class for 2D curve geometry.
 * Class described here is IBaseCurve.
 *
 *   IBM Open Class Library
 *   (C) Copyright International Business Machines Corporation,  1997
 *   Licensed Material - Program-Property of IBM - All Rights Reserved.
 *
 */

// Revision: 64 1.22.1.6 source/albert/graph2d/ibcurve.hpp, 2d, ioc.v400, 980918 

#ifndef _IBCURVE_
#define _IBCURVE_

#include <igbase2d.hpp>
#include <irawarr.hpp>
#include <ipt2darr.hpp>
#include <iprimtyp.hpp>

#if __IBMCPP__ >= 400
#pragma namemangling(compat)
#endif

class IGEllipse2D;
class IGLine2D;
class IGPolyline2D;
class IGPolygon2D;
class IGrafMatrix;

#ifndef HIDE_TEMPLATE_DEFINITIONS
// Assumption is made that(for now) user's don't want to instantiate
// the curve classes, because they're huge.
#define MAKE_TBaseCurve_DEFINITIONS_VISIBLE
#endif

#pragma enum(4)
#pragma pack(push,4)

typedef GParametric BasisMatrix[16]; // Internal type for matrix cubic spline

/**
 * IBaseCurve is the base templatized class for IGCurve2D.
 */
template <class RPointType, class PointType>
class IBaseCurve {

	public :
        IDataStream&    operator>>= (IDataStream&) const;
        IDataStream&    operator<<= (IDataStream&);
		void writeToStream( IDataStream& toWhere ) const;
		void readFromStream( IDataStream& toWhere );
  public:
	/** Defines types of end point conditions. */
     enum EndConditions {
    	kPinned,       // Knot vector for curve interpolating endpoints
        kFloating,     // Uniform knot vector(no endpoint interpolation)
        kBezier};      // Piecewise Bezier curve

	/** Defines types of discontinuity. */
     enum EDiscontinuity {
    	kBreak = 0,    // Break in curve - c0 discontinuity
        kKink = 1,     // "Kink" - c1(tangent) discontinuity
        kJerk = 2 };   // "Jerk" - c2(accelleration) discon.
                       // [Note - above term from automotive
                       // industry - see Blossoming book
                       // by Ramshaw]

	/**
	 */
    IBaseCurve();

	/**
 	 * Note: IRawArray does not check whether allocation is successful. Before construction,
	 * one should check if there is enough memory and use a reasonable size.
	 */
    IBaseCurve( unsigned long order, unsigned long numberPoints );

	/**
 	 * Note: IRawArray does not check whether allocation is successful. Before construction,
	 * one should check if there is enough memory and use a reasonable size.
	 */
    IBaseCurve( unsigned long order, unsigned long numberPoints,
               const IRawArray<GParametric>& knots );

	/**
 	 * Note: IRawArray does not check whether allocation is successful. Before construction,
	 * one should check if there is enough memory and use a reasonable size.
	 */
    IBaseCurve( unsigned long order, const IRawArray<RPointType>& points );

	/**
 	 * Note: IRawArray does not check whether allocation is successful. Before construction,
	 * one should check if there is enough memory and use a reasonable size.
	 */
    IBaseCurve( unsigned long order,
                const IRawArray<RPointType>& points,
                const IRawArray<GParametric>& knots );

	/**
	 */
    IBaseCurve( const PointType& p0,
                const PointType& p1,
                const PointType& p2 );

	/**
	 */
    IBaseCurve( const PointType& p0,
                const PointType& p1,
                const PointType& p2,
                const PointType& p3 );

	/**
 	 * Note: IRawArray does not check whether allocation is successful. Before construction,
	 * one should check if there is enough memory and use a reasonable size.
	 */
    IBaseCurve( const IBaseCurve<RPointType, PointType>& curve );

    virtual ~IBaseCurve();

	/**
	 * The parameter u has a range defined by the knot vector.  The valid limits on this range are:
	 * IBaseCurve::minParameter() >= u > IBaseCurve::maxParameter(). Evaluation outside these limits
	 * falls off towards zero as you get further outside of the range.  For pinned knot vectors(the
	 * usual case), there is a c0 discontinuity between the curve within the valid range and zero
	 * outside of it.  Since the W component also falls to zero, the result becomes a NaN when
	 * the W's get divided out.
	 */
    PointType evaluate( GParametric u ) const;

	/**
	 * Returns the point on the IBasicCurve at the specified parametric value without dividing out W.
	 */
    RPointType evaluateW( GParametric u ) const;

	/**
	 */
    PointType   evaluate( GParametric u,
                          PointType& tangent ) const;

	/**
	 */
    PointType   evaluate( GParametric u,
                          PointType& tangent,
                          PointType& deriv2 ) const;

    //2D All of the above, along with the gaussian curvature.
//2D    IGPoint2D evaluate(
//          GParametric u,
//          IGPoint2D& tangent,
//          IGPoint2D& deriv2,
//          GCoordinate& curvature) const;

	/**
	 * Note:  the current implementation is likely to have accuracy problems for curves with order
	 * higher than 5.
	 */
    GCoordinate     arcLength( GParametric uFrom,
                               GParametric uTo ) const;
	/**
	 */
    GCoordinate     arcLength() const;

	/**
	 * Approximates the parameter, given a particular arc length along the curve.
	 * Approximates the parameter, given a particular arc length along the curve.
	 * Tolerance is used for the accuracy of the root finder, leave it alone for most "screen sized" data.
	 */
    GParametric     approximateParameterFromArcLength(
                                GCoordinate length,
                                GCoordinate tolerance = 1.0e-5 ) const;

#ifdef NO_REPARAM_YET
    // PULLED FROM RELEASE - The interface and implementation are too
    // questionable and the benifit is too small to risk maintaining it
    // at this time

    // Generate a reparameterization curve that translates arc length
    // to parameter.  The curve may then be evaluated by arc length by
    // something like:
    //
    //          curve.evaluate(reparam.evaluate( lengthValue).fY );
    //
    // The tolerance default is a useful value for "screen-sized" curves,
    // those on much different scales may need adjustment.  MaxPts is the
    // total number of control points allowed in the reparameterization curve,
    // the default is 20 * the number of control points in the original curve.
    // Because the approximation is adaptive, it will generally use *much* less
    // than the total number allowed, so be generous(small numbers can cause
    // the approximation to be too conservative and inaccurate).
    //

	/**
	 * Generate a reparameterization curve that translates arc length to parameter.
	 */
    void            approximateArcLengthReparameterizationCurve(
                                                     IGCurve2D& reparamCurve,
                                                     unsigned long maxPts = 0,
                                                     GCoordinate tolerance = 0.01 );
#endif

    /**
     * Returns true if the curve or loop has no points or is an empty loop.
	 */
    bool            isEmpty() const;

    /**
     * Returns the order of this IBaseCurve.
	 */
    unsigned long   order() const;

    /**
     * Returns the number of control points in this IBaseCurve.
	 */
    unsigned long   numberOfPoints() const;

    /**
     * Returns the control point specified by the index.
	 */
    RPointType      point( unsigned long i ) const;

    /**
     * Returns, in its argument, the complete array of control points.
	 */
    void            points( IRawArray<RPointType>& pts ) const;

//2D    void controlPolyline(IGPolyline2D& polyline) const;

    /**
     * Returns the parametric value that has been associated with the curve's beginning point.
	 */
    GParametric     minParameter() const;

    /**
     * Returns the parametric value that has been associated with the curve's end point.
	 */
    GParametric     maxParameter() const;

    /**
     * Returns the number of knots in the knot vector. This is equal to the number of control points plus the order of the curve.
	 */
    unsigned long   numberOfKnots() const;

    /**
     * Gets the parametric value of the specified knot.
	 */
    GParametric knot( unsigned long i ) const;

    /**
     * Returns, by reference in its argument, the knot vector of this curve.
	 */
    void knots( IRawArray<GParametric>& knots ) const;

    /**
     * Determines whether this curve passes through the first and last control points (that is, whether the knot vector is pinned).
	 */
    bool    isPinned() const;

    /**
     * Determines whether this curve defines a piecewise Bezier curve.
	 */
    bool isBezier() const;

    /**
     * Returns the parametric value of the closest point on the curve to the center of the rectangle.
     * Returns the parametric value of the closest point on the curve to the center of the rectangle.
     * WARNING:  The current implementation works by discretizing the curve in 72 DPI device
     * space - beware of this fact if you call nearestParametric with gigantic or microscopic
     * coordinates.  In the future, there will be a resolution-independent implementation.
	 */
    GParametric nearestParametric( const PointType& test ) const;

	/**
	 * Returns the knot vector index of the next discontinuity following the specified knot.
	 * Returns the knot vector index of the next discontinuity following the specified knot.
	 * nextDiscontinuity returns the index of the first knot of a multiple knot sequence.  Call
	 * knot on this value to find the parameter of the curve at the discontinuity.  Note that for
	 * a c0 break in the curve, the value returned by knot(nextDiscontinuity(...)) is the start
	 * of the section of the curve after the break.  Subtracting any amount from that jumps to
	 * the section before the break).
	 * To find the control point associated with a C1 discontinuity, subtract one from the value
	 * returned by nextDiscontinuity. For a c0 discontinuity, nextDiscontinuity(...)-1 is the
	 * point before the break, and the following point is after the break.
	 * To skip from one discontinuity to the next, you can pass the value returned from the last
	 * call as the "startIndex" parameter.
	 * If there are no more discontinuities in the curve, numberKnots()-1 is returned(the last
	 * valid knot).
	 * Assertions fail if the discontinuity parameter is not 0 <= discon < order.
	 */
    unsigned long nextDiscontinuity( unsigned long startIndex,
                                        unsigned long discontinuity = 0 ) const;
	/**
	 * Returns the bounds of the curve's control points.
	 * Due to  the convex hull property, the curve is always contained within these bounds.
	 * Note this bounds is not cached, but recomputed with every call.
	 */
//2D    IGRect2D bounds() const;

	/**
	 * Checks if the curve intersects the rectangle.
	 * NOTE:  This is currently implemented by discretizing the curve in something resembling
	 * screen space.  In the future, the implementation will be changed to a truly device
	 * independant one.
	 */
//2D    bool    intersects(const IGRect2D& g) const;

	/**
	 * Returns the section of the curve between the two specified parametric values.
	 * Returns the section of the curve between the two specified parametric values.
	 * Note if "to" < "from", then the direction of the subsection is reversed.
	 */
    void        sectionOfCurve(
                    GParametric from,
                    GParametric to,
                    IBaseCurve<RPointType, PointType>& section ) const;

	/**
	 * Appends the given curve at the end of the current curve.
	 * Appends the given curve at the end of the current curve.
   * Glue parameter determines whether joining beginning and end points should be merged(glue==true)
	 * or left as double control points.
	 */
    void concatenate( const IBaseCurve<RPointType,PointType>& p,
                      bool glue = true );

	/**
	 * Changes the curve shape so that at parameter u, it goes through ToPoint.
	 */
    void dragPosition(  GParametric u,  const PointType& toPoint,
            GParametric segmentMinimum = 0.2,GParametric segmentMaximum = 0.8);

	/**
	 * Change curve shape so that at parameter u, it has the specified tangent.
	 * Change curve shape so that at parameter u, it has the specified tangent.
	 * Like dragCurve, but instead modifies the -tangent- at the u parameter given.  i.e., Adobe
	 * rocker arms you can put anyplace on the curve.
	 */
    void dragTangent(  GParametric u,  const PointType& toTangent,
            GParametric segmentMinimum = 0.2,GParametric segmentMaximum = 0.8);

	/**
	 * Reverses the order of a curve's points so the parameterization runs the opposite direction.  The geometric shape is unchanged.
	 */
    void reverseDirection();

    // Transform all of the curve's control points by the specified matrix
//2D    void transformBy(const IGrafMatrix& mat);

    /**
     * Change order of curve. This DOES change the shape, but leaves the number of points intact.
     */
    void setOrder( unsigned long order );

    /**
     * Raises the order of the curve without changing its shape (changes number points and knots).
     */
    void raiseOrder( unsigned long newOrder );

   /**
    * Approximates a higher-order curve with a lower-order one.
    * Approximates a higher-order curve with a lower-order one.
	 * Control points are added to the lower order curve until the approximation falls within "tolerance".
	 * The curve in question is Bezified first.  You can't lower something to linear (newOrder must
	 * be > 2) or "lower" it to an order higher than it already is(doing so fails an assertion).
	 * The tolerance is specified in absolute coordinates(not relative to the size of the curve).
     */
    void approximateLowerOrder( unsigned long newOrder,
                                GCoordinate tolerance = 0.2 );

	/**
	 * Replaces this curve's control point at the specified index with the specified point.
	 */
    void setPoint( unsigned long i, const RPointType& p );

	/**
	 * Copies points in from your heap block. (The heap block must have same number of points).
	 */
    void setPoints( const IRawArray<RPointType>& controlPoints );

	/**
	 * Sets the knot vector to one of three standard schemes (pinned, floating, or Bezier), without any refinement.
	 */
    void setKnotScheme( EndConditions theType = kPinned );

	/**
	 * Resets this curve's knot vector to the specified array.
	 * Resets this curve's knot vector to the specified array.
	 * The data is copied into the curve, and must have the same number of knots as the curve's
	 * existing knot vector. No refinement or consistency checking is performed on this knot vector.
	 */
    void setKnots( const IRawArray<GParametric>& knots );

    /**
     * Moves the knot at index i to u. May re-sort knots to ensure knot(i+1)>=knot(i) for all i.
	 */
    void moveKnot( unsigned long index, GParametric u );

    /**
     * Modifies both curves to have the same order, the same number of points, and the same knot vector, without changing the shape of either curve.
     * Modifies both curves to have the same order, the same number of points, and the same knot vector, without changing the shape of either curve.
	 * This is accomplished by raising the order and refining the knot vector as necessary.
	 */
    static void makeCompatible( IBaseCurve<RPointType, PointType>& curve1,
                                IBaseCurve<RPointType, PointType>& curve2 );

//2D    static void makeCompatible(ICurveList& curveList);

/*
	 Refinement routines(add control points w/o changing shape)
*/

    /**
     * Inserts a single new knot (and the corresponding control point) at the specified parametric location.
	 */
    void insertKnot( GParametric u );

	/**
	 * Adds a specified discontinuity at the specified parametric location.
	 * Adds a specified discontinuity at the specified parametric location.
	 * The values for n are determined by the EDiscontinuity parameter.
	 * If a discontinuity already exists at u, it is either left as is or raised to the desired one.
	 * Note this method just introduces the discontinuity into the knot vector, it does not change
	 * the shape of the curve.
	 */
    void makeDiscontinuity( GParametric u, EDiscontinuity cont );

    /**
     * Adds a new knot midway between every nonzero interval in the knot vector.
	 */
    void refineUniform();

    /**
     * Turn the curve into a collection of piecewise Bezier segments.
     * Inserts additional knots so that all interior knots have a multiplicity equal to the order minus one.
	 * Does not change the shape.
	 */
    void refineToBeziers();

    /**
     * Insert the given knots into this IBaseCurve, adding new control points without modifying the curve's shape.
	 */
    void refine( const IRawArray<GParametric>& newKnots );

    /**
     * Adds knots to the beginning and end of the knot vector so that the control polygon is pinned to the ends of the curve.
     * Adds knots to the beginning and end of the knot vector so that the control polygon is pinned to the ends of the curve.
	 * This function is only applicable to curves with floating end conditions. The shape of the curve is not changed.
	 */
    void refineToPinned();

	/**
	 * Assignment operator.
	 */
    IBaseCurve<RPointType,PointType>& operator= (const IBaseCurve<RPointType,PointType>& Crv);

	/**
	 * Tests two curves for equality.
	 */
    bool operator== (const IBaseCurve<RPointType,PointType>&) const;

	/**
	 * Tests two curves for inequality.
	 */
    bool operator!= (const IBaseCurve<RPointType,PointType>&) const;

    /**
     * Checks for invalid knot vectors, W's, duplicate points, and values grossly out of range.
	 */
    bool    isConsistent();

  protected:

//2D    void makeArc(unsigned long numPoints, IGRPoint2DArray& pts);

    friend class IGLoop2D;              // For access by IGLoop2D::contains, etc.
    friend class IGCurve2D;

    /**
     * Convert a k order spline to a k+1 order spline.
     * Convert a k order spline to a k+1 order spline.
     * Note this procedure generates spurious control points splines with other
     * than "Closed" end conditions (k-fold knots at each end).
     */
    void incrementOrder();

	/**
	 * Pre-appends the given curve at the beginning of the current curve.
	 * Pre-appends the given curve at the beginning of the current curve.
  	 * Glue parameter determines whether joining beginning and end points should be merged(glue==true)
	 * or left as double control points.
	 */
    void prAppendCurve(IBaseCurve<RPointType, PointType>& crv, bool glue);

    /**
     * Internal version used only by derived classes.
     */
    PointType evaluate(GParametric u, unsigned long delta) const;

    /**
     * Assumes the input is a complete peicewise Bezier curve of the specified order (does no error checking!)
     */
    static void reduceOneDegree(
    	IRawArray<RPointType>& pts,
        unsigned long order,
        unsigned long numPts,
        GCoordinate tolerance,
        long* discons,
        unsigned long numDiscons,
        unsigned long* newPts);

  private:
    void setBasisSpline(const BasisMatrix, unsigned long step);

  private:
    IRawArray<RPointType> fPoints;
    IRawArray<GParametric> fKnots;
    unsigned long fNumPoints;     // CACHED COPY
    unsigned long fOrder;
};

#pragma pack(pop)
#pragma enum(pop)

#if __IBMCPP__ >= 400
#pragma namemangling()
#endif

#ifdef MAKE_TBaseCurve_DEFINITIONS_VISIBLE
// Includes are present in GeometryInstantiations.C - API police prohibit inclusion here.
#endif

#endif // _IBCURVE_
