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