AbstractBucketPointMap.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.geometry.core.internal;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Set;
import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.collection.PointMap;
import org.apache.commons.numbers.core.Precision;
/** Abstract tree-based {@link PointMap} implementation that stores entries in bucket nodes
* that are split once a certain entry count threshold is reached. The main goal of this class
* is to provide a generic, multidimensional implementation that maintains reasonable performance
* regardless of point count and insertion order. Like other tree data structures, performance
* is tied closely to tree depth, which can vary depending on insertion order for a given set of
* points. In order to help maintain performance in cases of non-optimal point insertion order,
* this class uses a strategy of "point folding", implemented as follows:
* <ul>
* <li>Two separate tree roots are maintained by the map: a primary root and a secondary root.</li>
* <li>Entries are added to the primary root until the it reaches its capacity and is split using
* an algorithm specific to the space and dimension. At this point, the populated primary root
* becomes the secondary root and a new, empty primary root is created.</li>
* <li>Points are inserted into the new primary root as before. However, for each new point inserted,
* an existing point is removed from the secondary root and inserted into the primary root.</li>
* <li>Points are moved from the secondary root and inserted into the primary root in this way until the
* secondary root is empty. At this point, the primary root becomes the secondary root and another
* primary root is created.</li>
* </ul>
* In this way, previously inserted points can apply a balancing influence on the low levels of the tree
* as new points are inserted.
*
* <p>This class is <em>not</em> thread-safe.</p>
* @param <P> Point type
* @param <V> Map value type
*/
public abstract class AbstractBucketPointMap<P extends Point<P>, V>
extends AbstractMap<P, V>
implements PointMap<P, V> {
/** Interface for constructing new {@link BucketNode} instances.
* @param <P> Point type
* @param <V> Map value type
*/
@FunctionalInterface
public interface BucketNodeFactory<P extends Point<P>, V> {
/** Create a new {@link BucketNode} instance.
* @param map owning map
* @param parent parent node; will be null for the tree root
* @param childIndex index of the new node in its parent child list; will be {@code -1}
* if the new node does not have a parent
* @return the newly created node
*/
BucketNode<P, V> createNode(AbstractBucketPointMap<P, V> map, BucketNode<P, V> parent, int childIndex);
}
/** Child index used when no node parent exists. */
private static final int DEFAULT_CHILD_INDEX = -1;
/** Function used to construct new node instances. */
private final BucketNodeFactory<P, V> nodeFactory;
/** Maximum number of entries stored per node before the node is split. */
private final int maxNodeEntryCount;
/** Number of child nodes for each non-leaf node. */
private final int nodeChildCount;
/** Precision context. */
private final Precision.DoubleEquivalence precision;
/** Primary tree root. */
private BucketNode<P, V> root;
/** Secondary tree root. */
private BucketNode<P, V> secondaryRoot;
/** Cached entry set; instances are stateless so we need only one. */
private EntrySet entrySetInstance;
/** Version counter, used to track tree modifications. */
private int version;
/** Construct a new instance.
* @param nodeFactory object used to construct new node instances
* @param maxNodeEntryCount maximum number of map entries per node before
* the node is split
* @param nodeChildCount number of child nodes per internal node
* @param precision precision object used for floating point comparisons
*/
protected AbstractBucketPointMap(
final BucketNodeFactory<P, V> nodeFactory,
final int maxNodeEntryCount,
final int nodeChildCount,
final Precision.DoubleEquivalence precision) {
this.nodeFactory = nodeFactory;
this.maxNodeEntryCount = maxNodeEntryCount;
this.nodeChildCount = nodeChildCount;
this.precision = precision;
this.root = nodeFactory.createNode(this, null, DEFAULT_CHILD_INDEX);
}
/** {@inheritDoc} */
@Override
public Entry<P, V> getEntry(final P pt) {
return findEntryByPoint(pt);
}
/** {@inheritDoc} */
@Override
public int size() {
return root.getEntryCount() +
(secondaryRoot != null ? secondaryRoot.getEntryCount() : 0);
}
/** {@inheritDoc} */
@Override
public V put(final P key, final V value) {
GeometryInternalUtils.requireFinite(key);
final Entry<P, V> entry = findEntryByPoint(key);
if (entry != null) {
return entry.setValue(value);
}
root.insertEntry(new SimpleEntry<>(key, value));
entryAdded();
return null;
}
/** {@inheritDoc} */
@Override
public V get(final Object key) {
return getValue(findEntry(key));
}
/** {@inheritDoc} */
@Override
public V remove(final Object key) {
@SuppressWarnings("unchecked")
final Entry<P, V> entry = removeEntryByPoint((P) key);
if (entry != null) {
entryRemoved();
return entry.getValue();
}
return null;
}
/** {@inheritDoc} */
@Override
public boolean containsKey(final Object key) {
return findEntry(key) != null;
}
/** {@inheritDoc} */
@Override
public boolean containsValue(final Object value) {
return root.findEntryByValue(value) != null ||
(secondaryRoot != null && secondaryRoot.findEntryByValue(value) != null);
}
/** {@inheritDoc} */
@Override
public Set<Entry<P, V>> entrySet() {
if (entrySetInstance == null) {
entrySetInstance = new EntrySet();
}
return entrySetInstance;
}
/** {@inheritDoc} */
@Override
public void clear() {
root = createNode(null, DEFAULT_CHILD_INDEX);
secondaryRoot = null;
}
/** {@inheritDoc} */
@Override
public Entry<P, V> nearestEntry(final P pt) {
GeometryInternalUtils.requireFinite(pt);
DistancedValue<Entry<P, V>> result = root.findNearestEntry(pt);
if (secondaryRoot != null) {
final DistancedValue<Entry<P, V>> secondaryResult = secondaryRoot.findNearestEntry(pt);
result = getNearest(secondaryResult, result);
}
return result != null ?
result.getValue() :
null;
}
/** {@inheritDoc} */
@Override
public Entry<P, V> farthestEntry(final P pt) {
GeometryInternalUtils.requireFinite(pt);
DistancedValue<Entry<P, V>> result = root.findFarthestEntry(pt);
if (secondaryRoot != null) {
final DistancedValue<Entry<P, V>> secondaryResult = secondaryRoot.findFarthestEntry(pt);
result = getFarthest(secondaryResult, result);
}
return result != null ?
result.getValue() :
null;
}
/** {@inheritDoc} */
@Override
public Collection<Entry<P, V>> entriesNearToFar(final P pt) {
GeometryInternalUtils.requireFinite(pt);
return new AbstractEntryCollection() {
@Override
public Iterator<Entry<P, V>> iterator() {
return new NearToFarIterator<>(AbstractBucketPointMap.this, pt);
}
};
}
/** {@inheritDoc} */
@Override
public Collection<Entry<P, V>> entriesFarToNear(final P pt) {
GeometryInternalUtils.requireFinite(pt);
return new AbstractEntryCollection() {
@Override
public Iterator<Entry<P, V>> iterator() {
return new FarToNearIterator<>(AbstractBucketPointMap.this, pt);
}
};
}
/** Get the configured precision for the instance.
* @return precision object
*/
protected Precision.DoubleEquivalence getPrecision() {
return precision;
}
/** Return true if the given points are equivalent using the precision
* configured for the map.
* @param a first point
* @param b second point
* @return true if the given points are equivalent
*/
protected abstract boolean pointsEq(P a, P b);
/** Compare two points to determine a consistent ordering when other comparison
* criteria consider them equal.
* @param a first point
* @param b second point
* @return integer comparison result
*/
protected abstract int disambiguatePointComparison(P a, P b);
/** Construct a new node instance.
* @param parent parent node; will be null for the tree root
* @param childIndex index of the node in its parent child list
* @return the new node instance
*/
private BucketNode<P, V> createNode(final BucketNode<P, V> parent, final int childIndex) {
return nodeFactory.createNode(this, parent, childIndex);
}
/** Method called when a new entry is added to the tree.
*/
private void entryAdded() {
++version;
if (!root.isLeaf() && secondaryRoot == null) {
secondaryRoot = root;
root = createNode(null, DEFAULT_CHILD_INDEX);
}
migrateSecondaryEntry();
checkRemoveSecondaryRoot();
}
/** Method called when an entry is removed from the tree.
*/
private void entryRemoved() {
++version;
checkRemoveSecondaryRoot();
}
/** Create a list for storing map entries.
* @return list for storing map entries
*/
private List<Entry<P, V>> createEntryList() {
return new ArrayList<>(maxNodeEntryCount);
}
/** Create a list for storing node children. The returned list contains
* {@code nodeChildCount} number of {@code null} entries.
* @return list for storing node children
*/
@SuppressWarnings("unchecked")
private List<BucketNode<P, V>> createNodeChildList() {
return Arrays.asList(new BucketNode[nodeChildCount]);
}
/** Get the entry for the given key or null if not found.
* @param key key to search for
* @return entry for the given key or null if not found
*/
@SuppressWarnings("unchecked")
private Entry<P, V> findEntry(final Object key) {
return findEntryByPoint((P) key);
}
/** Find the entry for the given point or null if one does not
* exist.
* @param pt point to find the entry for
* @return entry for the given point or null if one does not exist
*/
private Entry<P, V> findEntryByPoint(final P pt) {
Entry<P, V> entry = null;
if (pt.isFinite()) {
entry = root.findEntry(pt);
if (entry == null && secondaryRoot != null) {
entry = secondaryRoot.findEntry(pt);
}
}
return entry;
}
/** Remove and return the entry for the given point or null
* if no such entry exists.
* @param pt point to remove the entry for
* @return the removed entry or null if not found
*/
private Entry<P, V> removeEntryByPoint(final P pt) {
Entry<P, V> entry = null;
if (pt.isFinite()) {
entry = root.removeEntry(pt);
if (entry == null && secondaryRoot != null) {
entry = secondaryRoot.removeEntry(pt);
}
}
return entry;
}
/** Move an entry from the secondary root (if present) to the primary root. This process
* reintroduces points from a previous insertion back into higher levels of the root tree,
* thereby giving the root tree more balanced split points.
*/
private void migrateSecondaryEntry() {
if (secondaryRoot != null) {
final int offset = version % nodeChildCount;
final boolean even = (offset & 1) > 0;
final int idx = even ?
offset / 2 :
nodeChildCount - 1 - (offset / 2);
final Entry<P, V> entry = secondaryRoot.removeEntryAlongIndexPath(idx);
if (entry != null) {
root.insertEntry(entry);
}
}
}
/** Remove the secondary root if empty.
*/
private void checkRemoveSecondaryRoot() {
if (secondaryRoot != null && secondaryRoot.isEmpty()) {
secondaryRoot.destroy();
secondaryRoot = null;
}
}
/** Get the argument with the smallest distance value.
* @param a first entry; may be null
* @param b second entry; may be null
* @return argument with the smallest distance value
*/
private DistancedValue<Entry<P, V>> getNearest(
final DistancedValue<Entry<P, V>> a,
final DistancedValue<Entry<P, V>> b) {
return compareEntries(a, b, Double.POSITIVE_INFINITY) < 0 ?
a :
b;
}
/** Get the argument with the largest distance value.
* @param a first entry; may be null
* @param b second entry; may be null
* @return argument with the largest distance value
*/
private DistancedValue<Entry<P, V>> getFarthest(
final DistancedValue<Entry<P, V>> a,
final DistancedValue<Entry<P, V>> b) {
return compareEntries(a, b, 0d) > 0 ?
a :
b;
}
/** Compare two entries with distance values. If either entry is null, the distance
* for that entry is taken to be {@code nullDistance}.
* @param a first entry; may be null
* @param b second entry; may be null
* @param nullDistance distance used for null arguments
* @return integer comparison result
*/
private int compareEntries(
final DistancedValue<Entry<P, V>> a,
final DistancedValue<Entry<P, V>> b,
final double nullDistance) {
final double aDist = a != null ? a.getDistance() : nullDistance;
final double bDist = b != null ? b.getDistance() : nullDistance;
int cmp = Double.compare(aDist, bDist);
if (cmp == 0 &&
a != null &&
b != null) {
return disambiguatePointComparison(a.getValue().getKey(), b.getValue().getKey());
}
return cmp;
}
/** Return true if {@code dist} is within the specified maximum value, meaning if it
* is less than or equal to {@code maxDist} using the configured precision context.
* @param dist distance to test
* @param maxDist maximum distance
* @return true if {@code dist} is within the given maximum
*/
private boolean distanceIsWithinMax(final double dist, final double maxDist) {
return precision.lte(dist, maxDist);
}
/** Return the value for the argument or {@code null} if {@code entry}
* is {@code null}.
* @param <V> Value type
* @param entry entry to return the value for; may be null
* @return value for the argument or null if the argument is null
*/
private static <V> V getValue(final Entry<?, V> entry) {
return entry != null ?
entry.getValue() :
null;
}
/** Spatial partitioning node type that stores map entries in a list until
* a threshold is reached, at which point the node is split.
* @param <P> Point type
* @param <V> Value type
*/
protected abstract static class BucketNode<P extends Point<P>, V>
implements Iterable<Entry<P, V>> {
/** Owning map. */
private AbstractBucketPointMap<P, V> map;
/** Parent node. */
private BucketNode<P, V> parent;
/** Index of this node in its parent child list. */
private int childIndex;
/** Child nodes; elements may be null. */
private List<BucketNode<P, V>> children;
/** Entries stored in the node; will be null for non-leaf nodes. */
private List<Entry<P, V>> entries;
/** Number of entries in this subtree. */
private int entryCount;
/** Construct a new instance.
* @param map owning map
* @param parent parent node or null if the tree root
* @param childIndex index of this node in its parent, or {@code -1}
* if no parent exists
*/
protected BucketNode(
final AbstractBucketPointMap<P, V> map,
final BucketNode<P, V> parent,
final int childIndex) {
this.map = map;
this.parent = parent;
this.childIndex = childIndex;
// pull an entry list from the parent map; this will make
// this node a leaf initially
this.entries = map.createEntryList();
}
/** Get the index of this node in its parent, or {@code -1} if this
* node does not have a parent.
* @return index of this node in its parent, or {@code -1} if this
* node does not have a parent
*/
public int getChildIndex() {
return childIndex;
}
/**
* Return true if this node is a leaf node.
* @return true if this node is a leaf node
*/
public boolean isLeaf() {
return entries != null;
}
/**
* Return true if the subtree rooted at this node does not
* contain any map entries.
* @return true if the subtree root at this node is empty
*/
public boolean isEmpty() {
return entryCount < 1;
}
/** Get the number of map entries in the subtree rooted at this node.
* @return number of map entries in the subtree rooted at this node
*/
public int getEntryCount() {
return entryCount;
}
/** Find and return the map entry matching the given key.
* @param key point key
* @return entry matching the given key or null if not found
*/
public Entry<P, V> findEntry(final P key) {
if (isLeaf()) {
// leaf node; check the list of entries for a match
for (final Entry<P, V> entry : entries) {
if (map.pointsEq(key, entry.getKey())) {
return entry;
}
}
return null;
}
// internal node; delegate to each child that could possibly contain
// the point or an equivalent point
return findEntryInChildren(key);
}
/** Find and return the map entry matching the given key in the node's children.
* This method must only be called on internal nodes.
* @param key point key
* @return entry matching the given key or null if not found
*/
private Entry<P, V> findEntryInChildren(final P key) {
final int loc = getSearchLocation(key);
for (int i = 0; i < children.size(); ++i) {
if (testChildLocation(i, loc)) {
final Entry<P, V> entry = getEntryInChild(i, key);
if (entry != null) {
return entry;
}
}
}
return null;
}
/** Find the first entry in the tree with the given value or null if not found.
* @param value value to search for
* @return the first entry in the tree with the given value or null if not found
*/
public Entry<P, V> findEntryByValue(final Object value) {
if (isLeaf()) {
// leaf node; check the list of entries for a match
for (final Entry<P, V> entry : entries) {
if (Objects.equals(entry.getValue(), value)) {
return entry;
}
}
return null;
}
// internal node; delegate to each child
return findEntryByValueInChildren(value);
}
/** Find the first entry in the child subtrees for this node with the given value or null
* if not found. This method must only be called on internal nodes.
* @param value value to search for
* @return the first entry in the child subtrees with the given value or null if not found
*/
private Entry<P, V> findEntryByValueInChildren(final Object value) {
for (final BucketNode<P, V> child : children) {
if (child != null) {
final Entry<P, V> childResult = child.findEntryByValue(value);
if (childResult != null) {
return childResult;
}
}
}
return null;
}
/** Insert a new entry into the subtree, returning the new size of the
* subtree. No check is made as to whether or not the entry already exists.
* @param entry entry to insert
*/
public void insertEntry(final Entry<P, V> entry) {
if (isLeaf()) {
if (entries.size() < map.maxNodeEntryCount) {
// we have an open spot here so just add the entry
append(entry);
return;
}
// no available entries; split the node and add the new
// entry to a child
splitNode();
}
// insert into the first matching child
final int loc = getInsertLocation(entry.getKey());
for (int i = 0; i < children.size(); ++i) {
if (testChildLocation(i, loc)) {
getOrCreateChild(i).insertEntry(entry);
// update the subtree state
subtreeEntryAdded();
break;
}
}
}
/** Remove the given key, returning the previously mapped entry.
* @param key key to remove
* @return the value previously mapped to the key or null if no
* value was mapped
*/
public Entry<P, V> removeEntry(final P key) {
if (isLeaf()) {
// leaf node; check the existing entries for a match
final Iterator<Entry<P, V>> it = entries.iterator();
while (it.hasNext()) {
final Entry<P, V> entry = it.next();
if (map.pointsEq(key, entry.getKey())) {
it.remove();
// update the subtree state
subtreeEntryRemoved();
return entry;
}
}
return null;
}
// internal node; delegate to each child
return removeEntryFromChildren(key);
}
/** Remove the given key from the node's child subtrees, returning the previously
* mapped entry. This method must only be called on internal nodes.
* @param key key to remove
* @return the value previously mapped to the key or null if no
* value was mapped
*/
private Entry<P, V> removeEntryFromChildren(final P key) {
final int loc = getSearchLocation(key);
for (int i = 0; i < children.size(); ++i) {
if (testChildLocation(i, loc)) {
final Entry<P, V> entry = removeFromChild(i, key);
if (entry != null) {
// update the subtree state
subtreeEntryRemoved();
return entry;
}
}
}
return null;
}
/** Find the nearest entry to {@code refPt} in the subtree rooted at this node, or null if
* the subtree is empty.
* @param refPt reference point
* @return nearest entry to {@code refPt} in the subtree rooted at this node, or null if no
* such entry exists
*/
public DistancedValue<Entry<P, V>> findNearestEntry(final P refPt) {
return findNearestEntry(refPt, Double.POSITIVE_INFINITY);
}
/** Find the nearest entry to {@code refPt} within the maximum distance specified in the subtree
* rooted at this node, or null if no such entry exists.
* @param refPt reference point
* @param maxDist maximum search distance
* @return nearest entry to {@code refPt} within the maximum distance specified in the subtree
* rooted at this node, or null if no such entry exists.
*/
private DistancedValue<Entry<P, V>> findNearestEntry(final P refPt, final double maxDist) {
if (isLeaf()) {
// leaf node; look through the stored entries
DistancedValue<Entry<P, V>> closest = null;
for (final Entry<P, V> entry : entries) {
final DistancedValue<Entry<P, V>> entryWithDist = DistancedValue.of(
entry,
entry.getKey().distance(refPt));
if (map.distanceIsWithinMax(entryWithDist.getDistance(), maxDist)) {
closest = map.getNearest(entryWithDist, closest);
}
}
return closest;
}
// internal node;
return findNearestEntryInChildren(refPt, maxDist);
}
/** Find the nearest entry to {@code refPt} within the maximum distance specified in the child subtrees
* rooted at this node, or null if no such entry exists. This method must only be call on internal
* nodes.
* @param refPt reference point
* @param maxDist maximum search distance
* @return nearest entry to {@code refPt} within the maximum distance specified in the subtree
* rooted at this node, or null if no such entry exists.
*/
private DistancedValue<Entry<P, V>> findNearestEntryInChildren(final P refPt, final double maxDist) {
// look through children in order of increasing minimum distance from the
// reference point
final List<DistancedValue<BucketNode<P, V>>> sortedNodeList = new ArrayList<>(map.nodeChildCount);
final int loc = getInsertLocation(refPt);
for (int i = 0; i < children.size(); ++i) {
final BucketNode<P, V> child = children.get(i);
if (child != null) {
final double minChildDist = getMinChildDistance(i, refPt, loc);
if (map.distanceIsWithinMax(minChildDist, maxDist)) {
sortedNodeList.add(DistancedValue.of(child, minChildDist));
}
}
}
Collections.sort(sortedNodeList, DistancedValue.ascendingDistance());
DistancedValue<Entry<P, V>> closest = null;
for (final DistancedValue<BucketNode<P, V>> nodeValue : sortedNodeList) {
if (closest != null &&
map.distanceIsWithinMax(closest.getDistance(), nodeValue.getDistance())) {
// no more child nodes can contain anything closer so we can stop looking
break;
}
final DistancedValue<Entry<P, V>> entry = nodeValue.getValue()
.findNearestEntry(refPt, maxDist);
closest = map.getNearest(entry, closest);
}
return closest;
}
/** Find the farthest entry from {@code refPt} within the subtree rooted at this node..
* @param refPt reference point
* @return farthest entry from {@code refPt} in the subtree rooted at this node, or null
* if no such entry exists.
*/
public DistancedValue<Entry<P, V>> findFarthestEntry(final P refPt) {
if (isLeaf()) {
// leaf node; look through the stored entries
DistancedValue<Entry<P, V>> farthest = null;
for (final Entry<P, V> entry : entries) {
final DistancedValue<Entry<P, V>> entryWithDist = DistancedValue.of(
entry,
entry.getKey().distance(refPt));
farthest = map.getFarthest(entryWithDist, farthest);
}
return farthest;
} else {
// internal node; look through children in order of decreasing maximum distance
// distance from the reference point
final List<DistancedValue<BucketNode<P, V>>> sortedNodeList = new ArrayList<>(map.nodeChildCount);
final int loc = getInsertLocation(refPt);
for (int i = 0; i < children.size(); ++i) {
final BucketNode<P, V> child = children.get(i);
if (child != null) {
final double maxChildDist = getMaxChildDistance(i, refPt, loc);
sortedNodeList.add(DistancedValue.of(child, maxChildDist));
}
}
Collections.sort(sortedNodeList, DistancedValue.descendingDistance());
DistancedValue<Entry<P, V>> farthest = null;
for (final DistancedValue<BucketNode<P, V>> nodeValue : sortedNodeList) {
if (farthest != null &&
map.precision.gt(farthest.getDistance(), nodeValue.getDistance())) {
break;
}
final DistancedValue<Entry<P, V>> entry = nodeValue.getValue()
.findFarthestEntry(refPt);
farthest = map.getFarthest(entry, farthest);
}
return farthest;
}
}
/** Append an entry to the entry list for this node. This method must
* only be called on leaf nodes.
* @param entry entry to append
*/
public void append(final Entry<P, V> entry) {
entries.add(entry);
subtreeEntryAdded();
}
/** Remove an entry in a leaf node lying on the given child index path.
* @param idx target child index
* @return removed entry
*/
public Entry<P, V> removeEntryAlongIndexPath(final int idx) {
if (isLeaf()) {
if (!entries.isEmpty()) {
// remove the last entry in the list
final Entry<P, V> entry = entries.remove(entries.size() - 1);
subtreeEntryRemoved();
return entry;
}
} else {
final int childCount = children.size();
final int delta = idx < (map.nodeChildCount / 2) ?
+1 :
-1;
for (int n = 0, i = idx;
n < childCount;
++n, i += delta) {
final int adjustedIndex = (i + childCount) % childCount;
final Entry<P, V> entry = removeEntryAlongIndexPathFromChild(adjustedIndex, idx);
if (entry != null) {
return entry;
}
}
}
return null;
}
/** Remove an entry in a leaf node lying on the given index path, starting at the child at the
* given index.
* @param childIdx child index to remove from
* @param idx index path
* @return removed entry
*/
private Entry<P, V> removeEntryAlongIndexPathFromChild(final int childIdx, final int idx) {
final BucketNode<P, V> child = children.get(childIdx);
if (child != null) {
final Entry<P, V> entry = child.removeEntryAlongIndexPath(idx);
if (entry != null) {
// destroy and remove the child if empty
if (child.isEmpty()) {
child.destroy();
children.set(childIdx, null);
}
subtreeEntryRemoved();
return entry;
}
}
return null;
}
/** Destroy this node. The node must not be used after this method is called.
*/
public void destroy() {
this.map = null;
this.parent = null;
this.childIndex = DEFAULT_CHILD_INDEX;
this.children = null;
this.entries = null;
this.entryCount = 0;
}
/** Return true if this node has been destroyed.
* @return true if this node has been destroyed
*/
public boolean isDestroyed() {
return map == null;
}
/** Return an iterator for accessing the entries stored in this node. The {@code remove()}
* method of the returned iterator correctly updates the tree state. This method must only
* be called on leaf nodes.
* @return iterator for accessing the entries stored in this node
*/
@Override
public Iterator<Entry<P, V>> iterator() {
return iterator(0);
}
/** Return an iterator for accessing the entries stored in this node, starting at the given
* index. The {@code remove()} method of the returned iterator correctly updates the tree state.
* This method must only be called on leaf nodes.
* @param idx starting index for the iterator
* @return iterator for accessing the entries stored in this node, starting with the entry at
* the given index
*/
private Iterator<Entry<P, V>> iterator(final int idx) {
final List<Entry<P, V>> iteratedList = idx == 0 ?
entries :
entries.subList(idx, entries.size());
final Iterator<Entry<P, V>> it = iteratedList.iterator();
return new Iterator<Entry<P, V>>() {
@Override
public boolean hasNext() {
return !isDestroyed() && it.hasNext();
}
@Override
public Entry<P, V> next() {
return it.next();
}
@Override
public void remove() {
it.remove();
// store the owning map since we may be destroyed as part of
// entry removal
final AbstractBucketPointMap<P, V> owningMap = map;
// navigate up the tree and perform updates
BucketNode<P, V> current = BucketNode.this;
while (current != null) {
current.subtreeEntryRemoved();
current = current.parent;
}
// notify the owning map
owningMap.entryRemoved();
}
};
}
/** Compute the split for this node from the current set
* of map entries. Subclasses are responsible for managing
* the storage of the split.
*/
protected abstract void computeSplit();
/** Get an int encoding the search locations of {@code pt} relative to the
* node split. The return value must include all possible locations of
* {@code pt} and equivalent points.
* @param pt point to determine the relative location of
* @return encoded search location
*/
protected abstract int getSearchLocation(P pt);
/** Get an integer encoding the insert location of {@code pt} relative to the
* node split. The return value must be strict and only include the single
* location where {@code pt} should be inserted.
* @param pt point to determine the insert location of
* @return encoded insert location
*/
protected abstract int getInsertLocation(P pt);
/** Return true if the child node at {@code childIdx} matches the given
* encoded point location.
* @param childIdx child index to test
* @param loc encoded relative point location
* @return true if the child node a {@code childIdx} matches the location
*/
protected abstract boolean testChildLocation(int childIdx, int loc);
/** Get the minimum distance from {@code pt} to the split boundary for the child at
* the given index.
* @param childIdx child index
* @param pt point to compute the minimum distance from
* @param ptLoc encoded relative point location
* @return minimum distance from {@code pt} to the split boundary for the indicated child
*/
protected abstract double getMinChildDistance(int childIdx, P pt, int ptLoc);
/** Get the maximum distance from {@code pt} to the region for the child
* child node at the specified index. A value of {@code Double#POSITIVE_INFINITY}
* should be returned if there is no maximum.
* @param childIdx index of the child in question
* @param pt reference point
* @param ptLoc encoded relative point location
* @return maximum distance from {@code pt} to the node region
*/
protected abstract double getMaxChildDistance(int childIdx, P pt, int ptLoc);
/** Make this node a leaf node, using the given list of entries.
* @param leafEntries list of map entries to use for the node
*/
protected void makeLeaf(final List<Entry<P, V>> leafEntries) {
children = null;
entries = leafEntries;
}
/** Split the node and place all entries into the new child nodes.
* This node becomes an internal node.
*/
protected void splitNode() {
computeSplit();
children = map.createNodeChildList();
for (final Entry<P, V> entry : entries) {
moveToChild(entry);
}
entries = null;
}
/** Get the parent node or null if one does not exist.
* @return parent node or null if one does not exist.
*/
protected BucketNode<P, V> getParent() {
return parent;
}
/** Get the precision context for the instance.
* @return precision context for the instance
*/
protected Precision.DoubleEquivalence getPrecision() {
return map.precision;
}
/** Get the given entry in the child at {@code idx} or null if not found.
* @param idx child index
* @param key key to search for
* @return entry matching {@code key} in child or null if not found
*/
private Entry<P, V> getEntryInChild(final int idx, final P key) {
final BucketNode<P, V> child = children.get(idx);
if (child != null) {
return child.findEntry(key);
}
return null;
}
/** Remove the given key from the child at {@code idx}.
* @param idx index of the child
* @param key key to remove
* @return entry removed from the child or null if not found
*/
private Entry<P, V> removeFromChild(final int idx, final P key) {
final BucketNode<P, V> child = children.get(idx);
if (child != null) {
return child.removeEntry(key);
}
return null;
}
/** Move the previously created entry to a child node.
* @param entry entry to mode
*/
private void moveToChild(final Entry<P, V> entry) {
final int loc = getInsertLocation(entry.getKey());
final int numChildren = children.size();
for (int i = 0; i < numChildren; ++i) {
// place the entry in the first child that contains it
if (testChildLocation(i, loc)) {
getOrCreateChild(i).append(entry);
break;
}
}
}
/** Get the child node at the given index, creating it if needed.
* @param idx index of the child node
* @return child node at the given index
*/
private BucketNode<P, V> getOrCreateChild(final int idx) {
BucketNode<P, V> child = children.get(idx);
if (child == null) {
child = map.createNode(this, idx);
children.set(idx, child);
}
return child;
}
/** Method called when an entry is added to the subtree represented
* by this node.
*/
private void subtreeEntryAdded() {
++entryCount;
}
/** Method called when an entry is removed from the subtree represented
* by this node. If the subtree is an empty internal node, it is converted
* to a leaf node.
*/
private void subtreeEntryRemoved() {
--entryCount;
final int condenseThreshold = map.maxNodeEntryCount / 2;
if (!isLeaf() && entryCount <= condenseThreshold) {
final List<Entry<P, V>> subtreeEntries = map.createEntryList();
if (!isEmpty() &&
(parent == null || parent.getEntryCount() > condenseThreshold)) {
collectSubtreeEntriesRecursive(subtreeEntries, false);
}
makeLeaf(subtreeEntries);
}
}
/** Add all map entries in the subtree rooted at this node to {@code entryList}. If {@code destroyNode}
* is true, the node is destroyed after its entries are added to the list.
* @param entryList list to add entries to
* @param destroyNode if true, the node will be destroyed after its entries are added to the list
*/
private void collectSubtreeEntriesRecursive(final List<Entry<P, V>> entryList, final boolean destroyNode) {
if (isLeaf()) {
entryList.addAll(entries);
} else {
for (final BucketNode<P, V> child : children) {
if (child != null) {
child.collectSubtreeEntriesRecursive(entryList, true);
}
}
}
if (destroyNode) {
destroy();
}
}
/** Get an encoded search location value for the given comparison result. If
* {@code cmp} is {@code 0}, then the bitwise OR of {@code neg} and {@code pos}
* is returned, indicating that both spaces are valid search locations. Otherwise,
* {@code neg} is returned for negative {@code cmp} values and {@code pos} for
* positive ones. This location value is to be used during entry searches,
* when comparisons must be loose and all possible locations included.
* @param cmp comparison result
* @param neg negative flag
* @param pos positive flag
* @return encoded search location value
*/
public static int getSearchLocationValue(final int cmp, final int neg, final int pos) {
if (cmp < 0) {
return neg;
} else if (cmp > 0) {
return pos;
}
return neg | pos;
}
/** Get an insert location value for the given comparison result. If {@code cmp}
* is less than or equal to {@code 0}, then {@code neg} is returned. Otherwise,
* {@code pos} is returned. This location value is to be used during entry inserts,
* where comparisons must be strict.
* @param cmp comparison result
* @param neg negative flag
* @param pos positive flag
* @return encoded insert location value
*/
public static int getInsertLocationValue(final int cmp, final int neg, final int pos) {
return cmp <= 0 ?
neg :
pos;
}
/** Get the maximum distance value from {@code n} to either {@code a} or {@code b}.
* @param n test coordinate
* @param a first coordinate
* @param b second coordinate
* @return maximum distance from {@code n} to {@code a} or {@code b}
*/
public static double getMaxDistance(final double n, final double a, final double b) {
return Math.max(
Math.abs(n - a),
Math.abs(n - b));
}
}
/** Set view of the map entries.
*/
private final class EntrySet
extends AbstractSet<Entry<P, V>> {
/** {@inheritDoc} */
@SuppressWarnings("unchecked")
@Override
public boolean contains(final Object obj) {
if (obj instanceof Entry) {
final Entry<?, ?> search = (Entry<?, ?>) obj;
final Object key = search.getKey();
final Entry<P, V> actual = findEntry(key);
if (actual != null) {
return pointsEq(actual.getKey(), (P) search.getKey()) &&
Objects.equals(actual.getValue(), search.getValue());
}
}
return false;
}
/** {@inheritDoc} */
@Override
public Iterator<Entry<P, V>> iterator() {
return new EntryIterator();
}
/** {@inheritDoc} */
@Override
public int size() {
return AbstractBucketPointMap.this.size();
}
}
/** Iterator for iterating through each entry in the map.
*/
private final class EntryIterator
implements Iterator<Entry<P, V>> {
/** Size of the owning map. */
private int size;
/** Iterator that produces the next entry to be returned. */
private Iterator<Entry<P, V>> nextEntryIterator;
/** Index of the entry that will be returned next from the iterator. */
private int nextIdx;
/** Expected map modification version. */
private int expectedVersion;
/** Simple constructor.
*/
EntryIterator() {
this.size = AbstractBucketPointMap.this.size();
updateExpectedVersion();
}
/** {@inheritDoc} */
@Override
public boolean hasNext() {
if (nextEntryIterator == null ||
!nextEntryIterator.hasNext()) {
nextEntryIterator = findIterator();
}
return nextEntryIterator != null;
}
/** {@inheritDoc} */
@Override
public Entry<P, V> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
checkVersion();
final Entry<P, V> result = nextEntryIterator.next();
++nextIdx;
return result;
}
/** {@inheritDoc} */
@Override
public void remove() {
if (nextEntryIterator == null) {
throw new IllegalStateException("Cannot remove: no entry has yet been returned");
}
nextEntryIterator.remove();
--nextIdx;
--size;
updateExpectedVersion();
}
/** Find the next entry iterator in the map.
* @return next map entry iterator
*/
private Iterator<Entry<P, V>> findIterator() {
int offset = 0;
if (secondaryRoot != null) {
final Iterator<Entry<P, V>> secondaryIt = findIteratorRecursive(secondaryRoot, offset);
if (secondaryIt != null) {
return secondaryIt;
}
offset += secondaryRoot.getEntryCount();
}
return findIteratorRecursive(root, offset);
}
/** Find the next map entry iterator recursively in the subtree rooted at {@code node}.
* @param node root of the subtree to obtain an iterator in
* @param offset index offset of the first entry in the subtree
* @return the next map entry iterator or null if no leaf nodes in the subtree contain the
* entry at {@code nextIdx}
*/
private Iterator<Entry<P, V>> findIteratorRecursive(final BucketNode<P, V> node, final int offset) {
if (nextIdx >= offset && nextIdx < offset + node.getEntryCount()) {
if (node.isLeaf()) {
return node.iterator(nextIdx - offset);
} else {
return findIteratorInNodeChildren(node, offset);
}
}
return null;
}
/** Find the next map entry iterator in the children of {@code node}.
* @param node root of the subtree to obtain an iterator in
* @param offset index offset of the first entry in the subtree
* @return the next map entry iterator or null if no leaf nodes in the subtree contain the
* entry at {@code nextIdx}
*/
private Iterator<Entry<P, V>> findIteratorInNodeChildren(final BucketNode<P, V> node, final int offset) {
final int childCount = node.children.size();
int currentOffset = offset;
for (int i = 0; i < childCount; ++i) {
final BucketNode<P, V> child = node.children.get(i);
if (child != null) {
Iterator<Entry<P, V>> childIt = findIteratorRecursive(child, currentOffset);
if (childIt != null) {
return childIt;
}
currentOffset += child.getEntryCount();
}
}
return null;
}
/** Throw a {@link ConcurrentModificationException} if the map version does
* not match the expected version.
*/
private void checkVersion() {
if (expectedVersion != version) {
throw new ConcurrentModificationException();
}
}
/** Update the expected modification version of the map. This must be called
* whenever the map is changed through this instance.
*/
private void updateExpectedVersion() {
expectedVersion = version;
}
}
/** Abstract type representing a collection over the entries in this map.
*/
private abstract class AbstractEntryCollection extends AbstractCollection<Entry<P, V>> {
/** {@inheritDoc} */
@Override
public int size() {
return AbstractBucketPointMap.this.size();
}
}
/** Abstract base class for iterators that returned entries in order of distance relative
* to a reference point.
* @param <P> Point type
* @param <V> Value type
*/
private abstract static class AbstractDistanceOrderIterator<P extends Point<P>, V>
implements Iterator<Entry<P, V>> {
/** Owning map. */
private final AbstractBucketPointMap<P, V> map;
/** The expected modification version of the map. */
private final int expectedVersion;
/** Distance order reference point. */
private final P refPt;
/** Queue of nodes remaining to be visited. */
private final PriorityQueue<DistancedValue<BucketNode<P, V>>> nodes;
/** Queue of entries waiting to be returned. */
private final PriorityQueue<DistancedValue<Entry<P, V>>> entries;
/** The next entry to be returned from the iterator. */
private Entry<P, V> nextEntry;
/** Construct a new instance for ordering map entries by distance in reference
* to {@code refPt}.
* @param map owning map
* @param refPt reference point used to determine distance
* @param rootDistance distance value to use for the root nodes
* @param nodeComparator node comparator
* @param entryComparator entry comparator
*/
AbstractDistanceOrderIterator(
final AbstractBucketPointMap<P, V> map,
final P refPt,
final double rootDistance,
final Comparator<DistancedValue<BucketNode<P, V>>> nodeComparator,
final Comparator<DistancedValue<Entry<P, V>>> entryComparator) {
this.map = map;
this.expectedVersion = map.version;
this.refPt = refPt;
this.nodes = new PriorityQueue<>(nodeComparator);
this.entries = new PriorityQueue<>(entryComparator);
this.nodes.add(DistancedValue.of(map.root, rootDistance));
if (map.secondaryRoot != null) {
this.nodes.add(DistancedValue.of(map.secondaryRoot, rootDistance));
}
}
/** {@inheritDoc} */
@Override
public boolean hasNext() {
return nextEntry != null;
}
/** {@inheritDoc} */
@Override
public Entry<P, V> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
checkVersion();
final Entry<P, V> result = nextEntry;
queueNextEntry();
return result;
}
/** Queue the next entry to be returned from the iterator. This must be
* called after initialization to prepare the first return value.
*/
void queueNextEntry() {
while (requiresTreeTraversal()) {
final DistancedValue<BucketNode<P, V>> nodeEntry = nodes.remove();
final BucketNode<P, V> node = nodeEntry.getValue();
if (node.isLeaf()) {
// add the entries to the entries queue
queueLeafEntries(node);
} else {
// queue the child nodes
queueChildren(nodeEntry, refPt);
}
}
nextEntry = entries.isEmpty() ?
null :
entries.remove().getValue();
}
/** Return true if the given entry is ready to be returned based on the values in the
* next queue node.
* @param entry next entry in the queue
* @param nextNode next node in the queue
* @param precision precision context to use for floating point comparisons
* @return true if the given entry can be returned from the iterator
*/
abstract boolean canReturnEntry(
DistancedValue<Entry<P, V>> entry,
DistancedValue<BucketNode<P, V>> nextNode,
Precision.DoubleEquivalence precision);
/** Queue the child nodes of the argument.
* @param nodeEntry distance entry containing the parent node
* @param pt reference point
*/
abstract void queueChildren(DistancedValue<BucketNode<P, V>> nodeEntry, P pt);
/** Add a node and its computed distance to the queue.
* @param nodeEntry node entry to add
*/
void queue(final DistancedValue<BucketNode<P, V>> nodeEntry) {
nodes.add(nodeEntry);
}
/** Add all entries in the given leaf node to the entries queue.
* @param node leaf node
*/
private void queueLeafEntries(final BucketNode<P, V> node) {
for (final Entry<P, V> entry : node.entries) {
final double dist = entry.getKey().distance(refPt);
entries.add(DistancedValue.of(entry, dist));
}
}
/** Return true if the tree needs to be traversed more in order to determine the next
* entry to return.
* @return true if the tree needs to be traversed more to determine the next entry to
* return
*/
private boolean requiresTreeTraversal() {
return !nodes.isEmpty() &&
(entries.isEmpty() || !canReturnEntry(entries.peek(), nodes.peek(), map.precision));
}
/** Throw a {@link ConcurrentModificationException} if the map version does
* not match the expected version.
*/
private void checkVersion() {
if (expectedVersion != map.version) {
throw new ConcurrentModificationException();
}
}
}
/** Iterator that returns map entries in order of increasing distance from a specified point.
* @param <P> Point type
* @param <V> Value type
*/
private static final class NearToFarIterator<P extends Point<P>, V>
extends AbstractDistanceOrderIterator<P, V> {
/** Construct a new iterator instance for the given map and reference point.
* @param map owning map
* @param refPt reference point
*/
NearToFarIterator(final AbstractBucketPointMap<P, V> map, final P refPt) {
super(map,
refPt,
0d,
DistancedValue.ascendingDistance(),
(a, b) -> map.compareEntries(a, b, Double.POSITIVE_INFINITY));
queueNextEntry();
}
/** {@inheritDoc} */
@Override
protected boolean canReturnEntry(
final DistancedValue<Entry<P, V>> nextEntry,
final DistancedValue<BucketNode<P, V>> nextNode,
final Precision.DoubleEquivalence precision) {
return precision.lt(nextEntry.getDistance(), nextNode.getDistance());
}
/** {@inheritDoc} */
@Override
void queueChildren(final DistancedValue<BucketNode<P, V>> nodeEntry, final P refPt) {
final BucketNode<P, V> node = nodeEntry.getValue();
final int loc = node.getInsertLocation(refPt);
final int childCount = node.children.size();
for (int i = 0; i < childCount; ++i) {
final BucketNode<P, V> child = node.children.get(i);
if (child != null) {
final double childDist = node.getMinChildDistance(i, refPt, loc);
queue(DistancedValue.of(child, childDist));
}
}
}
}
/** Iterator that returns map entries in order of decreasing distance from a specified point.
* @param <P> Point type
* @param <V> Value type
*/
private static final class FarToNearIterator<P extends Point<P>, V>
extends AbstractDistanceOrderIterator<P, V> {
/** Construct a new iterator instance for the given map and reference point.
* @param map owning map
* @param refPt reference point
*/
FarToNearIterator(final AbstractBucketPointMap<P, V> map, final P refPt) {
super(map,
refPt,
Double.POSITIVE_INFINITY,
DistancedValue.descendingDistance(),
(a, b) -> -map.compareEntries(a, b, 0d));
queueNextEntry();
}
/** {@inheritDoc} */
@Override
protected boolean canReturnEntry(
final DistancedValue<Entry<P, V>> nextEntry,
final DistancedValue<BucketNode<P, V>> nextNode,
final Precision.DoubleEquivalence precision) {
return precision.gt(nextEntry.getDistance(), nextNode.getDistance());
}
/** {@inheritDoc} */
@Override
void queueChildren(final DistancedValue<BucketNode<P, V>> nodeEntry, final P refPt) {
final BucketNode<P, V> node = nodeEntry.getValue();
final double nodeDist = nodeEntry.getDistance();
final int loc = node.getInsertLocation(refPt);
final int childCount = node.children.size();
for (int i = 0; i < childCount; ++i) {
final BucketNode<P, V> child = node.children.get(i);
if (child != null) {
// use the minimum of distance from the parent and the child since the child
// cannot contain anything that is not also in the parent
final double childDist = Math.min(nodeDist, node.getMaxChildDistance(i, refPt, loc));
queue(DistancedValue.of(child, childDist));
}
}
}
}
}