Test for 0022778: Bug in BRepMesh
[occt.git] / src / BooleanOperations / BooleanOperations_OnceExplorer.cxx
CommitLineData
b311480e 1// Created on: 2000-09-07
2// Created by: Vincent DELOS
3// Copyright (c) 2000-2012 OPEN CASCADE SAS
4//
5// The content of this file is subject to the Open CASCADE Technology Public
6// License Version 6.5 (the "License"). You may not use the content of this file
7// except in compliance with the License. Please obtain a copy of the License
8// at http://www.opencascade.org and read it completely before using this file.
9//
10// The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
11// main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
12//
13// The Original Code and all software distributed under the License is
14// distributed on an "AS IS" basis, without warranty of any kind, and the
15// Initial Developer hereby disclaims all such warranties, including without
16// limitation, any warranties of merchantability, fitness for a particular
17// purpose or non-infringement. Please see the License for the specific terms
18// and conditions governing the rights and limitations under the License.
19
7fd59977 20
21
22#include <BooleanOperations_OnceExplorer.ixx>
23
24//#define theStackSize (20)
25const static Standard_Integer theStackSize=20;
26
27#define BITFLAG(n) (1 << (n)) // creation of 2 power n.
28#define BITSET(word,mask) (word) |= (mask) // to set a bit to 1 in word using mask.
29#define BITCLEAR(word,mask) (word) &= ~(mask) // to set a bit to 0 in word using mask.
30#define BITISSET(word,mask) ((word) & (mask)) // returns the value of the bit corresponding to mask.
31#define LEMOT(id) ((id) >> 5) // the number of the integer we will work on.
32#define LEBIT(id) (BITFLAG((id) & 31)) // the number of the bit we will work on (2 power (id%32)).
33#define CC0BIT(id,anArray) BITCLEAR(anArray[LEMOT(id)],LEBIT(id)) // sets to 0 the bit number id in anArray.
34#define CC1BIT(id,anArray) BITSET(anArray[LEMOT(id)],LEBIT(id)) // sets to 1 the bit number id in anArray.
35#define NNNBIT(id,anArray) (BITISSET(anArray[LEMOT(id)],LEBIT(id)) ? 1 : 0) // returns the bit number id in anArray.
36
37//===========================================================================
38//function : BooleanOperations_OnceExplorer
39//purpose :
40//===========================================================================
41 BooleanOperations_OnceExplorer::BooleanOperations_OnceExplorer
42 (const BooleanOperations_ShapesDataStructure& SDS):
43 BooleanOperations_Explorer(SDS)
44{
45 hasMore = Standard_False;
46 // The size of the array of bits is the lower multiple of
47 //32 greater than the number of shapes in myShapesDataStructure.
48 Standard_Integer MultipleOf32= (((*myShapesDataStructure).myLength+31) & (~31));
49
50 mySizeOfArrayOfBits = MultipleOf32/32;
51 myArrayOfBits = 0L;
52}
53//modified by NIZNHY-PKV Sun Dec 15 16:28:15 2002 f
54//===========================================================================
55//function : Delete
56//purpose : alias ~BooleanOperations_Explorer
57//===========================================================================
58 void BooleanOperations_OnceExplorer::Delete()
59{
60 if (myArrayOfBits) {
61 free (myArrayOfBits);
62 }
63 BooleanOperations_Explorer::Delete();
64}
65//modified by NIZNHY-PKV Sun Dec 15 16:29:10 2002 t
66//===========================================================================
67//function : Init
68//purpose :
69//===========================================================================
70 void BooleanOperations_OnceExplorer::Init(const Standard_Integer aShapeNumber,
71 const TopAbs_ShapeEnum TargetToFind,
72 const TopAbs_ShapeEnum TargetToAvoid)
73{
74 Standard_Integer i,j,k,theNumberOfTheShapeOnTop,aSuccessorNumber;
75 Standard_Integer* anArrayOfBits;
76 Standard_Boolean shapeAlreadyProcessed;
77 TopAbs_ShapeEnum theTypeOfShapeOnTop,successorType;
78
79 myTargetToFind = TargetToFind;
80 myTargetToAvoid = TargetToAvoid;
81
82// Modified by skv - Thu Apr 7 11:19:39 2005 Begin
83 hasMore = Standard_False;
84// Modified by skv - Thu Apr 7 11:19:41 2005 End
85
86 // We first test if myShapesDataStructure has changed.
87 Standard_Integer MultipleOf32= (((*myShapesDataStructure).myLength+31) & (~31));
88 Standard_Integer NewSize = MultipleOf32/32;
89 if (myArrayOfBits!=0L)
90 free(myArrayOfBits);
91 myArrayOfBits = (Standard_Integer*)calloc(mySizeOfArrayOfBits,sizeof(Standard_Integer));
92 mySizeOfArrayOfBits = NewSize;
93
94 if (myStack != 0L) {
95 Standard::Free((Standard_Address&)myStack);
96 }
97 mySizeOfStack = theStackSize;
98 myStack = (Standard_Integer*)Standard::Allocate(theStackSize*sizeof(Standard_Integer));
99
100 ((Standard_Integer*)myStack)[0] = aShapeNumber;
101 myTopOfStack = 0;
102
103 theNumberOfTheShapeOnTop = ((Standard_Integer*)myStack)[myTopOfStack];
104 theTypeOfShapeOnTop = (*myShapesDataStructure).GetShapeType(theNumberOfTheShapeOnTop);
105 if (theTypeOfShapeOnTop == myTargetToFind)
106 {
107 hasMore = Standard_True;
108 return;
109 }
110// Modified by skv - Thu Apr 7 11:19:39 2005 Begin
111 if (theTypeOfShapeOnTop == TopAbs_VERTEX) {
112 hasMore = Standard_False;
113
114 return;
115 }
116// Modified by skv - Thu Apr 7 11:19:41 2005 End
117
118 while (theTypeOfShapeOnTop != myTargetToFind)
119 {
120 Standard_Address theSuccessors;
121 Standard_Integer theNumberOfSuccessors;
122 // We get the successors of the shape on top of the stack.
123 (*myShapesDataStructure).GetSuccessors(theNumberOfTheShapeOnTop,theSuccessors,theNumberOfSuccessors);
124 // Do we have enough place to store our new successors ?
125 if ((myTopOfStack+theNumberOfSuccessors > mySizeOfStack) && (theSuccessors != 0L))
126 {
127 // We don't have enough place so we reallocate.
128 Standard_Address theNewStack = (Standard_Integer*)Standard::Allocate
129 ((mySizeOfStack+theStackSize+theNumberOfSuccessors)*sizeof(Standard_Integer));
130 // We copy the old array in the new one.
131 for (j=0;j<myTopOfStack;j++)
132 ((Standard_Integer*)theNewStack)[j] = ((Standard_Integer*)myStack)[j];
133
134 Standard::Free((Standard_Address&)myStack);
135 myStack = theNewStack;
136 mySizeOfStack = mySizeOfStack+theStackSize+theNumberOfSuccessors;
137 }
138 // We remove the shape on top and replace it by its own successors.
139 // We must skip the shape of type TargetToAvoid, k counts them.
140 k = 0;
141 anArrayOfBits = (Standard_Integer*)myArrayOfBits;
142 for (i=0;i<theNumberOfSuccessors;i++)
143 {
144 aSuccessorNumber = ((Standard_Integer*)theSuccessors)[i];
145 shapeAlreadyProcessed = NNNBIT(aSuccessorNumber,anArrayOfBits);
146 successorType = (*myShapesDataStructure).GetShapeType(((Standard_Integer*)theSuccessors)[i]);
147// Modified by skv - Thu Apr 7 11:19:39 2005 Begin
148// if ((successorType == myTargetToAvoid) || (shapeAlreadyProcessed==1))
149 if ((successorType == myTargetToAvoid) || (shapeAlreadyProcessed==1) ||
150 (successorType != myTargetToFind && successorType == TopAbs_VERTEX))
151// Modified by skv - Thu Apr 7 11:19:41 2005 End
152 k++;
153 else
154 {
155 // Insertion of the successor in the stack.
156 ((Standard_Integer*)myStack)[i+myTopOfStack-k] = ((Standard_Integer*)theSuccessors)[i];
157 // We need to set the corresponding bit to one to say that we processed this shape.
158 CC1BIT(aSuccessorNumber,anArrayOfBits);
159 }
160 }
161 if (theNumberOfSuccessors-k == 0)
162 {
163 // No successor of a type different of myTargetToAvoid.
164 myTopOfStack--;
165 if (myTopOfStack < 0)
166 {
167 // Empty stack.
168 hasMore = Standard_False;
169 return;
170 }
171 }
172 else
173 myTopOfStack = myTopOfStack+theNumberOfSuccessors-k-1;
174 theNumberOfTheShapeOnTop = ((Standard_Integer*)myStack)[myTopOfStack];
175 theTypeOfShapeOnTop = (*myShapesDataStructure).GetShapeType(theNumberOfTheShapeOnTop);
176 if (theTypeOfShapeOnTop == myTargetToFind)
177 {
178 hasMore = Standard_True;
179 return;
180 }
181 }
182}
183
184//===========================================================================
185//function : Current
186//purpose :
187//===========================================================================
188 Standard_Integer BooleanOperations_OnceExplorer::Current()
189{
190 myTopOfStack--;
191 if (myTopOfStack < 0)
192 hasMore = Standard_False;
193 return ((Standard_Integer*)myStack)[myTopOfStack+1];
194}
195
196//===========================================================================
197//function : Next
198//purpose :
199//===========================================================================
200 void BooleanOperations_OnceExplorer::Next()
201{
202 TopAbs_ShapeEnum theTypeOfShapeOnTop,successorType;
203 Standard_Integer j,k,theNumberOfTheShapeOnTop,successorNumber;
204 Standard_Boolean shapeAlreadyProcessed;
205 Standard_Integer* anArrayOfBits;
206
207 if (myTopOfStack < 0)
208 {
209 hasMore = Standard_False;
210 return;
211 }
212 theNumberOfTheShapeOnTop = ((Standard_Integer*)myStack)[myTopOfStack];
213 theTypeOfShapeOnTop = (*myShapesDataStructure).GetShapeType(theNumberOfTheShapeOnTop);
214 if (theTypeOfShapeOnTop == myTargetToFind)
215 {
216 hasMore = Standard_True;
217 return;
218 }
219 while (theTypeOfShapeOnTop != myTargetToFind)
220 {
221 Standard_Address theSuccessors = 0L;
222 Standard_Integer theNumberOfSuccessors;
223 (*myShapesDataStructure).GetSuccessors(theNumberOfTheShapeOnTop,(Standard_Address&)theSuccessors,theNumberOfSuccessors);
224 // Do we have enough place to store our new successors ?
225 if ((myTopOfStack+theNumberOfSuccessors > mySizeOfStack) && (theSuccessors != 0L))
226 {
227 Standard_Address theNewStack;
228 theNewStack = (Standard_Integer*)Standard::Allocate
229 ((mySizeOfStack+theNumberOfSuccessors+theStackSize)*sizeof(Standard_Integer));
230 for (j=0;j<myTopOfStack;j++)
231 ((Standard_Integer*)theNewStack)[j] = ((Standard_Integer*)myStack)[j];
232 Standard::Free((Standard_Address&)myStack);
233 myStack = theNewStack;
234 mySizeOfStack = mySizeOfStack+theNumberOfSuccessors+theStackSize;
235 }
236 // We remove the shape on top and replace it by its own successors.
237 // We must skip the shape of type TargetToAvoid.
238 k = 0;
239 anArrayOfBits = (Standard_Integer*)myArrayOfBits;
240 for (j=0;j<theNumberOfSuccessors;j++)
241 {
242 successorNumber = ((Standard_Integer*)theSuccessors)[j];
243 successorType = (*myShapesDataStructure).GetShapeType(successorNumber);
244 shapeAlreadyProcessed = NNNBIT(successorNumber,anArrayOfBits);
245 if ((successorType == myTargetToAvoid) || (shapeAlreadyProcessed==1))
246 k++;
247 else
248 {
249 ((Standard_Integer*)myStack)[j+myTopOfStack-k] = ((Standard_Integer*)theSuccessors)[j];
250 // We need to set the corresponding bit to one to say that we processed this shape.
251 CC1BIT(successorNumber,anArrayOfBits);
252 }
253 }
254 if (theNumberOfSuccessors-k == 0)
255 {
256 // No valid successors...
257 myTopOfStack--;
258 if (myTopOfStack < 0)
259 {
260 // Empty stack...
261 hasMore = Standard_False;
262 return;
263 }
264 }
265 else
266 myTopOfStack = myTopOfStack+theNumberOfSuccessors-k-1;
267 theNumberOfTheShapeOnTop = ((Standard_Integer*)myStack)[myTopOfStack];
268 theTypeOfShapeOnTop = (*myShapesDataStructure).GetShapeType(theNumberOfTheShapeOnTop);
269 if (theTypeOfShapeOnTop == myTargetToFind)
270 {
271 hasMore = Standard_True;
272 return;
273 }
274 }
275}
276
277//===========================================================================
278//function : Dump
279//purpose :
280//===========================================================================
281 void BooleanOperations_OnceExplorer::Dump(Standard_OStream& S) const
282{
283 Standard_Integer u;
284 Standard_Integer* anArrayOfBits;
285 Standard_Integer* theSuccessors;
286
287 theSuccessors = ((Standard_Integer*)myStack);
288 S << "\n" << "Dump of BooleanOperations_Explorer:" << "\n";
289 S << "mySizeOfStack = " << mySizeOfStack << "\n";
290 S << "myTopOfStack = " << myTopOfStack << "\n";
291 S << "myTargetToFind = " << myTargetToFind << "\n";
292 S << "myTargetToAvoid = " << myTargetToAvoid << "\n";
293 S << "hasMore = " << hasMore << "\n";
294 for (u=0;u<=myTopOfStack;u++)
295 {
296 S << " " << *theSuccessors;
297 theSuccessors++;
298 }
299
300 anArrayOfBits = (Standard_Integer*)myArrayOfBits;
301
302 S << "\n" ;
303 for (u=1; u<=mySizeOfArrayOfBits*32; u++)
304 {
305 S << NNNBIT(u,anArrayOfBits);
306 if (u%32==0)
307 S << " ";
308 }
309 S << "\n" ;
310}