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