src/BOPDS/BOPDS_DS.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 1999-2012 OPEN CASCADE SAS
   3 //
   4 // The content of this file is subject to the Open CASCADE Technology Public
   5 // License Version 6.5 (the "License"). You may not use the content of this file
   6 // except in compliance with the License. Please obtain a copy of the License
   7 // at http://www.opencascade.org and read it completely before using this file.
   8 //
   9 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
  10 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  11 //
  12 // The Original Code and all software distributed under the License is
  13 // distributed on an "AS IS" basis, without warranty of any kind, and the
  14 // Initial Developer hereby disclaims all such warranties, including without
  15 // limitation, any warranties of merchantability, fitness for a particular
  16 // purpose or non-infringement. Please see the License for the specific terms
  17 // and conditions governing the rights and limitations under the License.
  18
  19
  20 #include <BOPDS_DS.ixx>
  21 //
  22 #include <NCollection_IncAllocator.hxx>
  23 #include <NCollection_BaseAllocator.hxx>
  24
  25 #include <gp_Pnt.hxx>
  26 #include <Bnd_Box.hxx>
  27 //
  28 #include <TopoDS_Shape.hxx>
  29 #include <TopoDS_Iterator.hxx>
  30 #include <TopoDS_Vertex.hxx>
  31 #include <TopoDS_Edge.hxx>
  32 #include <TopoDS_Face.hxx>
  33 #include <BRep_Tool.hxx>
  34 //
  35 #include <BRepBndLib.hxx>
  36 //
  37 #include <BOPCol_MapOfInteger.hxx>
  38 #include <BOPCol_ListOfInteger.hxx>
  39 #include <BOPCol_DataMapOfShapeInteger.hxx>
  40 //
  41 #include <BOPDS_IndexRange.hxx>
  42 #include <BOPDS_ShapeInfo.hxx>
  43 #include <BOPDS_PassKey.hxx>
  44 #include <BOPDS_DataMapOfPassKeyListOfPaveBlock.hxx>
  45 #include <BOPDS_PassKey.hxx>
  46
  47 #include <Geom_Curve.hxx>
  48 #include <BRep_Builder.hxx>
  49 #include <Precision.hxx>
  50 #include <IntTools_Tools.hxx>
  51 #include <BOPTools_AlgoTools.hxx>
  52 #include <GeomAPI_ProjectPointOnCurve.hxx>
  53 #include <BOPDS_MapOfPave.hxx>
  54
  55 //
  56 static
  57   inline void ResetShape(const TopoDS_Shape& aS);
  58
  59 static
  60   inline void ResetShapes(const TopoDS_Shape& aS);
  61
  62 static
  63   void TotalShapes(const TopoDS_Shape& aS,
  64                    Standard_Integer& aNbS);
  65
  66 static
  67   Standard_Real ComputeParameter(const TopoDS_Vertex& aV,
  68                                  const TopoDS_Edge& aE);
  69 static
  70   void SortShell(const int n, BOPDS_Pave *a);
  71
  72 //=======================================================================
  73 //function :
  74 //purpose  :
  75 //=======================================================================
  76   BOPDS_DS::BOPDS_DS()
  77 :
  78   myAllocator(NCollection_BaseAllocator::CommonBaseAllocator()),
  79   myArguments(myAllocator),
  80   myRanges(myAllocator),
  81   myLines(myAllocator),
  82   myMapShapeIndex(100, myAllocator),
  83   myPaveBlocksPool(myAllocator),
  84   myFaceInfoPool(myAllocator),
  85   myShapesSD(100, myAllocator),
  86   myMapPBCB(100, myAllocator),
  87   myInterfTB(100, myAllocator),
  88   myInterfVV(myAllocator),
  89   myInterfVE(myAllocator),
  90   myInterfVF(myAllocator),
  91   myInterfEE(myAllocator),
  92   myInterfEF(myAllocator),
  93   myInterfFF(myAllocator)
  94 {
  95   myNbShapes=0;
  96   myNbSourceShapes=0;
  97 }
  98 //=======================================================================
  99 //function :
 100 //purpose  :
 101 //=======================================================================
 102   BOPDS_DS::BOPDS_DS(const Handle(NCollection_BaseAllocator)& theAllocator)
 103 :
 104   myAllocator(theAllocator),
 105   myArguments(myAllocator),
 106   myRanges(myAllocator),
 107   myLines(myAllocator),
 108   myMapShapeIndex(100, myAllocator),
 109   myPaveBlocksPool(myAllocator),
 110   myFaceInfoPool(myAllocator),
 111   myShapesSD(100, myAllocator),
 112   myMapPBCB(100, myAllocator),
 113   myInterfTB(100, myAllocator),
 114   myInterfVV(myAllocator),
 115   myInterfVE(myAllocator),
 116   myInterfVF(myAllocator),
 117   myInterfEE(myAllocator),
 118   myInterfEF(myAllocator),
 119   myInterfFF(myAllocator)
 120 {
 121   myNbShapes=0;
 122   myNbSourceShapes=0;
 123 }
 124 //=======================================================================
 125 //function : ~
 126 //purpose  :
 127 //=======================================================================
 128   BOPDS_DS::~BOPDS_DS()
 129 {
 130   Clear();
 131 }
 132 //=======================================================================
 133 //function : Clear
 134 //purpose  :
 135 //=======================================================================
 136   void BOPDS_DS::Clear()
 137 {
 138   myNbShapes=0;
 139   myNbSourceShapes=0;
 140   //
 141   myArguments.Clear();
 142   myRanges.Clear();
 143   myLines.Clear();
 144   myMapShapeIndex.Clear();
 145   myPaveBlocksPool.Clear();
 146   myFaceInfoPool.Clear();
 147   myShapesSD.Clear();
 148   myMapPBCB.Clear();
 149   myInterfTB.Clear();
 150   myInterfVV.Clear();
 151   myInterfVE.Clear();
 152   myInterfVF.Clear();
 153   myInterfEE.Clear();
 154   myInterfEF.Clear();
 155   myInterfFF.Clear();
 156 }
 157 //=======================================================================
 158 //function : SetArguments
 159 //purpose  :
 160 //=======================================================================
 161   void BOPDS_DS::SetArguments(const BOPCol_ListOfShape& theLS)
 162 {
 163   myArguments=theLS;
 164 }
 165 //=======================================================================
 166 //function : Arguments
 167 //purpose  :
 168 //=======================================================================
 169   const BOPCol_ListOfShape& BOPDS_DS::Arguments()const
 170 {
 171   return myArguments;
 172 }
 173 //=======================================================================
 174 //function : Allocator
 175 //purpose  :
 176 //=======================================================================
 177   const Handle(NCollection_BaseAllocator)& BOPDS_DS::Allocator()const
 178 {
 179   return myAllocator;
 180 }
 181
 182 //=======================================================================
 183 //function : NbShapes
 184 //purpose  :
 185 //=======================================================================
 186   Standard_Integer BOPDS_DS::NbShapes()const
 187 {
 188   return myLines.Size();
 189 }
 190 //=======================================================================
 191 //function : NbSourceShapes
 192 //purpose  :
 193 //=======================================================================
 194   Standard_Integer BOPDS_DS::NbSourceShapes()const
 195 {
 196   return myNbSourceShapes;
 197 }
 198 //=======================================================================
 199 //function : NbRanges
 200 //purpose  :
 201 //=======================================================================
 202   Standard_Integer BOPDS_DS::NbRanges()const
 203 {
 204   return myRanges.Size();
 205 }
 206 //=======================================================================
 207 //function : Range
 208 //purpose  :
 209 //=======================================================================
 210   const BOPDS_IndexRange& BOPDS_DS::Range(const Standard_Integer theI)const
 211 {
 212   return myRanges(theI);
 213 }
 214 //=======================================================================
 215 //function : Rank
 216 //purpose  :
 217 //=======================================================================
 218   Standard_Integer BOPDS_DS::Rank(const Standard_Integer theI)const
 219 {
 220   Standard_Integer i, aNb, iErr;
 221   //
 222   iErr=-1;
 223   aNb=NbRanges();
 224   for(i=0; i<aNb; ++i) {
 225     const BOPDS_IndexRange& aR=Range(i);
 226     if (aR.Contains(theI)) {
 227       return i;
 228     }
 229   }
 230   return iErr;
 231 }
 232 //=======================================================================
 233 //function : IsNewShape
 234 //purpose  :
 235 //=======================================================================
 236   Standard_Boolean BOPDS_DS::IsNewShape(const Standard_Integer theI)const
 237 {
 238   return theI>=NbSourceShapes();
 239 }
 240 //=======================================================================
 241 //function : Append
 242 //purpose  :
 243 //=======================================================================
 244   Standard_Integer BOPDS_DS::Append(const BOPDS_ShapeInfo& theSI)
 245 {
 246   Standard_Integer iX;
 247   //
 248   iX=myLines.Append()-1;
 249   myLines(iX)=theSI;
 250   return iX;
 251 }
 252 //=======================================================================
 253 //function : Append
 254 //purpose  :
 255 //=======================================================================
 256   Standard_Integer BOPDS_DS::Append(const TopoDS_Shape& theS)
 257 {
 258   Standard_Integer iX;
 259   //
 260   iX=myLines.Append()-1;
 261   myLines(iX).SetShape(theS);
 262   return iX;
 263 }
 264 //=======================================================================
 265 //function : ShapeInfo
 266 //purpose  :
 267 //=======================================================================
 268   const BOPDS_ShapeInfo& BOPDS_DS::ShapeInfo(const Standard_Integer theI)const
 269 {
 270   return myLines(theI);
 271 }
 272 //=======================================================================
 273 //function : ChangeShapeInfo
 274 //purpose  :
 275 //=======================================================================
 276   BOPDS_ShapeInfo& BOPDS_DS::ChangeShapeInfo(const Standard_Integer theI)
 277 {
 278   BOPDS_ShapeInfo *pSI;
 279   //
 280   const BOPDS_ShapeInfo& aSI=ShapeInfo(theI);
 281   pSI=(BOPDS_ShapeInfo *)&aSI;
 282   return *pSI;
 283 }
 284 //=======================================================================
 285 //function : Shape
 286 //purpose  :
 287 //=======================================================================
 288   const TopoDS_Shape& BOPDS_DS::Shape(const Standard_Integer theI)const
 289 {
 290   const TopoDS_Shape& aS=ShapeInfo(theI).Shape();
 291   return aS;
 292 }
 293 //=======================================================================
 294 //function : Index
 295 //purpose  :
 296 //=======================================================================
 297   Standard_Integer BOPDS_DS::Index(const TopoDS_Shape& theS)const
 298 {
 299   Standard_Integer iRet;
 300   //
 301   iRet=-1;
 302   if (myMapShapeIndex.IsBound(theS)) {
 303     iRet=myMapShapeIndex.Find(theS);
 304   }
 305   return iRet;
 306 }
 307
 308 //=======================================================================
 309 //function : Init
 310 //purpose  :
 311 //=======================================================================
 312   void BOPDS_DS::Init()
 313 {
 314   Standard_Integer i1, i2, j, aI, aNb, aNbS, aNbE, aNbSx, nV, nW, nE, aNbF;
 315   Standard_Real aTol;
 316   TopAbs_ShapeEnum aTS;
 317   BOPCol_ListIteratorOfListOfInteger aIt1, aIt2, aIt3;
 318   BOPCol_ListIteratorOfListOfShape aIt;
 319   BOPDS_IndexRange aR;
 320   Handle(NCollection_IncAllocator) aAllocator;
 321   //
 322   // 1 Append Source Shapes
 323   aNb=myArguments.Extent();
 324   if (!aNb) {
 325     return;
 326   }
 327   //
 328   myRanges.SetStartSize(aNb);
 329   myRanges.Init();
 330   //
 331   aIt.Initialize(myArguments);
 332   for (; aIt.More(); aIt.Next()) {
 333     const TopoDS_Shape& aSx=aIt.Value();
 334     ResetShapes(aSx);
 335   }
 336   //
 337   aNbS=0;
 338   aIt.Initialize(myArguments);
 339   for (; aIt.More(); aIt.Next()) {
 340     const TopoDS_Shape& aSx=aIt.Value();
 341     //
 342     aNbSx=0;
 343     TotalShapes(aSx, aNbSx);
 344     aNbS=aNbS+aNbSx;
 345   }
 346   //
 347   myLines.SetStartSize(2*aNbS);
 348   myLines.SetIncrement(aNbS);
 349   myLines.Init();
 350   //
 351   //-----------------------------------------------------scope_1 f
 352   aAllocator=new NCollection_IncAllocator();
 353   //
 354   BOPCol_DataMapOfShapeInteger& aMSI=myMapShapeIndex;
 355   //
 356   i1=0;
 357   i2=0;
 358   aIt.Initialize(myArguments);
 359   for (; aIt.More(); aIt.Next()) {
 360     const TopoDS_Shape& aS=aIt.Value();
 361     aI=Append(aS);
 362     aMSI.Bind(aS, aI);
 363     //
 364     InitShape(aI, aS, aAllocator, aMSI);
 365     //
 366     i2=NbShapes()-1;
 367     aR.SetIndices(i1, i2);
 368     myRanges.Append(aR);
 369     i1=i2+1;
 370   }
 371   //
 372   //aMSI.Clear();
 373   //
 374   myNbSourceShapes=NbShapes();
 375   //
 376   // 2 Bounding Boxes
 377   //
 378   // 2.1 Vertex
 379   for (j=0; j<myNbSourceShapes; ++j) {
 380     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
 381     //
 382     const TopoDS_Shape& aS=aSI.Shape();
 383     ResetShape(aS);
 384     //
 385     aTS=aSI.ShapeType();
 386     //
 387     if (aTS==TopAbs_VERTEX) {
 388       Bnd_Box& aBox=aSI.ChangeBox();
 389       const TopoDS_Vertex& aV=*((TopoDS_Vertex*)&aS);
 390       const gp_Pnt& aP=BRep_Tool::Pnt(aV);
 391       aTol=BRep_Tool::Tolerance(aV);
 392       aBox.SetGap(aTol);
 393       aBox.Add(aP);
 394     }
 395   }
 396   // 2.2 Edge
 397   aNbE=0;
 398   for (j=0; j<myNbSourceShapes; ++j) {
 399     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
 400     //
 401     aTS=aSI.ShapeType();
 402     if (aTS==TopAbs_EDGE) {
 403       const TopoDS_Shape& aS=aSI.Shape();
 404       const TopoDS_Edge& aE=*((TopoDS_Edge*)&aS);
 405       aTol=BRep_Tool::Tolerance(aE);
 406       //
 407       if (!BRep_Tool::Degenerated(aE)) {
 408         Standard_Boolean bInf1, bInf2;
 409         Standard_Integer aIx;
 410         Standard_Real aT1, aT2;
 411         gp_Pnt aPx;
 412         Handle(Geom_Curve) aC3D;
 413         TopoDS_Vertex aVx;
 414         TopoDS_Edge aEx;
 415         BRep_Builder aBB;
 416         BOPDS_ShapeInfo aSIx;
 417         //
 418         BOPCol_ListOfInteger& aLI=aSI.ChangeSubShapes();
 419         //
 420         aEx=aE;
 421         aEx.Orientation(TopAbs_FORWARD);
 422         //
 423         aC3D=BRep_Tool::Curve (aEx, aT1, aT2);
 424         bInf1=Precision::IsNegativeInfinite(aT1);
 425         bInf2=Precision::IsPositiveInfinite(aT2);
 426         //
 427         if (bInf1) {
 428           aC3D->D0(aT1, aPx);
 429           aBB.MakeVertex(aVx, aPx, aTol);
 430           aVx.Orientation(TopAbs_FORWARD);
 431           //
 432           aSIx.SetShape(aVx);
 433           aSIx.SetShapeType(TopAbs_VERTEX);
 434           aSIx.SetFlag(1); //infinite flag
 435           //
 436           aIx=Append(aSIx);
 437           aLI.Append(aIx);
 438         }
 439         if (bInf2) {
 440           aC3D->D0(aT2, aPx);
 441           aBB.MakeVertex(aVx, aPx, aTol);
 442           aVx.Orientation(TopAbs_REVERSED);
 443           //
 444           aSIx.SetShape(aVx);
 445           aSIx.SetShapeType(TopAbs_VERTEX);
 446           aSIx.SetFlag(1);//infinite flag
 447           //
 448           aIx=Append(aSIx);
 449           aLI.Append(aIx);
 450         }
 451       }
 452       else {
 453         aSI.SetFlag(j);
 454       }
 455       //
 456       Bnd_Box& aBox=aSI.ChangeBox();
 457       BRepBndLib::Add(aE, aBox);
 458       //
 459       const BOPCol_ListOfInteger& aLV=aSI.SubShapes();
 460       aIt1.Initialize(aLV);
 461       for (; aIt1.More(); aIt1.Next()) {
 462         nV=aIt1.Value();
 463         BOPDS_ShapeInfo& aSIV=ChangeShapeInfo(nV);
 464         Bnd_Box& aBx=aSIV.ChangeBox();
 465         aBox.Add(aBx);
 466       }
 467       ++aNbE;
 468     }
 469   }
 470   // 2.3 Face
 471   BOPCol_MapOfInteger aMI(100, aAllocator);
 472   BOPCol_MapIteratorOfMapOfInteger aItMI;
 473   //
 474   aNbF=0;
 475   for (j=0; j<myNbSourceShapes; ++j) {
 476     BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
 477     //
 478     aTS=aSI.ShapeType();
 479     if (aTS==TopAbs_FACE) {
 480       const TopoDS_Shape& aS=aSI.Shape();
 481       const TopoDS_Face& aF=*((TopoDS_Face*)&aS);
 482       aTol=BRep_Tool::Tolerance(aF);
 483       //
 484       Bnd_Box& aBox=aSI.ChangeBox();
 485       BRepBndLib::Add(aS, aBox);
 486       //
 487       BOPCol_ListOfInteger& aLW=aSI.ChangeSubShapes();
 488       aIt1.Initialize(aLW);
 489       for (; aIt1.More(); aIt1.Next()) {
 490         nW=aIt1.Value();
 491         BOPDS_ShapeInfo& aSIW=ChangeShapeInfo(nW);
 492         //
 493         const BOPCol_ListOfInteger& aLE=aSIW.SubShapes();
 494         aIt2.Initialize(aLE);
 495         for (; aIt2.More(); aIt2.Next()) {
 496           nE=aIt2.Value();
 497           BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
 498           Bnd_Box& aBx=aSIE.ChangeBox();
 499           aBox.Add(aBx);
 500           aMI.Add(nE);
 501           //
 502           const TopoDS_Edge& aE=*(TopoDS_Edge*)(&aSIE.Shape());
 503           if (BRep_Tool::Degenerated(aE)) {
 504             aSIE.SetFlag(j);
 505           }
 506           //
 507           const BOPCol_ListOfInteger& aLV=aSIE.SubShapes();
 508           aIt3.Initialize(aLV);
 509           for (; aIt3.More(); aIt3.Next()) {
 510             nV=aIt3.Value();
 511             aMI.Add(nV);
 512           }
 513         }
 514       }//for (; aIt1.More(); aIt1.Next()) {
 515       //
 516       //
 517       // For a Face: change wires for BRep sub-shapes
 518       aLW.Clear();
 519       aItMI.Initialize(aMI);
 520       for (; aItMI.More(); aItMI.Next()) {
 521         nV=aItMI.Value();
 522         aLW.Append(nV);
 523       }
 524       aMI.Clear();
 525       ++aNbF;
 526     }//if (aTS==TopAbs_FACE) {
 527   }//for (j=0; j<myNbSourceShapes; ++j) {
 528   //
 529   aMI.Clear();
 530   aAllocator.Nullify();
 531   //-----------------------------------------------------scope_1 t
 532   //
 533   // 3 myPaveBlocksPool
 534   myPaveBlocksPool.SetStartSize(aNbE);
 535   myPaveBlocksPool.SetIncrement(aNbE);
 536   myPaveBlocksPool.Init();
 537   //
 538   // 4. myFaceInfoPool
 539   myFaceInfoPool.SetStartSize(aNbF);
 540   myFaceInfoPool.SetIncrement(aNbF);
 541   myFaceInfoPool.Init();
 542   //
 543 }
 544 //=======================================================================
 545 //function : InitShape
 546 //purpose  :
 547 //=======================================================================
 548   void BOPDS_DS::InitShape(const Standard_Integer aI,
 549                            const TopoDS_Shape& aS,
 550                            Handle(NCollection_BaseAllocator)& theAllocator,
 551                            BOPCol_DataMapOfShapeInteger& aMSI)
 552 {
 553   Standard_Integer aIx;
 554   TopoDS_Iterator aIt;
 555   BOPCol_ListIteratorOfListOfInteger aIt1;
 556   //
 557   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(aI);
 558   aSI.SetShapeType(aS.ShapeType());
 559   BOPCol_ListOfInteger& aLI=aSI.ChangeSubShapes();
 560   //
 561   BOPCol_MapOfInteger aM(100, theAllocator);
 562   //
 563   aIt1.Initialize(aLI);
 564   for (; aIt1.More(); aIt1.Next()) {
 565     aM.Add(aIt1.Value());
 566   }
 567   //
 568   aIt.Initialize(aS);
 569   for (; aIt.More(); aIt.Next()) {
 570     const TopoDS_Shape& aSx=aIt.Value();
 571     if (aMSI.IsBound(aSx)) {
 572       aIx=aMSI.Find(aSx);
 573     }
 574     else {
 575       aIx=Append(aSx);
 576       aMSI.Bind(aSx, aIx);
 577     }
 578     //
 579     InitShape(aIx, aSx, theAllocator, aMSI);
 580     //
 581     if (aM.Add(aIx)) {
 582       aLI.Append(aIx);
 583     }
 584   }
 585 }
 586
 587 //=======================================================================
 588 //function : HasInterf
 589 //purpose  :
 590 //=======================================================================
 591   Standard_Boolean BOPDS_DS::HasInterf(const Standard_Integer theI) const
 592 {
 593   Standard_Integer n1, n2;
 594   Standard_Boolean bRet;
 595   BOPDS_MapIteratorMapOfPassKey aIt;
 596   //
 597   bRet = Standard_False;
 598   //
 599   aIt.Initialize(myInterfTB);
 600   for (; aIt.More(); aIt.Next()) {
 601     const BOPDS_PassKey& aPK = aIt.Value();
 602     aPK.Ids(n1, n2);
 603     if (n1 == theI || n2 == theI) {
 604       bRet = Standard_True;
 605       break;
 606     }
 607   }
 608   //
 609   return bRet;
 610 }
 611
 612 //=======================================================================
 613 //function : HasInterfShapeSubShapes
 614 //purpose  :
 615 //=======================================================================
 616   Standard_Boolean BOPDS_DS::HasInterfShapeSubShapes(const Standard_Integer theI1,
 617                                                      const Standard_Integer theI2)const
 618 {
 619   Standard_Boolean bRet;
 620   Standard_Integer n2;
 621   BOPCol_ListIteratorOfListOfInteger aIt;
 622   bRet = Standard_False;
 623   //
 624   const BOPDS_ShapeInfo& aSI=ShapeInfo(theI2);
 625   const BOPCol_ListOfInteger& aLI=aSI.SubShapes();
 626   aIt.Initialize(aLI);
 627   for (; aIt.More(); aIt.Next()) {
 628     n2=aIt.Value();
 629     bRet=HasInterf(theI1, n2);
 630     if(bRet) {
 631       break;
 632     }
 633   }
 634   return bRet;
 635 }
 636
 637 //=======================================================================
 638 //function : HasInterfSubShapes
 639 //purpose  :
 640 //=======================================================================
 641   Standard_Boolean BOPDS_DS::HasInterfSubShapes(const Standard_Integer theI1,
 642                                                 const Standard_Integer theI2)const
 643 {
 644   Standard_Boolean bRet;
 645   Standard_Integer n1;
 646   BOPCol_ListIteratorOfListOfInteger aIt;
 647   bRet = Standard_False;
 648   //
 649   const BOPDS_ShapeInfo& aSI=ShapeInfo(theI1);
 650   const BOPCol_ListOfInteger& aLI=aSI.SubShapes();
 651   aIt.Initialize(aLI);
 652   for (; aIt.More(); aIt.Next()) {
 653     n1=aIt.Value();
 654     bRet=HasInterfShapeSubShapes(n1, theI2);
 655     if(bRet) {
 656       break;
 657     }
 658   }
 659   return bRet;
 660 }
 661 //
 662 // PaveBlocks
 663 //=======================================================================
 664 //function : PaveBlocksPool
 665 //purpose  :
 666 //=======================================================================
 667   const BOPDS_VectorOfListOfPaveBlock& BOPDS_DS::PaveBlocksPool()const
 668 {
 669   return myPaveBlocksPool;
 670 }
 671 //=======================================================================
 672 //function : ChangePaveBlocksPool
 673 //purpose  :
 674 //=======================================================================
 675   BOPDS_VectorOfListOfPaveBlock& BOPDS_DS::ChangePaveBlocksPool()
 676 {
 677   return myPaveBlocksPool;
 678 }
 679 //=======================================================================
 680 //function : HasPaveBlocks
 681 //purpose  :
 682 //=======================================================================
 683   Standard_Boolean BOPDS_DS::HasPaveBlocks(const Standard_Integer theI)const
 684 {
 685   return ShapeInfo(theI).HasReference();
 686 }
 687 //=======================================================================
 688 //function : PaveBlocks
 689 //purpose  :
 690 //=======================================================================
 691   const BOPDS_ListOfPaveBlock& BOPDS_DS::PaveBlocks(const Standard_Integer theI)const
 692 {
 693   static BOPDS_ListOfPaveBlock sLPB;
 694   Standard_Integer aRef;
 695   //
 696   if (HasPaveBlocks(theI)) {
 697     aRef=ShapeInfo(theI).Reference();
 698     const BOPDS_ListOfPaveBlock& aLPB=myPaveBlocksPool(aRef);
 699     return aLPB;
 700   }
 701   return sLPB;
 702 }
 703 //=======================================================================
 704 //function : ChangePaveBlocks
 705 //purpose  :
 706 //=======================================================================
 707   BOPDS_ListOfPaveBlock& BOPDS_DS::ChangePaveBlocks(const Standard_Integer theI)
 708 {
 709   Standard_Boolean bHasReference;
 710   Standard_Integer aRef;
 711   //
 712   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
 713   bHasReference=aSI.HasReference();
 714   if (!bHasReference) {
 715     InitPaveBlocks(theI);
 716   }
 717   //
 718   aRef=aSI.Reference();
 719   return myPaveBlocksPool(aRef);
 720 }
 721 //=======================================================================
 722 //function : InitPaveBlocks
 723 //purpose  :
 724 //=======================================================================
 725   void BOPDS_DS::InitPaveBlocks(const Standard_Integer theI)
 726 {
 727   Standard_Integer nV, iRef, aNbV, nVSD, i;
 728   Standard_Real aT;
 729   TopoDS_Vertex aV;
 730   BOPCol_ListIteratorOfListOfInteger aIt;
 731   BOPDS_Pave aPave;
 732   Handle(BOPDS_PaveBlock) aPB;
 733   //
 734   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
 735   const TopoDS_Edge& aE=*(TopoDS_Edge*)(&aSI.Shape());
 736   //
 737   const BOPCol_ListOfInteger& aLV=aSI.SubShapes();
 738   aNbV=aLV.Extent();
 739   if (!aNbV) {
 740     return;
 741   }
 742   //
 743   aPB=new BOPDS_PaveBlock;
 744   aPB->SetOriginalEdge(theI);
 745   //
 746   aIt.Initialize(aLV);
 747   for (i=0; aIt.More(); aIt.Next(), ++i) {
 748     nV=aIt.Value();
 749     //
 750     const BOPDS_ShapeInfo& aSIV=ShapeInfo(nV);
 751     aV=*(TopoDS_Vertex*)(&aSIV.Shape());
 752     if (aSIV.HasFlag()) {
 753       aT=ComputeParameter(aV, aE);
 754     }
 755     else {
 756       aT=BRep_Tool::Parameter(aV, aE);
 757     }
 758     //
 759     if (HasShapeSD(nV, nVSD)) {
 760       nV=nVSD;
 761     }
 762     aPave.SetIndex(nV);
 763     aPave.SetParameter(aT);
 764     aPB->AppendExtPave(aPave);
 765   }
 766   //
 767   if (aNbV==1) {
 768     aV.Reverse();
 769     aT=BRep_Tool::Parameter(aV, aE);
 770     aPave.SetIndex(nV);
 771     aPave.SetParameter(aT);
 772     aPB->AppendExtPave1(aPave);
 773   }
 774   //
 775   iRef = myPaveBlocksPool.Append() - 1;
 776   BOPDS_ListOfPaveBlock &aLPB=myPaveBlocksPool(iRef);
 777   //
 778   aPB->Update(aLPB, Standard_False);
 779   aSI.SetReference(iRef);
 780 }
 781 //=======================================================================
 782 //function : UpdatePaveBlocks
 783 //purpose  :
 784 //=======================================================================
 785   void BOPDS_DS::UpdatePaveBlocks()
 786 {
 787   Standard_Boolean bIsToUpdate;
 788   Standard_Integer i, aNbPBP;
 789   BOPDS_ListOfPaveBlock aLPBN(myAllocator);
 790   BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBN;
 791   //
 792   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
 793   //
 794   aNbPBP=aPBP.Size();
 795   for (i=0; i<aNbPBP; ++i) {
 796     BOPDS_ListOfPaveBlock& aLPB=aPBP(i);
 797     //
 798     aItPB.Initialize(aLPB);
 799     for (; aItPB.More(); aItPB.Next()) {
 800       Handle(BOPDS_PaveBlock)& aPB=aItPB.ChangeValue();
 801       //
 802       bIsToUpdate=aPB->IsToUpdate();
 803       if (bIsToUpdate){
 804         aLPBN.Clear();
 805         aPB->Update(aLPBN);
 806
 807         aItPBN.Initialize(aLPBN);
 808         for (; aItPBN.More(); aItPBN.Next()) {
 809           Handle(BOPDS_PaveBlock)& aPBN=aItPBN.ChangeValue();
 810           aLPB.Append(aPBN);
 811         }
 812         aLPB.Remove(aItPB);
 813       }
 814     }// for (; aItPB.More(); aItPB.Next()) {
 815   }// for (i=0; i<aNbPBP; ++i) {
 816 }
 817 //=======================================================================
 818 //function : UpdatePaveBlock
 819 //purpose  :
 820 //=======================================================================
 821   void BOPDS_DS::UpdatePaveBlock(const Handle(BOPDS_PaveBlock)& thePB)
 822 {
 823   if (!thePB->IsToUpdate()){
 824     return;
 825   }
 826   //
 827   Standard_Integer nE, iRef;
 828   BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBN;
 829   BOPDS_ListOfPaveBlock aLPBN(myAllocator);
 830   Handle(BOPDS_PaveBlock) aPB;
 831   //
 832   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
 833   //
 834   nE=thePB->OriginalEdge();
 835   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(nE);
 836   iRef=aSI.Reference();
 837   BOPDS_ListOfPaveBlock& aLPB=aPBP(iRef);
 838   //
 839   aItPB.Initialize(aLPB);
 840   for (; aItPB.More(); aItPB.Next()) {
 841     aPB=aItPB.ChangeValue();
 842     if (aPB==thePB) {
 843       aPB->Update(aLPBN);
 844       //
 845       aItPBN.Initialize(aLPBN);
 846       for (; aItPBN.More(); aItPBN.Next()) {
 847         Handle(BOPDS_PaveBlock)& aPBN=aItPBN.ChangeValue();
 848         aLPB.Append(aPBN);
 849       }
 850       aLPB.Remove(aItPB);
 851       break;
 852     }
 853   }
 854 }
 855 //=======================================================================
 856 //function : UpdateCommonBlock
 857 //purpose  :
 858 //=======================================================================
 859   void BOPDS_DS::UpdateCommonBlock(const Handle(BOPDS_CommonBlock)& theCB)
 860 {
 861   Standard_Integer nE, iRef, n1, n2;
 862   BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBCB, aItPBN;
 863   BOPDS_DataMapIteratorOfDataMapOfPassKeyListOfPaveBlock aItMPKLPB;
 864   BOPDS_ListOfPaveBlock aLPBN;
 865   BOPDS_DataMapOfPassKeyListOfPaveBlock aMPKLPB;
 866   Handle(BOPDS_PaveBlock) aPB;
 867   Handle(BOPDS_CommonBlock) aCBx;
 868   BOPDS_PassKey aPK;
 869   //
 870   const BOPDS_ListOfPaveBlock& aLPBCB=theCB->PaveBlocks();
 871   if (!aLPBCB.First()->IsToUpdate()){
 872     return;
 873   }
 874   //
 875   const BOPCol_ListOfInteger& aLF=theCB->Faces();
 876   //
 877   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
 878   //
 879   aItPBCB.Initialize(aLPBCB);
 880   for (; aItPBCB.More(); aItPBCB.Next()) {
 881     const Handle(BOPDS_PaveBlock)& aPBCB=aItPBCB.ChangeValue();
 882     //
 883     nE=aPBCB->OriginalEdge();
 884     iRef=ChangeShapeInfo(nE).Reference();
 885     BOPDS_ListOfPaveBlock& aLPB=aPBP(iRef);
 886     //
 887     aItPB.Initialize(aLPB);
 888     for (; aItPB.More(); aItPB.Next()) {
 889       aPB=aItPB.ChangeValue();
 890       if (aPB==aPBCB) {
 891         //
 892         aLPBN.Clear();
 893         aPB->Update(aLPBN);
 894         //
 895         aItPBN.Initialize(aLPBN);
 896         for (; aItPBN.More(); aItPBN.Next()) {
 897           Handle(BOPDS_PaveBlock)& aPBN=aItPBN.ChangeValue();
 898           aLPB.Append(aPBN);
 899           //
 900           aPBN->Indices(n1, n2);
 901           aPK.SetIds(n1, n2);
 902           if (aMPKLPB.IsBound(aPK)) {
 903             BOPDS_ListOfPaveBlock& aLPBx=aMPKLPB.ChangeFind(aPK);
 904             aLPBx.Append(aPBN);
 905           }
 906           else {
 907             BOPDS_ListOfPaveBlock aLPBx;
 908             aLPBx.Append(aPBN);
 909             aMPKLPB.Bind(aPK, aLPBx);
 910           }
 911         }
 912         aLPB.Remove(aItPB);
 913         break;
 914       }
 915     }
 916   }
 917   //
 918   aItMPKLPB.Initialize(aMPKLPB);
 919   for (; aItMPKLPB.More(); aItMPKLPB.Next()) {
 920     BOPDS_ListOfPaveBlock& aLPBx=aItMPKLPB.ChangeValue();
 921     //
 922     while (aLPBx.Extent()) {
 923       Standard_Boolean bCoinside;
 924       Standard_Real aTol, aTolMax(0.);
 925       BOPDS_ListOfPaveBlock aLPBxN;
 926       //
 927       aItPB.Initialize(aLPBx);
 928       for(; aItPB.More(); ) {
 929         const Handle(BOPDS_PaveBlock)& aPBx=aItPB.Value();
 930         if (aLPBxN.Extent()) {
 931           const Handle(BOPDS_PaveBlock)& aPBCx = aLPBxN.First();
 932           bCoinside = CheckCoincidence(aPBx, aPBCx);
 933           if (bCoinside) {
 934             nE = aPBx->OriginalEdge();
 935             const TopoDS_Edge& aE = *(TopoDS_Edge*)&Shape(nE);
 936             aTol = BRep_Tool::Tolerance(aE);
 937             //
 938             //pave block with the max tolerance of the original edge
 939             //must be the first in the common block
 940             if (aTolMax < aTol) {
 941               aTolMax = aTol;
 942               aLPBxN.Prepend(aPBx);
 943             } else {
 944               aLPBxN.Append(aPBx);
 945             }
 946             aLPBx.Remove(aItPB);
 947             continue;
 948           }//if (bCoinside) {
 949         }//if (aLPBxN.Extent()) {
 950         else {
 951           nE = aPBx->OriginalEdge();
 952           const TopoDS_Edge& aE = *(TopoDS_Edge*)&Shape(nE);
 953           aTolMax = BRep_Tool::Tolerance(aE);
 954           //
 955           aLPBxN.Append(aPBx);
 956           aLPBx.Remove(aItPB);
 957           continue;
 958         }
 959         aItPB.Next();
 960       }//for(; aItPB.More(); ) {
 961       //
 962       aCBx=new BOPDS_CommonBlock;
 963       aCBx->AddPaveBlocks(aLPBxN);
 964       aCBx->AddFaces(aLF);
 965       //
 966       aItPB.Initialize(aLPBxN);
 967       for (; aItPB.More(); aItPB.Next()) {
 968         aPB=aItPB.ChangeValue();
 969         SetCommonBlock(aPB, aCBx);
 970       }
 971     }
 972   }
 973 }
 974
 975 //=======================================================================
 976 // function: RealPaveBlock
 977 // purpose:
 978 //=======================================================================
 979   Handle(BOPDS_PaveBlock) BOPDS_DS::RealPaveBlock
 980     (const Handle(BOPDS_PaveBlock)& thePB) const
 981 {
 982   if (IsCommonBlock(thePB)) {
 983     const Handle(BOPDS_CommonBlock)& aCB = CommonBlock(thePB);
 984     const Handle(BOPDS_PaveBlock)& aPB = aCB->PaveBlock1();
 985     return aPB;
 986   }
 987   return thePB;
 988 }
 989
 990 //=======================================================================
 991 // function: IsCommonBlockOnEdge
 992 // purpose:
 993 //=======================================================================
 994   Standard_Boolean BOPDS_DS::IsCommonBlockOnEdge
 995     (const Handle(BOPDS_PaveBlock)& thePB) const
 996 {
 997   if (IsCommonBlock(thePB)) {
 998     const Handle(BOPDS_CommonBlock)& aCB = CommonBlock(thePB);
 999     return aCB->PaveBlocks().Extent()>1;
1000   }
1001   return Standard_False;
1002 }
1003
1004 //=======================================================================
1005 //function : IsCommonBlock
1006 //purpose  :
1007 //=======================================================================
1008   Standard_Boolean BOPDS_DS::IsCommonBlock
1009     (const Handle(BOPDS_PaveBlock)& thePB) const
1010 {
1011   return myMapPBCB.IsBound(thePB);
1012 }
1013
1014 //=======================================================================
1015 //function : CommonBlock
1016 //purpose  :
1017 //=======================================================================
1018   const Handle(BOPDS_CommonBlock)& BOPDS_DS::CommonBlock
1019     (const Handle(BOPDS_PaveBlock)& thePB) const
1020 {
1021   Handle(BOPDS_CommonBlock) aNullCB;
1022   //
1023   const Handle(BOPDS_CommonBlock)& aCB =
1024     IsCommonBlock(thePB) ? myMapPBCB.Find(thePB) : aNullCB;
1025   //
1026   return aCB;
1027 }
1028
1029 //=======================================================================
1030 //function : SetCommonBlock
1031 //purpose  :
1032 //=======================================================================
1033   void BOPDS_DS::SetCommonBlock(const Handle(BOPDS_PaveBlock)& thePB,
1034                                 const Handle(BOPDS_CommonBlock)& theCB)
1035 {
1036   if (IsCommonBlock(thePB)) {
1037     Handle(BOPDS_CommonBlock)& aCB = myMapPBCB.ChangeFind(thePB);
1038     aCB=theCB;
1039   }
1040   else {
1041     myMapPBCB.Bind(thePB, theCB);
1042   }
1043 }
1044
1045 //
1046 // FaceInfo
1047 //
1048
1049 //=======================================================================
1050 //function : FaceInfoPool
1051 //purpose  :
1052 //=======================================================================
1053   const BOPDS_VectorOfFaceInfo& BOPDS_DS::FaceInfoPool()const
1054 {
1055   return myFaceInfoPool;
1056 }
1057 //=======================================================================
1058 //function : HasFaceInfo
1059 //purpose  :
1060 //=======================================================================
1061   Standard_Boolean BOPDS_DS::HasFaceInfo(const Standard_Integer theI)const
1062 {
1063   return ShapeInfo(theI).HasReference();
1064 }
1065 //=======================================================================
1066 //function : FaceInfo
1067 //purpose  :
1068 //=======================================================================
1069   const BOPDS_FaceInfo& BOPDS_DS::FaceInfo(const Standard_Integer theI)const
1070 {
1071   static BOPDS_FaceInfo sFI;
1072   Standard_Integer aRef;
1073   //
1074   if (HasFaceInfo(theI)) {
1075     aRef=ShapeInfo(theI).Reference();
1076     const BOPDS_FaceInfo& aFI=myFaceInfoPool(aRef);
1077     return aFI;
1078   }
1079   return sFI;
1080 }
1081 //=======================================================================
1082 //function : ChangeFaceInfo
1083 //purpose  :
1084 //=======================================================================
1085   BOPDS_FaceInfo& BOPDS_DS::ChangeFaceInfo(const Standard_Integer theI)
1086 {
1087   Standard_Boolean bHasReference;
1088   Standard_Integer aRef;
1089   BOPDS_FaceInfo* pFI;
1090   //
1091   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1092   bHasReference=aSI.HasReference();
1093   if (!bHasReference) {
1094     InitFaceInfo(theI);
1095   }
1096   //
1097   aRef=aSI.Reference();
1098   const BOPDS_FaceInfo& aFI=myFaceInfoPool(aRef);
1099   pFI=(BOPDS_FaceInfo*)&aFI;
1100   return *pFI;
1101 }
1102 //=======================================================================
1103 //function : InitFaceInfo
1104 //purpose  :
1105 //=======================================================================
1106   void BOPDS_DS::InitFaceInfo(const Standard_Integer theI)
1107 {
1108   Standard_Integer iRef;
1109   //
1110   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1111   iRef=myFaceInfoPool.Append()-1;
1112   BOPDS_FaceInfo &aFI=myFaceInfoPool(iRef);
1113   aSI.SetReference(iRef);
1114   //
1115   aFI.SetIndex(theI);
1116   UpdateFaceInfoIn(theI);
1117   UpdateFaceInfoOn(theI);
1118 }
1119 //=======================================================================
1120 //function : UpdateFaceInfoIn
1121 //purpose  :
1122 //=======================================================================
1123   void BOPDS_DS::UpdateFaceInfoIn(const Standard_Integer theI)
1124 {
1125   Standard_Integer iRef;
1126   //
1127   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1128   if (aSI.HasReference()) {
1129     iRef=aSI.Reference();
1130     BOPDS_FaceInfo &aFI=myFaceInfoPool(iRef);
1131     //
1132     BOPDS_IndexedMapOfPaveBlock& aMPBIn=aFI.ChangePaveBlocksIn();
1133     BOPCol_MapOfInteger& aMVIn=aFI.ChangeVerticesIn();
1134     aMPBIn.Clear();
1135     aMVIn.Clear();
1136     FaceInfoIn(theI, aMPBIn, aMVIn);
1137   }
1138 }
1139 //=======================================================================
1140 //function : UpdateFaceInfoOn
1141 //purpose  :
1142 //=======================================================================
1143   void BOPDS_DS::UpdateFaceInfoOn(const Standard_Integer theI)
1144 {
1145   Standard_Integer iRef;
1146   //
1147   BOPDS_ShapeInfo& aSI=ChangeShapeInfo(theI);
1148   if (aSI.HasReference()) {
1149     iRef=aSI.Reference();
1150     BOPDS_FaceInfo &aFI=myFaceInfoPool(iRef);
1151     //
1152     BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.ChangePaveBlocksOn();
1153     BOPCol_MapOfInteger& aMVOn=aFI.ChangeVerticesOn();
1154     aMPBOn.Clear();
1155     aMVOn.Clear();
1156     FaceInfoOn(theI, aMPBOn, aMVOn);
1157   }
1158 }
1159 //=======================================================================
1160 //function : FaceInfoOn
1161 //purpose  :
1162 //=======================================================================
1163   void BOPDS_DS::FaceInfoOn(const Standard_Integer theF,
1164                             BOPDS_IndexedMapOfPaveBlock& theMPB,
1165                             BOPCol_MapOfInteger& theMI)
1166 {
1167   Standard_Integer nS, nSD, nV1, nV2;
1168   BOPCol_ListIteratorOfListOfInteger aIt;
1169   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
1170   //
1171   const BOPDS_ShapeInfo& aSI=ShapeInfo(theF);
1172   const BOPCol_ListOfInteger& aLI=aSI.SubShapes();
1173   aIt.Initialize(aLI);
1174   for (; aIt.More(); aIt.Next()) {
1175     nS=aIt.Value();
1176     const BOPDS_ShapeInfo& aSIE=ShapeInfo(nS);
1177     if (aSIE.ShapeType()==TopAbs_EDGE) {
1178       const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nS);
1179       aItPB.Initialize(aLPB);
1180       for (; aItPB.More(); aItPB.Next()) {
1181         const Handle(BOPDS_PaveBlock)& aPB=aItPB.Value();
1182         aPB->Indices(nV1, nV2);
1183         theMI.Add(nV1);
1184         theMI.Add(nV2);
1185         Handle(BOPDS_PaveBlock) aPBR=RealPaveBlock(aPB);
1186         theMPB.Add(aPBR);
1187       }
1188     }//if (aSIE.ShapeType()==TopAbs_EDGE)
1189     else {
1190       // nE is TopAbs_VERTEX
1191       if (HasShapeSD(nS, nSD)) {
1192         nS=nSD;
1193       }
1194       theMI.Add(nS);
1195     }
1196   }
1197 }
1198 //=======================================================================
1199 //function : FaceInfoIn
1200 //purpose  :
1201 //=======================================================================
1202   void BOPDS_DS::FaceInfoIn(const Standard_Integer theF,
1203                             BOPDS_IndexedMapOfPaveBlock& theMPB,
1204                             BOPCol_MapOfInteger& theMI)
1205 {
1206   Standard_Integer i, aNbVF, aNbEF, nV, nE;
1207   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
1208   //
1209   BOPDS_VectorOfInterfVF& aVFs=InterfVF();
1210   aNbVF=aVFs.Extent();
1211   for (i=0; i<aNbVF; ++i) {
1212     BOPDS_InterfVF& aVF=aVFs(i);
1213     if(aVF.Contains(theF)) {
1214       nV=aVF.OppositeIndex(theF);
1215       theMI.Add(nV);
1216     }
1217   }
1218   //
1219   BOPDS_VectorOfInterfEF& aEFs=InterfEF();
1220   aNbEF=aEFs.Extent();
1221   for (i=0; i<aNbEF; ++i) {
1222     BOPDS_InterfEF& aEF=aEFs(i);
1223     if(aEF.Contains(theF)) {
1224       if(aEF.HasIndexNew(nV)) {
1225         theMI.Add(nV);
1226       }
1227       else {
1228         nE=aEF.OppositeIndex(theF);
1229         const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nE);
1230         aItPB.Initialize(aLPB);
1231         for (; aItPB.More(); aItPB.Next()) {
1232           const Handle(BOPDS_PaveBlock)& aPB=aItPB.Value();
1233           if (IsCommonBlock(aPB)) {
1234             const Handle(BOPDS_CommonBlock)& aCB=CommonBlock(aPB);
1235             if (aCB->Contains(theF)) {
1236               const Handle(BOPDS_PaveBlock)& aPB1=aCB->PaveBlock1();
1237               theMPB.Add(aPB1);
1238             }
1239           }
1240         }// for (; aItPB.More(); aItPB.Next()) {
1241       }// else {
1242     }// if(aEF.Contains(theF)) {
1243   }// for (i=0; i<aNbEF; ++i) {
1244 }
1245
1246 //=======================================================================
1247 //function : RefineFaceInfoOn
1248 //purpose  :
1249 //=======================================================================
1250   void BOPDS_DS::RefineFaceInfoOn()
1251 {
1252   Standard_Integer i, aNb, nF, aNbPB, j;
1253   BOPDS_IndexedMapOfPaveBlock aMPB;
1254   //
1255   aNb=myFaceInfoPool.Extent();
1256   for (i=0; i<aNb; ++i) {
1257     BOPDS_FaceInfo &aFI=myFaceInfoPool(i);
1258     nF=aFI.Index();
1259     UpdateFaceInfoOn(nF);
1260     BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.ChangePaveBlocksOn();
1261     //
1262     aMPB.Clear();
1263     aMPB.Assign(aMPBOn);
1264     aMPBOn.Clear();
1265     //
1266     aNbPB=aMPB.Extent();
1267     for (j=1; j<=aNbPB; ++j) {
1268       const Handle(BOPDS_PaveBlock)& aPB=aMPB(j);
1269       if (aPB->HasEdge()) {
1270         aMPBOn.Add(aPB);
1271       }
1272     }
1273   }
1274 }
1275 //=======================================================================
1276 //function : AloneVertices
1277 //purpose  :
1278 //=======================================================================
1279   void BOPDS_DS::AloneVertices(const Standard_Integer theI,
1280                                BOPCol_ListOfInteger& theLI)const
1281 {
1282   if (HasFaceInfo(theI)) {
1283     //
1284     Standard_Integer i, nV1, nV2, nV;
1285     BOPDS_MapIteratorOfMapOfPaveBlock aItMPB;
1286     BOPCol_MapIteratorOfMapOfInteger aItMI;
1287     //
1288     BOPCol_MapOfInteger aMI(100, myAllocator);
1289     //
1290     const BOPDS_FaceInfo& aFI=FaceInfo(theI);
1291     //
1292     for (i=0; i<2; ++i) {
1293       const BOPDS_IndexedMapOfPaveBlock& aMPB=(!i) ? aFI.PaveBlocksIn() : aFI.PaveBlocksSc();
1294       aItMPB.Initialize(aMPB);
1295       for (; aItMPB.More(); aItMPB.Next()) {
1296         const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
1297         aPB->Indices(nV1, nV2);
1298         aMI.Add(nV1);
1299         aMI.Add(nV2);
1300       }
1301     }
1302     //
1303     for (i=0; i<2; ++i) {
1304       const BOPCol_MapOfInteger& aMIV=(!i) ? aFI.VerticesIn() : aFI.VerticesSc();
1305       aItMI.Initialize(aMIV);
1306       for (; aItMI.More(); aItMI.Next()) {
1307         nV=aItMI.Value();
1308         if (nV>0) {
1309           if (aMI.Add(nV)) {
1310             theLI.Append(nV);
1311           }
1312         }
1313       }
1314     }
1315   }
1316 }
1317
1318 //=======================================================================
1319 //function : VerticesOnIn
1320 //purpose  :
1321 //=======================================================================
1322   void BOPDS_DS::VerticesOnIn(const Standard_Integer nF1,
1323                               const Standard_Integer nF2,
1324                               BOPCol_MapOfInteger& aMI,
1325                               BOPDS_MapOfPaveBlock& aMPB)const
1326 {
1327   Standard_Integer nV, nV1, nV2;
1328   BOPCol_MapIteratorOfMapOfInteger aIt;
1329   BOPDS_MapIteratorOfMapOfPaveBlock aItMPB;
1330   //
1331   const BOPDS_FaceInfo& aFI1=FaceInfo(nF1);
1332   const BOPDS_FaceInfo& aFI2=FaceInfo(nF2);
1333   //
1334   const BOPDS_IndexedMapOfPaveBlock& aMPBOn1=aFI1.PaveBlocksOn();
1335   aItMPB.Initialize(aMPBOn1);
1336   for (; aItMPB.More(); aItMPB.Next()) {
1337     const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
1338     aMPB.Add(aPB);
1339     aPB->Indices(nV1, nV2);
1340     aMI.Add(nV1);
1341     aMI.Add(nV2);
1342   }
1343   //
1344   const BOPDS_IndexedMapOfPaveBlock& aMPBIn1=aFI1.PaveBlocksIn();
1345   aItMPB.Initialize(aMPBIn1);
1346   for (; aItMPB.More(); aItMPB.Next()) {
1347     const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
1348     aMPB.Add(aPB);
1349     aPB->Indices(nV1, nV2);
1350     aMI.Add(nV1);
1351     aMI.Add(nV2);
1352   }
1353   //
1354   const BOPDS_IndexedMapOfPaveBlock& aMPBOn2=aFI2.PaveBlocksOn();
1355   aItMPB.Initialize(aMPBOn2);
1356   for (; aItMPB.More(); aItMPB.Next()) {
1357     const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
1358     aMPB.Add(aPB);
1359     aPB->Indices(nV1, nV2);
1360     aMI.Add(nV1);
1361     aMI.Add(nV2);
1362   }
1363   //
1364   const BOPDS_IndexedMapOfPaveBlock& aMPBIn2=aFI2.PaveBlocksIn();
1365   aItMPB.Initialize(aMPBIn2);
1366   for (; aItMPB.More(); aItMPB.Next()) {
1367     const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
1368     aMPB.Add(aPB);
1369     aPB->Indices(nV1, nV2);
1370     aMI.Add(nV1);
1371     aMI.Add(nV2);
1372   }
1373   //
1374   const BOPCol_MapOfInteger& aMVOn1=aFI1.VerticesOn();
1375   aIt.Initialize(aMVOn1);
1376   for (; aIt.More(); aIt.Next()) {
1377     nV=aIt.Value();
1378     aMI.Add(nV);
1379   }
1380   //
1381   const BOPCol_MapOfInteger& aMVIn1=aFI1.VerticesIn();
1382   aIt.Initialize(aMVIn1);
1383   for (; aIt.More(); aIt.Next()) {
1384     nV=aIt.Value();
1385     aMI.Add(nV);
1386   }
1387   //
1388   const BOPCol_MapOfInteger& aMVOn2=aFI2.VerticesOn();
1389   aIt.Initialize(aMVOn2);
1390   for (; aIt.More(); aIt.Next()) {
1391     nV=aIt.Value();
1392     aMI.Add(nV);
1393   }
1394   //
1395   const BOPCol_MapOfInteger& aMVIn2=aFI2.VerticesIn();
1396   aIt.Initialize(aMVIn2);
1397   for (; aIt.More(); aIt.Next()) {
1398     nV=aIt.Value();
1399     aMI.Add(nV);
1400   }
1401 }
1402 //=======================================================================
1403 //function : SharedEdges
1404 //purpose  :
1405 //=======================================================================
1406   void BOPDS_DS::SharedEdges(const Standard_Integer nF1,
1407                              const Standard_Integer nF2,
1408                              BOPCol_ListOfInteger& theLI,
1409                              const Handle(NCollection_BaseAllocator)& aAllocator)
1410 {
1411   Standard_Integer nE, nSp;
1412   BOPCol_ListIteratorOfListOfInteger aItLI;
1413   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
1414   BOPCol_MapOfInteger aMI(100, aAllocator);
1415   //
1416   const BOPDS_ShapeInfo& aSI1=ShapeInfo(nF1);
1417   const BOPCol_ListOfInteger& aLI1=aSI1.SubShapes();
1418   aItLI.Initialize(aLI1);
1419   for (; aItLI.More(); aItLI.Next()) {
1420     nE=aItLI.Value();
1421     const BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
1422     if(aSIE.ShapeType()==TopAbs_EDGE) {
1423       const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nE);
1424       if (aLPB.IsEmpty()) {
1425         aMI.Add(nE);
1426       }
1427       else {
1428         aItLPB.Initialize(aLPB);
1429         for (; aItLPB.More(); aItLPB.Next()) {
1430           const Handle(BOPDS_PaveBlock) aPB=RealPaveBlock(aItLPB.Value());
1431           nSp=aPB->Edge();
1432           aMI.Add(nSp);
1433         }
1434       }
1435     }
1436   }
1437   //
1438   const BOPDS_ShapeInfo& aSI2=ShapeInfo(nF2);
1439   const BOPCol_ListOfInteger& aLI2=aSI2.SubShapes();
1440   aItLI.Initialize(aLI2);
1441   for (; aItLI.More(); aItLI.Next()) {
1442     nE=aItLI.Value();
1443     const BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
1444     if(aSIE.ShapeType()==TopAbs_EDGE) {
1445       const BOPDS_ListOfPaveBlock& aLPB=PaveBlocks(nE);
1446       if (aLPB.IsEmpty()) {
1447         if (aMI.Contains(nE)) {
1448           theLI.Append(nE);
1449         }
1450       }
1451       else {
1452         aItLPB.Initialize(aLPB);
1453         for (; aItLPB.More(); aItLPB.Next()) {
1454           const Handle(BOPDS_PaveBlock) aPB=RealPaveBlock(aItLPB.Value());
1455           nSp=aPB->Edge();
1456           if (aMI.Contains(nSp)) {
1457             theLI.Append(nSp);
1458           }
1459         }
1460       }
1461     }
1462   }
1463 }
1464
1465 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1466 //
1467 // same domain shapes
1468 //
1469 //=======================================================================
1470 //function : ShapesSD
1471 //purpose  :
1472 //=======================================================================
1473   BOPCol_DataMapOfIntegerInteger& BOPDS_DS::ShapesSD()
1474 {
1475   return myShapesSD;
1476 }
1477 //=======================================================================
1478 //function : AddShapeSD
1479 //purpose  :
1480 //=======================================================================
1481   void BOPDS_DS::AddShapeSD(const Standard_Integer theIndex,
1482                             const Standard_Integer theIndexSD)
1483 {
1484   myShapesSD.Bind(theIndex, theIndexSD);
1485 }
1486 //=======================================================================
1487 //function : HasShapeSD
1488 //purpose  :
1489 //=======================================================================
1490   Standard_Boolean BOPDS_DS::HasShapeSD(const Standard_Integer theIndex,
1491                                         Standard_Integer& theIndexSD)const
1492 {
1493   Standard_Boolean bRet;
1494   //
1495   bRet=myShapesSD.IsBound(theIndex);
1496   if (bRet) {
1497    theIndexSD=myShapesSD.Find(theIndex);
1498   }
1499   return bRet;
1500 }
1501 //=======================================================================
1502 //function : Dump
1503 //purpose  :
1504 //=======================================================================
1505   void BOPDS_DS::Dump()const
1506 {
1507   Standard_Integer i, aNb, aNbSS;
1508   //
1509   printf(" *** DS ***\n");
1510   aNb=NbRanges();
1511   printf(" Ranges:%d\n", aNb);
1512   for (i=0; i<aNb; ++i) {
1513     const BOPDS_IndexRange& aR=Range(i);
1514     aR.Dump();
1515     printf("\n");
1516   }
1517   //
1518   aNbSS=NbSourceShapes();
1519   printf(" Shapes:%d\n", aNbSS);
1520   aNb=NbShapes();
1521   for (i=0; i<aNb; ++i) {
1522     const BOPDS_ShapeInfo& aSI=ShapeInfo(i);
1523     printf(" %d :", i);
1524     aSI.Dump();
1525     printf("\n");
1526     if (i==aNbSS-1) {
1527       printf(" ****** adds\n");
1528     }
1529   }
1530   printf(" ******\n");
1531 }
1532
1533 //=======================================================================
1534 // function: CheckCoincidence
1535 // purpose:
1536 //=======================================================================
1537   Standard_Boolean BOPDS_DS::CheckCoincidence(const Handle(BOPDS_PaveBlock)& aPB1,
1538                                               const Handle(BOPDS_PaveBlock)& aPB2)
1539 {
1540   Standard_Boolean bRet;
1541   Standard_Integer nE1, nE2, aNbPoints;
1542   Standard_Real aT11, aT12, aT21, aT22, aT1m, aD, aTol, aT2x;
1543   gp_Pnt aP1m;
1544   //
1545   bRet=Standard_False;
1546   //
1547   aPB1->Range(aT11, aT12);
1548   aT1m=IntTools_Tools::IntermediatePoint (aT11, aT12);
1549   nE1=aPB1->OriginalEdge();
1550   const TopoDS_Edge& aE1=(*(TopoDS_Edge*)(&Shape(nE1)));
1551   BOPTools_AlgoTools::PointOnEdge(aE1, aT1m, aP1m);
1552   //
1553   aPB2->Range(aT21, aT22);
1554   nE2=aPB2->OriginalEdge();
1555   const TopoDS_Edge& aE2=(*(TopoDS_Edge*)(&Shape(nE2)));
1556   //
1557   Standard_Real f, l;
1558   Handle(Geom_Curve)aC2 = BRep_Tool::Curve (aE2, f, l);
1559   GeomAPI_ProjectPointOnCurve aPPC;
1560   aPPC.Init(aC2, f, l);
1561   aPPC.Perform(aP1m);
1562   aNbPoints=aPPC.NbPoints();
1563   if (aNbPoints) {
1564     aD=aPPC.LowerDistance();
1565     //
1566     aTol=BRep_Tool::Tolerance(aE1);
1567     aTol=aTol+BRep_Tool::Tolerance(aE2);
1568     if (aD<aTol) {
1569       aT2x=aPPC.LowerDistanceParameter();
1570       if (aT2x>aT21 && aT2x<aT22) {
1571         return !bRet;
1572       }
1573     }
1574   }
1575   return bRet;
1576 }
1577
1578 //=======================================================================
1579 // function: SortPaveBlocks
1580 // purpose:
1581 //=======================================================================
1582   void BOPDS_DS::SortPaveBlocks(const Handle(BOPDS_CommonBlock)& aCB)
1583 {
1584   Standard_Integer theI;
1585   Standard_Boolean bToSort;
1586   bToSort = IsToSort(aCB, theI);
1587   if (!bToSort) {
1588     return;
1589   }
1590
1591   Standard_Integer i(0);
1592   const BOPDS_ListOfPaveBlock& aLPB = aCB->PaveBlocks();
1593   BOPDS_ListOfPaveBlock aLPBN = aLPB;
1594
1595   Handle(BOPDS_PaveBlock) aPB;
1596   BOPDS_ListIteratorOfListOfPaveBlock aIt;
1597   //
1598   aIt.Initialize(aLPBN);
1599   for (aIt.Next(); aIt.More(); ) {
1600     i++;
1601     if(i == theI) {
1602       aPB = aIt.Value();
1603       aLPBN.Remove(aIt);
1604       aLPBN.Prepend(aPB);
1605       break;
1606     }
1607     aIt.Next();
1608   }
1609   //
1610   aCB->AddPaveBlocks(aLPBN);
1611 }
1612
1613 //=======================================================================
1614 // function: IsToSort
1615 // purpose:
1616 //=======================================================================
1617   Standard_Boolean BOPDS_DS::IsToSort(const Handle(BOPDS_CommonBlock)& aCB,
1618                                       Standard_Integer& theI)
1619 {
1620   Standard_Boolean bRet;
1621   bRet = Standard_False;
1622   const BOPDS_ListOfPaveBlock& aLPB = aCB->PaveBlocks();
1623   if (aLPB.Extent()==1) {
1624     return bRet;
1625   }
1626
1627   Standard_Integer nE;
1628   Standard_Real aTolMax, aTol;
1629   Handle(BOPDS_PaveBlock) aPB;
1630   TopoDS_Edge aE;
1631   BOPDS_ListIteratorOfListOfPaveBlock aIt;
1632   //
1633   aPB = aLPB.First();
1634   nE = aPB->OriginalEdge();
1635   aE = (*(TopoDS_Edge *)(&Shape(nE)));
1636   aTolMax = BRep_Tool::Tolerance(aE);
1637   //
1638   theI = 0;
1639   aIt.Initialize(aLPB);
1640   for (aIt.Next(); aIt.More(); aIt.Next()) {
1641     theI++;
1642     aPB = aIt.Value();
1643     nE = aPB->OriginalEdge();
1644     aE = (*(TopoDS_Edge *)(&Shape(nE)));
1645     aTol = BRep_Tool::Tolerance(aE);
1646     if (aTolMax < aTol) {
1647       aTolMax = aTol;
1648       bRet = Standard_True;
1649     }
1650   }
1651
1652   return bRet;
1653 }
1654
1655 //=======================================================================
1656 // function: IsSubShape
1657 // purpose:
1658 //=======================================================================
1659   Standard_Boolean BOPDS_DS::IsSubShape(const Standard_Integer theI1,
1660                                         const Standard_Integer theI2)
1661 {
1662   Standard_Boolean bRet;
1663   Standard_Integer nS;
1664   bRet = Standard_False;
1665   //
1666   BOPCol_ListIteratorOfListOfInteger aItLI;
1667   //
1668   const BOPDS_ShapeInfo& aSI = ShapeInfo(theI2);
1669   const BOPCol_ListOfInteger& aLI = aSI.SubShapes();
1670   aItLI.Initialize(aLI);
1671   for(;aItLI.More(); aItLI.Next()) {
1672     nS = aItLI.Value();
1673     if (nS == theI1) {
1674       bRet = Standard_True;
1675       break;
1676     }
1677   }
1678
1679   return bRet;
1680 }
1681
1682 //=======================================================================
1683 // function: Paves
1684 // purpose:
1685 //=======================================================================
1686   void BOPDS_DS::Paves(const Standard_Integer theEdge,
1687                        BOPDS_ListOfPave& theLP)
1688 {
1689   Standard_Integer aNb, i;
1690   BOPDS_Pave *pPaves;
1691   BOPDS_ListIteratorOfListOfPaveBlock aIt;
1692   BOPDS_MapOfPave aMP;
1693   //
1694   const BOPDS_ListOfPaveBlock& aLPB = PaveBlocks(theEdge);
1695   aNb = aLPB.Extent();
1696   aNb = (aNb==0) ? 0 : (aNb+1);
1697   //
1698   pPaves=(BOPDS_Pave *)myAllocator->Allocate(aNb*sizeof(BOPDS_Pave));
1699   for (i=0; i<aNb; ++i) {
1700     new (pPaves+i) BOPDS_Pave();
1701   }
1702   //
1703   i = 0;
1704   for (aIt.Initialize(aLPB); aIt.More(); aIt.Next()) {
1705     const Handle(BOPDS_PaveBlock)& aPB = aIt.Value();
1706     if (aMP.Add(aPB->Pave1())){
1707       pPaves[i] = aPB->Pave1();
1708       ++i;
1709     }
1710     if (aMP.Add(aPB->Pave2())){
1711       pPaves[i] = aPB->Pave2();
1712       ++i;
1713     }
1714   }
1715   //
1716   SortShell(aNb, pPaves);
1717   //
1718   for (i = 0; i < aNb; ++i) {
1719     theLP.Append(pPaves[i]);
1720   }
1721 }
1722
1723 //=======================================================================
1724 // function: UpdateTolerance
1725 // purpose:
1726 //=======================================================================
1727   void BOPDS_DS::UpdateEdgeTolerance(const Standard_Integer nE,
1728                                      const Standard_Real aTol)
1729 {
1730   Standard_Integer nV;
1731   Standard_Real aTolV;
1732   BRep_Builder aBB;
1733   BOPCol_ListIteratorOfListOfInteger aIt;
1734   //
1735   const TopoDS_Edge& aE = *(TopoDS_Edge*)&Shape(nE);
1736   aBB.UpdateEdge(aE, aTol);
1737   BOPDS_ShapeInfo& aSIE=ChangeShapeInfo(nE);
1738   Bnd_Box& aBoxE=aSIE.ChangeBox();
1739   BRepBndLib::Add(aE, aBoxE);
1740   //
1741   const BOPCol_ListOfInteger& aLI = aSIE.SubShapes();
1742   aIt.Initialize(aLI);
1743   for (; aIt.More(); aIt.Next()) {
1744     nV = aIt.Value();
1745     const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&Shape(nV);
1746     aTolV = BRep_Tool::Tolerance(aV);
1747     if (aTolV < aTol) {
1748       aBB.UpdateVertex(aV, aTol);
1749       BOPDS_ShapeInfo& aSIV = ChangeShapeInfo(nV);
1750       Bnd_Box& aBoxV = aSIV.ChangeBox();
1751       BRepBndLib::Add(aV, aBoxV);
1752     }
1753   }
1754 }
1755
1756 //=======================================================================
1757 //function : TotalShapes
1758 //purpose  :
1759 //=======================================================================
1760 void TotalShapes(const TopoDS_Shape& aS,
1761                  Standard_Integer& aNbS)
1762 {
1763   TopoDS_Shape *pS;
1764   //
1765   pS=(TopoDS_Shape *)&aS;
1766   if (!pS->Checked()) {
1767     TopoDS_Iterator aIt;
1768     //
1769     pS->Checked(1);
1770     ++aNbS;
1771     aIt.Initialize(aS);
1772     for (; aIt.More(); aIt.Next()) {
1773       const TopoDS_Shape& aSx=aIt.Value();
1774       TotalShapes(aSx, aNbS);
1775     }
1776   }
1777 }
1778 //=======================================================================
1779 //function : ResetShape
1780 //purpose  :
1781 //=======================================================================
1782 void ResetShape(const TopoDS_Shape& aS)
1783 {
1784   TopoDS_Shape *pS;
1785   //
1786   pS=(TopoDS_Shape *)&aS;
1787   pS->Checked(0);
1788 }
1789 //=======================================================================
1790 //function : ResetShape
1791 //purpose  :
1792 //=======================================================================
1793 void ResetShapes(const TopoDS_Shape& aS)
1794 {
1795   TopoDS_Iterator aIt;
1796   //
1797   ResetShape(aS);
1798   aIt.Initialize(aS);
1799   for (; aIt.More(); aIt.Next()) {
1800     const TopoDS_Shape& aSx=aIt.Value();
1801     ResetShape(aSx);
1802   }
1803 }
1804 #include <Geom_Curve.hxx>
1805
1806 //=======================================================================
1807 //function : ComputeParameter
1808 //purpose  :
1809 //=======================================================================
1810 Standard_Real ComputeParameter(const TopoDS_Vertex& aV,
1811                                const TopoDS_Edge& aE)
1812 {
1813   Standard_Real aT1, aT2, aTRet, aTolE2, aD2;
1814   gp_Pnt aPC, aPV;
1815   Handle(Geom_Curve) aC3D;
1816   TopoDS_Edge aEE;
1817   //
1818   aEE=aE;
1819   aEE.Orientation(TopAbs_FORWARD);
1820   //
1821   aTRet=0.;
1822   //
1823   aTolE2=BRep_Tool::Tolerance(aE);
1824   aTolE2=aTolE2*aTolE2;
1825   //
1826   aPV=BRep_Tool::Pnt(aV);
1827   //
1828   aC3D=BRep_Tool::Curve (aEE, aT1, aT2);
1829   //
1830   aC3D->D0(aT1, aPC);
1831   aD2=aPC.SquareDistance(aPV);
1832   if (aD2<aTolE2) {
1833     aTRet=aT1;
1834   }
1835   //
1836   aC3D->D0(aT2, aPC);
1837   aD2=aPC.SquareDistance(aPV);
1838   if (aD2<aTolE2) {
1839     aTRet=aT2;
1840   }
1841   //
1842   return aTRet;
1843 }
1844 //=======================================================================
1845 // function: SortShell
1846 // purpose :
1847 //=======================================================================
1848 void SortShell(const int n, BOPDS_Pave *a)
1849 {
1850   int nd, i, j, l, d=1;
1851   BOPDS_Pave x;
1852   //
1853   while(d<=n) {
1854     d*=2;
1855   }
1856   //
1857   while (d) {
1858     d=(d-1)/2;
1859     //
1860     nd=n-d;
1861     for (i=0; i<nd; ++i) {
1862       j=i;
1863     m30:;
1864       l=j+d;
1865       if (a[l] < a[j]){
1866         x=a[j];
1867         a[j]=a[l];
1868         a[l]=x;
1869         j-=d;
1870         if (j > -1) goto m30;
1871       }//if (a[l] < a[j]){
1872     }//for (i=0; i<nd; ++i)
1873   }//while (1)
1874 }