# [R] truly object oriented programming in R

Jason Liao jg_liao at yahoo.com
Thu Aug 12 17:28:18 CEST 2004

```Good morning! I recently implemented a KD tree in JAVA for faster
kernel density estimation (part of the code follows). It went well. To
hook it with R, however, has proved more difficult. My question is: is
it possible to implement the algorithm in R? My impression seems to
indicate no as the code requires a complete class-object framework that
R does not support. But is there an R package or something that may

Java implementation of KD tree:

public class Kdnode {

private double[] center; //center of the bounding box
private double diameter; //maximum distance from center to
anywhere within the bounding box
private int numOfPoints; //number of source data points in the
bounding box

private Kdnode left, right;

public Kdnode(double[][] points, int split_dim, int [][]
sortedIndices, double[][] bBox) {
//bBox: the bounding box, 1st row the lower bound, 2nd row
the upper bound
numOfPoints = points.length;
int d = points[0].length;

center = new double[d];
for(int j=0; j<d; j++) center[j] =
(bBox[0][j]+bBox[1][j])/2.;
diameter = get_diameter(bBox);

if(numOfPoints==1) {
diameter = 0.;
for(int j=0; j<d; j++) center[j] = points[0][j];
left = null;
right = null;
}
else {
int middlePoint =
sortedIndices[split_dim][numOfPoints/2];
double splitValue = points[middlePoint][split_dim];

middlePoint =
sortedIndices[split_dim][numOfPoints/2-1];
double splitValue_small =
points[middlePoint][split_dim];

int left_size = numOfPoints/2;
int right_size = numOfPoints - left_size;

double[][] leftPoints = new double[left_size][d];
double[][] rightPoints = new double[right_size][d];

int[][] leftSortedIndices = new int[d][left_size];
int[][] rightSortedIndices = new int[d][right_size];

int left_counter = 0, right_counter = 0;
int[] splitInfo = new int [numOfPoints];

for(int i = 0; i < numOfPoints; i++) {
if(points[i][split_dim] < splitValue) {
for(int j=0; j<d; j++) leftPoints[left_counter][j] = points[i][j];
splitInfo[i] = right_counter;
left_counter++;
}

else {
for(int j=0; j<d; j++) rightPoints[right_counter][j] = points[i][j];
splitInfo[i] = left_counter;
right_counter++;
}
}
// modify appropriately the indices to correspond to the new lists
for(int i = 0; i < d; i++) {
int left_index = 0, right_index = 0;
for(int j = 0; j < numOfPoints; j++) {
if(points[sortedIndices[i][j]][split_dim] < splitValue)
leftSortedIndices[i][left_index++] = sortedIndices[i][j] -
splitInfo[sortedIndices[i][j]];
else    rightSortedIndices[i][right_index++] = sortedIndices[i][j]
- splitInfo[sortedIndices[i][j]];
}
}

// Recursively compute the kdnodes for the points in the two
splitted spaces
double[][] leftBBox = new double[2][];
double[][] rightBBox = new double[2][];

for(int i=0; i<2; i++) {
leftBBox[i] =
(double[])bBox[i].clone();
rightBBox[i] =
(double[])bBox[i].clone();
}

leftBBox[1][split_dim] = splitValue_small;
rightBBox[0][split_dim] = splitValue;

int next_dim = (split_dim + 1) % (d);
left = new Kdnode(leftPoints, next_dim, leftSortedIndices,
leftBBox);
right = new Kdnode(rightPoints, next_dim, rightSortedIndices,
rightBBox);
}
}

public double evaluate(double[] target, double delta, double
bandwidth) throws Exception
{

double dis_2_center = Common.distance(target,
center)/bandwidth;
double dm = diameter/bandwidth;

if(dis_2_center >= 1+dm) return 0.;
if(numOfPoints==1) return Common.K(dis_2_center);

/*if(dis_2_center<1)
{
double temp2 = dm*Common.KDeriv(dis_2_center);
if(temp2<delta) return
Common.K(dis_2_center)*numOfPoints;
} */

return left.evaluate(target,delta, bandwidth) +
right.evaluate(target,delta, bandwidth);
}

public double get_diameter(double[][] bBox)
{
double value = 0., diff;
for (int i=0; i<bBox[0].length;i++)
{
diff = (bBox[1][i] - bBox[0][i])/2.;
value += diff*diff;
}
return Math.sqrt(value);
}
}

=====
Jason Liao, http://www.geocities.com/jg_liao
Dept. of Biostatistics, http://www2.umdnj.edu/bmtrxweb
University of Medicine and Dentistry of New Jersey
phone 732-235-5429, School of Public Health office
phone 732-235-8611, Cancer Institute of New Jersey office
moble phone 908-720-4205

```