// 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.

#ifdef CHRONO
#include <OSD_Chronometer.hxx>
OSD_Chronometer Chronrsnld;

#endif

#include <NCollection_IncAllocator.hxx>
#include <Precision.hxx>

//==================================================================================
// function : IsTangentExtCheck
// purpose  : Additional check if the point (theU, theV) in parametric surface
//            is a tangent point.
//            If that is TRUE then we can go along any (!) direction in order to
//            obtain next intersection point. At present, this case is difficult
//            for processing. Therefore, we will return an empty intersection line
//            in this case.
//==================================================================================
static Standard_Boolean IsTangentExtCheck(TheIWFunction& theFunc,
                                          const Standard_Real theU,
                                          const Standard_Real theV,
                                          const Standard_Real theStepU,
                                          const Standard_Real theStepV,
                                          const Standard_Real theUinf,
                                          const Standard_Real theUsup,
                                          const Standard_Real theVinf,
                                          const Standard_Real theVsup)
{
  const Standard_Real aTol = theFunc.Tolerance();
  const Standard_Integer aNbItems = 4;
  const Standard_Real aParU[aNbItems] = { Min(theU + theStepU, theUsup),
                                          Max(theU - theStepU, theUinf),
                                          theU, theU};
  const Standard_Real aParV[aNbItems] = { theV, theV,
                                          Min(theV + theStepV, theVsup),
                                          Max(theV - theStepV, theVinf)};

  math_Vector aX(1, 2), aVal(1, 1);

  for(Standard_Integer i = 0; i < aNbItems; i++)
  {
    aX.Value(1) = aParU[i];
    aX.Value(2) = aParV[i];

    if(!theFunc.Value(aX, aVal))
      continue;

    if(aVal(1) > aTol)
      return Standard_False;
  }

  return Standard_True;
}



IntWalk_IWalking::IntWalk_IWalking (const Standard_Real Epsilon,
                                    const Standard_Real Deflection,
                                    const Standard_Real Increment,
                                    const Standard_Boolean theToFillHoles) :
      done(Standard_False),
      fleche(Deflection),
      pas(Increment),
      tolerance(1,2),
      epsilon(Epsilon*Epsilon),
      reversed(Standard_False),
      wd1 (IntWalk_VectorOfWalkingData::allocator_type (new NCollection_IncAllocator)),
      wd2 (wd1.get_allocator()),
      nbMultiplicities (wd1.get_allocator()),
      Um(0.0),
      UM(0.0),
      Vm(0.0),
      VM(0.0),
      ToFillHoles(theToFillHoles)
{
}

    
//=======================================================================
//function : Reset
//purpose  : Clears NCollection_Vector-based containers and adds
//           dummy data to maintain start index of 1 and consistent with
//           previous TCollection_Sequence-based implementation and other
//           used TCollection-based containers
//=======================================================================

void IntWalk_IWalking::Clear()
{
  wd1.clear();
  wd2.clear();
  IntWalk_WalkingData aDummy;
  aDummy.etat = -10;
  aDummy.ustart = aDummy.vstart = 0.;
  wd1.push_back (aDummy);
  wd2.push_back (aDummy);
  nbMultiplicities.clear();
  nbMultiplicities.push_back (-1);
  
  done = Standard_False;
  seqAjout.Clear();
  lines.Clear();
}

// ***************************************************************************
     //  etat1=12 not tangent, not passes
     //  etat1=11 tangent, not passes
     //  etat1=2  not tangent, passes
     //  etat1=1  tangent, passes
     //  after a point is processed its state becomes negative.
// ***************************************************************************
     //  etat2=13  interior start point on closed line
     //  etat2=12  interior start point on open line 
     //            (line initially closed -> la line s is open)       
     //  after a point is processed (or if it is passed over during
     //  routing) its state becomes negative.
// ****************************************************************************

//
// Perform with interior points
//
void IntWalk_IWalking::Perform(const ThePOPIterator& Pnts1,
			       const ThePOLIterator& Pnts2,
			       TheIWFunction& Func,
			       const ThePSurface& Caro,
			       const Standard_Boolean Reversed)

{
  Standard_Integer I;
  Standard_Boolean Rajout = Standard_False;
  Standard_Integer nbPnts1 = Pnts1.Length();
  Standard_Integer nbPnts2 = Pnts2.Length();
  Standard_Real U,V;

  Clear();
  reversed = Reversed;

  Um = ThePSurfaceTool::FirstUParameter(Caro);
  Vm = ThePSurfaceTool::FirstVParameter(Caro);
  UM = ThePSurfaceTool::LastUParameter(Caro);
  VM = ThePSurfaceTool::LastVParameter(Caro);

  if (UM < Um) {
    Standard_Real utemp = UM;
    UM = Um;
    Um = utemp;
  }
  if (VM < Vm) {
    Standard_Real vtemp = VM;
    VM = Vm;
    Vm = vtemp;
  }

  const Standard_Real aStepU = pas*(UM-Um), aStepV = pas*(VM-Vm);

  // Loading of etat1 and etat2  as well as  ustart and vstart.

  TColStd_SequenceOfReal Umult;
  TColStd_SequenceOfReal Vmult;

  Standard_Integer decal=0;
  wd1.reserve (nbPnts1+decal);
  nbMultiplicities.reserve (nbPnts1+decal);
  for (I=1;I <= nbPnts1+decal; I++) {
    const ThePointOfPath& PathPnt = Pnts1.Value(I-decal);
    IntWalk_WalkingData aWD1;
    aWD1.etat = 1;
    if (!ThePointOfPathTool::IsPassingPnt(PathPnt)) 
      aWD1.etat = 11;
    if (!ThePointOfPathTool::IsTangent(PathPnt))   
      ++aWD1.etat;

    if(aWD1.etat==2) {   
      aWD1.etat=11;
    }      

    ThePointOfPathTool::Value2d(PathPnt, aWD1.ustart, aWD1.vstart);
    mySRangeU.Add(aWD1.ustart);
    mySRangeV.Add(aWD1.vstart);

    wd1.push_back (aWD1);
    Standard_Integer aNbMult = ThePointOfPathTool::Multiplicity(PathPnt);
    nbMultiplicities.push_back(aNbMult);

    for (Standard_Integer J = 1; J <= aNbMult; J++) {
      ThePointOfPathTool::Parameters(PathPnt, J, U, V);
      Umult.Append(U);
      Vmult.Append(V);
    }
  }

  wd2.reserve (nbPnts2);
  for (I = 1; I <= nbPnts2; I++) {
    IntWalk_WalkingData aWD2;
    aWD2.etat = 1;
    const IntSurf_InteriorPoint& anIP = Pnts2.Value(I);
    ThePointOfLoopTool::Value2d(anIP, aWD2.ustart, aWD2.vstart);
    mySRangeU.Add(aWD2.ustart);
    mySRangeV.Add(aWD2.vstart);

    if (!IsTangentExtCheck(Func, aWD2.ustart, aWD2.vstart, aStepU, aStepV, Um, UM, Vm, VM))
      aWD2.etat = 13;
    
    wd2.push_back (aWD2);
  }

  tolerance(1) = ThePSurfaceTool::UResolution(Caro,Precision::Confusion());
  tolerance(2) = ThePSurfaceTool::VResolution(Caro,Precision::Confusion());

  Func.Set(Caro);

  if (mySRangeU.Delta() > Max(tolerance(1), Precision::PConfusion()))
  {
    mySRangeU.Enlarge(mySRangeU.Delta());
    mySRangeU.Common(Bnd_Range(Um, UM));
  }
  else
  {
    mySRangeU = Bnd_Range(Um, UM);
  }

  if (mySRangeV.Delta() > Max(tolerance(2), Precision::PConfusion()))
  {
    mySRangeV.Enlarge(mySRangeV.Delta());
    mySRangeV.Common(Bnd_Range(Vm, VM));
  }
  else
  {
    mySRangeV = Bnd_Range(Vm, VM);
  }

  // calculation of all open lines   
  if (nbPnts1 != 0)
    ComputeOpenLine(Umult,Vmult,Pnts1,Func,Rajout); 

  // calculation of all closed lines 
  if (nbPnts2 != 0)
    ComputeCloseLine(Umult,Vmult,Pnts1,Pnts2,Func,Rajout);

  if (ToFillHoles)
  {
    Standard_Integer MaxNbIter = 10, nb_iter = 0;
    while (seqAlone.Length() > 1 && nb_iter < MaxNbIter)
    {
      nb_iter++;
      IntSurf_SequenceOfInteriorPoint PntsInHoles;
      TColStd_SequenceOfInteger CopySeqAlone = seqAlone;
      FillPntsInHoles(Func, CopySeqAlone, PntsInHoles);
      wd2.clear();
      IntWalk_WalkingData aDummy;
      aDummy.etat = -10;
      aDummy.ustart = aDummy.vstart = 0.;
      wd2.push_back (aDummy);
      Standard_Integer nbHoles = PntsInHoles.Length();
      wd2.reserve(nbHoles);
      for (I = 1; I <= nbHoles; I++)
      {
        IntWalk_WalkingData aWD2;
        aWD2.etat = 13;
        const IntSurf_InteriorPoint& anIP = PntsInHoles.Value(I);
        ThePointOfLoopTool::Value2d(anIP, aWD2.ustart, aWD2.vstart);
        wd2.push_back (aWD2);
      }
      ComputeCloseLine(Umult,Vmult,Pnts1,PntsInHoles,Func,Rajout);
    }
  }
  
  for (I = 1; I <= nbPnts1; I++) { 
    if (wd1[I].etat >0) seqSingle.Append(Pnts1(I));
  }
  done = Standard_True;
}



//
// Perform without interior point
//

void IntWalk_IWalking::Perform(const ThePOPIterator& Pnts1,
			       TheIWFunction& Func,
			       const ThePSurface& Caro,
			       const Standard_Boolean Reversed)

{
  Standard_Integer I;
  Standard_Boolean Rajout = Standard_False;
  Standard_Integer nbPnts1 = Pnts1.Length();
  Standard_Real U,V;

  reversed = Reversed;


  // Loading of etat1 as well as ustart1 and vstart1.

  TColStd_SequenceOfReal Umult;
  TColStd_SequenceOfReal Vmult;

  wd1.reserve (nbPnts1);
  for (I=1;I <= nbPnts1; I++) {
    const ThePointOfPath& PathPnt = Pnts1.Value(I);
    IntWalk_WalkingData aWD1;
    aWD1.etat = 1;
    if (!ThePointOfPathTool::IsPassingPnt(PathPnt)) aWD1.etat = 11; 
    if (!ThePointOfPathTool::IsTangent(PathPnt))   ++aWD1.etat;
    ThePointOfPathTool::Value2d(PathPnt, aWD1.ustart, aWD1.vstart);
    wd1.push_back (aWD1);
    Standard_Integer aNbMult = ThePointOfPathTool::Multiplicity(PathPnt);
    nbMultiplicities.push_back(aNbMult);

    for (Standard_Integer J = 1; J <= aNbMult; J++) {
      ThePointOfPathTool::Parameters(PathPnt, J, U, V);
      Umult.Append(U);
      Vmult.Append(V);
    }
  }

  tolerance(1) = ThePSurfaceTool::UResolution(Caro,Precision::Confusion());
  tolerance(2) = ThePSurfaceTool::VResolution(Caro,Precision::Confusion());

  Um = ThePSurfaceTool::FirstUParameter(Caro);
  Vm = ThePSurfaceTool::FirstVParameter(Caro);
  UM = ThePSurfaceTool::LastUParameter(Caro);
  VM = ThePSurfaceTool::LastVParameter(Caro);

  if (UM < Um) {
    Standard_Real utemp = UM;
    UM = Um;
    Um = utemp;
  }
  if (VM < Vm) {
    Standard_Real vtemp = VM;
    VM = Vm;
    Vm = vtemp;
  }

  Func.Set(Caro);

  // calcul de toutes les lignes ouvertes   
  if (nbPnts1 != 0) ComputeOpenLine(Umult,Vmult,Pnts1,Func,Rajout); 

  for (I = 1; I <= nbPnts1; I++) { 
    if (wd1[I].etat >0) seqSingle.Append(Pnts1(I));
  }
  done = Standard_True;
}