// Copyright (c) 1995-1999 Matra Datavision
// Copyright (c) 1999-2014 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.

#include <NCollection_IncAllocator.hxx>
#include <NCollection_LocalArray.hxx>


// modified by NIZHNY-MKK  Thu Nov  2 15:07:26 2000.BEGIN
static Standard_Boolean TestPassedSolutionWithNegativeState(const IntWalk_VectorOfWalkingData& wd,
							    const TColStd_SequenceOfReal& Umult,
							    const TColStd_SequenceOfReal& Vmult,
							    const Standard_Real& prevUp, 
							    const Standard_Real& prevVp,
							    const IntWalk_VectorOfInteger& nbMultiplicities,
							    const math_Vector& tolerance,
							    TheIWFunction& sp,
							    math_Vector& UV,
							    Standard_Integer& Irang);
// modified by NIZHNY-MKK  Thu Nov  2 15:07:39 2000.END


void IntWalk_IWalking::ComputeOpenLine(const TColStd_SequenceOfReal& Umult,
				       const TColStd_SequenceOfReal& Vmult,
				       const ThePOPIterator& Pnts1,
				       TheIWFunction& Func,
				       Standard_Boolean& Rajout) 

// Processing of open line.
//
// 1) for any starting point, which is not passing and not tangent and not yet processed,
//    calculation of the step of advancement = step depending on the arrow and the maximum step.
//
// 2) calculate a point of approach (this point is on the tangent to the section
// of distance = no point in the interior)
//  
// 3) conditions  {
//            (all calculated points do not exceed a point in the
//             list of starting points)
//                              or                    
//            (all points do not form an open line going 
//            from one border of the domain to the other or from a point tangent 
//            to border or from 2 tangent points : single cases)
//  
//     1) framing of approached point on borders if necessary (there is
//        calculation of step)
//     2) calculation of the point
//     3) if the point is not found the step is divided
//     4) stop tests
//     5) calculation of the step depending on the arrow and the max step,
//        (TestDeflection)
//        stop  possible.
//    end of conditions.

{
  Standard_Integer I = 0, N = 0, SaveN = 0;
  Standard_Real aBornInf[2] = {}, aBornSup[2] = {}, aUVap[2] = {};
  math_Vector BornInf(aBornInf,1,2), BornSup(aBornSup,1,2), UVap(aUVap,1,2);
  Standard_Real PasC = 0.0, PasCu = 0.0, PasCv = 0.0;
  Standard_Boolean Arrive = false; // shows if the line ends
  Standard_Boolean Cadre = false;  // shows if one is on border of the domain
  Standard_Boolean ArretAjout = false;  //shows if one is on added point
  IntSurf_PntOn2S Psol;
  Handle(IntWalk_TheIWLine)  CurrentLine;    // line under construction
  Standard_Boolean Tgtend = false;

  IntWalk_StatusDeflection aStatus = IntWalk_OK, StatusPrecedent = IntWalk_OK;
  
  Standard_Integer NbDivision = 0;
  // number of divisions of step for each section

  Standard_Integer StepSign = 0;
  
  ThePointOfPath PathPnt;

  BornInf(1) = Um;
  BornSup(1) = UM;
  BornInf(2) = Vm;
  BornSup(2) = VM;

  math_FunctionSetRoot Rsnld(Func, tolerance);
  Standard_Integer nbPath = Pnts1.Length();

  // modified by NIZHNY-MKK  Fri Oct 27 12:32:34 2000.BEGIN
  NCollection_LocalArray<Standard_Integer> movementdirectioninfoarr (nbPath + 1);
  Standard_Integer* movementdirectioninfo = movementdirectioninfoarr;
  for (I = 0; I <= nbPath; I++) {
    movementdirectioninfo[I] = 0;
  }
  // modified by NIZHNY-MKK  Fri Oct 27 12:32:38 2000.END

  TheIWFunction aFuncForDuplicate = Func;

  for (I = 1; I <= nbPath; I++) {
    //start point of the progression
    //     if (wd1[I].etat > 11) {                
    // modified by NIZHNY-MKK  Fri Oct 27 12:33:37 2000.BEGIN
    if ((wd1[I].etat > 11) || ((wd1[I].etat < -11) && (movementdirectioninfo[I]!=0))) {
    // modified by NIZHNY-MKK  Fri Oct 27 12:33:43 2000.END
      PathPnt = Pnts1.Value(I);
      UVap(1) = wd1[I].ustart;
      UVap(2) = wd1[I].vstart;
      MakeWalkingPoint(11, UVap(1), UVap(2), Func, previousPoint);

      if (IsPointOnLine(previousPoint, BornInf, BornSup, Rsnld, aFuncForDuplicate))
      {
        wd1[I].etat = -Abs(wd1[I].etat); //mark point as processed
        continue;
      }

      CurrentLine = new IntWalk_TheIWLine (new NCollection_IncAllocator());
      CurrentLine->SetTangencyAtBegining(Standard_False);
      Tgtend = Standard_False;
      CurrentLine->AddStatusFirst(Standard_False, Standard_True, I, PathPnt);
      previousd3d = Func.Direction3d();
      previousd2d = Func.Direction2d();
      CurrentLine->AddPoint(previousPoint);
      // modified by NIZHNY-MKK  Fri Oct 27 12:34:32 2000.BEGIN
      if(movementdirectioninfo[I] !=0) {
        if(movementdirectioninfo[I] < 0) {
          StepSign = -1;
          CurrentLine->SetTangentVector(previousd3d.Reversed(),1);
        } else {
          StepSign = 1; 
          CurrentLine->SetTangentVector(previousd3d,1);
        }
      } else {
        Standard_Real tyutuyt=ThePointOfPathTool::Direction3d(PathPnt) * previousd3d;
        if( tyutuyt < 0) {
          StepSign = -1;
          CurrentLine->SetTangentVector(previousd3d.Reversed(),1);
        }
        else {
          StepSign = 1; 
          CurrentLine->SetTangentVector(previousd3d,1);
        }
      }
      // modified by NIZHNY-MKK  Fri Oct 27 12:34:37 2000.END

      //  Modified by Sergey KHROMOV - Tue Nov 20 10:41:45 2001 Begin
      wd1[I].etat = -Abs(wd1[I].etat);
      movementdirectioninfo[I] = (movementdirectioninfo[I]==0) ? StepSign : 0;
//  Modified by Sergey KHROMOV - Tue Nov 20 10:41:56 2001 End
      // first step of advancement
      Standard_Real d2dx = Abs(previousd2d.X()); 
      Standard_Real d2dy = Abs(previousd2d.Y()); 
      if (d2dx < tolerance(1)) {
        PasC = pas * (VM-Vm)/d2dy;
      }
      else if (d2dy < tolerance(2)) {
        PasC = pas * (UM-Um)/d2dx;
      }
      else {
        PasC = pas * Min((UM-Um)/d2dx,(VM-Vm)/d2dy);
      }

      Arrive = Standard_False;
      ArretAjout = Standard_False;
      NbDivision = 0;
      StatusPrecedent = IntWalk_OK;
      // modified by NIZHNY-MKK  Fri Oct 27 12:39:37 2000
      Standard_Integer IndexOfPathPointDoNotCheck=0;
      Standard_Integer aNbIter = 10;
      while (!Arrive) { //    as one of stop tests is not checked
        Cadre = Cadrage(BornInf,BornSup,UVap,PasC,StepSign);
        //  Border?

#ifdef CHRONO
        Chronrsnld.Start();
#endif

        Rsnld.Perform(Func,UVap,BornInf,BornSup);

#ifdef CHRONO
        Chronrsnld.Stop();
#endif

        if (Cadre) {
          BornInf(1) = Um; BornSup(1) = UM; BornInf(2) = Vm; BornSup(2) = VM;
        }
        if (Rsnld.IsDone()) {
          if (Abs(Func.Root()) > Func.Tolerance()) {
            PasC = PasC / 2.0;
            PasCu = Abs(PasC*previousd2d.X());
            PasCv = Abs(PasC*previousd2d.Y());
            if (PasCu <= tolerance(1) && PasCv <= tolerance(2)) {
              if (CurrentLine->NbPoints() == 1) break;
              Arrive = Standard_True;
              CurrentLine->AddStatusLast(Standard_False);
              Tgtend = Standard_True; // check
              Rajout = Standard_True;
              seqAlone.Append(lines.Length() + 1);
              seqAjout.Append(lines.Length() + 1);
            }  
          }
          else { // test stop
            Rsnld.Root(UVap);
            Arrive = TestArretPassage(Umult, Vmult, Func, UVap, N);
            if (Arrive) {
              Cadre = Standard_False;
              //in case if there is a frame and arrive at the same time
            }
            else {
              if (Rajout) {
                ArretAjout =TestArretAjout(Func, UVap, N, Psol);
                SaveN = N;
                if (ArretAjout) {
                  // jag 940615
                  Tgtend = lines.Value(N)->IsTangentAtEnd();
                  N = -N;
                }
              }
              // modified by NIZHNY-MKK  Thu Nov  2 15:09:08 2000.BEGIN
              if(!(Rajout && ArretAjout)) {
                Standard_Real prevUp, prevVp;
                if (!reversed) {
                  previousPoint.ParametersOnS2(prevUp, prevVp);
                }
                else {
                  previousPoint.ParametersOnS1(prevUp, prevVp);
                }
                Arrive = TestPassedSolutionWithNegativeState(wd1, Umult, Vmult, prevUp, prevVp,
                  nbMultiplicities, tolerance, Func, UVap, N);		
                if(Arrive) {
                  Cadre = Standard_False;
                }
              }
              // modified by NIZHNY-MKK  Thu Nov  2 15:09:13 2000.END
              if (!ArretAjout && Cadre) {
                if (CurrentLine->NbPoints() == 1) break; // cancel the line
                TestArretCadre(Umult, Vmult, CurrentLine, Func, UVap, N);
                //		if (N == 0) {
                if (N <= 0) { // jag 941017
                  MakeWalkingPoint(2, UVap(1), UVap(2), Func, Psol);
                  Tgtend = Func.IsTangent();
                  N = -N;
                }
              }
            }
            aStatus = TestDeflection(Func, Arrive, UVap, StatusPrecedent,
              NbDivision,PasC,StepSign);
            StatusPrecedent = aStatus;
            if (aStatus == IntWalk_PasTropGrand) {
              Arrive = Standard_False;
              ArretAjout = Standard_False;
              Tgtend = Standard_False; // jag 940615
              if (!reversed) {
                previousPoint.ParametersOnS2(UVap(1), UVap(2));
              }
              else {
                previousPoint.ParametersOnS1(UVap(1), UVap(2));
              }
            }
            else if (ArretAjout || Cadre) {
              Arrive = Standard_True;
              CurrentLine->AddStatusLast(Standard_False);
              //if (aStatus != IntWalk_ArretSurPointPrecedent)
              CurrentLine->AddPoint(Psol);                      
              //Remove <SaveN> from <seqAlone>
              for (Standard_Integer iseq = 1; iseq <= seqAlone.Length(); iseq++)
                if (seqAlone(iseq) == SaveN)
                {
                  seqAlone.Remove(iseq);
                  break;
                }

              if (Cadre && N==0) {
                Rajout = Standard_True;
                seqAjout.Append(lines.Length()+1);
              }
            }
            else if (aStatus == IntWalk_ArretSurPointPrecedent) {
              if (CurrentLine->NbPoints() == 1) { //cancel the line
                Arrive = Standard_False;
                break;
              }
              Arrive = Standard_True;
              Rajout = Standard_True;
              //AddAlonePoint();
              seqAlone.Append(lines.Length() + 1);
              seqAjout.Append(lines.Length() + 1);
              CurrentLine->AddStatusLast(Standard_False);
              Tgtend = Standard_True; // check
            }
            else if (Arrive)  {
              if (CurrentLine->NbPoints() == 1 &&    // cancel the line
                (N == I || aStatus == IntWalk_PointConfondu) ) {
                  // if N == I the main uv is probably lost
                  // or the point is a point of accumulation
                  // if point is confused the start data is bad
                  Arrive =  Standard_False;
                  break;
              }
              // necessairily N > 0 jag 940617
              // point of stop given at input 
              PathPnt = Pnts1.Value(N);

              Standard_Integer etat1N=wd1[N].etat;
              // modified by NIZHNY-MKK  Thu Nov  2 15:09:51 2000.BEGIN
              // 	      if (etat1N < 11) { // passing point that is a stop  
              if (Abs(etat1N) < 11) { // passing point that is a stop    
                // modified by NIZHNY-MKK  Thu Nov  2 15:12:11 2000.END
                if (aStatus == IntWalk_ArretSurPoint) {
                  CurrentLine->AddStatusLast(Standard_False);
                  Tgtend = Standard_True; // need check
                }
                else { 
                  Arrive = Standard_False;
                }
                CurrentLine->AddIndexPassing(N);
              }
              else { // point of stop given at input
                if (etat1N == 11) {
                  Tgtend = Standard_True;
                }
                CurrentLine->AddStatusLast(Standard_True, N, PathPnt);
              }
              AddPointInCurrentLine(N,PathPnt,CurrentLine);
              if ((etat1N != 1 && etat1N != 11)) {
                // modified by NIZHNY-MKK  Fri Oct 27 12:43:05 2000.BEGIN
                // 		wd1[N].etat= - wd1[N].etat;
                wd1[N].etat = - Abs(etat1N);		
                movementdirectioninfo[N] = (movementdirectioninfo[N]==0) ? StepSign : 0;
                if(Arrive && movementdirectioninfo[N]!=0) {
                  IndexOfPathPointDoNotCheck = N;
                }

                if(Arrive) {
                  Rajout = Standard_True;
                  seqAjout.Append(lines.Length() + 1);
                }
                // modified by NIZHNY-MKK  Fri Oct 27 12:45:33 2000.END
              }
            }
            else if (aStatus == IntWalk_ArretSurPoint) {
              Arrive = Standard_True;                   
              CurrentLine->AddStatusLast(Standard_False);
              Tgtend = Standard_True;
              MakeWalkingPoint(1, UVap(1), UVap(2), Func, Psol);
              CurrentLine->AddPoint(Psol);
              Rajout = Standard_True;
              seqAlone.Append(lines.Length() + 1);
              seqAjout.Append(lines.Length() + 1);
            }
            else if (aStatus == IntWalk_OK) {
              MakeWalkingPoint(2, UVap(1), UVap(2), Func, previousPoint);
              previousd3d = Func.Direction3d();
              previousd2d = Func.Direction2d();
              CurrentLine->AddPoint(previousPoint);
            }     
            else if (aStatus == IntWalk_PointConfondu)
            {
              aNbIter --;
            }
          }
        }
        else { // no numerical solution
          PasC = PasC / 2.;
          PasCu = Abs(PasC*previousd2d.X());
          PasCv = Abs(PasC*previousd2d.Y());
          if (PasCu <= tolerance(1) && PasCv <= tolerance(2)) {
            if (CurrentLine->NbPoints()==1) break;
            Arrive = Standard_True;
            CurrentLine->AddStatusLast(Standard_False);
            Tgtend = Standard_True; // need check
            Rajout = Standard_True;
            seqAlone.Append(lines.Length() + 1);
            seqAjout.Append(lines.Length() + 1);
          }  
        }

        if(aNbIter < 0)
          break;
      } // end of started line
      
      if (Arrive) {
        CurrentLine->SetTangencyAtEnd(Tgtend);
        lines.Append(CurrentLine);
        // modified by NIZHNY-MKK  Fri Oct 27 12:59:29 2000.BEGIN
        movementdirectioninfo[I]=0;
        if(wd1[I].etat > 0)
          // modified by NIZHNY-MKK  Fri Oct 27 12:59:42 2000.END
          wd1[I].etat=-wd1[I].etat;

        //-- lbr le 5 juin 97 (Pb ds Contap)
        for(Standard_Integer av=1; av<=nbPath; av++) { 
          // modified by NIZHNY-MKK  Fri Oct 27 13:00:22 2000.BEGIN
          // 	  if (wd1[av].etat > 11) {
          if ((wd1[av].etat > 11) || 
            ((av!=I) && 
            (av!=IndexOfPathPointDoNotCheck) && 
            (wd1[av].etat < -11)  && 
            (movementdirectioninfo[av]!=0)))
          {
            // modified by NIZHNY-MKK  Fri Oct 27 13:00:26 2000.END
            Standard_Real Uav=wd1[av].ustart;
            Standard_Real Vav=wd1[av].vstart;
            Standard_Real Uavp,Vavp;
            const IntSurf_PntOn2S &avP=CurrentLine->Value(CurrentLine->NbPoints());
            if (!reversed) {
              avP.ParametersOnS2(Uavp,Vavp);
            }
            else {
              avP.ParametersOnS1(Uavp,Vavp);
            }
            Uav-=Uavp;
            Vav-=Vavp;
            Uav*=0.001; Vav*=0.001;
            if(Abs(Uav)<tolerance(1) && Abs(Vav)<tolerance(2)) { 
              // modified by NIZHNY-MKK  Fri Oct 27 13:01:38 2000.BEGIN
              // 	      wd1[av].etat=-wd1[av].etat;
              if(wd1[av].etat < 0) {
                movementdirectioninfo[av] = 0;
              } else {
                wd1[av].etat=-wd1[av].etat;
                movementdirectioninfo[av] = StepSign;
              }
              // modified by NIZHNY-MKK  Fri Oct 27 13:01:42 2000.END
              CurrentLine->AddStatusLast(Standard_True, av, Pnts1.Value(av));
              //-- cout<<"\n Debug ? lbr ds IntWalk_IWalking_3.gxx"<<endl;
            }

            const IntSurf_PntOn2S &avPP=CurrentLine->Value(1);
            if (!reversed) {
              avPP.ParametersOnS2(Uavp,Vavp);
            }
            else {
              avPP.ParametersOnS1(Uavp,Vavp);
            }
            Uav=wd1[av].ustart;
            Vav=wd1[av].vstart;
            Uav-=Uavp;
            Vav-=Vavp;
            Uav*=0.001; Vav*=0.001;
            if(Abs(Uav)<tolerance(1) && Abs(Vav)<tolerance(2)) { 
              // modified by NIZHNY-MKK  Fri Oct 27 13:02:49 2000.BEGIN
              // 	      wd1[av].etat=-wd1[av].etat;
              if(wd1[av].etat < 0) {
                movementdirectioninfo[av] = 0;
              } else {
                wd1[av].etat=-wd1[av].etat;
                movementdirectioninfo[av] = -StepSign;
              }
              // modified by NIZHNY-MKK  Fri Oct 27 13:02:52 2000.END
              //-- cout<<"\n Debug ? lbr ds IntWalk_IWalking_3.gxx"<<endl;
              CurrentLine->AddStatusFirst(Standard_False, Standard_True, av, Pnts1.Value(av));
            }
          }
        }
      }
    } //end of point processing
  } //end of all points
}

// modified by NIZHNY-MKK  Thu Nov  2 15:07:53 2000.BEGIN
static Standard_Boolean TestPassedSolutionWithNegativeState(const IntWalk_VectorOfWalkingData& wd,
							    const TColStd_SequenceOfReal& Umult,
							    const TColStd_SequenceOfReal& Vmult,
							    const Standard_Real& prevUp,
							    const Standard_Real& prevVp,
							    const IntWalk_VectorOfInteger& nbMultiplicities,
							    const math_Vector& tolerance,
							    TheIWFunction& sp,
							    math_Vector& UV,
							    Standard_Integer& Irang) {
  Standard_Boolean Arrive = Standard_False;
  Standard_Real Dup, Dvp, Utest,Vtest;
  Standard_Real tolu = tolerance(1);
  Standard_Real tolv = tolerance(2);
  Standard_Integer i, j, k, N;
  for (i = 1; i < (int)wd.size(); i++) {
    if (wd[i].etat < -11) {

 // debug jag see with isg

      Utest = wd[i].ustart;
      Vtest = wd[i].vstart;
      Dup = prevUp - Utest;
      Dvp = prevVp - Vtest;
      if (Abs(Dup) >= tolu || Abs(Dvp) >= tolv) {
	Standard_Real UV1mUtest = UV(1)-Utest;
	Standard_Real UV2mVtest = UV(2)-Vtest;
	if(( (Dup*UV1mUtest + Dvp*UV2mVtest) < 0) ||
	   (   Abs(UV1mUtest) < tolu 
	    && Abs(UV2mVtest) < tolv)) {
	  Irang=i;
	  Arrive = Standard_True;
	  UV(1) = Utest;
	  UV(2) = Vtest;
	}
	else if (nbMultiplicities[i] > 0) {
	  N=0;
	  for (k = 1; k < i; k++) { 
	    N+=nbMultiplicities[k];
	  }
	  for (j = N + 1; j <= N + nbMultiplicities[i]; j++) {
	    if (((prevUp-Umult(j))*(UV(1)-Umult(j)) +
		 (prevVp-Vmult(j))*(UV(2)-Vmult(j)) < 0) ||
		(Abs(UV(1)-Umult(j)) < tolu &&
		 Abs(UV(2)-Vmult(j)) < tolv)) {
	      Irang=i;
	      Arrive = Standard_True;
	      UV(1) = Utest;
	      UV(2) = Vtest;
	      break;
	    }
	  }
	}
	if (Arrive) {
	  Standard_Real abidF[1], abidD[1][2];
	  math_Vector bidF(abidF,1,1);
	  math_Matrix bidD(abidD,1,1,1,2); 
      sp.Values(UV,bidF,bidD);
	  break;
	}
      }
    }    
  }
  return Arrive;
}
// modified by NIZHNY-MKK  Thu Nov  2 15:07:58 2000.END