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