慕课test 5星练习题

package net.mooctest; import java.util.ArrayDeque; import java.util.Deque; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.PriorityQueue; import java.util.Set; import net.mooctest.SplitFunction.SplitResult; /** * The main class that implements the M-Tree. * * @param <DATA> The type of data that will be indexed by the M-Tree. Objects of * this type are stored in HashMaps and HashSets, so their * {@code hashCode()} and {@code equals()} methods must be consistent. */ public class MTree<DATA> { /** * The type of the results for nearest-neighbor queries. */ public class ResultItem { private ResultItem(DATA data, double distance) { this.data = data; this.distance = distance; } /** A nearest-neighbor. */ public DATA data; /** * The distance from the nearest-neighbor to the query data object * parameter. */ public double distance; } // Exception classes private static class SplitNodeReplacement extends Exception { // A subclass of Throwable cannot be generic. :-( // So, we have newNodes declared as Object[] instead of Node[]. private Object newNodes[]; private SplitNodeReplacement(Object... newNodes) { this.newNodes = newNodes; } } private static class RootNodeReplacement extends Exception { // A subclass of Throwable cannot be generic. :-( // So, we have newRoot declared as Object instead of Node. private Object newRoot; private RootNodeReplacement(Object newRoot) { this.newRoot = newRoot; } } private static class NodeUnderCapacity extends Exception { } private static class DataNotFound extends Exception { } /** * An {@link Iterable} class which can be iterated to fetch the results of a * nearest-neighbors query. * * <p>The neighbors are presented in non-decreasing order from the {@code * queryData} argument to the {@link MTree#getNearest(Object, double, int) * getNearest*()} * call. * * <p>The query on the M-Tree is executed during the iteration, as the * results are fetched. It means that, by the time when the <i>n</i>-th * result is fetched, the next result may still not be known, and the * resources allocated were only the necessary to identify the <i>n</i> * first results. */ public class Query implements Iterable<ResultItem> { private class ResultsIterator implements Iterator<ResultItem> { private class ItemWithDistances <U> implements Comparable<ItemWithDistances<U>> { private U item; private double distance; private double minDistance; public ItemWithDistances(U item, double distance, double minDistance) { this.item = item; this.distance = distance; this.minDistance = minDistance; } @Override public int compareTo(ItemWithDistances<U> that) { if(this.minDistance < that.minDistance) { return -1; } else if(this.minDistance > that.minDistance) { return +1; } else { return 0; } } } private ResultItem nextResultItem = null; private boolean finished = false; private PriorityQueue<ItemWithDistances<Node>> pendingQueue = new PriorityQueue<ItemWithDistances<Node>>(); private double nextPendingMinDistance; private PriorityQueue<ItemWithDistances<Entry>> nearestQueue = new PriorityQueue<ItemWithDistances<Entry>>(); private int yieldedCount; private ResultsIterator() { if(MTree.this.root == null) { finished = true; return; } double distance = MTree.this.distanceFunction.calculate(Query.this.data, MTree.this.root.data); double minDistance = Math.max(distance - MTree.this.root.radius, 0.0); pendingQueue.add(new ItemWithDistances<Node>(MTree.this.root, distance, minDistance)); nextPendingMinDistance = minDistance; } @Override public boolean hasNext() { if(finished) { return false; } if(nextResultItem == null) { fetchNext(); } if(nextResultItem == null) { finished = true; return false; } else { return true; } } @Override public ResultItem next() { if(hasNext()) { ResultItem next = nextResultItem; nextResultItem = null; return next; } else { throw new NoSuchElementException(); } } @Override public void remove() { throw new UnsupportedOperationException(); } private void fetchNext() { assert !finished; if(finished || yieldedCount >= Query.this.limit) { finished = true; return; } while(!pendingQueue.isEmpty() || !nearestQueue.isEmpty()) { if(prepareNextNearest()) { return; } assert !pendingQueue.isEmpty(); ItemWithDistances<Node> pending = pendingQueue.poll(); Node node = pending.item; for(IndexItem child : node.children.values()) { if(Math.abs(pending.distance - child.distanceToParent) - child.radius <= Query.this.range) { double childDistance = MTree.this.distanceFunction.calculate(Query.this.data, child.data); double childMinDistance = Math.max(childDistance - child.radius, 0.0); if(childMinDistance <= Query.this.range) { if(child instanceof MTree.Entry) { @SuppressWarnings("unchecked") Entry entry = (Entry)child; nearestQueue.add(new ItemWithDistances<Entry>(entry, childDistance, childMinDistance)); } else { @SuppressWarnings("unchecked") Node childNode = (Node)child; pendingQueue.add(new ItemWithDistances<Node>(childNode, childDistance, childMinDistance)); } } } } if(pendingQueue.isEmpty()) { nextPendingMinDistance = Double.POSITIVE_INFINITY; } else { nextPendingMinDistance = pendingQueue.peek().minDistance; } } finished = true; } private boolean prepareNextNearest() { if(!nearestQueue.isEmpty()) { ItemWithDistances<Entry> nextNearest = nearestQueue.peek(); if(nextNearest.distance <= nextPendingMinDistance) { nearestQueue.poll(); nextResultItem = new ResultItem(nextNearest.item.data, nextNearest.distance); ++yieldedCount; return true; } } return false; } } private Query(DATA data, double range, int limit) { this.data = data; this.range = range; this.limit = limit; } @Override public Iterator<ResultItem> iterator() { return new ResultsIterator(); } private DATA data; private double range; private int limit; } /** * The default minimum capacity of nodes in an M-Tree, when not specified in * the constructor call. */ public static final int DEFAULT_MIN_NODE_CAPACITY = 50; protected int minNodeCapacity; protected int maxNodeCapacity; protected DistanceFunction<? super DATA> distanceFunction; protected SplitFunction<DATA> splitFunction; protected Node root; /** * Constructs an M-Tree with the specified distance function. * @param distanceFunction The object used to calculate the distance between * two data objects. */ public MTree(DistanceFunction<? super DATA> distanceFunction, SplitFunction<DATA> splitFunction) { this(DEFAULT_MIN_NODE_CAPACITY, distanceFunction, splitFunction); } /** * Constructs an M-Tree with the specified minimum node capacity and * distance function. * @param minNodeCapacity The minimum capacity for the nodes of the tree. * @param distanceFunction The object used to calculate the distance between * two data objects. * @param splitFunction The object used to process the split of nodes if * they are full when a new child must be added. */ public MTree(int minNodeCapacity, DistanceFunction<? super DATA> distanceFunction, SplitFunction<DATA> splitFunction) { this(minNodeCapacity, 2 * minNodeCapacity - 1, distanceFunction, splitFunction);