/// <summary>
 /// Default constructor</summary>
 /// <param name="curve">Curve for which evaluator created</param>
 public HermiteCurveEvaluator(ICurve curve)
 {
     if (curve == null)
         throw new ArgumentNullException("curve");
     m_curve = curve;            
     Reset();
 }

  static IEnumerable<CurveTangent> TangentsAroundCurve(ICurve iCurve) {
     Curve c = iCurve as Curve;
     if (c != null) {
         foreach (ICurve seg in c.Segments)
             foreach (CurveTangent ct in TangentsAroundCurve(seg))
                 yield return ct;
     } else {
         LineSegment ls = iCurve as LineSegment;
         if (ls != null)
             yield return new CurveTangent(ls.Start, ls.Derivative(0));
         else {
             Ellipse ellipse = iCurve as Ellipse;
             if (ellipse != null) {
                 foreach (CurveTangent ct in TangentsOfEllipse(ellipse))
                     yield return ct;
             } else {
                 CubicBezierSegment bez = iCurve as CubicBezierSegment;
                 if (bez != null)
                     foreach (CurveTangent ct in TangentsOfBezier(bez))
                         yield return ct;
                 }
         }
         
     }
 }

        /// <summary>
        /// Flattens the specified curve. See <see cref="ICurve{TParam, TPoint}.Flatten"/>.
        /// </summary>
        /// <remarks>
        /// This method cannot be used for curves that contain gaps!
        /// </remarks>
        internal static void Flatten(ICurve<float, Vector3F> curve, ICollection<Vector3F> points, int maxNumberOfIterations, float tolerance)
        {
            if (tolerance <= 0)
            throw new ArgumentOutOfRangeException("tolerance", "The tolerance must be greater than zero.");

              float totalLength = curve.GetLength(0, 1, maxNumberOfIterations, tolerance);

              // No line segments if the curve has zero length.
              if (totalLength == 0)
            return;

              // A single line segment if the curve's length is less than the tolerance.
              if (totalLength < tolerance)
              {
            points.Add(curve.GetPoint(0));
            points.Add(curve.GetPoint(1));
            return;
              }

              var list = ResourcePools<Vector3F>.Lists.Obtain();

              Flatten(curve, list, 0, 1, curve.GetPoint(0), curve.GetPoint(1), 0, totalLength, 1, maxNumberOfIterations, tolerance);

              foreach (var point in list)
            points.Add(point);

              ResourcePools<Vector3F>.Lists.Recycle(list);
        }

        static bool WithinEpsilon(ICurve bc, double start, double end) {
            int n = 3; //hack !!!!
            double d = (end - start)/n;
            P2 s = bc[start];
            P2 e = bc[end];

            return DistToSegm(bc[start + d], s, e) < epsilon && DistToSegm(bc[start + d*(n - 1)], s, e) < epsilon;
        }

 /// <summary>
 /// Offsets curve</summary>
 /// <param name="curve">Curve</param>
 /// <param name="x">X offset</param>
 /// <param name="y">Y offset</param>
 public static void OffsetCurve(ICurve curve, float x, float y)
 {
     foreach (IControlPoint cpt in curve.ControlPoints)
     {
         cpt.X += x;
         cpt.Y += y;
     }
 }

 public static Polyline PolylineAroundClosedCurve(ICurve curve) {
     Polyline poly = new Polyline();
     foreach (Point point in PointsOnAroundPolyline(curve))
         poly.AddPoint(point);
     if (Point.GetTriangleOrientation(poly.StartPoint.Point, poly.StartPoint.Next.Point, poly.StartPoint.Next.Next.Point) == TriangleOrientation.Counterclockwise)
         poly = (Polyline)poly.Reverse();
     poly.Closed = true;
     return poly;
 }

        public WeierstrassCurvePoint(FiniteFieldElement x, FiniteFieldElement y, ICurve curve)
        {
            if (!(curve is WeierstrassCurve))
                throw new ArgumentException("A weierstrass curve point should only be placed on a weierstrass curve, but was placed on " + curve + ".", "curve");

            _x = x;
            _y = y;
            _curve = curve as WeierstrassCurve;
        }

        internal Rail(ICurve curveSegment, LgEdgeInfo topRankedEdgeInfoOfTheRail, int zoomLevel)
#if DEBUG
            : this()
#endif
        {
            TopRankedEdgeInfoOfTheRail = topRankedEdgeInfoOfTheRail;
            this.ZoomLevel = zoomLevel;
            Geometry = curveSegment;
        }

 /// <summary>
 /// constructor
 /// </summary>
 internal BundleBase(int count, ICurve boundaryCurve, Point position, bool belongsToRealNode, int stationIndex) {
     BelongsToRealNode = belongsToRealNode;
     Curve = boundaryCurve;
     Position = position;
     this.stationIndex = stationIndex;
     points = new Point[count];
     tangents = new Point[count];
     OrientedHubSegments = new OrientedHubSegment[count];
     ParameterSpan = Curve.ParEnd - Curve.ParStart;
 }

        public PortEntryOnCurve(ICurve entryCurve, IEnumerable<Tuple<double, double>> parameterSpans) {
            EntryCurve = entryCurve;
#if TEST_MSAGL
            var polyline = entryCurve as Polyline;
            curveIsClosed = (polyline != null) ? polyline.Closed : ApproximateComparer.Close(EntryCurve.Start, EntryCurve.End);
#endif
            Spans = parameterSpans;
#if TEST_MSAGL
            TestSpans(entryCurve, parameterSpans, curveIsClosed);
#endif
        }

 /// <summary>
 /// Creates a curve evaluator for a curve</summary>
 /// <param name="curve">Curve</param>
 /// <returns>Curve evaluator</returns>
 /// <remarks>A curve evaluator calculates y-coordinates from x-coordinates using appropriate interpolation for a curve</remarks>
 public static ICurveEvaluator CreateCurveEvaluator(ICurve curve)
 {
     ICurveEvaluator cv = null;
     if (curve.CurveInterpolation == InterpolationTypes.Linear)
         cv = new LinearCurveEvaluator(curve);
     else if (curve.CurveInterpolation == InterpolationTypes.Hermite)
         cv = new HermiteCurveEvaluator(curve);
     else
         throw new NotImplementedException("CurveEvaluator not implement for "
             + curve.CurveInterpolation);
     return cv;
 }

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="steeringCurve">Steering curve</param>
        /// <param name="pushCurve">Push amount curve</param>
        /// <param name="elevationCurve">Elevation curve</param>
        public KinectPilotProcessor(ICurve steeringCurve, ICurve pushCurve, ICurve elevationCurve)
        {
            if (steeringCurve == null)
                throw new ArgumentNullException("steeringCurve");
            if (pushCurve == null)
                throw new ArgumentNullException("pushCurve");
            if (elevationCurve == null)
                throw new ArgumentNullException("elevationCurve");

            this.steeringCurve = steeringCurve;
            this.pushCurve = pushCurve;
            this.elevationCurve = elevationCurve;
        }

        internal IntersectionInfo(double pr0, double pr1, Point x, ICurve s0, ICurve s1) {
            par0 = pr0;
            par1 = pr1;
            this.x = x;
            seg0 = s0;
            seg1 = s1;
#if DETAILED_DEBUG
            System.Diagnostics.Debug.Assert(ApproximateComparer.Close(x, s0[pr0], ApproximateComparer.IntersectionEpsilon*10),
                    string.Format("intersection not at curve[param]; x = {0}, s0[pr0] = {1}, diff = {2}", x, s0[pr0], x - s0[pr0]));
            System.Diagnostics.Debug.Assert(ApproximateComparer.Close(x, s1[pr1], ApproximateComparer.IntersectionEpsilon*10),
                    string.Format("intersection not at curve[param]; x = {0}, s1[pr1] = {1}, diff = {2}", x, s1[pr1], x - s1[pr1]));
#endif 
        }

        internal static void Serialize(string fileName, ICurve i) {

            Stream file = File.Open(fileName, FileMode.Create);

            // Create a formatter object based on command line arguments
            IFormatter formatter = new BinaryFormatter();

            // Serialize the object graph to stream
            formatter.Serialize(file, i);

            // All done
            file.Close();
        }

        internal static List<LineSegment> Interpolate(double a, ref Point ap, double b, ref Point bp, ICurve s,
            double eps) {
            var r = new List<LineSegment>();
            if (IsCloseToLineSeg(a, ref ap, b, ref bp, s, eps))
                r.Add(new LineSegment(ap, bp));
            else {
                double m = 0.5*(a + b);
                Point mp = s[m];
                r.AddRange(Interpolate(a, ref ap, m, ref mp, s, eps));
                r.AddRange(Interpolate(m, ref mp, b, ref bp, s, eps));
            }

            return r;
        }

        ///// <summary>
        ///// Gets the closest point on the curve to the point
        ///// </summary>
        ///// <param name="curve"></param>
        ///// <param name="coeff"></param>
        ///// <param name="hint">will return Double.MaxVal if Newton iterations fail</param>
        ///// <param name="closestPointParam"></param>
        internal static double ClosestPoint(ICurve curve, Point a, double hint, double low, double high) {
            /*
              * Let F=(c(t)-a)^2. We try to bring to zero the first derivative of F, Ft. Denote it by f(t).
              * Applying the Newton method we see that dt=-f(t)/der(f(t)
              * The first derivative of F, f, has the form (c-a)*ct. We discarded a multiplier here.
              * The second derivative has the form ct*ct+(c-a)*ctt
              * The new t becomes t-dt
              */
            const int numberOfIterationsMax = 5;
            const int numberOfOverShootsMax = 5;
            double t = hint;
      
            int numberOfIteration = 0;
            int numberOfOvershoots = 0;
            double dt;
            bool abort = false;
            do {
                Point c = curve[t];
                Point ct = curve.Derivative(t);
                Point ctt = curve.SecondDerivative(t);

                double secondDerivative = ct * ct + (c - a) * ctt;

                if (Math.Abs(secondDerivative) < ApproximateComparer.Tolerance) 
                    return t;

                dt = (c - a) * ct / secondDerivative;
               
                t -= dt;
                
                if (t > high + ApproximateComparer.Tolerance) {
                    t = high;
                    numberOfOvershoots++;
                } else if (t < low - ApproximateComparer.Tolerance) {
                    t = low;
                    numberOfOvershoots++;
                }
                numberOfIteration++;
            } while (Math.Abs(dt) > ApproximateComparer.Tolerance &&!
                (abort = (numberOfIteration >= numberOfIterationsMax || numberOfOvershoots >= numberOfOverShootsMax)));

            //may be the initial value was just fine
            if (abort && (curve[hint] - a).Length < ApproximateComparer.DistanceEpsilon) 
                t = hint;
            
            return t;

           }

         static IEnumerable<Point> PointsOnAroundPolyline(ICurve curve) {
            bool firstSide = true;
            CurveTangent prevTangent = null;
            CurveTangent firstCurveTangent = null;
            foreach (CurveTangent curveTangent in TangentsAroundCurve(curve)) {
                if (firstSide) {
                    firstSide = false;
                    firstCurveTangent = prevTangent = curveTangent;
                } else {
                    if (!TangentsAreParallel(prevTangent, curveTangent))
                        yield return TangentIntersection(prevTangent, curveTangent);
                    prevTangent = curveTangent;
                }
            }
            yield return TangentIntersection(firstCurveTangent, prevTangent);

        }

        static bool WithinEpsilon(ICurve seg, double start, double end, double eps) {
            if (seg is LineSegment)
                return true;

            int n = 3; //hack !!!! but maybe can be proven for Bezier curves and other regular curves
            double d = (end - start) / n;
            Point s = seg[start];
            Point e = seg[end];

            double d0 = DistToSegm(seg[start + d], s, e);
            double d1 = DistToSegm(seg[start + d * (n-1)], s, e);
            //double d1d1 = seg.d1(start) * seg.d1(end);

            return d0 < eps
              &&
              d1 < eps;// && d1d1 > 0;

        }

/// <summary>
/// constructor
/// </summary>
/// <param name="curveAPar">first curve</param>
/// <param name="curveBPar">second curve</param>
/// <param name="lowBound0">the first curve minimal parameter</param>
        /// <param name="upperBound0">the first curve maximal parameter</param>
        /// <param name="lowBound1">the second curve minimal parameter</param>
        /// <param name="upperBound1">the first curve maximal parameter</param>
/// <param name="guess0"></param>
/// <param name="guess1"></param>
        public MinDistCurveCurve(ICurve curveAPar,
                ICurve curveBPar,
                double lowBound0,
                double upperBound0, 
                double lowBound1,
                double upperBound1,
                double guess0,
                double guess1) {
            this.curveA = curveAPar;
            this.curveB = curveBPar;
            this.aMin = lowBound0;
            this.bMin = lowBound1;
            this.aMax = upperBound0;
            this.bMax = upperBound1;
            this.aGuess = guess0;
            this.bGuess = guess1;
            this.si = guess0;
            this.ti = guess1;
        }

        /// <summary>
        /// Validates the curve</summary>
        /// <param name="curve">Curve to validate</param>
        /// <returns>True iff curve is valid</returns>
        public static bool IsValid(ICurve curve)
        {
            if (curve == null)
                return false;
            ReadOnlyCollection<IControlPoint> points = curve.ControlPoints;
            if (points.Count < 2)
                return true;

            int count = points.Count;
            IControlPoint prev = points[0];
            for (int i = 1; i < count; i++)
            {
                IControlPoint curPoint = points[i];
                if ((curPoint.X - prev.X) < s_epsilone)
                    return false;
                prev = curPoint;
            }
            return true;
        }