trees/thirdGenKD/NearestNeighborIterator.java

package ags.utils.dataStructures.trees.thirdGenKD;

import ags.utils.dataStructures.BinaryHeap;
import ags.utils.dataStructures.IntervalHeap;
import ags.utils.dataStructures.MinHeap;

import java.util.Arrays;
import java.util.Iterator;

/**
 *
 */
public class NearestNeighborIterator<T> implements Iterator<T>, Iterable<T> {
    private DistanceFunction distanceFunction;
    private double[] searchPoint;
    private MinHeap<KdNode<T>> pendingPaths;
    private IntervalHeap<T> evaluatedPoints;
    private int pointsRemaining;
    private double lastDistanceReturned;

    protected NearestNeighborIterator(KdNode<T> treeRoot, double[] searchPoint, int maxPointsReturned, DistanceFunction distanceFunction) {
        this.searchPoint = Arrays.copyOf(searchPoint, searchPoint.length);
        this.pointsRemaining = Math.min(maxPointsReturned, treeRoot.size());
        this.distanceFunction = distanceFunction;
        this.pendingPaths = new BinaryHeap.Min<KdNode<T>>();
        this.pendingPaths.offer(0, treeRoot);
        this.evaluatedPoints = new IntervalHeap<T>();
    }

    /* -------- INTERFACE IMPLEMENTATION -------- */

    @Override
    public boolean hasNext() {
        return pointsRemaining > 0;
    }

    @Override
    public T next() {
        if (!hasNext()) {
            throw new IllegalStateException("NearestNeighborIterator has reached end!");
        }

        while (pendingPaths.size() > 0 && (evaluatedPoints.size() == 0 || (pendingPaths.getMinKey() < evaluatedPoints.getMinKey()))) {
            KdTree.nearestNeighborSearchStep(pendingPaths, evaluatedPoints, pointsRemaining, distanceFunction, searchPoint);
        }

        // Return the smallest distance point
        pointsRemaining--;
        lastDistanceReturned = evaluatedPoints.getMinKey();
        T value = evaluatedPoints.getMin();
        evaluatedPoints.removeMin();
        return value;
    }

    public double distance() {
        return lastDistanceReturned;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator<T> iterator() {
        return this;
    }
}
1	package ags.utils.dataStructures.trees.thirdGenKD;
2
3	import ags.utils.dataStructures.BinaryHeap;
4	import ags.utils.dataStructures.IntervalHeap;
5	import ags.utils.dataStructures.MinHeap;
6
7	import java.util.Arrays;
8	import java.util.Iterator;
9
10	/**
11	*
12	*/
13	public class NearestNeighborIterator<T> implements Iterator<T>, Iterable<T> {
14	private DistanceFunction distanceFunction;
15	private double[] searchPoint;
16	private MinHeap<KdNode<T>> pendingPaths;
17	private IntervalHeap<T> evaluatedPoints;
18	private int pointsRemaining;
19	private double lastDistanceReturned;
20
21	protected NearestNeighborIterator(KdNode<T> treeRoot, double[] searchPoint, int maxPointsReturned, DistanceFunction distanceFunction) {
22	this.searchPoint = Arrays.copyOf(searchPoint, searchPoint.length);
23	this.pointsRemaining = Math.min(maxPointsReturned, treeRoot.size());
24	this.distanceFunction = distanceFunction;
25	this.pendingPaths = new BinaryHeap.Min<KdNode<T>>();
26	this.pendingPaths.offer(0, treeRoot);
27	this.evaluatedPoints = new IntervalHeap<T>();
28	}
29
30	/* -------- INTERFACE IMPLEMENTATION -------- */
31
32	@Override
33	public boolean hasNext() {
34	return pointsRemaining > 0;
35	}
36
37	@Override
38	public T next() {
39	if (!hasNext()) {
40	throw new IllegalStateException("NearestNeighborIterator has reached end!");
41	}
42
43	while (pendingPaths.size() > 0 && (evaluatedPoints.size() == 0 \|\| (pendingPaths.getMinKey() < evaluatedPoints.getMinKey()))) {
44	KdTree.nearestNeighborSearchStep(pendingPaths, evaluatedPoints, pointsRemaining, distanceFunction, searchPoint);
45	}
46
47	// Return the smallest distance point
48	pointsRemaining--;
49	lastDistanceReturned = evaluatedPoints.getMinKey();
50	T value = evaluatedPoints.getMin();
51	evaluatedPoints.removeMin();
52	return value;
53	}
54
55	public double distance() {
56	return lastDistanceReturned;
57	}
58
59	@Override
60	public void remove() {
61	throw new UnsupportedOperationException();
62	}
63
64	@Override
65	public Iterator<T> iterator() {
66	return this;
67	}
68	}