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