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