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