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	torben	2744	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			}