trees/thirdGenKD/KdNode.java

package ags.utils.dataStructures.trees.thirdGenKD;

import java.util.Arrays;

/**
 *
 */
class KdNode<T> {
    // All types
    protected int dimensions;
    protected int bucketCapacity;
    protected int size;

    // Leaf only
    protected double[][] points;
    protected Object[] data;

    // Stem only
    protected KdNode<T> left, right;
    protected int splitDimension;
    protected double splitValue;

    // Bounds
    protected double[] minBound, maxBound;
    protected boolean singlePoint;

    protected KdNode(int dimensions, int bucketCapacity) {
        // Init base
        this.dimensions = dimensions;
        this.bucketCapacity = bucketCapacity;
        this.size = 0;
        this.singlePoint = true;

        // Init leaf elements
        this.points = new double[bucketCapacity+1][];
        this.data = new Object[bucketCapacity+1];
    }

    /* -------- SIMPLE GETTERS -------- */

    public int size() {
        return size;
    }

    public boolean isLeaf() {
        return points != null;
    }

    /* -------- OPERATIONS -------- */

    public void addPoint(double[] point, T value) {
        KdNode<T> cursor = this;
        while (!cursor.isLeaf()) {
            cursor.extendBounds(point);
            cursor.size++;
            if (point[cursor.splitDimension] > cursor.splitValue) {
                cursor = cursor.right;
            }
            else {
                cursor = cursor.left;
            }
        }
        cursor.addLeafPoint(point, value);
    }

    /* -------- INTERNAL OPERATIONS -------- */

    public void addLeafPoint(double[] point, T value) {
        // Add the data point
        points[size] = point;
        data[size] = value;
        extendBounds(point);
        size++;

        if (size == points.length - 1) {
            // If the node is getting too large
            if (calculateSplit()) {
                // If the node successfully had it's split value calculated, split node
                splitLeafNode();
            } else {
                // If the node could not be split, enlarge node
                increaseLeafCapacity();
            }
        }
    }

    private boolean checkBounds(double[] point) {
        for (int i = 0; i < dimensions; i++) {
            if (point[i] > maxBound[i]) return false;
            if (point[i] < minBound[i]) return false;
        }
        return true;
    }

    private void extendBounds(double[] point) {
        if (minBound == null) {
            minBound = Arrays.copyOf(point, dimensions);
            maxBound = Arrays.copyOf(point, dimensions);
            return;
        }

        for (int i = 0; i < dimensions; i++) {
            if (Double.isNaN(point[i])) {
                if (!Double.isNaN(minBound[i]) || !Double.isNaN(maxBound[i])) {
                    singlePoint = false;
                }
                minBound[i] = Double.NaN;
                maxBound[i] = Double.NaN;
            }
            else if (minBound[i] > point[i]) {
                minBound[i] = point[i];
                singlePoint = false;
            }
            else if (maxBound[i] < point[i]) {
                maxBound[i] = point[i];
                singlePoint = false;
            }
        }
    }

    private void increaseLeafCapacity() {
        points = Arrays.copyOf(points, points.length*2);
        data = Arrays.copyOf(data, data.length*2);
    }

    private boolean calculateSplit() {
        if (singlePoint) return false;

        double width = 0;
        for (int i = 0; i < dimensions; i++) {
            double dwidth = (maxBound[i] - minBound[i]);
            if (Double.isNaN(dwidth)) dwidth = 0;
            if (dwidth > width) {
                splitDimension = i;
                width = dwidth;
            }
        }

        if (width == 0) {
            return false;
        }

        // Start the split in the middle of the variance
        splitValue = (minBound[splitDimension] + maxBound[splitDimension]) * 0.5;

        // Never split on infinity or NaN
        if (splitValue == Double.POSITIVE_INFINITY) {
            splitValue = Double.MAX_VALUE;
        }
        else if (splitValue == Double.NEGATIVE_INFINITY) {
            splitValue = -Double.MAX_VALUE;
        }

        // Don't let the split value be the same as the upper value as
        // can happen due to rounding errors!
        if (splitValue == maxBound[splitDimension]) {
            splitValue = minBound[splitDimension];
        }

        // Success
        return true;
    }

    private void splitLeafNode() {
        right = new KdNode<T>(dimensions, bucketCapacity);
        left = new KdNode<T>(dimensions, bucketCapacity);

        // Move locations into children
        for (int i = 0; i < size; i++) {
            double[] oldLocation = points[i];
            Object oldData = data[i];
            if (oldLocation[splitDimension] > splitValue) {
                right.addLeafPoint(oldLocation, (T) oldData);
            }
            else {
                left.addLeafPoint(oldLocation, (T) oldData);
            }
        }

        points = null;
        data = null;
    }
}
1	package ags.utils.dataStructures.trees.thirdGenKD;
2
3	import java.util.Arrays;
4
5	/**
6	*
7	*/
8	class KdNode<T> {
9	// All types
10	protected int dimensions;
11	protected int bucketCapacity;
12	protected int size;
13
14	// Leaf only
15	protected double[][] points;
16	protected Object[] data;
17
18	// Stem only
19	protected KdNode<T> left, right;
20	protected int splitDimension;
21	protected double splitValue;
22
23	// Bounds
24	protected double[] minBound, maxBound;
25	protected boolean singlePoint;
26
27	protected KdNode(int dimensions, int bucketCapacity) {
28	// Init base
29	this.dimensions = dimensions;
30	this.bucketCapacity = bucketCapacity;
31	this.size = 0;
32	this.singlePoint = true;
33
34	// Init leaf elements
35	this.points = new double[bucketCapacity+1][];
36	this.data = new Object[bucketCapacity+1];
37	}
38
39	/* -------- SIMPLE GETTERS -------- */
40
41	public int size() {
42	return size;
43	}
44
45	public boolean isLeaf() {
46	return points != null;
47	}
48
49	/* -------- OPERATIONS -------- */
50
51	public void addPoint(double[] point, T value) {
52	KdNode<T> cursor = this;
53	while (!cursor.isLeaf()) {
54	cursor.extendBounds(point);
55	cursor.size++;
56	if (point[cursor.splitDimension] > cursor.splitValue) {
57	cursor = cursor.right;
58	}
59	else {
60	cursor = cursor.left;
61	}
62	}
63	cursor.addLeafPoint(point, value);
64	}
65
66	/* -------- INTERNAL OPERATIONS -------- */
67
68	public void addLeafPoint(double[] point, T value) {
69	// Add the data point
70	points[size] = point;
71	data[size] = value;
72	extendBounds(point);
73	size++;
74
75	if (size == points.length - 1) {
76	// If the node is getting too large
77	if (calculateSplit()) {
78	// If the node successfully had it's split value calculated, split node
79	splitLeafNode();
80	} else {
81	// If the node could not be split, enlarge node
82	increaseLeafCapacity();
83	}
84	}
85	}
86
87	private boolean checkBounds(double[] point) {
88	for (int i = 0; i < dimensions; i++) {
89	if (point[i] > maxBound[i]) return false;
90	if (point[i] < minBound[i]) return false;
91	}
92	return true;
93	}
94
95	private void extendBounds(double[] point) {
96	if (minBound == null) {
97	minBound = Arrays.copyOf(point, dimensions);
98	maxBound = Arrays.copyOf(point, dimensions);
99	return;
100	}
101
102	for (int i = 0; i < dimensions; i++) {
103	if (Double.isNaN(point[i])) {
104	if (!Double.isNaN(minBound[i]) \|\| !Double.isNaN(maxBound[i])) {
105	singlePoint = false;
106	}
107	minBound[i] = Double.NaN;
108	maxBound[i] = Double.NaN;
109	}
110	else if (minBound[i] > point[i]) {
111	minBound[i] = point[i];
112	singlePoint = false;
113	}
114	else if (maxBound[i] < point[i]) {
115	maxBound[i] = point[i];
116	singlePoint = false;
117	}
118	}
119	}
120
121	private void increaseLeafCapacity() {
122	points = Arrays.copyOf(points, points.length*2);
123	data = Arrays.copyOf(data, data.length*2);
124	}
125
126	private boolean calculateSplit() {
127	if (singlePoint) return false;
128
129	double width = 0;
130	for (int i = 0; i < dimensions; i++) {
131	double dwidth = (maxBound[i] - minBound[i]);
132	if (Double.isNaN(dwidth)) dwidth = 0;
133	if (dwidth > width) {
134	splitDimension = i;
135	width = dwidth;
136	}
137	}
138
139	if (width == 0) {
140	return false;
141	}
142
143	// Start the split in the middle of the variance
144	splitValue = (minBound[splitDimension] + maxBound[splitDimension]) * 0.5;
145
146	// Never split on infinity or NaN
147	if (splitValue == Double.POSITIVE_INFINITY) {
148	splitValue = Double.MAX_VALUE;
149	}
150	else if (splitValue == Double.NEGATIVE_INFINITY) {
151	splitValue = -Double.MAX_VALUE;
152	}
153
154	// Don't let the split value be the same as the upper value as
155	// can happen due to rounding errors!
156	if (splitValue == maxBound[splitDimension]) {
157	splitValue = minBound[splitDimension];
158	}
159
160	// Success
161	return true;
162	}
163
164	private void splitLeafNode() {
165	right = new KdNode<T>(dimensions, bucketCapacity);
166	left = new KdNode<T>(dimensions, bucketCapacity);
167
168	// Move locations into children
169	for (int i = 0; i < size; i++) {
170	double[] oldLocation = points[i];
171	Object oldData = data[i];
172	if (oldLocation[splitDimension] > splitValue) {
173	right.addLeafPoint(oldLocation, (T) oldData);
174	}
175	else {
176	left.addLeafPoint(oldLocation, (T) oldData);
177	}
178	}
179
180	points = null;
181	data = null;
182	}
183	}