src/nnsearch.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2010 by Matthias Ihrke                                  *
 *   ihrke@nld.ds.mpg.de
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   aint with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#ifndef NNSEARCH_H
# define NNSEARCH_H
#include "mathadd.h"
#include "distances.h"
#include "definitions.h"
#include "optarg.h"
#include "distances.h"

#ifdef __cplusplus
extern "C" {
#endif
  /*-----------------------------------------------------------
     - Search Tree
     ---------------------------------------------------------*/

  struct btree{
     int c;     /* center */
     double R;  /* maximal distance from c to any point */
     double g;  /* min[ d(c,x)-d(sister,x) ] */
     int start; /* start of cluster in A */
     int end;   /* end of cluster in A */
     double *cdist; /* distances from center for terminal nodes */
     struct btree *left;
     struct btree *right;
  };
  typedef struct btree TreeNode;
  typedef struct {
     int *A;       
     const double **d;    
     int m, N;      
     VectorDistanceFunction distfct; 
     TreeNode *root; 
     OptArgList *optargs;
  } SearchTree;

  TreeNode*   tnode_init();
  bool tnode_isleaf( TreeNode *C );
  void build_tree_recursive( TreeNode *C, double **D, int N, int *A, int maxel );
  SearchTree* searchtree_init( int n );
  SearchTree* nn_prepare( const double **X, int m, int N, OptArgList *optargs );
  void        nn_search_k( const SearchTree *S, const double *x, int k, 
                                    int *nn_idx, double *nn_dist );
  void        nn_searck_k_slow( const double **X, int N, int m, 
                                          const double *x, int k, int *nn_idx,
                                          double *nn_dist, OptArgList *optargs );

#ifdef __cplusplus
}
#endif


#endif