/*
   File:        kdtr.h
   Author:      Andrew W. Moore
   Created:     Sat Sep 12 16:05:15 EDT 1992
   Description: Header for Basic kd-tree operations

   Copyright (C) 1992, Andrew W. Moore
*/

typedef struct kdnode_struct
{
  int split;      /* Dimension which we are cutting. -1 denotes leaf */
  float pivot;
  struct kdnode_struct *left;    /* leaf => left and right null */
  struct kdnode_struct *right;   /* not_leaf => both non-null */
  struct kdnode_struct *parent;  /* parent NULL => we are root */
  char *data;
} kdnode;

typedef struct kdtree_struct
{
  int dim;       /* Number of dimensions */
  float *middle;
  float *scales;
  kdnode *root;  /* must be non-null */
} kdtree;

typedef struct kdnode_list_struct
{
  kdnode *kdnode;
  struct kdnode_list_struct *next;
} kdnode_list;

/* The middle and scales arrays give us an indication of the expected
   spread of datapoints within the tree. scales also defines the distance
   metric we'll be using if we need to. Roughly, these fields tell us
   the centre of the space we're interested in is at middle, and the
   variation in expected values in each dimension is according to scales..
   the larger scale[i] the more variation we expect in the ith component.
   Ball park figure is 95% of ith components will lie in the range
   middle[i] - scales[i] to middle[i] + scales[i]. But don't quote me.
*/

extern void init_kdtree();                    /* (kd,dim,middle,scales) */
extern bool is_leaf();                        /* (kdn) */
extern kdnode *child();                       /* (kdn,heading) */
extern void free_kdnode_and_below();          /* (kdn) */
extern void free_descendants();               /* (kdn) */
extern void free_kdtree_contents();           /* (kd) */
extern kdnode *leaf_search();                 /* (kd,floats) */
extern kdnode *leaf_search_to_level();        /* (kd,floats,level) */
extern void split_node();                     /* (kdn,split,pivot) */
extern void fprint_kdtree();                  /* (s,kd) */
extern void gp_draw_kdtree();                 /* (gp,kd) */
extern void gproj_from_kdtree();              /* (kd,gp) */
extern kdnode_list *add_to_kdnode_list();     /* (kdn,ks) */
extern void free_kdnode_list();               /* (ks) */
extern kdnode_list *adjacent_leaves();        /* (kdn,kddim) */
extern void hype_of_kdnode();                 /* (kdn,hy) */
extern int kdnode_depth();                    /* (kdn) */
extern int number_nodes_below();              /* (kdn) */
extern int kdtree_size();                     /* (kd) */
extern int partition_depth_histogram();       /* (kd) */
extern int kdtree_depth();                    /* (kd) */