0029151: GCC 7.1 warnings "this statement may fall through" [-Wimplicit-fallthrough=]
[occt.git] / src / NCollection / NCollection_CellFilter.hxx
CommitLineData
b311480e 1// Created on: 2007-05-26
2// Created by: Andrey BETENEV
973c2be1 3// Copyright (c) 2007-2014 OPEN CASCADE SAS
b311480e 4//
973c2be1 5// This file is part of Open CASCADE Technology software library.
b311480e 6//
d5f74e42 7// This library is free software; you can redistribute it and/or modify it under
8// the terms of the GNU Lesser General Public License version 2.1 as published
973c2be1 9// by the Free Software Foundation, with special exception defined in the file
10// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11// distribution for complete text of the license and disclaimer of any warranty.
b311480e 12//
973c2be1 13// Alternatively, this file may be used under the terms of Open CASCADE
14// commercial license or contractual agreement.
7fd59977 15
16#ifndef NCollection_CellFilter_HeaderFile
17#define NCollection_CellFilter_HeaderFile
18
19#include <Standard_Real.hxx>
50bc8f96 20#include <NCollection_LocalArray.hxx>
21#include <NCollection_Array1.hxx>
7fd59977 22#include <NCollection_List.hxx>
23#include <NCollection_Map.hxx>
24#include <NCollection_DataMap.hxx>
ddf2fe8e 25#include <NCollection_IncAllocator.hxx>
1c35b92f 26#include <NCollection_TypeDef.hxx>
7fd59977 27
28//! Auxiliary enumeration serving as responce from method Inspect
29enum NCollection_CellFilter_Action
30{
31 CellFilter_Keep = 0, //!< Target is needed and should be kept
32 CellFilter_Purge = 1 //!< Target is not needed and can be removed from the current cell
33};
34
35/**
36 * A data structure for sorting geometric objects (called targets) in
37 * n-dimensional space into cells, with associated algorithm for fast checking
38 * of coincidence (overlapping, intersection, etc.) with other objects
39 * (called here bullets).
40 *
41 * Description
42 *
43 * The algorithm is based on hash map, thus it has linear time of initialization
44 * (O(N) where N is number of cells covered by added targets) and constant-time
45 * search for one bullet (more precisely, O(M) where M is number of cells covered
46 * by the bullet).
47 *
48 * The idea behind the algorithm is to separate each co-ordinate of the space
49 * into equal-size cells. Note that this works well when cell size is
50 * approximately equal to the characteristic size of the involved objects
51 * (targets and bullets; including tolerance eventually used for coincidence
52 * check).
53 *
54 * Usage
55 *
56 * The target objects to be searched are added to the tool by methods Add();
57 * each target is classified as belonging to some cell(s). The data on cells
58 * (list of targets found in each one) are stored in the hash map with key being
59 * cumulative index of the cell by all co-ordinates.
60 * Thus the time needed to find targets in some cell is O(1) * O(number of
61 * targets in the cell).
62 *
63 * As soon as all the targets are added, the algorithm is ready to check for
64 * coincidence.
65 * To find the targets coincident with any given bullet, it checks all the
66 * candidate targets in the cell(s) covered by the bullet object
67 * (methods Inspect()).
68 *
69 * The methods Add() and Inspect() have two flavours each: one accepts
70 * single point identifying one cell, another accept two points specifying
71 * the range of cells. It should be noted that normally at least one of these
72 * methods is called as for range of cells: either due to objects having non-
73 * zero size, or in order to account for the tolerance when objects are points.
74 *
75 * The set of targets can be modified during the process: new targets can be
76 * added by Add(), existing targets can be removed by Remove().
77 *
78 * Implementation
79 *
80 * The algorithm is implemented as template class, thus it is capable to
81 * work with objects of any type. The only argument of the template should be
82 * the specific class providing all necessary features required by the
83 * algorithm:
84 *
85 * - typedef "Target" defining type of target objects.
86 * This type must have copy constructor
87 *
88 * - typedef "Point" defining type of geometrical points used
89 *
90 * - enum Dimension whose value must be dimension of the point
91 *
92 * - method Coord() returning value of the i-th coordinate of the point:
93 *
94 * static Standard_Real Coord (int i, const Point& thePnt);
95 *
96 * Note that index i is from 0 to Dimension-1.
97 *
98 * - method IsEqual() used by Remove() to identify objects to be removed:
99 *
100 * Standard_Boolean IsEqual (const Target& theT1, const Target& theT2);
101 *
102 * - method Inspect() performing necessary actions on the candidate target
103 * object (usially comparison with the currently checked bullet object):
104 *
105 * NCollection_CellFilter_Action Inspect (const Target& theObject);
106 *
107 * The returned value can be used to command CellFilter
108 * to remove the inspected item from the current cell; this allows
109 * to exclude the items that has been processed and are not needed any
110 * more in further search (for better performance).
111 *
112 * Note that method Inspect() can be const and/or virtual.
113 */
114
50bc8f96 115template <class Inspector> class NCollection_CellFilter
116{
7fd59977 117public:
1c35b92f 118 typedef TYPENAME Inspector::Target Target;
119 typedef TYPENAME Inspector::Point Point;
7fd59977 120
121public:
122
50bc8f96 123 //! Constructor; initialized by dimension count and cell size.
7fd59977 124 //!
50bc8f96 125 //! Note: the cell size must be ensured to be greater than
7fd59977 126 //! maximal co-ordinate of the involved points divided by INT_MAX,
127 //! in order to avoid integer overflow of cell index.
128 //!
129 //! By default cell size is 0, which is invalid; thus if default
130 //! constructor is used, the tool must be initialized later with
131 //! appropriate cell size by call to Reset()
a7653f4f 132 //! Constructor when dimension count is unknown at compilation time.
50bc8f96 133 NCollection_CellFilter (const Standard_Integer theDim,
134 const Standard_Real theCellSize = 0,
135 const Handle(NCollection_IncAllocator)& theAlloc = 0)
136 : myCellSize(0, theDim - 1)
7fd59977 137 {
50bc8f96 138 myDim = theDim;
7fd59977 139 Reset (theCellSize, theAlloc);
140 }
141
a7653f4f 142 //! Constructor when dimenstion count is known at compilation time.
143 NCollection_CellFilter (const Standard_Real theCellSize = 0,
144 const Handle(NCollection_IncAllocator)& theAlloc = 0)
145 : myCellSize(0, Inspector::Dimension - 1)
146 {
147 myDim = Inspector::Dimension;
148 Reset (theCellSize, theAlloc);
149 }
150
7fd59977 151 //! Clear the data structures, set new cell size and allocator
152 void Reset (Standard_Real theCellSize,
153 const Handle(NCollection_IncAllocator)& theAlloc=0)
154 {
50bc8f96 155 for (int i=0; i < myDim; i++)
156 myCellSize(i) = theCellSize;
7fd59977 157 resetAllocator ( theAlloc );
158 }
159
160 //! Clear the data structures and set new cell sizes and allocator
e1c1b6b9 161 void Reset (NCollection_Array1<Standard_Real>& theCellSize,
7fd59977 162 const Handle(NCollection_IncAllocator)& theAlloc=0)
163 {
50bc8f96 164 myCellSize = theCellSize;
7fd59977 165 resetAllocator ( theAlloc );
166 }
167
168 //! Adds a target object for further search at a point (into only one cell)
169 void Add (const Target& theTarget, const Point &thePnt)
170 {
171 Cell aCell (thePnt, myCellSize);
172 add (aCell, theTarget);
173 }
174
175 //! Adds a target object for further search in the range of cells
176 //! defined by two points (the first point must have all co-ordinates equal or
177 //! less than the same co-ordinate of the second point)
178 void Add (const Target& theTarget,
179 const Point &thePntMin, const Point &thePntMax)
180 {
181 // get cells range by minimal and maximal co-ordinates
182 Cell aCellMin (thePntMin, myCellSize);
183 Cell aCellMax (thePntMax, myCellSize);
184 Cell aCell = aCellMin;
185 // add object recursively into all cells in range
50bc8f96 186 iterateAdd (myDim-1, aCell, aCellMin, aCellMax, theTarget);
7fd59977 187 }
188
189 //! Find a target object at a point and remove it from the structures.
190 //! For usage of this method "operator ==" should be defined for Target.
191 void Remove (const Target& theTarget, const Point &thePnt)
192 {
193 Cell aCell (thePnt, myCellSize);
194 remove (aCell, theTarget);
195 }
196
197 //! Find a target object in the range of cells defined by two points and
198 //! remove it from the structures
199 //! (the first point must have all co-ordinates equal or
200 //! less than the same co-ordinate of the second point).
201 //! For usage of this method "operator ==" should be defined for Target.
202 void Remove (const Target& theTarget,
203 const Point &thePntMin, const Point &thePntMax)
204 {
205 // get cells range by minimal and maximal co-ordinates
206 Cell aCellMin (thePntMin, myCellSize);
207 Cell aCellMax (thePntMax, myCellSize);
208 Cell aCell = aCellMin;
209 // remove object recursively from all cells in range
50bc8f96 210 iterateRemove (myDim-1, aCell, aCellMin, aCellMax, theTarget);
7fd59977 211 }
212
213 //! Inspect all targets in the cell corresponding to the given point
214 void Inspect (const Point& thePnt, Inspector &theInspector)
215 {
216 Cell aCell (thePnt, myCellSize);
217 inspect (aCell, theInspector);
218 }
219
220 //! Inspect all targets in the cells range limited by two given points
221 //! (the first point must have all co-ordinates equal or
222 //! less than the same co-ordinate of the second point)
223 void Inspect (const Point& thePntMin, const Point& thePntMax,
224 Inspector &theInspector)
225 {
226 // get cells range by minimal and maximal co-ordinates
227 Cell aCellMin (thePntMin, myCellSize);
228 Cell aCellMax (thePntMax, myCellSize);
229 Cell aCell = aCellMin;
230 // inspect object recursively into all cells in range
50bc8f96 231 iterateInspect (myDim-1, aCell,
7fd59977 232 aCellMin, aCellMax, theInspector);
233 }
234
235#if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x530)
236public: // work-around against obsolete SUN WorkShop 5.3 compiler
237#else
238protected:
239#endif
240
241 /**
242 * Auxiliary class for storing points belonging to the cell as the list
243 */
50bc8f96 244 struct ListNode
245 {
246 ListNode()
247 {
248 // Empty constructor is forbidden.
9775fa61 249 throw Standard_NoSuchObject("NCollection_CellFilter::ListNode()");
50bc8f96 250 }
251
7fd59977 252 Target Object;
253 ListNode *Next;
254 };
255
256 /**
257 * Auxilary structure representing a cell in the space.
258 * Cells are stored in the map, each cell contains list of objects
259 * that belong to that cell.
260 */
261 struct Cell
262 {
263 public:
7fd59977 264
265 //! Constructor; computes cell indices
50bc8f96 266 Cell (const Point& thePnt,
267 const NCollection_Array1<Standard_Real>& theCellSize)
268 : index(theCellSize.Size()),
269 Objects(0)
7fd59977 270 {
50bc8f96 271 for (int i = 0; i < theCellSize.Size(); i++)
7fd59977 272 {
50bc8f96 273 Standard_Real val = (Standard_Real)(Inspector::Coord(i, thePnt) / theCellSize(theCellSize.Lower() + i));
7fd59977 274 //If the value of index is greater than
275 //INT_MAX it is decreased correspondingly for the value of INT_MAX. If the value
276 //of index is less than INT_MIN it is increased correspondingly for the absolute
277 //value of INT_MIN.
278 index[i] = long((val > INT_MAX - 1) ? fmod(val, (Standard_Real) INT_MAX)
279 : (val < INT_MIN + 1) ? fmod(val, (Standard_Real) INT_MIN)
280 : val);
281 }
282 }
283
284 //! Copy constructor: ensure that list is not deleted twice
50bc8f96 285 Cell (const Cell& theOther)
286 : index(theOther.index.Size())
287 {
288 (*this) = theOther;
289 }
7fd59977 290
291 //! Assignment operator: ensure that list is not deleted twice
292 void operator = (const Cell& theOther)
293 {
747f90db 294 Standard_Integer aDim = Standard_Integer(theOther.index.Size());
295 for(Standard_Integer anIdx = 0; anIdx < aDim; anIdx++)
50bc8f96 296 index[anIdx] = theOther.index[anIdx];
297
7fd59977 298 Objects = theOther.Objects;
299 ((Cell&)theOther).Objects = 0;
300 }
301
302 //! Destructor; calls destructors for targets contained in the list
303 ~Cell ()
304 {
305 for ( ListNode* aNode = Objects; aNode; aNode = aNode->Next )
306 aNode->Object.~Target();
307 // note that list nodes need not to be freed, since IncAllocator is used
308 Objects = 0;
309 }
310
311 //! Compare cell with other one
312 Standard_Boolean IsEqual (const Cell& theOther) const
313 {
747f90db 314 Standard_Integer aDim = Standard_Integer(theOther.index.Size());
315 for (int i=0; i < aDim; i++)
7fd59977 316 if ( index[i] != theOther.index[i] ) return Standard_False;
317 return Standard_True;
318 }
319
320 //! Compute hash code
321 Standard_Integer HashCode (const Standard_Integer theUpper) const
322 {
323 // number of bits per each dimension in the hash code
747f90db 324 Standard_Integer aDim = Standard_Integer(index.Size());
325 const Standard_Size aShiftBits = (BITS(long)-1) / aDim;
7fd59977 326 long aCode=0;
747f90db 327 for (int i=0; i < aDim; i++)
7fd59977 328 aCode = ( aCode << aShiftBits ) ^ index[i];
329 return (unsigned)aCode % theUpper;
330 }
331
332 public:
50bc8f96 333 NCollection_LocalArray<long, 10> index;
7fd59977 334 ListNode *Objects;
335 };
336
337 // definition of global functions is needed for map
338 friend Standard_Integer HashCode (const Cell &aCell, const Standard_Integer theUpper)
339 { return aCell.HashCode(theUpper); }
340 friend Standard_Boolean IsEqual (const Cell &aCell1, const Cell &aCell2)
341 { return aCell1.IsEqual(aCell2); }
342
343protected:
344
345 //! Reset allocator to the new one
346 void resetAllocator (const Handle(NCollection_IncAllocator)& theAlloc)
347 {
348 if ( theAlloc.IsNull() )
349 myAllocator = new NCollection_IncAllocator;
350 else
351 myAllocator = theAlloc;
352 myCells.Clear ( myAllocator );
353 }
354
355 //! Add a new target object into the specified cell
356 void add (const Cell& theCell, const Target& theTarget)
357 {
358 // add a new cell or get reference to existing one
359 Cell& aMapCell = (Cell&)myCells.Added (theCell);
360
361 // create a new list node and add it to the beginning of the list
362 ListNode* aNode = (ListNode*)myAllocator->Allocate(sizeof(ListNode));
363 new (&aNode->Object) Target (theTarget);
364 aNode->Next = aMapCell.Objects;
365 aMapCell.Objects = aNode;
366 }
367
368 //! Internal addition function, performing iteration for adjacent cells
369 //! by one dimension; called recursively to cover all dimensions
370 void iterateAdd (int idim, Cell &theCell,
371 const Cell& theCellMin, const Cell& theCellMax,
372 const Target& theTarget)
373 {
374 int start = theCellMin.index[idim];
375 int end = theCellMax.index[idim];
376 for (int i=start; i <= end; i++) {
377 theCell.index[idim] = i;
378 if ( idim ) // recurse
379 iterateAdd (idim-1, theCell, theCellMin, theCellMax, theTarget);
380 else // add to this cell
381 add (theCell, theTarget);
382 }
383 }
384
385 //! Remove the target object from the specified cell
386 void remove (const Cell& theCell, const Target& theTarget)
387 {
388 // check if any objects are recorded in that cell
389 if ( ! myCells.Contains (theCell) )
390 return;
391
392 // iterate by objects in the cell and check each
393 Cell& aMapCell = (Cell&)myCells.Added (theCell);
394 ListNode* aNode = aMapCell.Objects;
395 ListNode* aPrev = NULL;
396 while (aNode)
397 {
398 ListNode* aNext = aNode->Next;
399 if (Inspector::IsEqual (aNode->Object, theTarget))
400 {
401 aNode->Object.~Target();
402 (aPrev ? aPrev->Next : aMapCell.Objects) = aNext;
403 // note that aNode itself need not to be freed, since IncAllocator is used
404 }
405 else
406 aPrev = aNode;
407 aNode = aNext;
408 }
409 }
410
411 //! Internal removal function, performing iteration for adjacent cells
412 //! by one dimension; called recursively to cover all dimensions
413 void iterateRemove (int idim, Cell &theCell,
414 const Cell& theCellMin, const Cell& theCellMax,
415 const Target& theTarget)
416 {
417 int start = theCellMin.index[idim];
418 int end = theCellMax.index[idim];
419 for (int i=start; i <= end; i++) {
420 theCell.index[idim] = i;
421 if ( idim ) // recurse
422 iterateRemove (idim-1, theCell, theCellMin, theCellMax, theTarget);
423 else // remove from this cell
424 remove (theCell, theTarget);
425 }
426 }
427
428 //! Inspect the target objects in the specified cell.
429 void inspect (const Cell& theCell, Inspector& theInspector)
430 {
431 // check if any objects are recorded in that cell
432 if ( ! myCells.Contains (theCell) )
433 return;
434
435 // iterate by objects in the cell and check each
436 Cell& aMapCell = (Cell&)myCells.Added (theCell);
437 ListNode* aNode = aMapCell.Objects;
438 ListNode* aPrev = NULL;
439 while(aNode) {
440 ListNode* aNext = aNode->Next;
441 NCollection_CellFilter_Action anAction =
442 theInspector.Inspect (aNode->Object);
443 // delete items requested to be purged
444 if ( anAction == CellFilter_Purge ) {
445 aNode->Object.~Target();
446 (aPrev ? aPrev->Next : aMapCell.Objects) = aNext;
447 // note that aNode itself need not to be freed, since IncAllocator is used
448 }
449 else
450 aPrev = aNode;
451 aNode = aNext;
452 }
453 }
454
455 //! Inspect the target objects in the specified range of the cells
456 void iterateInspect (int idim, Cell &theCell,
457 const Cell& theCellMin, const Cell& theCellMax,
458 Inspector& theInspector)
459 {
460 int start = theCellMin.index[idim];
461 int end = theCellMax.index[idim];
462 for (int i=start; i <= end; i++) {
463 theCell.index[idim] = i;
464 if ( idim ) // recurse
465 iterateInspect (idim-1, theCell, theCellMin, theCellMax, theInspector);
466 else // inspect this cell
467 inspect (theCell, theInspector);
468 }
469 }
470
471protected:
50bc8f96 472 Standard_Integer myDim;
7fd59977 473 Handle(NCollection_BaseAllocator) myAllocator;
474 NCollection_Map<Cell> myCells;
50bc8f96 475 NCollection_Array1<Standard_Real> myCellSize;
7fd59977 476};
477
478/**
479 * Base class defining part of the Inspector interface
480 * for CellFilter algorithm, working with gp_XYZ points in 3d space
481 */
482
483class gp_XYZ;
484struct NCollection_CellFilter_InspectorXYZ
485{
486 //! Points dimension
487 enum { Dimension = 3 };
488
489 //! Points type
490 typedef gp_XYZ Point;
491
492 //! Access to co-ordinate
493 static Standard_Real Coord (int i, const Point &thePnt) { return thePnt.Coord(i+1); }
494
495 //! Auxiliary method to shift point by each coordinate on given value;
496 //! useful for preparing a points range for Inspect with tolerance
497 Point Shift (const Point& thePnt, Standard_Real theTol) const
498 { return Point (thePnt.X() + theTol, thePnt.Y() + theTol, thePnt.Z() + theTol); }
499};
500
501/**
502 * Base class defining part of the Inspector interface
503 * for CellFilter algorithm, working with gp_XY points in 2d space
504 */
505
506class gp_XY;
507struct NCollection_CellFilter_InspectorXY
508{
509 //! Points dimension
510 enum { Dimension = 2 };
511
512 //! Points type
513 typedef gp_XY Point;
514
515 //! Access to co-ordinate
516 static Standard_Real Coord (int i, const Point &thePnt) { return thePnt.Coord(i+1); }
517
518 //! Auxiliary method to shift point by each coordinate on given value;
519 //! useful for preparing a points range for Inspect with tolerance
520 Point Shift (const Point& thePnt, Standard_Real theTol) const
521 { return Point (thePnt.X() + theTol, thePnt.Y() + theTol); }
522};
523
524#endif