#include <ctime>
#include <cmath>
#include <cstring>
#include <fstream>
#include <ANN/ANN.h>
#include <ANN/ANNx.h>
#include <ANN/ANNperf.h>
#include "rand.h"

Include dependency graph for ann_test.cpp:

Go to the source code of this file.

Macros
#define	CLOCKS_PER_SEC 1000000

#define	log2(x) (log(x)/log(2.0))

Enumerations
enum	PtType { DATA, QUERY }

enum	StatLev { SILENT, EXEC_TIME, PREP_STATS, QUERY_STATS, QUERY_RES, SHOW_PTS, SHOW_STRUCT, N_STAT_LEVELS }

enum	Distrib { UNIFORM, GAUSS, LAPLACE, CO_GAUSS, CO_LAPLACE, CLUS_GAUSS, CLUS_ORTH_FLATS, CLUS_ELLIPSOIDS, PLANTED, N_DISTRIBS }

Functions
void	Error (const char *msg, ANNerr level)

void	printPoint (ANNpoint p, int dim)

int	lookUp (const char arg, const char(table)[STRING_LEN], int size)

void	generatePts (ANNpointArray &pa, int n, PtType type, ANNbool new_clust, ANNpointArray src=NULL, int n_src=0)

void	readPts (ANNpointArray &pa, int &n, char *file_nm, PtType type)

void	doValidation ()

void	getTrueNN ()

void	treeStats (ostream &out, ANNbool verbose)

void	initGlobals ()

ANNbool	skipComment (istream &in)

ANNbool	getDirective (istream &in, char *directive)

int	main (int argc, char **argv)

Variables
const int	STRING_LEN = 500

const double	ERR = 0.00001

const double	RND_OFF = 5E-16

const char	stat_table [N_STAT_LEVELS][STRING_LEN]

const char	distr_table [N_DISTRIBS][STRING_LEN]

const int	N_SPLIT_RULES = 6

const char	split_table [N_SPLIT_RULES][STRING_LEN]

const int	N_SHRINK_RULES = 4

const char	shrink_table [N_SHRINK_RULES][STRING_LEN]

const int	extra_nn = 10

const int	def_dim = 2

const int	def_data_size = 100

const int	def_query_size = 100

const int	def_n_color = 5

const ANNbool	def_new_clust = ANNfalse

const int	def_max_dim = 1

const Distrib	def_distr = UNIFORM

const double	def_std_dev = 1.00

const double	def_corr_coef = 0.05

const int	def_bucket_size = 1

const double	def_epsilon = 0.0

const int	def_near_neigh = 1

const int	def_max_visit = 0

const int	def_rad_bound = 0

const int	def_true_nn = def_near_neigh + extra_nn

const int	def_seed = 0

const ANNbool	def_validate = ANNfalse

const StatLev	def_stats = QUERY_STATS

const ANNsplitRule	def_split = ANN_KD_SUGGEST

const ANNshrinkRule	def_shrink = ANN_BD_NONE

int	dim

int	data_size

int	query_size

int	n_color

ANNbool	new_clust

int	max_dim

Distrib	distr

double	corr_coef

double	std_dev

double	std_dev_lo

double	std_dev_hi

int	bucket_size

double	epsilon

int	near_neigh

int	max_pts_visit

double	radius_bound

int	true_nn

ANNbool	validate

StatLev	stats

ANNsplitRule	split

ANNshrinkRule	shrink

ANNpointArray	data_pts

ANNpointArray	query_pts

ANNbd_tree *	the_tree

ANNidxArray	apx_nn_idx

ANNdistArray	apx_dists

int *	apx_pts_in_range

ANNidxArray	true_nn_idx

ANNdistArray	true_dists

int *	min_pts_in_range

int *	max_pts_in_range

ANNbool	valid_dirty

Macro Definition Documentation

#define CLOCKS_PER_SEC 1000000

Definition at line 52 of file ann_test.cpp.

Referenced by main().

#define log2 ( x ) (log(x)/log(2.0))

Definition at line 1570 of file ann_test.cpp.

Referenced by treeStats().

Enumeration Type Documentation

enum Distrib

Enumerator
UNIFORM
GAUSS
LAPLACE
CO_GAUSS
CO_LAPLACE
CLUS_GAUSS
CLUS_ORTH_FLATS
CLUS_ELLIPSOIDS
PLANTED
N_DISTRIBS

Definition at line 321 of file ann_test.cpp.

              {                                  // distributions
                 UNIFORM,                                                // uniform over cube [-1,1]^d.
                 GAUSS,                                                  // Gaussian with mean 0
                 LAPLACE,                                                // Laplacian, mean 0 and var 1
                 CO_GAUSS,                                               // correlated Gaussian
                 CO_LAPLACE,                                             // correlated Laplacian
                 CLUS_GAUSS,                                             // clustered Gaussian
                 CLUS_ORTH_FLATS,                                // clustered on orthog flats
                 CLUS_ELLIPSOIDS,                                // clustered on ellipsoids
                 PLANTED,                                                // planted distribution
                 N_DISTRIBS}

enum PtType

Enumerator
DATA
QUERY

Definition at line 291 of file ann_test.cpp.

291 {DATA, QUERY} PtType; // point types

PtType

Definition: ann_test.cpp:291

QUERY

Definition: ann_test.cpp:291

DATA

Definition: ann_test.cpp:291

enum StatLev

Enumerator
SILENT
EXEC_TIME
PREP_STATS
QUERY_STATS
QUERY_RES
SHOW_PTS
SHOW_STRUCT
N_STAT_LEVELS

Definition at line 297 of file ann_test.cpp.

              {                                  // stat levels
                 SILENT,                                                 // no output
                 EXEC_TIME,                                              // just execution time
                 PREP_STATS,                                             // preprocessing info
                 QUERY_STATS,                                    // query performance
                 QUERY_RES,                                              // query results
                 SHOW_PTS,                                               // show data points
                 SHOW_STRUCT,                                    // show tree structure
                 N_STAT_LEVELS}                                  // number of levels

Function Documentation

void doValidation ( )

Definition at line 1467 of file ann_test.cpp.

References ann_average_err, ANN_DBL_MAX, ANN_NULL_IDX, ann_rank_err, ANN_ROOT, ANNabort, apx_dists, apx_nn_idx, apx_pts_in_range, epsilon, ERR, Error(), max_pts_in_range, max_pts_visit, min_pts_in_range, near_neigh, query_size, radius_bound, RND_OFF, true_dists, true_nn, and true_nn_idx.

Referenced by main().

 {
         int*              curr_apx_idx = apx_nn_idx;    // approx index pointer
         ANNdistArray  curr_apx_dst = apx_dists;         // approx distance pointer
         int*              curr_tru_idx = true_nn_idx;   // true index pointer
         ANNdistArray  curr_tru_dst = true_dists;        // true distance pointer
         int i, j;
 
         if (true_nn < near_neigh) {
                 Error("Cannot validate with fewer true near neighbors than actual", ANNabort);
         }
 
         for (i = 0; i < query_size; i++) {                      // validate each query
                 //----------------------------------------------------------------
                 //      Compute result errors
                 //              In fixed radius search it is possible that not all k
                 //              nearest neighbors were computed.  Because the true
                 //              results are computed over the shrunken radius, we should
                 //              have at least as many true nearest neighbors as
                 //              approximate nearest neighbors. (If not, an infinite
                 //              error will be generated, and so an internal error will
                 //              will be generated.
                 //
                 //              Because nearest neighbors are sorted in increasing order
                 //              of distance, as soon as we see a null index, we can
                 //              terminate the distance checking.  The error in the
                 //              result should not exceed epsilon.  However, if
                 //              max_pts_visit is nonzero (meaning that the search is
                 //              terminated early) this might happen.
                 //----------------------------------------------------------------
                 for (j = 0; j < near_neigh; j++) {
                         if (curr_tru_idx[j] == ANN_NULL_IDX)// no more true neighbors?
                                 break;
                                                                                                 // true i-th smallest distance
                         double true_dist = ANN_ROOT(curr_tru_dst[j]);
                                                                                                 // reported i-th smallest
                         double rept_dist = ANN_ROOT(curr_apx_dst[j]);
                                                                                                 // better than optimum?
                         if (rept_dist < true_dist*(1-ERR)) {
                                 Error("INTERNAL ERROR: True nearest neighbor incorrect",
                                                 ANNabort);
                         }
 
                         double resultErr;                                       // result error
                         if (true_dist == 0.0) {                         // let's not divide by zero
                                 if (rept_dist != 0.0) resultErr = ANN_DBL_MAX;
                                 else                              resultErr = 0.0;
                         }
                         else {
                                 resultErr = (rept_dist - true_dist) / ((double) true_dist);
                         }
 
                         if (resultErr > epsilon + RND_OFF && max_pts_visit == 0) {
                                 Error("INTERNAL ERROR: Actual error exceeds epsilon",
                                                 ANNabort);
                         }
                         #ifdef ANN_PERF
                                 ann_average_err += resultErr;   // update statistics error
                         #endif
                 }
                 //--------------------------------------------------------------------
                 //  Compute rank errors (only needed for perf measurements)
                 //--------------------------------------------------------------------
                 #ifdef ANN_PERF
                         for (j = 0; j < near_neigh; j++) {
                                 if (curr_tru_idx[i] == ANN_NULL_IDX) // no more true neighbors?
                                         break;
 
                                 double rnkErr = 0.0;                    // rank error
                                                                                                 // reported j-th distance
                                 ANNdist rept_dist = curr_apx_dst[j];
                                 int rnk = 0;                                    // compute rank of this item
                                 while (rnk < true_nn && curr_tru_dst[rnk] <= rept_dist)
                                         rnk++;
                                 if (j+1-rnk > 0) rnkErr = (double) (j+1-rnk);
                                 ann_rank_err += rnkErr;                 // update average rank error
                         }
                 #endif
                 //----------------------------------------------------------------
                 //      Check range counts from fixed-radius query
                 //----------------------------------------------------------------
                 if (radius_bound != 0) {                                // fixed-radius search
                         if  (apx_pts_in_range[i] < min_pts_in_range[i] ||
                                  apx_pts_in_range[i] > max_pts_in_range[i])
                                 Error("INTERNAL ERROR: Invalid fixed-radius range count",
                                                 ANNabort);
                 }
 
                 curr_apx_idx += near_neigh;
                 curr_apx_dst += near_neigh;
                 curr_tru_idx += true_nn;                                // increment current pointers
                 curr_tru_dst += true_nn;
         }
 }

void Error	(	const char *	msg,
		ANNerr	level
	)

Definition at line 376 of file ann_test.cpp.

References ANNabort.

 {
         if (level == ANNabort) {
                 cerr << "ann_test: ERROR------->" << msg << "<-------------ERROR\n";
                 exit(1);
         }
         else {
                 cerr << "ann_test: WARNING----->" << msg << "<-------------WARNING\n";
         }
 }

void generatePts	(	ANNpointArray &	pa,
		int	n,
		PtType	type,
		ANNbool	new_clust,
		ANNpointArray	src = `NULL`,
		int	n_src = `0`
	)

Definition at line 1191 of file ann_test.cpp.

References ANNabort, annAllocPts(), annClusEllipsoids(), annClusGaussPts(), annClusOrthFlats(), annCoGaussPts(), annCoLaplacePts(), annDeallocPts(), annGaussPts(), annIdum, annLaplacePts(), annPlanted(), annUniformPts(), CLUS_ELLIPSOIDS, CLUS_GAUSS, CLUS_ORTH_FLATS, CO_GAUSS, CO_LAPLACE, corr_coef, DATA, dim, distr, distr_table, Error(), GAUSS, LAPLACE, max_dim, n_color, PLANTED, printPoint(), QUERY, QUERY_RES, SHOW_PTS, SILENT, stats, std_dev, std_dev_hi, std_dev_lo, and UNIFORM.

Referenced by main().

 {
         if (pa != NULL) annDeallocPts(pa);                      // get rid of any old points
         pa = annAllocPts(n, dim);                                       // allocate point storage
 
         switch (distr) {
                 case UNIFORM:                                                   // uniform over cube [-1,1]^d.
                         annUniformPts(pa, n, dim);
                         break;
                 case GAUSS:                                                             // Gaussian with mean 0
                         annGaussPts(pa, n, dim, std_dev);
                         break;
                 case LAPLACE:                                                   // Laplacian, mean 0 and var 1
                         annLaplacePts(pa, n, dim);
                         break;
                 case CO_GAUSS:                                                  // correlated Gaussian
                         annCoGaussPts(pa, n, dim, corr_coef);
                         break;
                 case CO_LAPLACE:                                                // correlated Laplacian
                         annCoLaplacePts(pa, n, dim, corr_coef);
                         break;
                 case CLUS_GAUSS:                                                // clustered Gaussian
                         annClusGaussPts(pa, n, dim, n_color, new_clust, std_dev);
                         break;
                 case CLUS_ORTH_FLATS:                                   // clustered on orthog flats
                         annClusOrthFlats(pa, n, dim, n_color, new_clust, std_dev, max_dim);
                         break;
                 case CLUS_ELLIPSOIDS:                                   // clustered ellipsoids
                         annClusEllipsoids(pa, n, dim, n_color, new_clust, std_dev,
                                                 std_dev_lo, std_dev_hi, max_dim);
                         break;
                 case PLANTED:                                                   // planted distribution
                         annPlanted(pa, n, dim, src, n_src, std_dev);
                         break;
                 default:
                         Error("INTERNAL ERROR: Unknown distribution", ANNabort);
                         break;
         }
 
         if (stats > SILENT) {
                 if(type == DATA) cout << "[Generating Data Points:\n";
                 else                     cout << "[Generating Query Points:\n";
                 cout << "  number        = " << n << "\n";
                 cout << "  dim           = " << dim << "\n";
                 cout << "  distribution  = " << distr_table[distr] << "\n";
                 if (annIdum < 0)
                         cout << "  seed          = " << annIdum << "\n";
                 if (distr == GAUSS || distr == CLUS_GAUSS
                  || distr == CLUS_ORTH_FLATS)
                         cout << "  std_dev       = " << std_dev << "\n";
                 if (distr == CLUS_ELLIPSOIDS) {
                         cout << "  std_dev       = " << std_dev << " (small) \n";
                         cout << "  std_dev_lo    = " << std_dev_lo << "\n";
                         cout << "  std_dev_hi    = " << std_dev_hi << "\n";
                 }
                 if (distr == CO_GAUSS || distr == CO_LAPLACE)
                         cout << "  corr_coef     = " << corr_coef << "\n";
                 if (distr == CLUS_GAUSS || distr == CLUS_ORTH_FLATS
                  || distr == CLUS_ELLIPSOIDS) {
                         cout << "  colors        = " << n_color << "\n";
                         if (new_clust)
                                 cout << "  (cluster centers regenerated)\n";
                 }
                 if (distr == CLUS_ORTH_FLATS || distr == CLUS_ELLIPSOIDS) {
                         cout << "  max_dim       = " << max_dim << "\n";
                 }
         }
                                                                                                 // want to see points?
         if ((type == DATA  && stats >= SHOW_PTS) ||
                 (type == QUERY && stats >= QUERY_RES)) {
                 if(type == DATA) cout << "(Data Points:\n";
                 else                     cout << "(Query Points:\n";
                 for (int i = 0; i < n; i++) {
                         cout << " " << setw(4) << i << "\t";
                         printPoint(pa[i], dim);
                         cout << "\n";
                 }
                 cout << "  )\n";
         }
         cout << "]\n";
 }

ANNbool getDirective	(	istream &	in,
		char *	directive
	)

Definition at line 611 of file ann_test.cpp.

References ANNfalse, ANNtrue, and skipComment().

Referenced by main().

 {
     if (!skipComment(in))                       // skip comments
         return ANNfalse;                        // found eof along the way?
     in >> directive;                            // read directive
     return ANNtrue;
 }

void getTrueNN ( )

Definition at line 1374 of file ann_test.cpp.

References ANN_POW, ANNfalse, ANNbruteForce::annkFRSearch(), ANNbruteForce::annkSearch(), data_pts, data_size, dim, epsilon, max_pts_in_range, min_pts_in_range, query_pts, query_size, radius_bound, SILENT, stats, true_dists, true_nn, true_nn_idx, and valid_dirty.

Referenced by main().

 {
         if (stats > SILENT) {
                 cout << "(Computing true nearest neighbors for validation.  This may take time.)\n";
         }
                                                                                                 // deallocate existing storage
         if (true_nn_idx                 != NULL) delete [] true_nn_idx;
         if (true_dists                  != NULL) delete [] true_dists;
         if (min_pts_in_range    != NULL) delete [] min_pts_in_range;
         if (max_pts_in_range    != NULL) delete [] max_pts_in_range;
 
         if (true_nn > data_size) {                                      // can't get more nn than points
                 true_nn = data_size;
         }
 
                                                                                                 // allocate true answer storage
         true_nn_idx = new ANNidx[true_nn*query_size];
         true_dists  = new ANNdist[true_nn*query_size];
         min_pts_in_range = new int[query_size];
         max_pts_in_range = new int[query_size];
 
         ANNidxArray  curr_nn_idx = true_nn_idx;         // current locations in arrays
         ANNdistArray curr_dists = true_dists;
 
                                                                                                 // allocate search structure
         ANNbruteForce *the_brute = new ANNbruteForce(data_pts, data_size, dim);
                                                                                                 // compute nearest neighbors
         for (int i = 0; i < query_size; i++) {
                 if (radius_bound == 0) {                                // standard kNN search
                         the_brute->annkSearch(                          // compute true near neighbors
                                                 query_pts[i],                   // query point
                                                 true_nn,                                // number of nearest neighbors
                                                 curr_nn_idx,                    // where to put indices
                                                 curr_dists);                    // where to put distances
                 }
                 else {                                                                  // fixed radius kNN search
                                                                                                 // search radii limits
                         ANNdist trueSqRadius = ANN_POW(radius_bound);
                         ANNdist minSqRadius = ANN_POW(radius_bound / (1+epsilon));
                         min_pts_in_range[i] = the_brute->annkFRSearch(
                                                 query_pts[i],                   // query point
                                                 minSqRadius,                    // shrunken search radius
                                                 true_nn,                                // number of near neighbors
                                                 curr_nn_idx,                    // nearest neighbors (returned)
                                                 curr_dists);                    // distance (returned)
                         max_pts_in_range[i] = the_brute->annkFRSearch(
                                                 query_pts[i],                   // query point
                                                 trueSqRadius,                   // true search radius
                                                 0, NULL, NULL);                 // (ignore kNN info)
                 }
                 curr_nn_idx += true_nn;                                 // increment nn index pointer
                 curr_dists  += true_nn;                                 // increment nn dist pointer
         }
         delete the_brute;                                                       // delete brute-force struct
         valid_dirty = ANNfalse;                                         // validation good for now
 }

void initGlobals ( )

Definition at line 550 of file ann_test.cpp.

References annIdum, ANNtrue, apx_dists, apx_nn_idx, apx_pts_in_range, bucket_size, corr_coef, data_pts, data_size, def_bucket_size, def_corr_coef, def_data_size, def_dim, def_distr, def_epsilon, def_max_dim, def_max_visit, def_n_color, def_near_neigh, def_new_clust, def_query_size, def_rad_bound, def_seed, def_shrink, def_split, def_stats, def_std_dev, def_true_nn, def_validate, dim, distr, epsilon, max_dim, max_pts_in_range, max_pts_visit, min_pts_in_range, n_color, near_neigh, new_clust, query_pts, query_size, radius_bound, shrink, split, stats, std_dev, std_dev_hi, std_dev_lo, the_tree, true_dists, true_nn, true_nn_idx, valid_dirty, and validate.

Referenced by main().

 {
         dim                                     = def_dim;                              // init execution parameters
         data_size                       = def_data_size;
         query_size                      = def_query_size;
         distr                           = def_distr;
         corr_coef                       = def_corr_coef;
         std_dev                         = def_std_dev;
         std_dev_lo                      = def_std_dev;
         std_dev_hi                      = def_std_dev;
         new_clust                       = def_new_clust;
         max_dim                         = def_max_dim;
         n_color                         = def_n_color;
         bucket_size                     = def_bucket_size;
         epsilon                         = def_epsilon;
         near_neigh                      = def_near_neigh;
         max_pts_visit           = def_max_visit;
         radius_bound            = def_rad_bound;
         true_nn                         = def_true_nn;
         validate                        = def_validate;
         stats                           = def_stats;
         split                           = def_split;
         shrink                          = def_shrink;
         annIdum                         = -def_seed;                    // init. global seed for ran0()
 
         data_pts                        = NULL;                                 // initialize storage pointers
         query_pts                       = NULL;
         the_tree                        = NULL;
         apx_nn_idx                      = NULL;
         apx_dists                       = NULL;
         apx_pts_in_range        = NULL;
         true_nn_idx             = NULL;
         true_dists                      = NULL;
         min_pts_in_range        = NULL;
         max_pts_in_range        = NULL;
 
         valid_dirty                     = ANNtrue;                              // (validation must be done)
 }

int lookUp	(	const char *	arg,
		const char(*)	table[STRING_LEN],
		int	size
	)

Definition at line 401 of file ann_test.cpp.

References table.

Referenced by main().

 {
         int i;
         for (i = 0; i < size; i++) {
                 if (!strcmp(arg, table[i])) return i;
         }
         return i;
 }

int main	(	int	argc,
		char **	argv
	)

Definition at line 628 of file ann_test.cpp.

References ANN_NULL_IDX, ANN_POW, ANN_ROOT, ANNabort, annClose(), ANNcopyright, annDeallocPts(), ANNfalse, annIdum, ANNkd_tree::annkFRSearch(), ANNkd_tree::annkPriSearch(), ANNkd_tree::annkSearch(), ANNlatestRev, annMaxPtsVisit(), annPrintStats(), annResetCounts(), annResetStats(), ANNtrue, annUpdateStats(), ANNversion, ANNversionCmt, ANNwarn, apx_dists, apx_nn_idx, apx_pts_in_range, bucket_size, CLOCKS_PER_SEC, corr_coef, DATA, data_pts, data_size, dim, distr, distr_table, doValidation(), ANNkd_tree::Dump(), epsilon, Error(), EXEC_TIME, extra_nn, generatePts(), getDirective(), getTrueNN(), initGlobals(), lookUp(), max_dim, max_pts_visit, method, n_color, N_DISTRIBS, N_SHRINK_RULES, N_SPLIT_RULES, N_STAT_LEVELS, near_neigh, new_clust, ANNkd_tree::nPoints(), PLANTED, PREP_STATS, ANNkd_tree::Print(), QUERY, query_pts, QUERY_RES, query_size, QUERY_STATS, radius_bound, readPts(), SHOW_STRUCT, shrink, shrink_table, SILENT, split, split_table, stat_table, stats, std_dev, std_dev_hi, std_dev_lo, STRING_LEN, the_tree, ANNkd_tree::theDim(), ANNkd_tree::thePoints(), treeStats(), true_nn, valid_dirty, and validate.

 {
         long            clock0;                                         // clock time
         char            directive[STRING_LEN];          // input directive
         char            arg[STRING_LEN];                        // all-purpose argument
 
         cout << "------------------------------------------------------------\n"
                  << "ann_test: Version " << ANNversion << " " << ANNversionCmt << "\n"
                  << "    Copyright: " << ANNcopyright << ".\n"
                  << "    Latest Revision: " << ANNlatestRev << ".\n"
                  << "------------------------------------------------------------\n\n";
 
         initGlobals();                                                          // initialize global values
 
         //--------------------------------------------------------------------
         //      Main input loop
         //--------------------------------------------------------------------
                                                                                                 // read input directive
         while (getDirective(cin, directive)) {
                 //----------------------------------------------------------------
                 //      Read options
                 //----------------------------------------------------------------
                 if (!strcmp(directive,"dim")) {
                         cin >> dim;
                 }
                 else if (!strcmp(directive,"colors")) {
                         cin >> n_color;
                 }
                 else if (!strcmp(directive,"new_clust")) {
                         new_clust = ANNtrue;
                 }
                 else if (!strcmp(directive,"max_clus_dim")) {
                         cin >> max_dim;
                 }
                 else if (!strcmp(directive,"std_dev")) {
                         cin >> std_dev;
                 }
                 else if (!strcmp(directive,"std_dev_lo")) {
                         cin >> std_dev_lo;
                 }
                 else if (!strcmp(directive,"std_dev_hi")) {
                         cin >> std_dev_hi;
                 }
                 else if (!strcmp(directive,"corr_coef")) {
                         cin >> corr_coef;
                 }
                 else if (!strcmp(directive, "data_size")) {
                         cin >> data_size;
                 }
                 else if (!strcmp(directive,"query_size")) {
                         cin >> query_size;
                 }
                 else if (!strcmp(directive,"bucket_size")) {
                         cin >> bucket_size;
                 }
                 else if (!strcmp(directive,"epsilon")) {
                         cin >> epsilon;
                 }
                 else if (!strcmp(directive,"max_pts_visit")) {
                         cin >> max_pts_visit;
                         valid_dirty = ANNtrue;                          // validation must be redone
                 }
                 else if (!strcmp(directive,"radius_bound")) {
                         cin >> radius_bound;
                         valid_dirty = ANNtrue;                          // validation must be redone
                 }
                 else if (!strcmp(directive,"near_neigh")) {
                         cin >> near_neigh;
                         true_nn = near_neigh + extra_nn;        // also reset true near neighs
                         valid_dirty = ANNtrue;                          // validation must be redone
                 }
                 else if (!strcmp(directive,"true_near_neigh")) {
                         cin >> true_nn;
                         valid_dirty = ANNtrue;                          // validation must be redone
                 }
                 //----------------------------------------------------------------
                 //      seed option
                 //              The seed is reset by setting the global annIdum to the
                 //              negation of the seed value.  See rand.cpp.
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"seed")) {
                         cin >> annIdum;
                         annIdum = -annIdum;
                 }
                 //----------------------------------------------------------------
                 //      validate option
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"validate")) {
                         cin >> arg;                                                     // input argument
                         if (!strcmp(arg, "on")) {
                                 validate = ANNtrue;
                                 cout << "validate = on   "
                                          << "(Warning: this may slow execution time.)\n";
                         }
                         else if (!strcmp(arg, "off")) {
                                 validate = ANNfalse;
                         }
                         else {
                                 cerr << "Argument: " << arg << "\n";
                                 Error("validate argument must be \"on\" or \"off\"", ANNabort);
                         }
                 }
                 //----------------------------------------------------------------
                 //      distribution option
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"distribution")) {
                         cin >> arg;                                                     // input name and translate
                         distr = (Distrib) lookUp(arg, distr_table, N_DISTRIBS);
                         if (distr >= N_DISTRIBS) {                      // not something we recognize
                                 cerr << "Distribution: " << arg << "\n";
                                 Error("Unknown distribution", ANNabort);
                         }
                 }
                 //----------------------------------------------------------------
                 //      stats option
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"stats")) {
                         cin >> arg;                                                     // input name and translate
                         stats = (StatLev) lookUp(arg, stat_table, N_STAT_LEVELS);
                         if (stats >= N_STAT_LEVELS) {           // not something we recognize
                                 cerr << "Stats level: " << arg << "\n";
                                 Error("Unknown statistics level", ANNabort);
                         }
                         if (stats > SILENT)
                                 cout << "stats = " << arg << "\n";
                 }
                 //----------------------------------------------------------------
                 //      split_rule option
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"split_rule")) {
                         cin >> arg;                                                     // input split_rule name
                         split = (ANNsplitRule) lookUp(arg, split_table, N_SPLIT_RULES);
                         if (split >= N_SPLIT_RULES) {           // not something we recognize
                                 cerr << "Splitting rule: " << arg << "\n";
                                 Error("Unknown splitting rule", ANNabort);
                         }
                 }
                 //----------------------------------------------------------------
                 //      shrink_rule option
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"shrink_rule")) {
                         cin >> arg;                                                     // input split_rule name
                         shrink = (ANNshrinkRule) lookUp(arg, shrink_table, N_SHRINK_RULES);
                         if (shrink >= N_SHRINK_RULES) {         // not something we recognize
                                 cerr << "Shrinking rule: " << arg << "\n";
                                 Error("Unknown shrinking rule", ANNabort);
                         }
                 }
                 //----------------------------------------------------------------
                 //      label operation
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"output_label")) {
                         cin >> arg;
                         if (stats > SILENT)
                                 cout << "<" << arg << ">\n";
                 }
                 //----------------------------------------------------------------
                 //      gen_data_pts operation
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"gen_data_pts")) {
                         if (distr == PLANTED) {                         // planted distribution
                                 Error("Cannot use planted distribution for data points", ANNabort);
                         }
                         generatePts(                                            // generate data points
                                 data_pts,                                               // data points
                                 data_size,                                              // data size
                                 DATA,                                                   // data points
                                 new_clust);                                             // new clusters flag
                         valid_dirty = ANNtrue;                          // validation must be redone
                         new_clust = ANNfalse;                           // reset flag
                 }
                 //----------------------------------------------------------------
                 //      gen_query_pts operation
                 //              If the distribution is PLANTED, then the query points
                 //              are planted near the data points (which must already be
                 //              generated).
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"gen_query_pts")) {
                         if (distr == PLANTED) {                         // planted distribution
                                 if (data_pts == NULL) {
                                         Error("Must generate data points before query points for planted distribution", ANNabort);
                                 }
                                 generatePts(                                    // generate query points
                                         query_pts,                                      // point array
                                         query_size,                                     // number of query points
                                         QUERY,                                          // query points
                                         new_clust,                                      // new clusters flag
                                         data_pts,                                       // plant around data pts
                                         data_size);
                         }
                         else {                                                          // all other distributions
                                 generatePts(                                    // generate query points
                                         query_pts,                                      // point array
                                         query_size,                                     // number of query points
                                         QUERY,                                          // query points
                                         new_clust);                                     // new clusters flag
                         }
                         valid_dirty = ANNtrue;                          // validation must be redone
                         new_clust = ANNfalse;                           // reset flag
                 }
                 //----------------------------------------------------------------
                 //      read_data_pts operation
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"read_data_pts")) {
                         cin >> arg;                                                     // input file name
                         readPts(
                                 data_pts,                                               // point array
                                 data_size,                                              // number of points
                                 arg,                                                    // file name
                                 DATA);                                                  // data points
                         valid_dirty = ANNtrue;                          // validation must be redone
                 }
                 //----------------------------------------------------------------
                 //      read_query_pts operation
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"read_query_pts")) {
                         cin >> arg;                                                     // input file name
                         readPts(
                                 query_pts,                                              // point array
                                 query_size,                                             // number of points
                                 arg,                                                    // file name
                                 QUERY);                                                 // query points
                         valid_dirty = ANNtrue;                          // validation must be redone
                 }
                 //----------------------------------------------------------------
                 //      build_ann operation
                 //              We always invoke the constructor for bd-trees.  Note
                 //              that when the shrinking rule is NONE (which is true by
                 //              default), then this constructs a kd-tree.
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"build_ann")) {
                         //------------------------------------------------------------
                         //      Build the tree
                         //------------------------------------------------------------
                         if (the_tree != NULL) {                         // tree exists already
                                 delete the_tree;                                // get rid of it
                         }
                         clock0 = clock();                                       // start time
 
                         the_tree = new ANNbd_tree(                      // build it
                                         data_pts,                                       // the data points
                                         data_size,                                      // number of points
                                         dim,                                            // dimension of space
                                         bucket_size,                            // maximum bucket size
                                         split,                                          // splitting rule
                                         shrink);                                        // shrinking rule
 
                         //------------------------------------------------------------
                         //      Print summary
                         //------------------------------------------------------------
                         long prep_time = clock() - clock0;      // end of prep time
 
                         if (stats > SILENT) {
                                 cout << "[Build ann-structure:\n";
                                 cout << "  split_rule    = " << split_table[split] << "\n";
                                 cout << "  shrink_rule   = " << shrink_table[shrink] << "\n";
                                 cout << "  data_size     = " << data_size << "\n";
                                 cout << "  dim           = " << dim << "\n";
                                 cout << "  bucket_size   = " << bucket_size << "\n";
 
                                 if (stats >= EXEC_TIME) {               // output processing time
                                         cout << "  process_time  = "
                                                  << double(prep_time)/CLOCKS_PER_SEC << " sec\n";
                                 }
 
                                 if (stats >= PREP_STATS)                // output or check tree stats
                                         treeStats(cout, ANNtrue);       // print tree stats
                                 else
                                         treeStats(cout, ANNfalse);      // check stats
 
                                 if (stats >= SHOW_STRUCT) {             // print the whole tree
                                         cout << "  (Structure Contents:\n";
                                         the_tree->Print(ANNfalse, cout);
                                         cout << "  )\n";
                                 }
                                 cout << "]\n";
                         }
                 }
                 //----------------------------------------------------------------
                 //      dump operation
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"dump")) {
                         cin >> arg;                                                     // input file name
                         if (the_tree == NULL) {                         // no tree
                                 Error("Cannot dump.  No tree has been built yet", ANNwarn);
                         }
                         else {                                                          // there is a tree
                                                                                                 // try to open file
                                 ofstream out_dump_file(arg);
                                 if (!out_dump_file) {
                                         cerr << "File name: " << arg << "\n";
                                         Error("Cannot open dump file", ANNabort);
                                 }
                                                                                                 // dump the tree and points
                                 the_tree->Dump(ANNtrue, out_dump_file);
                                 if (stats > SILENT) {
                                         cout << "(Tree has been dumped to file " << arg << ")\n";
                                 }
                         }
                 }
                 //----------------------------------------------------------------
                 //      load operation
                 //              Since this not only loads a tree, but loads a new set
                 //              of data points.
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"load")) {
                         cin >> arg;                                                     // input file name
                         if (the_tree != NULL) {                         // tree exists already
                                 delete the_tree;                                // get rid of it
                         }
                         if (data_pts != NULL) {                         // data points exist already
                                 delete data_pts;                                // get rid of them
                         }
 
                         ifstream in_dump_file(arg);                     // try to open file
                         if (!in_dump_file) {
                                 cerr << "File name: " << arg << "\n";
                                 Error("Cannot open file for loading", ANNabort);
                         }
                                                                                                 // build tree by loading
                         the_tree = new ANNbd_tree(in_dump_file);
 
                         dim = the_tree->theDim();                       // new dimension
                         data_size = the_tree->nPoints();        // number of points
                         data_pts = the_tree->thePoints();       // new points
 
                         valid_dirty = ANNtrue;                          // validation must be redone
 
                         if (stats > SILENT) {
                                         cout << "(Tree has been loaded from file " << arg << ")\n";
                         }
                         if (stats >= SHOW_STRUCT) {                     // print the tree
                                 cout << "  (Structure Contents:\n";
                                 the_tree->Print(ANNfalse, cout);
                                 cout << "  )\n";
                         }
                 }
                 //----------------------------------------------------------------
                 //      run_queries operation
                 //              This section does all the query processing.  It consists
                 //              of the following subsections:
                 //
                 //              **      input the argument (standard or priority) and output
                 //                      the header describing the essential information.
                 //              **      allocate space for the results to be stored.
                 //              **      run the queries by invoking the appropriate search
                 //                      procedure on the query points.  Print nearest neighbor
                 //                      if requested.
                 //              **      print final summaries
                 //
                 //      The approach for processing multiple nearest neighbors is
                 //      pretty crude.  We allocate an array whose size is the
                 //      product of the total number of queries times the number of
                 //      nearest neighbors (k), and then use each k consecutive
                 //      entries to store the results of each query.
                 //----------------------------------------------------------------
                 else if (!strcmp(directive,"run_queries")) {
 
                         //------------------------------------------------------------
                         //      Input arguments and print summary
                         //------------------------------------------------------------
                         enum {STANDARD, PRIORITY} method;
 
                         cin >> arg;                                                     // input argument
                         if (!strcmp(arg, "standard")) {
                                 method = STANDARD;
                         }
                         else if (!strcmp(arg, "priority")) {
                                 method = PRIORITY;
                         }
                         else {
                                 cerr << "Search type: " << arg << "\n";
                                 Error("Search type must be \"standard\" or \"priority\"",
                                                 ANNabort);
                         }
                         if (data_pts == NULL || query_pts == NULL) {
                                 Error("Either data set and query set not constructed", ANNabort);
                         }
                         if (the_tree == NULL) {
                                 Error("No search tree built.", ANNabort);
                         }
 
                         //------------------------------------------------------------
                         //      Set up everything
                         //------------------------------------------------------------
 
                         #ifdef ANN_PERF                                         // performance only
                                 annResetStats(data_size);                       // reset statistics
                         #endif
 
                         clock0 = clock();                                       // start time
                                                                                                 // deallocate existing storage
                         if (apx_nn_idx           != NULL) delete [] apx_nn_idx;
                         if (apx_dists            != NULL) delete [] apx_dists;
                         if (apx_pts_in_range != NULL) delete [] apx_pts_in_range;
                                                                                                 // allocate apx answer storage
                         apx_nn_idx = new ANNidx[near_neigh*query_size];
                         apx_dists  = new ANNdist[near_neigh*query_size];
                         apx_pts_in_range = new int[query_size];
 
                         annMaxPtsVisit(max_pts_visit);          // set max points to visit
 
                         //------------------------------------------------------------
                         //      Run the queries
                         //------------------------------------------------------------
                                                                                                 // pointers for current query
                         ANNidxArray       curr_nn_idx = apx_nn_idx;
                         ANNdistArray  curr_dists  = apx_dists;
 
                         for (int i = 0; i < query_size; i++) {
                                 #ifdef ANN_PERF
                                         annResetCounts();                       // reset counters
                                 #endif
                                 apx_pts_in_range[i] = 0;
 
                                 if (radius_bound == 0) {                // no radius bound
                                         if (method == STANDARD) {
                                                 the_tree->annkSearch(
                                                         query_pts[i],           // query point
                                                         near_neigh,                     // number of near neighbors
                                                         curr_nn_idx,            // nearest neighbors (returned)
                                                         curr_dists,                     // distance (returned)
                                                         epsilon);                       // error bound
                                         }
                                         else if (method == PRIORITY) {
                                                 the_tree->annkPriSearch(
                                                         query_pts[i],           // query point
                                                         near_neigh,                     // number of near neighbors
                                                         curr_nn_idx,            // nearest neighbors (returned)
                                                         curr_dists,                     // distance (returned)
                                                         epsilon);                       // error bound
                                         }
                                         else {
                                                 Error("Internal error - invalid method", ANNabort);
                                         }
                                 }
                                 else {                                                  // use radius bound
                                         if (method != STANDARD) {
                                                 Error("A nonzero radius bound assumes standard search",
                                                         ANNwarn);
                                         }
                                         apx_pts_in_range[i] = the_tree->annkFRSearch(
                                                 query_pts[i],                   // query point
                                                 ANN_POW(radius_bound),  // squared radius search bound
                                                 near_neigh,                             // number of near neighbors
                                                 curr_nn_idx,                    // nearest neighbors (returned)
                                                 curr_dists,                             // distance (returned)
                                                 epsilon);                               // error bound
                                 }
                                 curr_nn_idx += near_neigh;              // increment current pointers
                                 curr_dists      += near_neigh;
 
                                 #ifdef ANN_PERF
                                         annUpdateStats();                       // update stats
                                 #endif
                         }
 
                         long query_time = clock() - clock0; // end of query time
 
                         if (validate) {                                         // validation requested
                                 if (valid_dirty) getTrueNN();   // get true near neighbors
                                 doValidation();                                 // validate
                         }
 
                         //------------------------------------------------------------
                         //      Print summaries
                         //------------------------------------------------------------
 
                         if (stats > SILENT) {
                                 cout << "[Run Queries:\n";
                                 cout << "  query_size    = " << query_size << "\n";
                                 cout << "  dim           = " << dim << "\n";
                                 cout << "  search_method = " << arg << "\n";
                                 cout << "  epsilon       = " << epsilon << "\n";
                                 cout << "  near_neigh    = " << near_neigh << "\n";
                                 if (max_pts_visit != 0)
                                         cout << "  max_pts_visit = " << max_pts_visit << "\n";
                                 if (radius_bound != 0)
                                         cout << "  radius_bound  = " << radius_bound << "\n";
                                 if (validate)
                                         cout << "  true_nn       = " << true_nn << "\n";
 
                                 if (stats >= EXEC_TIME) {               // print exec time summary
                                         cout << "  query_time    = " <<
                                                 double(query_time)/(query_size*CLOCKS_PER_SEC)
                                                  << " sec/query";
                                         #ifdef ANN_PERF
                                                 cout << " (biased by perf measurements)";
                                         #endif
                                         cout << "\n";
                                 }
 
                                 if (stats >= QUERY_STATS) {             // output performance stats
                                         #ifdef ANN_PERF
                                                 cout.flush();
                                                 annPrintStats(validate);
                                         #else
                                                 cout << "  (Performance statistics unavailable.)\n";
                                         #endif
                                 }
 
                                 if (stats >= QUERY_RES) {               // output results
                                         cout << "  (Query Results:\n";
                                         cout << "    Pt\tANN\tDist\n";
                                         curr_nn_idx = apx_nn_idx;       // subarray pointers
                                         curr_dists  = apx_dists;
                                                                                                 // output nearest neighbors
                                         for (int i = 0; i < query_size; i++) {
                                                 cout << " " << setw(4) << i;
                                                 for (int j = 0; j < near_neigh; j++) {
                                                                                                 // exit if no more neighbors
                                                         if (curr_nn_idx[j] == ANN_NULL_IDX) {
                                                                 cout << "\t[no other pts in radius bound]\n";
                                                                 break;
                                                         }
                                                         else {                          // output point info
                                                                 cout << "\t" << curr_nn_idx[j]
                                                                         << "\t" << ANN_ROOT(curr_dists[j])
                                                                         << "\n";
                                                         }
                                                 }
                                                                                                 // output range count
                                                 if (radius_bound != 0) {
                                                         cout << "    pts_in_radius_bound = "
                                                                 << apx_pts_in_range[i] << "\n";
                                                 }
                                                                                                 // increment subarray pointers
                                                 curr_nn_idx += near_neigh;
                                                 curr_dists  += near_neigh;
                                         }
                                         cout << "  )\n";
                                 }
                                 cout << "]\n";
                         }
                 }
                 //----------------------------------------------------------------
                 //      Unknown directive
                 //----------------------------------------------------------------
                 else {
                         cerr << "Directive: " << directive << "\n";
                         Error("Unknown directive", ANNabort);
                 }
         }
         //--------------------------------------------------------------------
         //      End of input loop (deallocate stuff that was allocated)
         //--------------------------------------------------------------------
         if (the_tree            != NULL) delete the_tree;
         if (data_pts            != NULL) annDeallocPts(data_pts);
         if (query_pts           != NULL) annDeallocPts(query_pts);
         if (apx_nn_idx          != NULL) delete [] apx_nn_idx;
         if (apx_dists           != NULL) delete [] apx_dists;
         if (apx_pts_in_range != NULL) delete [] apx_pts_in_range;
 
         annClose();                     // close ANN
 
         return EXIT_SUCCESS;
 }

void printPoint	(	ANNpoint	p,
		int	dim
	)

Definition at line 389 of file ann_test.cpp.

References dim.

Referenced by generatePts(), and readPts().

 {
         cout << "[";
         for (int i = 0; i < dim; i++) {
                 cout << p[i];
                 if (i < dim-1) cout << ",";
         }
         cout << "]";
 }

void readPts	(	ANNpointArray &	pa,
		int &	n,
		char *	file_nm,
		PtType	type
	)

Definition at line 1283 of file ann_test.cpp.

References ANNabort, annAllocPts(), annDeallocPts(), ANNwarn, DATA, dim, Error(), printPoint(), QUERY, QUERY_RES, SHOW_PTS, SILENT, and stats.

Referenced by main().

 {
         int i;
         //--------------------------------------------------------------------
         //      Open input file and read points
         //--------------------------------------------------------------------
         ifstream in_file(file_nm);                                      // try to open data file
         if (!in_file) {
                 cerr << "File name: " << file_nm << "\n";
                 Error("Cannot open input data/query file", ANNabort);
         }
                                                                                                 // allocate storage for points
         if (pa != NULL) annDeallocPts(pa);                      // get rid of old points
         pa = annAllocPts(n, dim);
 
         for (i = 0; i < n; i++) {                                       // read the data
                 if (!(in_file >> pa[i][0])) break;
                 for (int d = 1; d < dim; d++) {
                         in_file >> pa[i][d];
                 }
         }
 
         char ignore_me;                                                         // character for EOF test
         in_file >> ignore_me;                                           // try to get one more character
         if (!in_file.eof()) {                                           // exhausted space before eof
                 if (type == DATA)
                         Error("`data_size' too small. Input file truncated.", ANNwarn);
                 else
                         Error("`query_size' too small. Input file truncated.", ANNwarn);
         }
         n = i;                                                                          // number of points read
 
         //--------------------------------------------------------------------
         //      Print summary
         //--------------------------------------------------------------------
         if (stats > SILENT) {
                 if (type == DATA) {
                         cout << "[Read Data Points:\n";
                         cout << "  data_size  = " << n << "\n";
                 }
                 else {
                         cout << "[Read Query Points:\n";
                         cout << "  query_size = " << n << "\n";
                 }
                 cout << "  file_name  = " << file_nm << "\n";
                 cout << "  dim        = " << dim << "\n";
                                                                                                 // print if results requested
                 if ((type == DATA && stats >= SHOW_PTS) ||
                         (type == QUERY && stats >= QUERY_RES)) {
                         cout << "  (Points:\n";
                         for (i = 0; i < n; i++) {
                                 cout << "    " << i << "\t";
                                 printPoint(pa[i], dim);
                                 cout << "\n";
                         }
                         cout << "  )\n";
                 }
                 cout << "]\n";
         }
 }

ANNbool skipComment ( istream & in )

Definition at line 594 of file ann_test.cpp.

References ANNfalse, and ANNtrue.

Referenced by getDirective().

 {
     char ch = 0;
                                                 // skip whitespace
     do { in.get(ch); } while (isspace(ch) && !in.eof());
     while (ch == '#' && !in.eof()) {            // comment?
                                                 // skip to end of line
         do { in.get(ch); } while(ch != '\n' && !in.eof());
                                                 // skip whitespace
         do { in.get(ch); } while(isspace(ch) && !in.eof());
     }
     if (in.eof()) return ANNfalse;                      // end of file
     in.putback(ch);                             // put character back
     return ANNtrue;
 }

void treeStats	(	ostream &	out,
		ANNbool	verbose
	)

Definition at line 1572 of file ann_test.cpp.

References ANNtrue, ANNkdStats::avg_ar, ANNkdStats::bkt_size, ANNkdStats::depth, ANNkdStats::dim, ANNkd_tree::getStats(), log2, ANNkdStats::n_lf, ANNkdStats::n_pts, ANNkdStats::n_shr, ANNkdStats::n_spl, ANNkdStats::n_tl, and the_tree.

Referenced by main().

 {
         const int       MIN_PTS         = 20;                           // min no. pts for checking
         const float MAX_FRAC_TL = 0.50;                         // max frac of triv leaves
         const float MAX_AVG_AR  = 20;                           // max average aspect ratio
 
         ANNkdStats st;                                                          // statistics structure
 
         the_tree->getStats(st);                                         // get statistics
                                                                                                 // total number of nodes
         int n_nodes = st.n_lf + st.n_spl + st.n_shr;
                                                                                                 // should be O(n/bs)
         int opt_n_nodes = (int) (2*(float(st.n_pts)/st.bkt_size));
         int too_many_nodes = 10*opt_n_nodes;
         if (st.n_pts >= MIN_PTS && n_nodes > too_many_nodes) {
                 out << "-----------------------------------------------------------\n";
                 out << "Warning: The tree has more than 10x as many nodes as points.\n";
                 out << "You may want to consider a different split or shrink method.\n";
                 out << "-----------------------------------------------------------\n";
                 verbose = ANNtrue;
         }
                                                                                                 // fraction of trivial leaves
         float frac_tl = (st.n_lf == 0 ? 0 : ((float) st.n_tl)/ st.n_lf);
         if (st.n_pts >= MIN_PTS && frac_tl > MAX_FRAC_TL) {
                 out << "-----------------------------------------------------------\n";
                 out << "Warning: A significant fraction of leaves contain no points.\n";
                 out << "You may want to consider a different split or shrink method.\n";
                 out << "-----------------------------------------------------------\n";
                 verbose = ANNtrue;
         }
                                                                                                 // depth should be O(dim*log n)
         int too_many_levels = (int) (2.0 * st.dim * log2((double) st.n_pts));
         int opt_levels = (int) log2(double(st.n_pts)/st.bkt_size);
         if (st.n_pts >= MIN_PTS && st.depth > too_many_levels) {
                 out << "-----------------------------------------------------------\n";
                 out << "Warning: The tree is more than 2x as deep as (dim*log n).\n";
                 out << "You may want to consider a different split or shrink method.\n";
                 out << "-----------------------------------------------------------\n";
                 verbose = ANNtrue;
         }
                                                                                                 // average leaf aspect ratio
         if (st.n_pts >= MIN_PTS && st.avg_ar > MAX_AVG_AR) {
                 out << "-----------------------------------------------------------\n";
                 out << "Warning: Average aspect ratio of cells is quite large.\n";
                 out << "This may slow queries depending on the point distribution.\n";
                 out << "-----------------------------------------------------------\n";
                 verbose = ANNtrue;
         }
 
         //------------------------------------------------------------------
         //  Print summaries if requested
         //------------------------------------------------------------------
         if (verbose) {                                                          // output statistics
                 out << "  (Structure Statistics:\n";
                 out << "    n_nodes          = " << n_nodes
                         << " (opt = " << opt_n_nodes
                         << ", best if < " << too_many_nodes << ")\n"
                         << "        n_leaves     = " << st.n_lf
                         << " (" << st.n_tl << " contain no points)\n"
                         << "        n_splits     = " << st.n_spl << "\n"
                         << "        n_shrinks    = " << st.n_shr << "\n";
                 out << "    empty_leaves     = " << frac_tl*100
                         << " percent (best if < " << MAX_FRAC_TL*100 << " percent)\n";
                 out << "    depth            = " << st.depth
                         << " (opt = " << opt_levels
                         << ", best if < " << too_many_levels << ")\n";
                 out << "    avg_aspect_ratio = " << st.avg_ar
                         << " (best if < " << MAX_AVG_AR << ")\n";
                 out << "  )\n";
         }
 }

Variable Documentation

ANNdistArray apx_dists

Definition at line 537 of file ann_test.cpp.

Referenced by doValidation(), initGlobals(), and main().

ANNidxArray apx_nn_idx

Definition at line 536 of file ann_test.cpp.

Referenced by doValidation(), initGlobals(), and main().

int* apx_pts_in_range

Definition at line 538 of file ann_test.cpp.

Referenced by doValidation(), initGlobals(), and main().

int bucket_size

Definition at line 483 of file ann_test.cpp.

Referenced by initGlobals(), and main().

double corr_coef

Definition at line 479 of file ann_test.cpp.

Referenced by generatePts(), initGlobals(), and main().

ANNpointArray data_pts

Definition at line 533 of file ann_test.cpp.

Referenced by getTrueNN(), initGlobals(), and main().

int data_size

Definition at line 473 of file ann_test.cpp.

Referenced by annResetStats(), getTrueNN(), initGlobals(), and main().

const int def_bucket_size = 1

Definition at line 452 of file ann_test.cpp.

Referenced by initGlobals().

const double def_corr_coef = 0.05

Definition at line 451 of file ann_test.cpp.

Referenced by initGlobals().

const int def_data_size = 100

Definition at line 444 of file ann_test.cpp.

Referenced by initGlobals().

const int def_dim = 2

Definition at line 443 of file ann_test.cpp.

Referenced by initGlobals().

const Distrib def_distr = UNIFORM

Definition at line 449 of file ann_test.cpp.

Referenced by initGlobals().

const double def_epsilon = 0.0

Definition at line 453 of file ann_test.cpp.

Referenced by initGlobals().

const int def_max_dim = 1

Definition at line 448 of file ann_test.cpp.

Referenced by initGlobals().

const int def_max_visit = 0

Definition at line 455 of file ann_test.cpp.

Referenced by initGlobals().

const int def_n_color = 5

Definition at line 446 of file ann_test.cpp.

Referenced by initGlobals().

const int def_near_neigh = 1

Definition at line 454 of file ann_test.cpp.

Referenced by initGlobals().

const ANNbool def_new_clust = ANNfalse

Definition at line 447 of file ann_test.cpp.

Referenced by initGlobals().

const int def_query_size = 100

Definition at line 445 of file ann_test.cpp.

Referenced by initGlobals().

const int def_rad_bound = 0

Definition at line 456 of file ann_test.cpp.

Referenced by initGlobals().

const int def_seed = 0

Definition at line 459 of file ann_test.cpp.

Referenced by initGlobals().

const ANNshrinkRule def_shrink = ANN_BD_NONE

Definition at line 466 of file ann_test.cpp.

Referenced by initGlobals().

const ANNsplitRule def_split = ANN_KD_SUGGEST

Definition at line 464 of file ann_test.cpp.

Referenced by initGlobals().

const StatLev def_stats = QUERY_STATS

Definition at line 462 of file ann_test.cpp.

Referenced by initGlobals().

const double def_std_dev = 1.00

Definition at line 450 of file ann_test.cpp.

Referenced by initGlobals().

const int def_true_nn = def_near_neigh + extra_nn

Definition at line 458 of file ann_test.cpp.

Referenced by initGlobals().

const ANNbool def_validate = ANNfalse

Definition at line 460 of file ann_test.cpp.

Referenced by initGlobals().

int dim

Definition at line 472 of file ann_test.cpp.

Distrib distr

Definition at line 478 of file ann_test.cpp.

Referenced by generatePts(), initGlobals(), and main().

const char distr_table[N_DISTRIBS][STRING_LEN]

Initial value:

= {
                "uniform",                                              
                "gauss",                                                
                "laplace",                                              
                "co_gauss",                                             
                "co_laplace",                                   
                "clus_gauss",                                   
                "clus_orth_flats",                              
                "clus_ellipsoids",                              
                "planted"}

Definition at line 334 of file ann_test.cpp.

Referenced by generatePts(), and main().

double epsilon

Definition at line 484 of file ann_test.cpp.

Referenced by doValidation(), getTrueNN(), initGlobals(), and main().

const double ERR = 0.00001

Definition at line 284 of file ann_test.cpp.

const int extra_nn = 10

Definition at line 441 of file ann_test.cpp.

Referenced by main().

int max_dim

Definition at line 477 of file ann_test.cpp.

Referenced by annMaxSpread(), generatePts(), initGlobals(), and main().

int* max_pts_in_range

Definition at line 542 of file ann_test.cpp.

Referenced by doValidation(), getTrueNN(), and initGlobals().

int max_pts_visit

Definition at line 486 of file ann_test.cpp.

Referenced by doValidation(), initGlobals(), and main().

int* min_pts_in_range

Definition at line 541 of file ann_test.cpp.

Referenced by doValidation(), getTrueNN(), and initGlobals().

int n_color

Definition at line 475 of file ann_test.cpp.

Referenced by generatePts(), initGlobals(), and main().

const int N_SHRINK_RULES = 4

Definition at line 362 of file ann_test.cpp.

Referenced by main().

const int N_SPLIT_RULES = 6

Definition at line 349 of file ann_test.cpp.

Referenced by main().

int near_neigh

Definition at line 485 of file ann_test.cpp.

Referenced by doValidation(), initGlobals(), and main().

ANNbool new_clust

Definition at line 476 of file ann_test.cpp.

Referenced by initGlobals(), and main().

ANNpointArray query_pts

Definition at line 534 of file ann_test.cpp.

Referenced by getTrueNN(), initGlobals(), and main().

int query_size

Definition at line 474 of file ann_test.cpp.

Referenced by doValidation(), getTrueNN(), initGlobals(), and main().

double radius_bound

Definition at line 487 of file ann_test.cpp.

Referenced by doValidation(), getTrueNN(), initGlobals(), and main().

const double RND_OFF = 5E-16

Definition at line 285 of file ann_test.cpp.

Referenced by doValidation().

ANNshrinkRule shrink

Definition at line 492 of file ann_test.cpp.

Referenced by initGlobals(), and main().

const char shrink_table[N_SHRINK_RULES][STRING_LEN]

Initial value:

= {
                "none",                                                 
                "simple",                                               
                "centroid",                                             
                "suggest"}

Definition at line 363 of file ann_test.cpp.

Referenced by main().

ANNsplitRule split

Definition at line 491 of file ann_test.cpp.

Referenced by initGlobals(), and main().

const char split_table[N_SPLIT_RULES][STRING_LEN]

Initial value:

= {
                "standard",                                             
                "midpt",                                                
                "fair",                                                 
                "sl_midpt",                                             
                "sl_fair",                                              
                "suggest"}

Definition at line 350 of file ann_test.cpp.

Referenced by main().

const char stat_table[N_STAT_LEVELS][STRING_LEN]

Initial value:

= {
                "silent",                                               
                "exec_time",                                    
                "prep_stats",                                   
                "query_stats",                                  
                "query_res",                                    
                "show_pts",                                             
                "show_struct"}