Basic Concepts

The main functionality of libfbi is the fast determination of pairs of intersection boxes from two sets. With respect to the interface, this functionality is provided by a single static function:

fbi::setA<BoxType1, TIndices1>::setB<BoxType2, TIndices2>::intersect(a, aBoxGen,  b, bBoxGen)

where a is the container (e.g. std::vector) of elements that make up the first set and b is the container that makes up the second set. The function returns a std::list of std::sets that holds the adjecency information for each element in both sets (the adjacency list index starts at 0, indexes all elements in a, then continues indexing all elements in b).

Using intersect(...)

It is important to realize that libfbi never touches the data contained in a or b. Instead, it constructs a box for each element in a and b on the fly and uses these boxes throughout the calculation. But how does libfbi acquire this information? This is where the user comes in: it is the task of the user to provide libfbi with functions that deliver the interval information in each dimension. Assume we have a type X. X has many data members, but for the context of the range search only a few of them are relevant:

struct X {
    double a, b, c, d, e, f, g, h, i, j;
    double sigma_b, sigma_h;
}

Assuming that the box intersection should be conducted for b and h, the user would provide the helper functions that extract the relevant information:

class BoxGeneratorX
{
  public:
    BoxGeneratorX(...) : ... {}

    template <size_t N>
      typename fbi::tuple_element<N,
      typename fbi::Traits<X>::key_type>::type
    get(const X&) const;
};

template <>
std::pair<double, double>
BoxGeneratorX::get<0>(const X& x) const
{
    return std::make_pair(x.b-3*x.sigma_b, x.b+3*x.sigma_b);
}

template <>
std::pair<double, double>
BoxGeneratorX::get<1>(const X& x) const
{
    return std::make_pair(x.g-3*x.sigma_g, x.g+3*x.sigma_g);
}

The get<0> accessor function now returns an interval for x.b and get<1> returns an interval for x.h. Assuming that we would like to intersect elements of type X with elements of type Y, we also need a definition for Y:

struct Y {
    double m, n, o, p, q;
};

The accessor functions for BoxGeneratorY can now be implemented similar to those for X, e.g:

class BoxGeneratorY
{
  public:
    BoxGeneratorY(...) : ... {}

    template <size_t N>
      typename fbi::tuple_element<N,
      typename fbi::Traits<Y>::key_type>::type
    get(const Y&) const;
};

template <>
std::pair<double, double>
BoxGeneratorY::get<0>(const Y& y) const
{
    return std::make_pair(y.m-7.54, y.m+1.3);
}

template <>
std::pair<double, double>
BoxGeneratorY::get<1>(const Y& y) const
{
    // this interval is completely to the left of y.p; this is possible.
    return std::make_pair(y.p-3.14, y.p-1.14);
}

Once the respective declarations and definitions are in place, calling the fast box intersection procedure is simply accomplished by

auto adjList = fbi::setA<X, 1, 2>::setB<Y, 1, 2>::intersect(x, BoxGeneratorX,
y, BoxGeneratorY);

where x and y are containers of instances of X and Y, respectively.

In the common use case where one is interested in self-intersection of a set of boxes, libfbi provides a useful shortcut. Assume one wants to determine the set of boxes in a that overlap with each other, given the box definition for the X type from above. In that case, the expression simplifies to

auto adjList = fbi::setA<X, 1, 2>::intersect(x, BoxGeneratorX);

Using the adjacency list

The call to intersect(...) returns an adjacency list, which in general is a std::vector<std::set<size_t> > object. The adjacency list has size x.size() + y.size(), is indexed starting from 0, runs through the indexes of all elements of x, and continues to index all elements of y. Hence the query results for x[k] are given by

...
std::set<size_t> queryResultIndexes = adjList[k];
...

However, note that the indexes for all elements in y are shifted by x.size(). Hence, indexing the elements of y requires some index calculation. For y[k], the query result is available with:

...
std::set<size_t> queryResultIndexes = adjList[k+x.size()];
...

The following illustrates indexing elements in y given its index in the adjacency list:

...
size_t shift = x.size();
typedef std::vector<std::set<size_t> >::const_iterator VSCI;
for (VSCI i = adjList.begin(); i != adjList.end(); ++i) {
    std::cout << x[std::distance(adjList.begin(), i)] << '\n';
    typedef std::set<size_t>::const_iterator SCI; 
    for (SCI j = i->begin(); j != i->end(); ++j) {
        std::cout << "  +- " << y[*j - shift] << '\n';
    }
}

This code will print all elements in x and y, each with all its neighbors indented beneath it. Note that (because box intersection calculates undirected graphs) this prints each pair twice: for every combination (m,n) present in adjList, there is also the combination (n,m).