// File:	AppParCurves_Variational_5.gxx
// Created:	Thu Dec 10 14:32:36 1998
// Author:	Igor FEOKTISTOV
//		<ifv@paradox.nnov.matra-dtv.fr>

#include <SortTools_ShellSortOfReal.hxx>
#include <TCollection_CompareOfReal.hxx>
#include <PLib_Base.hxx>

//----------------------------------------------------------//
// Standard_Integer NearIndex                               //
// Purpose: searching nearest index of TabPar corresponding //
// given value T (is similar to fortran routine MSRRE2)     //
//----------------------------------------------------------//

static Standard_Integer NearIndex(const Standard_Real T, 
				  const TColStd_Array1OfReal& TabPar,
				  const Standard_Real Eps, Standard_Integer& Flag)
{
  Standard_Integer Loi = TabPar.Lower(), Upi = TabPar.Upper();

  Flag = 0;

  if(T < TabPar(Loi)) { Flag = -1; return Loi;}
  if(T > TabPar(Upi)) { Flag =  1; return Upi;}

  Standard_Integer Ibeg = Loi, Ifin = Upi, Imidl;

  while(Ibeg + 1 != Ifin) {
    Imidl = (Ibeg + Ifin) / 2;
    if((T >= TabPar(Ibeg)) && (T <= TabPar(Imidl)))
      Ifin = Imidl;
    else
      Ibeg = Imidl;
  }

  if(Abs(T - TabPar(Ifin)) < Eps) return Ifin;

  return Ibeg;
}


//----------------------------------------------------------//
// void GettingKnots                                        //
// Purpose: calculating values of new Knots for elements    //
// with degree that is equal Deg                            //
//----------------------------------------------------------//

static void GettingKnots(const TColStd_Array1OfReal& TabPar, 
			 const Handle(FEmTool_Curve)& InCurve,
			 const Standard_Integer Deg,
			 Standard_Integer& NbElm,
			 TColStd_Array1OfReal& NewKnots)

{

  const Standard_Real Eps = 1.e-12;

  TColStd_Array1OfReal& OldKnots = InCurve->Knots();
  Standard_Integer NbMaxOld = InCurve->NbElements(); 
  Standard_Integer NbMax = NewKnots.Upper(), Ipt, Ipt1, Ipt2; 
  Standard_Integer el = 0, i1 = OldKnots.Lower(), i0 = i1 - 1, Flag;
  Standard_Real TPar;
  
  while((NbElm < NbMax) && (el < NbMaxOld)) {

    el++; i0++; i1++; // i0, i1 are indexes of left and right knots of element el

    if(InCurve->Degree(el) == Deg) {

      NbElm++;

      Ipt1 = NearIndex(OldKnots(i0), TabPar, Eps, Flag);
      if(Flag != 0) Ipt1 = TabPar.Lower();
      Ipt2 = NearIndex(OldKnots(i1), TabPar, Eps, Flag);
      if(Flag != 0) Ipt2 = TabPar.Upper();

      if(Ipt2 - Ipt1 >= 1) {
	
	Ipt = (Ipt1 + Ipt2) / 2;
	if(2 * Ipt == Ipt1 + Ipt2)
	  TPar = 2. * TabPar(Ipt);
	else
	  TPar = TabPar(Ipt) + TabPar(Ipt + 1);

	NewKnots(NbElm) = (OldKnots(i0) + OldKnots(i1) + TPar) / 4.;
      }
      else
	NewKnots(NbElm) = (OldKnots(i0) + OldKnots(i1)) / 2.;
    }
  }
}

void AppParCurves_Variational::SplitCurve(const Handle(FEmTool_Curve)& InCurve,
					  const TColStd_Array1OfReal& Ti,
					  const Standard_Real CurveTol,
					  Handle(FEmTool_Curve)& OutCurve,
					  Standard_Boolean& iscut) const
{
  Standard_Integer NbElmOld = InCurve->NbElements(); 

  if(NbElmOld >= myMaxSegment) {iscut = Standard_False; return;}
#ifdef DEB
  Standard_Integer MaxDegree = 
#endif
    InCurve->Base()->WorkDegree();
  Standard_Integer NbElm = NbElmOld;
  TColStd_Array1OfReal NewKnots(NbElm + 1, myMaxSegment);
#ifndef DEB 
  GettingKnots(Ti, InCurve, InCurve->Base()->WorkDegree(), NbElm, NewKnots);
  GettingKnots(Ti, InCurve, InCurve->Base()->WorkDegree() - 1, NbElm, NewKnots);
#else
  GettingKnots(Ti, InCurve, MaxDegree, NbElm, NewKnots);
  GettingKnots(Ti, InCurve, MaxDegree - 1, NbElm, NewKnots);

#endif
  if(NbElm > NbElmOld) {
    
    iscut = Standard_True;

    OutCurve = new FEmTool_Curve(InCurve->Dimension(), NbElm, InCurve->Base(), CurveTol); 
    TColStd_Array1OfReal& OutKnots = OutCurve->Knots();
    TColStd_Array1OfReal& InKnots = InCurve->Knots();
  
    Standard_Integer i, i0 = OutKnots.Lower();
    for(i = InKnots.Lower(); i <= InKnots.Upper(); i++) OutKnots(i) = InKnots(i);
    for(i = NbElmOld + 1; i <= NbElm; i++) OutKnots(i + i0) = NewKnots(i);

//    SortTools_ShellSortOfReal Sort;
    TCollection_CompareOfReal CompReal;

//    Sort.Sort(OutKnots, CompReal);
    SortTools_ShellSortOfReal::Sort(OutKnots, CompReal);
  }
  else
    iscut = Standard_False;
  
}