Usage

Each of the ORQ classes is templated on the following:

• N: The space dimension.
• _Record: The record type.
• _MultiKey: An N-tuple of keys.
• _Key: The number type for keys.
• _MultiKeyAccessor: A functor that takes a record as an argument and returns its multikey. (If possible, a const reference to its multikey.)

For example, the dense cell array is declared as:

template<int N,
         typename _Record,
         typename _MultiKey = typename std::iterator_traits<_Record>::value_type,
         typename _Key = typename _MultiKey::value_type,
         typename _MultiKeyAccessor = ads::Dereference<_Record> >
class CellArray;

Note that the KDTree and the Octree have an additional template parameter: a record output iterator. Also, the Octree is not templated on the space dimension.

The last three template parameters have default values. These are useful in the case that the record type is a handle to a multikey. ("Handle" is a generic term which includes pointers and iterators.) Then the multikey type can be obtained by taking the value type of this handle. The key type can be obtained from the multikey if the multikey is an STL-style container. By default the multikey accessor is just a functor which dereferences the record.

Simple scenario.

Consider the following usage scenario: You are performing a simulation with particles. You use orthogonal range queries to determine the particles which are in a neighborhood of a given particle. A particle has position, velocity, and possibly other fields. You store each of these fields in separate containers, say std::vector .

typedef ads::FixedArray<3, double> Point;
std::vector<Point> positions, velocities;

Here is how to use a cell array to perform orthogonal range queries.

// A record is a const iterator into the container of points.
typedef std::vector<Point>::const_iterator Record;

// Define the class we will use for orthogonal range queries.  It can deduce
// the multi-key type from the record type by dereferencing.  Since 
// ads::FixedArray is an STL-compliant container, the number type can be 
// deduced from the multi-key type.  Finally, the multi-key accessor is the
// default functor, which just dereferences the record.
typedef CellArray<3, Record> Orq;
// Define some geometric types.
typedef Orq::SemiOpenIntervalType SemiOpenIntervalType;
typedef Orq::BBox BBox;
typedef Orq::Point Point;

// Build the ORQ class.  The suggested cell size is 0.1 x 0.1 x 0.1.  The 
// domain is the semi-open interval [-1..1) x[-1..1) x[-1..1).  We insert
// all of the records in the positions vector.
Orq orq(Point(0.1, 0.1, 0.1), SemiOpenInterval(Point(-1, -1, -1), Point(1, 1, 1)), positions.begin(), positions.end());

Now we are ready to perform window queries.

// We want to get the records in the window [0..0.5] x [0..0.5] x [0..0.5].
BBox window(Point(0, 0, 0), Point(0.5, 0.5, 0.5));
std::vector<Record> inside;
orq.computeWindowQuery(std::back_inserter(inside), window);
std::cout << "Positions and velocities of the records in the window.\n";
for (std::vector<Record>::const_iterator i = inside.begin(); i != inside.end(); ++i) {
  // i is an iterator to a record.  *i is a record.  **i is multi-key, 
  // which is a Cartesian point.  We can take the difference of the record
  // *i and the record positions.begin() to get the index of the record in
  // our container: positions.  This index lets us access the velocity.
  std::cout << "Position = " << **i << ", Velocity = " << velocities[*i - positions.begin()] << "\n";
}
inside.clear();

More sophisticated scenario.

Now suppose that instead of storing each attribute of a particle in a separate container, you use a class to represent a particle.

class Particle {
public:
  typedef ads::FixedArray<3, double> Point;

private:
  Point _position;
  Point _velocity;
  ...

public:
  const Point&
  getPosition() const {
    return _position;
  }
  ...
};

Suppose that you store the particles in a std::vector.

std::vector<Particle> particles;

Here is how to use a cell array to perform orthogonal range queries.

// A record is a const iterator into the container of particles.
typedef std::vector<Particle>::const_iterator Record;
// The particle point type is the multikey.
typedef Particle::Point MultiKey;

// The functor to access the multikey.
struct ParticleLocationAccessor : 
  public std::unary_function<Record,MultiKey> {
  const MultiKey&
  operator()(const Record& record) const {
    return record->getPosition();
  }
}

// Define the class we will use for orthogonal range queries.
typedef CellArray<3, Record, MultiKey, double, ParticleLocationAccessor> Orq;
typedef Orq::SemiOpenIntervalType SemiOpenIntervalType;
typedef Orq::BBox BBox;
typedef Orq::Point Point;

// Build the ORQ class.
Orq orq(Point(0.1, 0.1, 0.1), SemiOpenInterval(Point(-1, -1, -1), Point(1, 1, 1)));
for (Record i = particles.begin(), i != particles.end(); ++i) {
  orq.insert(i);
}

Now we are ready to perform window queries.

BBox window(Point(0, 0, 0), Point(0.5, 0.5, 0.5));
// Just for variety, we'll store the records in a std::list.
std::list<Record> inside;
orq.computeWindowQuery(std::back_inserter(inside), window);
Particle::Point position;
for (std::list<Record>::const_iterator i = inside.begin(); i != inside.end(); ++i) {
  position = (*i)->getLocation();
  ...
}
inside.clear();