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