[boost] more on SMTL

From: conrado_at_[hidden]
Date: 2003-07-28 04:38:25

Dear Boost friends,

Thanks for all the comments. They encourage us to go ahead with our
plans for SMTL. SMTL spatial maps are implemented with Kd-trees and metric
containers are implemented with vantage-point trees (vp-trees), but
many other implementations are possible and we would like to support
several alternatives so that the user could choose the one most
appropriate to his needs. 

I'm now giving some sample code for spatial maps (= kd_trees). 

Cheers,
Conrado

//////////////////////////////////////////////////////////////////////////
//
//
using namespace smtl;

// for each city we store its coordinates (x,y) and its name
// the dimension of the keys is 2

typedef kd_tree<2, std::vector<double>, std::string> cities_container;
cities_container some_cities;

std::vector<double> z(2);
z[0] = 35; z[1] = 50;
some_cities.insert(std::make_pair(z, "Barcelona"));
z[0] = 33; z[1] = 47;
some_cities.insert(std::make_pair(z, "Tarragona"));
...

// insert actually returns a pair, consisting of an iterator to the new
// inserted item and/or to the already existing item with the given
// key, and a boolean which is true if and only the insertion is made
z[0] = 37; z[1] = 52;
std::pair<cities_container::iterator, bool> insertion_result = 
              some_cities.insert(std::make_pair(z, "Girona"));

// look up a city with given coordinates  
// the container also provides forward iterators 'begin' and 'end' 
// so most STL algorithms can be applied; but member 'find' runs in
// O(log N) 

z[0] = 35; z[1] = 50;
cities_container::iterator it = some_cities.find(z);
if (it != some_cities.end()) { 
 std::cout << "The city is " << it -> second << endl;
}

// queries are objects ... 
// cities_container::dimension = 2, cities_container::key_type = vector<double>

range_query<cities_container::dimension,cities_container::key_type> Q;

// obtain all cities such that 20 <= x <= 40 and 35 <= y <= 60

Q.set_ith_lower_bound(0, 20); // a third boolean parameter of
                              // set_ith_... indicates if
Q.set_ith_upper_bound(0, 40); // interval extreme is closed or open;
                              // defaults to open = false
Q.set_ith_lower_bound(1, 35); // lower_boud = -"infinity"  if not set
Q.set_ith_upper_bound(1, 60); // upper_bound = +"infinity" if not set

cities_container::query_result R = some_cities.query(Q);
std::for_each(R.begin(), R.end(), do_something);  

// spatial maps = kd_trees support nearest_neighbors search under
// Minkowski metrics L_k (but not for general metrics); L_2 is the usual
// euclidean distance in R^d space but squared. We do not extract square roots   
// since they do not matter when computing who is closest ...

typedef L_metric<2, cities_container::dimension,cities_container::key_type> L2;
z[0] = 31; z[1] = 46;
incremental_nearest_neighbor_query<cities_container::key_type,L2> Q(z);
cities_container::query_result R = some_cities.query(Q);
cities_container::query_iterator it = R.begin();

// get K closest neighbors to z, in order of increasing distance
for (int i = 0; it != R.end() && i < K; ++i) {
    do_something(*it); // it -> first = coordinates; it -> second = name
    ++it;
}

// the same as before but now query_iterator point to pairs <distance,item>
// these score_query_iterators are interesting to avoid redundant
// (and likely expensive) computation of distances

cities_container::score_query_result R = some_cities.query(Q);
cities_container::score_query_iterator it = R.begin();
// get K closest neighbors to z, in order of increasing distance
for (int i = 0; it != R.end() && i < K; ++i) {
    do_something(*it); // it -> first = distance^2 to z; extract
                       //               square root to obtain real distance
                       // it -> second = <coord, name>  
    ++it;
}