0025128: Memory leak in BOPDS_DS::Paves()
[occt.git] / src / BOPDS / BOPDS_DS.cxx
index 095e423..fc8ee91 100644 (file)
@@ -1,24 +1,21 @@
 // Created by: Peter KURNEV
-// Copyright (c) 1999-2012 OPEN CASCADE SAS
+// Copyright (c) 1999-2014 OPEN CASCADE SAS
 //
-// The content of this file is subject to the Open CASCADE Technology Public
-// License Version 6.5 (the "License"). You may not use the content of this file
-// except in compliance with the License. Please obtain a copy of the License
-// at http://www.opencascade.org and read it completely before using this file.
+// This file is part of Open CASCADE Technology software library.
 //
-// The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
-// main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
+// This library is free software; you can redistribute it and/or modify it under
+// the terms of the GNU Lesser General Public License version 2.1 as published
+// by the Free Software Foundation, with special exception defined in the file
+// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
+// distribution for complete text of the license and disclaimer of any warranty.
 //
-// The Original Code and all software distributed under the License is
-// distributed on an "AS IS" basis, without warranty of any kind, and the
-// Initial Developer hereby disclaims all such warranties, including without
-// limitation, any warranties of merchantability, fitness for a particular
-// purpose or non-infringement. Please see the License for the specific terms
-// and conditions governing the rights and limitations under the License.
-
+// Alternatively, this file may be used under the terms of Open CASCADE
+// commercial license or contractual agreement.
 
 #include <BOPDS_DS.ixx>
 //
+#include <Standard_Assert.hxx>
+//
 #include <NCollection_IncAllocator.hxx>
 #include <NCollection_BaseAllocator.hxx>
 
@@ -43,6 +40,9 @@
 #include <BOPDS_PassKey.hxx>
 #include <BOPDS_DataMapOfPassKeyListOfPaveBlock.hxx>
 #include <BOPDS_PassKey.hxx>
+#include <BOPDS_MapOfPave.hxx>
+#include <BOPDS_MapOfPaveBlock.hxx>
+#include <BOPDS_VectorOfPave.hxx>
 
 #include <Geom_Curve.hxx>
 #include <BRep_Builder.hxx>
@@ -50,7 +50,8 @@
 #include <IntTools_Tools.hxx>
 #include <BOPTools_AlgoTools.hxx>
 #include <GeomAPI_ProjectPointOnCurve.hxx>
-#include <BOPDS_MapOfPave.hxx>
+
+#include <algorithm>
 
 //
 static
@@ -66,8 +67,6 @@ static
 static
   Standard_Real ComputeParameter(const TopoDS_Vertex& aV,
                                  const TopoDS_Edge& aE);
-static
-  void SortShell(const int n, BOPDS_Pave *a);
 
 //=======================================================================
 //function : 
@@ -81,16 +80,20 @@ BOPDS_DS::BOPDS_DS()
   myLines(myAllocator),
   myMapShapeIndex(100, myAllocator),
   myPaveBlocksPool(myAllocator),
+  myMapPBCB(100, myAllocator),
   myFaceInfoPool(myAllocator),
   myShapesSD(100, myAllocator),
-  myMapPBCB(100, myAllocator),
   myInterfTB(100, myAllocator),
   myInterfVV(myAllocator),
   myInterfVE(myAllocator),
   myInterfVF(myAllocator),
   myInterfEE(myAllocator),
   myInterfEF(myAllocator),
-  myInterfFF(myAllocator)
+  myInterfFF(myAllocator),
+  myInterfVZ(myAllocator),
+  myInterfEZ(myAllocator),
+  myInterfFZ(myAllocator),
+  myInterfZZ(myAllocator)
 {
   myNbShapes=0;
   myNbSourceShapes=0;
@@ -107,16 +110,20 @@ BOPDS_DS::BOPDS_DS(const Handle(NCollection_BaseAllocator)& theAllocator)
   myLines(myAllocator),
   myMapShapeIndex(100, myAllocator),
   myPaveBlocksPool(myAllocator),
+  myMapPBCB(100, myAllocator),
   myFaceInfoPool(myAllocator),
   myShapesSD(100, myAllocator),
-  myMapPBCB(100, myAllocator),
   myInterfTB(100, myAllocator),
   myInterfVV(myAllocator),
   myInterfVE(myAllocator),
   myInterfVF(myAllocator),
   myInterfEE(myAllocator),
   myInterfEF(myAllocator),
-  myInterfFF(myAllocator)
+  myInterfFF(myAllocator),
+  myInterfVZ(myAllocator),
+  myInterfEZ(myAllocator),
+  myInterfFZ(myAllocator),
+  myInterfZZ(myAllocator)
 {
   myNbShapes=0;
   myNbSourceShapes=0;
@@ -153,6 +160,10 @@ void BOPDS_DS::Clear()
   myInterfEE.Clear();
   myInterfEF.Clear();
   myInterfFF.Clear();
+  myInterfVZ.Clear();
+  myInterfEZ.Clear();
+  myInterfFZ.Clear();
+  myInterfZZ.Clear();
 }
 //=======================================================================
 //function : SetArguments
@@ -265,7 +276,8 @@ Standard_Integer BOPDS_DS::Append(const TopoDS_Shape& theS)
 //function : ShapeInfo
 //purpose  : 
 //=======================================================================
-const BOPDS_ShapeInfo& BOPDS_DS::ShapeInfo(const Standard_Integer theI)const
+const BOPDS_ShapeInfo& BOPDS_DS::ShapeInfo
+  (const Standard_Integer theI)const
 {
   return myLines(theI);
 }
@@ -311,9 +323,11 @@ Standard_Integer BOPDS_DS::Index(const TopoDS_Shape& theS)const
 //=======================================================================
 void BOPDS_DS::Init()
 {
-  Standard_Integer i1, i2, j, aI, aNb, aNbS, aNbE, aNbSx, nV, nW, nE, aNbF;
+  Standard_Integer i1, i2, j, aI, aNb, aNbS, aNbE, aNbSx;
+  Standard_Integer n1, n2, n3, nV, nW, nE, aNbF;
   Standard_Real aTol;
   TopAbs_ShapeEnum aTS;
+  TopoDS_Iterator aItS;
   BOPCol_ListIteratorOfListOfInteger aIt1, aIt2, aIt3;
   BOPCol_ListIteratorOfListOfShape aIt;
   BOPDS_IndexRange aR;
@@ -514,6 +528,16 @@ void BOPDS_DS::Init()
         }
       }//for (; aIt1.More(); aIt1.Next()) {
       //
+      // pure internal vertices on the face
+      aItS.Initialize(aS);
+      for (; aItS.More(); aItS.Next()) {
+        const TopoDS_Shape& aSx=aItS.Value();
+        if (aSx.ShapeType()==TopAbs_VERTEX){
+          nV=Index(aSx);
+          aMI.Add(nV);
+        }
+      }
+      //
       //
       // For a Face: change wires for BRep sub-shapes
       aLW.Clear();
@@ -527,6 +551,59 @@ void BOPDS_DS::Init()
     }//if (aTS==TopAbs_FACE) {
   }//for (j=0; j<myNbSourceShapes; ++j) {
   //
+  // 2.4 Solids
+  for (j=0; j<myNbSourceShapes; ++j) {
+    BOPDS_ShapeInfo& aSI=ChangeShapeInfo(j);
+    //
+    aTS=aSI.ShapeType();
+    if (aTS!=TopAbs_SOLID) {
+      continue;
+    }
+    Bnd_Box& aBox=aSI.ChangeBox();
+    BuildBndBoxSolid(j, aBox); 
+    //
+    //
+    // update sub-shapes by BRep comprising ones
+    aMI.Clear();
+    BOPCol_ListOfInteger& aLI1=aSI.ChangeSubShapes();
+    //
+    aIt1.Initialize(aLI1);
+    for (; aIt1.More(); aIt1.Next()) {
+      n1=aIt1.Value();
+      BOPDS_ShapeInfo& aSI1=ChangeShapeInfo(n1);
+      if (aSI1.ShapeType()!=TopAbs_SHELL) {
+        continue;
+      }
+      //
+      const BOPCol_ListOfInteger& aLI2=aSI1.SubShapes(); 
+      aIt2.Initialize(aLI2);
+      for (; aIt2.More(); aIt2.Next()) {
+        n2=aIt2.Value();
+        BOPDS_ShapeInfo& aSI2=ChangeShapeInfo(n2);
+        if (aSI2.ShapeType()!=TopAbs_FACE) {
+          continue;
+        }
+        //
+        aMI.Add(n2);
+        //
+        const BOPCol_ListOfInteger& aLI3=aSI2.SubShapes(); 
+        aIt3.Initialize(aLI3);
+        for (; aIt3.More(); aIt3.Next()) {
+          n3=aIt3.Value();
+          aMI.Add(n3);
+        }
+      }
+    }
+    //
+    aLI1.Clear();
+    aItMI.Initialize(aMI);
+    for (; aItMI.More(); aItMI.Next()) {
+      n1=aItMI.Value();
+      aLI1.Append(n1);
+    }
+    aMI.Clear();
+  }//for (j=0; j<myNbSourceShapes; ++j) {
+  //
   aMI.Clear();
   aAllocator.Nullify();
   //-----------------------------------------------------scope_1 t
@@ -546,10 +623,11 @@ void BOPDS_DS::Init()
 //function : InitShape
 //purpose  : 
 //=======================================================================
-void BOPDS_DS::InitShape(const Standard_Integer aI,
-                        const TopoDS_Shape& aS,
-                        Handle(NCollection_BaseAllocator)& theAllocator,
-                        BOPCol_DataMapOfShapeInteger& aMSI)
+void BOPDS_DS::InitShape
+  (const Standard_Integer aI,
+   const TopoDS_Shape& aS,
+   Handle(NCollection_BaseAllocator)& theAllocator,
+   BOPCol_DataMapOfShapeInteger& aMSI)
 {
   Standard_Integer aIx;
   TopoDS_Iterator aIt;
@@ -609,13 +687,14 @@ Standard_Boolean BOPDS_DS::HasInterf(const Standard_Integer theI) const
   //
   return bRet;
 }
-
 //=======================================================================
 //function : HasInterfShapeSubShapes
 //purpose  : 
 //=======================================================================
-Standard_Boolean BOPDS_DS::HasInterfShapeSubShapes(const Standard_Integer theI1,
-                                                  const Standard_Integer theI2)const
+Standard_Boolean BOPDS_DS::HasInterfShapeSubShapes
+  (const Standard_Integer theI1,
+   const Standard_Integer theI2,
+   const Standard_Boolean theFlag)const
 {
   Standard_Boolean bRet;
   Standard_Integer n2;
@@ -628,19 +707,26 @@ Standard_Boolean BOPDS_DS::HasInterfShapeSubShapes(const Standard_Integer theI1,
   for (; aIt.More(); aIt.Next()) {
     n2=aIt.Value();
     bRet=HasInterf(theI1, n2);
-    if(bRet) {
-      break;
+    if (theFlag) {
+      if(bRet) {
+ break;
+      }
+    }
+    else {
+      if(!bRet) {
+ break;
+      }
     }
   }
   return bRet;
 }
-
 //=======================================================================
 //function : HasInterfSubShapes
 //purpose  : 
 //=======================================================================
-Standard_Boolean BOPDS_DS::HasInterfSubShapes(const Standard_Integer theI1,
-                                             const Standard_Integer theI2)const
+Standard_Boolean BOPDS_DS::HasInterfSubShapes
+  (const Standard_Integer theI1,
+   const Standard_Integer theI2)const
 {
   Standard_Boolean bRet;
   Standard_Integer n1;
@@ -689,7 +775,8 @@ Standard_Boolean BOPDS_DS::HasPaveBlocks(const Standard_Integer theI)const
 //function : PaveBlocks
 //purpose  : 
 //=======================================================================
-const BOPDS_ListOfPaveBlock& BOPDS_DS::PaveBlocks(const Standard_Integer theI)const
+const BOPDS_ListOfPaveBlock& BOPDS_DS::PaveBlocks
+  (const Standard_Integer theI)const
 {
   static BOPDS_ListOfPaveBlock sLPB;
   Standard_Integer aRef;
@@ -705,7 +792,8 @@ const BOPDS_ListOfPaveBlock& BOPDS_DS::PaveBlocks(const Standard_Integer theI)co
 //function : ChangePaveBlocks
 //purpose  : 
 //=======================================================================
-BOPDS_ListOfPaveBlock& BOPDS_DS::ChangePaveBlocks(const Standard_Integer theI)
+BOPDS_ListOfPaveBlock& BOPDS_DS::ChangePaveBlocks
+  (const Standard_Integer theI)
 {
   Standard_Boolean bHasReference;
   Standard_Integer aRef;
@@ -725,7 +813,7 @@ BOPDS_ListOfPaveBlock& BOPDS_DS::ChangePaveBlocks(const Standard_Integer theI)
 //=======================================================================
 void BOPDS_DS::InitPaveBlocks(const Standard_Integer theI)
 {
-  Standard_Integer nV, iRef, aNbV, nVSD, i;
+  Standard_Integer nV = 0, iRef, aNbV, nVSD, i;
   Standard_Real aT;
   TopoDS_Vertex aV;
   BOPCol_ListIteratorOfListOfInteger aIt;
@@ -1016,15 +1104,10 @@ Standard_Boolean BOPDS_DS::IsCommonBlock
 //function : CommonBlock
 //purpose  : 
 //=======================================================================
-const Handle(BOPDS_CommonBlock)& BOPDS_DS::CommonBlock
+Handle(BOPDS_CommonBlock) BOPDS_DS::CommonBlock
     (const Handle(BOPDS_PaveBlock)& thePB) const
 {
-  Handle(BOPDS_CommonBlock) aNullCB;
-  //
-  const Handle(BOPDS_CommonBlock)& aCB = 
-    IsCommonBlock(thePB) ? myMapPBCB.Find(thePB) : aNullCB;
-  //
-  return aCB;
+  return (IsCommonBlock(thePB) ? myMapPBCB.Find(thePB) : NULL);
 }
 
 //=======================================================================
@@ -1032,7 +1115,7 @@ const Handle(BOPDS_CommonBlock)& BOPDS_DS::CommonBlock
 //purpose  : 
 //=======================================================================
 void BOPDS_DS::SetCommonBlock(const Handle(BOPDS_PaveBlock)& thePB,
-                             const Handle(BOPDS_CommonBlock)& theCB)
+                              const Handle(BOPDS_CommonBlock)& theCB)
 {
   if (IsCommonBlock(thePB)) {
     Handle(BOPDS_CommonBlock)& aCB = myMapPBCB.ChangeFind(thePB);
@@ -1162,8 +1245,8 @@ void BOPDS_DS::UpdateFaceInfoOn(const Standard_Integer theI)
 //purpose  : 
 //=======================================================================
 void BOPDS_DS::FaceInfoOn(const Standard_Integer theF,
-                         BOPDS_IndexedMapOfPaveBlock& theMPB,
-                         BOPCol_MapOfInteger& theMI)
+                          BOPDS_IndexedMapOfPaveBlock& theMPB,
+                          BOPCol_MapOfInteger& theMI)
 {
   Standard_Integer nS, nSD, nV1, nV2;
   BOPCol_ListIteratorOfListOfInteger aIt;
@@ -1201,12 +1284,28 @@ void BOPDS_DS::FaceInfoOn(const Standard_Integer theF,
 //purpose  : 
 //=======================================================================
 void BOPDS_DS::FaceInfoIn(const Standard_Integer theF,
-                         BOPDS_IndexedMapOfPaveBlock& theMPB,
-                         BOPCol_MapOfInteger& theMI)
+                          BOPDS_IndexedMapOfPaveBlock& theMPB,
+                          BOPCol_MapOfInteger& theMI)
 {
-  Standard_Integer i, aNbVF, aNbEF, nV, nE;
+  Standard_Integer i, aNbVF, aNbEF, nV, nE, nVSD;
+  TopoDS_Iterator aItS;
   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
   //
+  // 1. Pure internal vertices on the face
+  const TopoDS_Shape& aF=Shape(theF);
+  aItS.Initialize(aF);
+  for (; aItS.More(); aItS.Next()) {
+    const TopoDS_Shape& aSx=aItS.Value();
+    if (aSx.ShapeType()==TopAbs_VERTEX){
+      nV=Index(aSx);
+      if (HasShapeSD(nV, nVSD)) {
+ nV=nVSD;
+      }
+      theMI.Add(nV);
+    }
+  }
+  //
+  // 2. aVFs
   BOPDS_VectorOfInterfVF& aVFs=InterfVF();
   aNbVF=aVFs.Extent();
   for (i=0; i<aNbVF; ++i) {
@@ -1217,6 +1316,7 @@ void BOPDS_DS::FaceInfoIn(const Standard_Integer theF,
     }
   }
   //
+  // 3. aEFs
   BOPDS_VectorOfInterfEF& aEFs=InterfEF();
   aNbEF=aEFs.Extent();
   for (i=0; i<aNbEF; ++i) {
@@ -1278,7 +1378,7 @@ void BOPDS_DS::RefineFaceInfoOn()
 //purpose  : 
 //=======================================================================
 void BOPDS_DS::AloneVertices(const Standard_Integer theI,
-                            BOPCol_ListOfInteger& theLI)const
+                             BOPCol_ListOfInteger& theLI)const
 {
   if (HasFaceInfo(theI)) {
     //
@@ -1291,7 +1391,8 @@ void BOPDS_DS::AloneVertices(const Standard_Integer theI,
     const BOPDS_FaceInfo& aFI=FaceInfo(theI);
     //
     for (i=0; i<2; ++i) {
-      const BOPDS_IndexedMapOfPaveBlock& aMPB=(!i) ? aFI.PaveBlocksIn() : aFI.PaveBlocksSc();
+      const BOPDS_IndexedMapOfPaveBlock& aMPB=
+        (!i) ? aFI.PaveBlocksIn() : aFI.PaveBlocksSc();
       aItMPB.Initialize(aMPB);
       for (; aItMPB.More(); aItMPB.Next()) {
         const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
@@ -1302,11 +1403,12 @@ void BOPDS_DS::AloneVertices(const Standard_Integer theI,
     }
     //
     for (i=0; i<2; ++i) {
-      const BOPCol_MapOfInteger& aMIV=(!i) ? aFI.VerticesIn() : aFI.VerticesSc();
+      const BOPCol_MapOfInteger& aMIV=
+        (!i) ? aFI.VerticesIn() : aFI.VerticesSc();
       aItMI.Initialize(aMIV);
       for (; aItMI.More(); aItMI.Next()) {
         nV=aItMI.Value();
-        if (nV>0) {
+        if (nV>=0) {
           if (aMI.Add(nV)) {
             theLI.Append(nV);
           }
@@ -1315,89 +1417,53 @@ void BOPDS_DS::AloneVertices(const Standard_Integer theI,
     }
   }
 }
-
 //=======================================================================
 //function : VerticesOnIn
 //purpose  : 
 //=======================================================================
-void BOPDS_DS::VerticesOnIn(const Standard_Integer nF1,
-                           const Standard_Integer nF2,
-                           BOPCol_MapOfInteger& aMI,
-                           BOPDS_MapOfPaveBlock& aMPB)const
+void BOPDS_DS::VerticesOnIn
+  (const Standard_Integer nF1,
+   const Standard_Integer nF2,
+   BOPCol_MapOfInteger& aMI,
+   BOPDS_IndexedMapOfPaveBlock& aMPB)const
 {
-  Standard_Integer nV, nV1, nV2;
+  Standard_Integer i, j, nV, nV1, nV2, aNbPB;
   BOPCol_MapIteratorOfMapOfInteger aIt;
-  BOPDS_MapIteratorOfMapOfPaveBlock aItMPB;
+  BOPDS_IndexedMapOfPaveBlock pMPB[4];
   //
   const BOPDS_FaceInfo& aFI1=FaceInfo(nF1);
   const BOPDS_FaceInfo& aFI2=FaceInfo(nF2);
   //
-  const BOPDS_IndexedMapOfPaveBlock& aMPBOn1=aFI1.PaveBlocksOn();
-  aItMPB.Initialize(aMPBOn1);
-  for (; aItMPB.More(); aItMPB.Next()) {
-    const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
-    aMPB.Add(aPB);
-    aPB->Indices(nV1, nV2);
-    aMI.Add(nV1);
-    aMI.Add(nV2);
-  }
-  //
-  const BOPDS_IndexedMapOfPaveBlock& aMPBIn1=aFI1.PaveBlocksIn();
-  aItMPB.Initialize(aMPBIn1);
-  for (; aItMPB.More(); aItMPB.Next()) {
-    const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
-    aMPB.Add(aPB);
-    aPB->Indices(nV1, nV2);
-    aMI.Add(nV1);
-    aMI.Add(nV2);
-  }
-  //
-  const BOPDS_IndexedMapOfPaveBlock& aMPBOn2=aFI2.PaveBlocksOn();
-  aItMPB.Initialize(aMPBOn2);
-  for (; aItMPB.More(); aItMPB.Next()) {
-    const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
-    aMPB.Add(aPB);
-    aPB->Indices(nV1, nV2);
-    aMI.Add(nV1);
-    aMI.Add(nV2);
-  }
-  //
-  const BOPDS_IndexedMapOfPaveBlock& aMPBIn2=aFI2.PaveBlocksIn();
-  aItMPB.Initialize(aMPBIn2);
-  for (; aItMPB.More(); aItMPB.Next()) {
-    const Handle(BOPDS_PaveBlock)& aPB=aItMPB.Value();
-    aMPB.Add(aPB);
-    aPB->Indices(nV1, nV2);
-    aMI.Add(nV1);
-    aMI.Add(nV2);
+  pMPB[0]=aFI1.PaveBlocksOn();
+  pMPB[1]=aFI1.PaveBlocksIn();
+  pMPB[2]=aFI2.PaveBlocksOn();
+  pMPB[3]=aFI2.PaveBlocksIn();
+  //
+  for (i=0; i<4; ++i) {
+    aNbPB = pMPB[i].Extent();
+    for (j = 1; j <= aNbPB; ++j) {
+      const Handle(BOPDS_PaveBlock)& aPB = pMPB[i](j);
+      aMPB.Add(aPB);
+      aPB->Indices(nV1, nV2);
+      aMI.Add(nV1);
+      aMI.Add(nV2);
+    }
   }
   //
   const BOPCol_MapOfInteger& aMVOn1=aFI1.VerticesOn();
-  aIt.Initialize(aMVOn1);
-  for (; aIt.More(); aIt.Next()) {
-    nV=aIt.Value();
-    aMI.Add(nV);
-  }
-  //
   const BOPCol_MapOfInteger& aMVIn1=aFI1.VerticesIn();
-  aIt.Initialize(aMVIn1);
-  for (; aIt.More(); aIt.Next()) {
-    nV=aIt.Value();
-    aMI.Add(nV);
-  }
-  //
   const BOPCol_MapOfInteger& aMVOn2=aFI2.VerticesOn();
-  aIt.Initialize(aMVOn2);
-  for (; aIt.More(); aIt.Next()) {
-    nV=aIt.Value();
-    aMI.Add(nV);
-  }
-  //
   const BOPCol_MapOfInteger& aMVIn2=aFI2.VerticesIn();
-  aIt.Initialize(aMVIn2);
-  for (; aIt.More(); aIt.Next()) {
-    nV=aIt.Value();
-    aMI.Add(nV);
+  //
+  for (i=0; i<2; ++i) {
+    const BOPCol_MapOfInteger& aMV1=(!i) ? aMVOn1 : aMVIn1;
+    aIt.Initialize(aMV1);
+    for (; aIt.More(); aIt.Next()) {
+      nV=aIt.Value();
+      if (aMVOn2.Contains(nV) || aMVIn2.Contains(nV)) {
+        aMI.Add(nV);
+      }
+    }
   }
 } 
 //=======================================================================
@@ -1405,9 +1471,9 @@ void BOPDS_DS::VerticesOnIn(const Standard_Integer nF1,
 //purpose  : 
 //=======================================================================
 void BOPDS_DS::SharedEdges(const Standard_Integer nF1,
-                          const Standard_Integer nF2,
-                          BOPCol_ListOfInteger& theLI,
-                          const Handle(NCollection_BaseAllocator)& aAllocator)
+      const Standard_Integer nF2,
+      BOPCol_ListOfInteger& theLI,
+      const Handle(NCollection_BaseAllocator)& aAllocator)
 {
   Standard_Integer nE, nSp;
   BOPCol_ListIteratorOfListOfInteger aItLI;
@@ -1480,7 +1546,7 @@ BOPCol_DataMapOfIntegerInteger& BOPDS_DS::ShapesSD()
 //purpose  : 
 //=======================================================================
 void BOPDS_DS::AddShapeSD(const Standard_Integer theIndex,
-                            const Standard_Integer theIndexSD)
+                          const Standard_Integer theIndexSD)
 {
   myShapesSD.Bind(theIndex, theIndexSD);
 }
@@ -1488,8 +1554,9 @@ void BOPDS_DS::AddShapeSD(const Standard_Integer theIndex,
 //function : HasShapeSD
 //purpose  : 
 //=======================================================================
-Standard_Boolean BOPDS_DS::HasShapeSD(const Standard_Integer theIndex,
-                                     Standard_Integer& theIndexSD)const
+Standard_Boolean BOPDS_DS::HasShapeSD
+  (const Standard_Integer theIndex,
+   Standard_Integer& theIndexSD)const
 {
   Standard_Boolean bRet;
   //
@@ -1535,8 +1602,9 @@ void BOPDS_DS::Dump()const
 // function: CheckCoincidence
 // purpose:
 //=======================================================================
-Standard_Boolean BOPDS_DS::CheckCoincidence(const Handle(BOPDS_PaveBlock)& aPB1,
-                                           const Handle(BOPDS_PaveBlock)& aPB2)
+Standard_Boolean BOPDS_DS::CheckCoincidence
+  (const Handle(BOPDS_PaveBlock)& aPB1,
+   const Handle(BOPDS_PaveBlock)& aPB2)
 {
   Standard_Boolean bRet;
   Standard_Integer nE1, nE2, aNbPoints;
@@ -1575,7 +1643,6 @@ Standard_Boolean BOPDS_DS::CheckCoincidence(const Handle(BOPDS_PaveBlock)& aPB1,
   }
   return bRet;
 }
-
 //=======================================================================
 // function: SortPaveBlocks
 // purpose:
@@ -1610,13 +1677,13 @@ void BOPDS_DS::SortPaveBlocks(const Handle(BOPDS_CommonBlock)& aCB)
   //
   aCB->AddPaveBlocks(aLPBN);
 }
-
 //=======================================================================
 // function: IsToSort
 // purpose:
 //=======================================================================
-Standard_Boolean BOPDS_DS::IsToSort(const Handle(BOPDS_CommonBlock)& aCB,
-                                   Standard_Integer& theI)
+Standard_Boolean BOPDS_DS::IsToSort
+  (const Handle(BOPDS_CommonBlock)& aCB,
+   Standard_Integer& theI)
 {
   Standard_Boolean bRet;
   bRet = Standard_False;
@@ -1652,13 +1719,13 @@ Standard_Boolean BOPDS_DS::IsToSort(const Handle(BOPDS_CommonBlock)& aCB,
 
   return bRet;
 }
-
 //=======================================================================
 // function: IsSubShape
 // purpose:
 //=======================================================================
-Standard_Boolean BOPDS_DS::IsSubShape(const Standard_Integer theI1,
-                                     const Standard_Integer theI2)
+Standard_Boolean BOPDS_DS::IsSubShape
+  (const Standard_Integer theI1,
+   const Standard_Integer theI2)
 {
   Standard_Boolean bRet;
   Standard_Integer nS;
@@ -1685,39 +1752,44 @@ Standard_Boolean BOPDS_DS::IsSubShape(const Standard_Integer theI1,
 // purpose:
 //=======================================================================
 void BOPDS_DS::Paves(const Standard_Integer theEdge,
-                    BOPDS_ListOfPave& theLP)
+                     BOPDS_ListOfPave& theLP)
 {
   Standard_Integer aNb, i;
-  BOPDS_Pave *pPaves;
   BOPDS_ListIteratorOfListOfPaveBlock aIt;
   BOPDS_MapOfPave aMP;
   //
   const BOPDS_ListOfPaveBlock& aLPB = PaveBlocks(theEdge);
-  aNb = aLPB.Extent();
-  aNb = (aNb==0) ? 0 : (aNb+1);
-  //
-  pPaves=(BOPDS_Pave *)myAllocator->Allocate(aNb*sizeof(BOPDS_Pave));
-  for (i=0; i<aNb; ++i) {
-    new (pPaves+i) BOPDS_Pave();
+  aNb = aLPB.Extent() + 1;
+  if (aNb == 1) {
+    return;
   }
   //
-  i = 0;
-  for (aIt.Initialize(aLPB); aIt.More(); aIt.Next()) {
+  BOPDS_VectorOfPave pPaves(1, aNb);
+  //
+  i = 1;
+  aIt.Initialize(aLPB);
+  for (; aIt.More(); aIt.Next()) {
     const Handle(BOPDS_PaveBlock)& aPB = aIt.Value();
-    if (aMP.Add(aPB->Pave1())){
-      pPaves[i] = aPB->Pave1();
+    const BOPDS_Pave& aPave1 = aPB->Pave1();
+    const BOPDS_Pave& aPave2 = aPB->Pave2();
+    //
+    if (aMP.Add(aPave1)){
+      pPaves(i) = aPave1;
       ++i;
     }
-    if (aMP.Add(aPB->Pave2())){
-      pPaves[i] = aPB->Pave2();
+    //
+    if (aMP.Add(aPave2)){
+      pPaves(i) = aPave2;
       ++i;
     }
   }
   //
-  SortShell(aNb, pPaves);
+  Standard_ASSERT_VOID(aNb == aMP.Extent(), "Abnormal number of paves");
   //
-  for (i = 0; i < aNb; ++i) {
-    theLP.Append(pPaves[i]);
+  std::sort(pPaves.begin(), pPaves.end());
+  //
+  for (i = 1; i <= aNb; ++i) {
+    theLP.Append(pPaves(i));
   }
 }
 
@@ -1726,7 +1798,7 @@ void BOPDS_DS::Paves(const Standard_Integer theEdge,
 // purpose:
 //=======================================================================
 void BOPDS_DS::UpdateEdgeTolerance(const Standard_Integer nE,
-                                  const Standard_Real aTol)
+                                   const Standard_Real aTol)
 {
   Standard_Integer nV;
   Standard_Real aTolV;
@@ -1802,8 +1874,6 @@ void ResetShapes(const TopoDS_Shape& aS)
     ResetShape(aSx);
   }
 }
-#include <Geom_Curve.hxx>
-
 //=======================================================================
 //function : ComputeParameter
 //purpose  : 
@@ -1843,33 +1913,78 @@ Standard_Real ComputeParameter(const TopoDS_Vertex& aV,
   return aTRet;
 }
 //=======================================================================
-// function: SortShell
-// purpose : 
+//function : BuildBndBoxSolid
+//purpose  : 
 //=======================================================================
-void SortShell(const int n, BOPDS_Pave *a) 
+void BOPDS_DS::BuildBndBoxSolid(const Standard_Integer theIndex,
+                                Bnd_Box& aBoxS)
 {
-  int nd, i, j, l, d=1;
-  BOPDS_Pave x;
+  Standard_Boolean bIsOpenBox, bIsInverted;
+  Standard_Integer nSh, nFc;
+  Standard_Real aTolS, aTolFc;
+  BOPCol_ListIteratorOfListOfInteger aItLI, aItLI1;
   //
-  while(d<=n) {
-    d*=2;
-  }
+  const BOPDS_ShapeInfo& aSI=ShapeInfo(theIndex);
+  const TopoDS_Shape& aS=aSI.Shape();
+  const TopoDS_Solid& aSolid=(*(TopoDS_Solid*)(&aS));
   //
-  while (d) {
-    d=(d-1)/2;
+  bIsOpenBox=Standard_False;
+  //
+  aTolS=0.;
+  const BOPCol_ListOfInteger& aLISh=aSI.SubShapes();
+  aItLI.Initialize(aLISh);
+  for (; aItLI.More(); aItLI.Next()) {
+    nSh=aItLI.Value();
+    const BOPDS_ShapeInfo& aSISh=ShapeInfo(nSh);
+    if (aSISh.ShapeType()!=TopAbs_SHELL) {
+      continue;
+    }
+    //
+    const BOPCol_ListOfInteger& aLIFc=aSISh.SubShapes();
+    aItLI1.Initialize(aLIFc);
+    for (; aItLI1.More(); aItLI1.Next()) {
+      nFc=aItLI1.Value();
+      const BOPDS_ShapeInfo& aSIFc=ShapeInfo(nFc);
+      if (aSIFc.ShapeType()!=TopAbs_FACE) {
+        continue;
+      }
+      //
+      const Bnd_Box& aBFc=aSIFc.Box();
+      aBoxS.Add(aBFc);
+      //
+      if (!bIsOpenBox) {
+        bIsOpenBox=(aBFc.IsOpenXmin() || aBFc.IsOpenXmax() ||
+                    aBFc.IsOpenYmin() || aBFc.IsOpenYmax() ||
+                    aBFc.IsOpenZmin() || aBFc.IsOpenZmax()); 
+        if (bIsOpenBox) {
+          break;
+        }
+      }
+      //
+      const TopoDS_Face& aFc=*((TopoDS_Face*)&aSIFc.Shape());
+      aTolFc=BRep_Tool::Tolerance(aFc);
+      if (aTolFc>aTolS) {
+        aTolS=aTolFc;
+      }
+    }//for (; aItLI1.More(); aItLI1.Next()) {
+    if (bIsOpenBox) {
+      break;
+    }
     //
-    nd=n-d;
-    for (i=0; i<nd; ++i) {
-      j=i;
-    m30:;
-      l=j+d;
-      if (a[l] < a[j]){
-        x=a[j];
-        a[j]=a[l];
-        a[l]=x;
-        j-=d;
-        if (j > -1) goto m30;
-      }//if (a[l] < a[j]){
-    }//for (i=0; i<nd; ++i) 
-  }//while (1)
+    const TopoDS_Shell& aSh=*((TopoDS_Shell*)&aSISh.Shape());
+    bIsOpenBox=BOPTools_AlgoTools::IsOpenShell(aSh);
+    if (bIsOpenBox) {
+      break;
+    }
+  }//for (; aItLI.More(); aItLI.Next()) {
+  //
+  if (bIsOpenBox) {
+    aBoxS.SetWhole();
+  }
+  else {
+    bIsInverted=BOPTools_AlgoTools::IsInvertedSolid(aSolid);
+    if (bIsInverted) {
+      aBoxS.SetWhole(); 
+    }
+  }
 }