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