path: root/inc/NCollection_CellFilter.hxx

// File:      NCollection_CellFilter.hxx
// Created:   Sat May 26 06:05:25 2007
// Author:    Andrey BETENEV
// Copyright: Open CASCADE SAS 2007

#ifndef NCollection_CellFilter_HeaderFile
#define NCollection_CellFilter_HeaderFile

#include <Standard_Real.hxx>
#include <NCollection_List.hxx>
#include <NCollection_Map.hxx>
#include <NCollection_DataMap.hxx>
#include <NCollection_BaseAllocator.hxx>

// work-around for obsolete SUN WorkShop 5.3 compiler 
// which does not recognize typename keyword
#if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x530) && ! defined(typename)
#define typename
#endif

//! Auxiliary enumeration serving as responce from method Inspect
enum NCollection_CellFilter_Action 
{
  CellFilter_Keep  = 0, //!< Target is needed and should be kept
  CellFilter_Purge = 1  //!< Target is not needed and can be removed from the current cell
};

/**
 * A data structure for sorting geometric objects (called targets) in 
 * n-dimensional space into cells, with associated algorithm for fast checking 
 * of coincidence (overlapping, intersection, etc.) with other objects 
 * (called here bullets).
 *
 * Description
 * 
 * The algorithm is based on hash map, thus it has linear time of initialization 
 * (O(N) where N is number of cells covered by added targets) and constant-time 
 * search for one bullet (more precisely, O(M) where M is number of cells covered 
 * by the bullet).
 *
 * The idea behind the algorithm is to separate each co-ordinate of the space 
 * into equal-size cells. Note that this works well when cell size is 
 * approximately equal to the characteristic size of the involved objects 
 * (targets and bullets; including tolerance eventually used for coincidence 
 * check). 
 *
 * Usage
 *
 * The target objects to be searched are added to the tool by methods Add(); 
 * each target is classified as belonging to some cell(s). The data on cells 
 * (list of targets found in each one) are stored in the hash map with key being 
 * cumulative index of the cell by all co-ordinates.
 * Thus the time needed to find targets in some cell is O(1) * O(number of 
 * targets in the cell).
 *
 * As soon as all the targets are added, the algorithm is ready to check for 
 * coincidence.
 * To find the targets coincident with any given bullet, it checks all the 
 * candidate targets in the cell(s) covered by the bullet object 
 * (methods Inspect()).
 *
 * The methods Add() and Inspect() have two flavours each: one accepts
 * single point identifying one cell, another accept two points specifying
 * the range of cells. It should be noted that normally at least one of these
 * methods is called as for range of cells: either due to objects having non-
 * zero size, or in order to account for the tolerance when objects are points.
 *
 * The set of targets can be modified during the process: new targets can be
 * added by Add(), existing targets can be removed by Remove().
 *
 * Implementation
 *
 * The algorithm is implemented as template class, thus it is capable to 
 * work with objects of any type. The only argument of the template should be 
 * the specific class providing all necessary features required by the 
 * algorithm:
 *
 * - typedef "Target" defining type of target objects.
 *   This type must have copy constructor
 *
 * - typedef "Point" defining type of geometrical points used 
 *
 * - enum Dimension whose value must be dimension of the point
 *
 * - method Coord() returning value of the i-th coordinate of the point:
 *
 *   static Standard_Real Coord (int i, const Point& thePnt);
 *
 *   Note that index i is from 0 to Dimension-1.
 *
 * - method IsEqual() used by Remove() to identify objects to be removed:
 *
 *   Standard_Boolean IsEqual (const Target& theT1, const Target& theT2);
 *
 * - method Inspect() performing necessary actions on the candidate target 
 *   object (usially comparison with the currently checked bullet object):
 *
 *   NCollection_CellFilter_Action Inspect (const Target& theObject);
 *
 *   The returned value can be used to command CellFilter
 *   to remove the inspected item from the current cell; this allows
 *   to exclude the items that has been processed and are not needed any 
 *   more in further search (for better performance).
 *
 *   Note that method Inspect() can be const and/or virtual.
 */

template <class Inspector> 
class NCollection_CellFilter
{  
public:
  typedef typename Inspector::Target Target;
  typedef typename Inspector::Point  Point;

public:

  //! Constructor; initialized by cell size.
  //!
  //! Note: the cell size must be ensured to be greater than 
  //! maximal co-ordinate of the involved points divided by INT_MAX,
  //! in order to avoid integer overflow of cell index.
  //! 
  //! By default cell size is 0, which is invalid; thus if default
  //! constructor is used, the tool must be initialized later with
  //! appropriate cell size by call to Reset()
  NCollection_CellFilter (Standard_Real theCellSize=0,
                          const Handle(NCollection_IncAllocator)& theAlloc=0) 
  {
    Reset (theCellSize, theAlloc);
  }

  //! Constructor; initialized by cell sizes along each dimension.
  //! Note: the cell size in each dimension must be ensured to be greater than 
  //! maximal co-ordinate of the involved points by this dimension divided by INT_MAX,
  //! in order to avoid integer overflow of cell index.
  NCollection_CellFilter (Standard_Real theCellSize[],
                          const Handle(NCollection_IncAllocator)& theAlloc=0) 
  {
    Reset (theCellSize, theAlloc);
  }

  //! Clear the data structures, set new cell size and allocator
  void Reset (Standard_Real theCellSize, 
              const Handle(NCollection_IncAllocator)& theAlloc=0)
  {
    for (int i=0; i < Inspector::Dimension; i++)
      myCellSize[i] = theCellSize;    
    resetAllocator ( theAlloc );
  }

  //! Clear the data structures and set new cell sizes and allocator
  void Reset (Standard_Real theCellSize[], 
              const Handle(NCollection_IncAllocator)& theAlloc=0)
  {
    for (int i=0; i < Inspector::Dimension; i++)
      myCellSize[i] = theCellSize[i];
    resetAllocator ( theAlloc );
  }
  
  //! Adds a target object for further search at a point (into only one cell)
  void Add (const Target& theTarget, const Point &thePnt)
  {
    Cell aCell (thePnt, myCellSize);
    add (aCell, theTarget);
  }

  //! Adds a target object for further search in the range of cells 
  //! defined by two points (the first point must have all co-ordinates equal or
  //! less than the same co-ordinate of the second point)
  void Add (const Target& theTarget, 
	    const Point &thePntMin, const Point &thePntMax)
  {
    // get cells range by minimal and maximal co-ordinates
    Cell aCellMin (thePntMin, myCellSize);
    Cell aCellMax (thePntMax, myCellSize);
    Cell aCell = aCellMin;
    // add object recursively into all cells in range
    iterateAdd (Inspector::Dimension-1, aCell, aCellMin, aCellMax, theTarget);
  }

  //! Find a target object at a point and remove it from the structures.
  //! For usage of this method "operator ==" should be defined for Target.
  void Remove (const Target& theTarget, const Point &thePnt)
  {
    Cell aCell (thePnt, myCellSize);
    remove (aCell, theTarget);
  }

  //! Find a target object in the range of cells defined by two points and
  //! remove it from the structures
  //! (the first point must have all co-ordinates equal or
  //! less than the same co-ordinate of the second point).
  //! For usage of this method "operator ==" should be defined for Target.
  void Remove (const Target& theTarget, 
               const Point &thePntMin, const Point &thePntMax)
  {
    // get cells range by minimal and maximal co-ordinates
    Cell aCellMin (thePntMin, myCellSize);
    Cell aCellMax (thePntMax, myCellSize);
    Cell aCell = aCellMin;
    // remove object recursively from all cells in range
    iterateRemove (Inspector::Dimension-1, aCell, aCellMin, aCellMax, theTarget);
  }

  //! Inspect all targets in the cell corresponding to the given point
  void Inspect (const Point& thePnt, Inspector &theInspector) 
  {
    Cell aCell (thePnt, myCellSize);
    inspect (aCell, theInspector);
  }

  //! Inspect all targets in the cells range limited by two given points
  //! (the first point must have all co-ordinates equal or
  //! less than the same co-ordinate of the second point)
  void Inspect (const Point& thePntMin, const Point& thePntMax, 
                Inspector &theInspector) 
  {
    // get cells range by minimal and maximal co-ordinates
    Cell aCellMin (thePntMin, myCellSize);
    Cell aCellMax (thePntMax, myCellSize);
    Cell aCell = aCellMin;
    // inspect object recursively into all cells in range
    iterateInspect (Inspector::Dimension-1, aCell, 
                    aCellMin, aCellMax, theInspector);
  }
//Borland needs to have the Cell struct public in order to access it from
//the global functions HashCode and IsEqual ... See below on the declarations of them
#if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x530) || defined(__BORLANDC__)
public: // work-around against obsolete SUN WorkShop 5.3 compiler
#else
protected:
#endif
 
  /**
   * Auxiliary class for storing points belonging to the cell as the list
   */
  struct ListNode {
    Target Object;
    ListNode *Next;
  };

  /**
   * Auxilary structure representing a cell in the space. 
   * Cells are stored in the map, each cell contains list of objects 
   * that belong to that cell.
   */
  struct Cell
  {
  public:
    //! Empty constructor -- required only for NCollection_Map,
    //! therefore does not initialize index (avoid cycle)
    Cell () : Objects(0) {}

    //! Constructor; computes cell indices
    Cell (const Point& thePnt, const Standard_Real theCellSize[])
      : Objects(0)
    {
      for (int i=0; i < Inspector::Dimension; i++)
      {
          Standard_Real val = (Standard_Real)(Inspector::Coord(i, thePnt) / theCellSize[i]);
          //If the value of index is greater than
          //INT_MAX it is decreased correspondingly for the value of INT_MAX. If the value
          //of index is less than INT_MIN it is increased correspondingly for the absolute
          //value of INT_MIN.
          index[i] = long((val > INT_MAX - 1) ? fmod(val, (Standard_Real) INT_MAX) 
                                               : (val < INT_MIN + 1) ? fmod(val, (Standard_Real) INT_MIN)
                                                                     : val);
      }
    }

    //! Copy constructor: ensure that list is not deleted twice
    Cell (const Cell& theOther) { (*this) = theOther; }

    //! Assignment operator: ensure that list is not deleted twice
    void operator = (const Cell& theOther)
    {
      for (int i=0; i < Inspector::Dimension; i++)
        index[i] = theOther.index[i];
      Objects = theOther.Objects;
      ((Cell&)theOther).Objects = 0;
    }

    //! Destructor; calls destructors for targets contained in the list
    ~Cell ()
    {
      for ( ListNode* aNode = Objects; aNode; aNode = aNode->Next )
        aNode->Object.~Target();
      // note that list nodes need not to be freed, since IncAllocator is used
      Objects = 0;
    }

    //! Compare cell with other one
    Standard_Boolean IsEqual (const Cell& theOther) const
    {
      for (int i=0; i < Inspector::Dimension; i++) 
        if ( index[i] != theOther.index[i] ) return Standard_False;
      return Standard_True;
    }

    //! Compute hash code
    Standard_Integer HashCode (const Standard_Integer theUpper) const
    {
      // number of bits per each dimension in the hash code
      const Standard_Size aShiftBits = (BITS(long)-1) / Inspector::Dimension;
      long aCode=0;
      for (int i=0; i < Inspector::Dimension; i++)
        aCode = ( aCode << aShiftBits ) ^ index[i];
      return (unsigned)aCode % theUpper;
    }

  public:
    long index[Inspector::Dimension];
    ListNode *Objects;
  };

  // definition of global functions is needed for map
#ifdef __BORLANDC__
  //It seems that Borland compiler does not support template friends ...
  //If one wants to use the below global functions must instantiate them outside the
  //class body.See MeshAlgo_CellFilter.hxx file
  template <class CellContainer>
  friend Standard_Integer HashCode (const CellContainer::Cell &aCell, const Standard_Integer theUpper);
  template <class CellContainer>
  friend Standard_Boolean IsEqual (const CellContainer::Cell &aCell1, const CellContainer::Cell &aCell2);
#else
  friend Standard_Integer HashCode (const Cell &aCell, const Standard_Integer theUpper)
  { return aCell.HashCode(theUpper); }
  friend Standard_Boolean IsEqual (const Cell &aCell1, const Cell &aCell2)
  { return aCell1.IsEqual(aCell2); }
#endif

protected:

  //! Reset allocator to the new one
  void resetAllocator (const Handle(NCollection_IncAllocator)& theAlloc)
  {
    if ( theAlloc.IsNull() )
      myAllocator = new NCollection_IncAllocator;
    else 
      myAllocator = theAlloc;
    myCells.Clear ( myAllocator );
  }
  
  //! Add a new target object into the specified cell
  void add (const Cell& theCell, const Target& theTarget)
  {
    // add a new cell or get reference to existing one
    Cell& aMapCell = (Cell&)myCells.Added (theCell);

    // create a new list node and add it to the beginning of the list
    ListNode* aNode = (ListNode*)myAllocator->Allocate(sizeof(ListNode));
    new (&aNode->Object) Target (theTarget);
    aNode->Next = aMapCell.Objects;
    aMapCell.Objects = aNode;
  }

  //! Internal addition function, performing iteration for adjacent cells
  //! by one dimension; called recursively to cover all dimensions
  void iterateAdd (int idim, Cell &theCell, 
		   const Cell& theCellMin, const Cell& theCellMax, 
                   const Target& theTarget)
  {
    int start = theCellMin.index[idim];
    int end   = theCellMax.index[idim];
    for (int i=start; i <= end; i++) {
      theCell.index[idim] = i;
      if ( idim ) // recurse
        iterateAdd (idim-1, theCell, theCellMin, theCellMax, theTarget);
      else // add to this cell
        add (theCell, theTarget);
    }
  }
  
  //! Remove the target object from the specified cell
  void remove (const Cell& theCell, const Target& theTarget)
  {
    // check if any objects are recorded in that cell
    if ( ! myCells.Contains (theCell) ) 
      return;

    // iterate by objects in the cell and check each
    Cell& aMapCell = (Cell&)myCells.Added (theCell);
    ListNode* aNode = aMapCell.Objects;
    ListNode* aPrev = NULL;
    while (aNode)
    {
      ListNode* aNext = aNode->Next;
      if (Inspector::IsEqual (aNode->Object, theTarget))
      {
        aNode->Object.~Target();
        (aPrev ? aPrev->Next : aMapCell.Objects) = aNext;
        // note that aNode itself need not to be freed, since IncAllocator is used
      }
      else
        aPrev = aNode;
      aNode = aNext;
    }
  }

  //! Internal removal function, performing iteration for adjacent cells
  //! by one dimension; called recursively to cover all dimensions
  void iterateRemove (int idim, Cell &theCell, 
                      const Cell& theCellMin, const Cell& theCellMax, 
                      const Target& theTarget)
  {
    int start = theCellMin.index[idim];
    int end   = theCellMax.index[idim];
    for (int i=start; i <= end; i++) {
      theCell.index[idim] = i;
      if ( idim ) // recurse
        iterateRemove (idim-1, theCell, theCellMin, theCellMax, theTarget);
      else // remove from this cell
        remove (theCell, theTarget);
    }
  }

  //! Inspect the target objects in the specified cell.
  void inspect (const Cell& theCell, Inspector& theInspector) 
  {
    // check if any objects are recorded in that cell
    if ( ! myCells.Contains (theCell) ) 
      return;

    // iterate by objects in the cell and check each
    Cell& aMapCell = (Cell&)myCells.Added (theCell);
    ListNode* aNode = aMapCell.Objects;
    ListNode* aPrev = NULL;
    while(aNode) {
      ListNode* aNext = aNode->Next;
      NCollection_CellFilter_Action anAction = 
        theInspector.Inspect (aNode->Object);
      // delete items requested to be purged
      if ( anAction == CellFilter_Purge ) {
        aNode->Object.~Target();
        (aPrev ? aPrev->Next : aMapCell.Objects) = aNext;
        // note that aNode itself need not to be freed, since IncAllocator is used
      }
      else
        aPrev = aNode;
      aNode = aNext;      
    }
  }

  //! Inspect the target objects in the specified range of the cells
  void iterateInspect (int idim, Cell &theCell, 
	               const Cell& theCellMin, const Cell& theCellMax, 
                       Inspector& theInspector) 
  {
    int start = theCellMin.index[idim];
    int end   = theCellMax.index[idim];
    for (int i=start; i <= end; i++) {
      theCell.index[idim] = i;
      if ( idim ) // recurse
        iterateInspect (idim-1, theCell, theCellMin, theCellMax, theInspector);
      else // inspect this cell
        inspect (theCell, theInspector);
    }
  }

protected:
  Handle(NCollection_BaseAllocator) myAllocator;
  NCollection_Map<Cell>             myCells;
  Standard_Real                     myCellSize [Inspector::Dimension];
};

/**
 * Base class defining part of the Inspector interface 
 * for CellFilter algorithm, working with gp_XYZ points in 3d space
 */

class gp_XYZ;
struct NCollection_CellFilter_InspectorXYZ
{
  //! Points dimension
  enum { Dimension = 3 };

  //! Points type
  typedef gp_XYZ Point;

  //! Access to co-ordinate
  static Standard_Real Coord (int i, const Point &thePnt) { return thePnt.Coord(i+1); }
  
  //! Auxiliary method to shift point by each coordinate on given value;
  //! useful for preparing a points range for Inspect with tolerance
  Point Shift (const Point& thePnt, Standard_Real theTol) const 
  { return Point (thePnt.X() + theTol, thePnt.Y() + theTol, thePnt.Z() + theTol); }
};

/**
 * Base class defining part of the Inspector interface 
 * for CellFilter algorithm, working with gp_XY points in 2d space
 */

class gp_XY;
struct NCollection_CellFilter_InspectorXY
{
  //! Points dimension
  enum { Dimension = 2 };

  //! Points type
  typedef gp_XY Point;

  //! Access to co-ordinate
  static Standard_Real Coord (int i, const Point &thePnt) { return thePnt.Coord(i+1); }

  //! Auxiliary method to shift point by each coordinate on given value;
  //! useful for preparing a points range for Inspect with tolerance
  Point Shift (const Point& thePnt, Standard_Real theTol) const 
  { return Point (thePnt.X() + theTol, thePnt.Y() + theTol); }
};

#endif