You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ma...@apache.org on 2022/04/30 03:43:18 UTC
[commons-geometry] branch master updated: GEOMETRY-146: adding near/far methods to PointMap and PointSet
This is an automated email from the ASF dual-hosted git repository.
mattjuntunen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
The following commit(s) were added to refs/heads/master by this push:
new ffc9ff96 GEOMETRY-146: adding near/far methods to PointMap and PointSet
ffc9ff96 is described below
commit ffc9ff964654948aab93438dff8b8a2bbdab03d7
Author: Matt <ma...@apache.org>
AuthorDate: Sat Apr 23 07:36:22 2022 -0400
GEOMETRY-146: adding near/far methods to PointMap and PointSet
---
.../commons/geometry/core/collection/PointMap.java | 45 +-
.../commons/geometry/core/collection/PointSet.java | 45 +-
.../core/internal/AbstractBucketPointMap.java | 717 +++++++++++++++++++--
.../geometry/core/internal/AbstractPointMap1D.java | 112 +++-
.../geometry/core/internal/DistancedValue.java | 82 +++
.../core/internal/GeometryInternalUtils.java | 10 +-
.../core/internal/PointMapAsSetAdapter.java | 98 ++-
.../core/collection/PointCollectionTestBase.java | 62 ++
.../geometry/core/collection/PointMapTestBase.java | 448 +++++++++++++
.../geometry/core/collection/PointSetTestBase.java | 407 ++++++++++++
.../core/internal/AbstractBucketPointMapTest.java | 60 ++
.../core/internal/AbstractPointMap1DTest.java | 177 ++++-
.../core/internal/PointMapAsSetAdapterTest.java | 6 +
.../core/internal/TestBucketPointMap1D.java | 35 +-
.../core/partitioning/test/TestPoint1D.java | 17 +
.../commons/geometry/euclidean/PointMap1DImpl.java | 195 +++++-
.../commons/geometry/euclidean/PointMap2DImpl.java | 66 +-
.../commons/geometry/euclidean/PointMap3DImpl.java | 82 ++-
.../geometry/euclidean/oned/PointMap1DTest.java | 67 ++
.../geometry/euclidean/oned/PointSet1DTest.java | 6 +
.../geometry/euclidean/threed/PointMap3DTest.java | 76 +++
.../geometry/euclidean/threed/PointSet3DTest.java | 6 +
.../geometry/euclidean/twod/PointMap2DTest.java | 72 +++
.../geometry/euclidean/twod/PointSet2DTest.java | 6 +
.../jmh/euclidean/PointMap3DPerformance.java | 341 ++++++++--
.../commons/geometry/spherical/PointMap1SImpl.java | 172 ++++-
.../commons/geometry/spherical/PointMap2SImpl.java | 108 +++-
.../geometry/spherical/oned/PointMap1STest.java | 6 +
.../geometry/spherical/oned/PointSet1STest.java | 6 +
.../geometry/spherical/twod/PointMap2STest.java | 6 +
.../geometry/spherical/twod/PointSet2STest.java | 6 +
31 files changed, 3351 insertions(+), 191 deletions(-)
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/collection/PointMap.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/collection/PointMap.java
index d8b16abf..9973f3f5 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/collection/PointMap.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/collection/PointMap.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.geometry.core.collection;
+import java.util.Collection;
import java.util.Map;
import org.apache.commons.geometry.core.Point;
@@ -24,6 +25,14 @@ import org.apache.commons.geometry.core.Point;
* use in cases where effectively equivalent (but not necessarily equal) points must
* map to the same entry. As such, this interface breaks the strict contract for
* {@link Map} where key equality is consistent with {@link Object#equals(Object)}.
+ *
+ * <p><strong>Distance Ordering</strong></p>
+ * <p>For methods such as {@link #nearestEntry(Point)} and {@link #entriesNearToFar(Point)}
+ * that order entries by distance, implementations are free to choose the criteria used to
+ * break ties in distance. For example, if entries {@code A} and {@code B} have keys at equal
+ * distances from point {@code P}, implementations may choose to return either {@code A} or
+ * {@code B} for {@code map.nearestEntry(P)}.
+ * </p>
* @param <P> Point type
* @param <V> Value type
*/
@@ -31,11 +40,43 @@ public interface PointMap<P extends Point<P>, V> extends Map<P, V> {
/** Get the map entry with a key equivalent to {@code pt} or {@code null}
* if no such entry exists. The returned instance supports use of
- * the {@link Map.Entry#setValue(Object)} method to modify the
+ * the {@link Entry#setValue(Object)} method to modify the
* mapping.
* @param pt point to fetch the map entry for
* @return map entry for the given point or null if no such entry
* exists
*/
- Map.Entry<P, V> getEntry(P pt);
+ Entry<P, V> getEntry(P pt);
+
+ /** Get the entry from the map with the key nearest to {@code pt} or
+ * {@code null} if the map is empty.
+ * @param pt reference point
+ * @return entry from the map with the key nearest to {@code pt} or
+ * {@code null} if the map is entry
+ */
+ Entry<P, V> nearestEntry(P pt);
+
+ /** Get the entry from the map with the key farthest from {@code pt} or
+ * {@code null} if the map is empty.
+ * @param pt reference point
+ * @return entry from the map with the key farthest to {@code pt} or
+ * {@code null} if the map is entry
+ */
+ Entry<P, V> farthestEntry(P pt);
+
+ /** Get a collection containing the map entries in order of increasing
+ * distance from {@code pt}.
+ * @param pt reference point
+ * @return collection containing the map entries in order of increasing
+ * distance from {@code pt}
+ */
+ Collection<Entry<P, V>> entriesNearToFar(P pt);
+
+ /** Get a collection containing the map entries in order of decreasing
+ * distance from {@code pt}.
+ * @param pt reference point
+ * @return collection containing the map entries in order of decreasing
+ * distance from {@code pt}
+ */
+ Collection<Entry<P, V>> entriesFarToNear(P pt);
}
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/collection/PointSet.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/collection/PointSet.java
index 539f6357..ac30d76a 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/collection/PointSet.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/collection/PointSet.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.geometry.core.collection;
+import java.util.Collection;
import java.util.Set;
import org.apache.commons.geometry.core.Point;
@@ -24,15 +25,55 @@ import org.apache.commons.geometry.core.Point;
* use in cases where effectively equivalent (but not necessarily equal) points must
* be considered as equal by the set. As such, this interface breaks the strict contract
* for {@link Set} where membership is consistent with {@link Object#equals(Object)}.
+ *
+ * <p><strong>Distance Ordering</strong></p>
+ * <p>For methods such as {@link #nearest(Point)} and {@link #nearToFar(Point)}
+ * that order elements by distance, implementations are free to choose the criteria used to
+ * break ties in distance. For example, if points {@code A} and {@code B} are at equal distances
+ * from {@code P}, implementations may choose to return either {@code A} or {@code B} for
+ * {@code map.nearest(P)}.
+ * </p>
* @param <P> Point type
*/
public interface PointSet<P extends Point<P>> extends Set<P> {
- /** Get the set entry equivalent to {@code pt} or null if no
- * such entry exists.
+ /** Get the element equivalent to {@code pt} or null if no
+ * such an element exists.
* @param pt point to find an equivalent for
* @return set entry equivalent to {@code pt} or null if
* no such entry exists
*/
P get(P pt);
+
+ /** Get the element from the set nearest to {@code pt} or {@code null}
+ * if the set is empty.
+ * @param pt reference point
+ * @return the element from the set nearest to {@code pt} or {@code null}
+ * if the set is empty
+ */
+ P nearest(P pt);
+
+ /** Get the element from the set farthest to {@code pt} or {@code null}
+ * if the set is empty.
+ * @param pt reference point
+ * @return the element from the set farthest to {@code pt} or {@code null}
+ * if the set is empty
+ */
+ P farthest(P pt);
+
+ /** Get a collection containing the set elements in order of increasing
+ * distance from {@code pt}.
+ * @param pt reference point
+ * @return collection containing the set elements in order of increasing
+ * distance from {@code pt}
+ */
+ Collection<P> nearToFar(P pt);
+
+ /** Get a collection containing the set elements in order of decreasing
+ * distance from {@code pt}.
+ * @param pt reference point
+ * @return collection containing the set elements in order of decreasing
+ * distance from {@code pt}
+ */
+ Collection<P> farToNear(P pt);
}
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/AbstractBucketPointMap.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/AbstractBucketPointMap.java
index cbb19b4b..3e0d5ec6 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/AbstractBucketPointMap.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/AbstractBucketPointMap.java
@@ -16,18 +16,21 @@
*/
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.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
+import java.util.PriorityQueue;
import java.util.Set;
-import java.util.function.BiFunction;
import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.collection.PointMap;
@@ -62,8 +65,28 @@ 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 BiFunction<AbstractBucketPointMap<P, V>, BucketNode<P, V>, BucketNode<P, V>> nodeFactory;
+ private final BucketNodeFactory<P, V> nodeFactory;
/** Maximum number of entries stored per node before the node is split. */
private final int maxNodeEntryCount;
@@ -80,6 +103,9 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
/** Secondary tree root. */
private BucketNode<P, V> secondaryRoot;
+ /** Cached entry set instance. */
+ private EntrySet entrySetInstance;
+
/** Version counter, used to track tree modifications. */
private int version;
@@ -91,7 +117,7 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
* @param precision precision object used for floating point comparisons
*/
protected AbstractBucketPointMap(
- final BiFunction<AbstractBucketPointMap<P, V>, BucketNode<P, V>, BucketNode<P, V>> nodeFactory,
+ final BucketNodeFactory<P, V> nodeFactory,
final int maxNodeEntryCount,
final int nodeChildCount,
final Precision.DoubleEquivalence precision) {
@@ -99,12 +125,12 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
this.maxNodeEntryCount = maxNodeEntryCount;
this.nodeChildCount = nodeChildCount;
this.precision = precision;
- this.root = nodeFactory.apply(this, null);
+ this.root = nodeFactory.createNode(this, null, DEFAULT_CHILD_INDEX);
}
/** {@inheritDoc} */
@Override
- public Map.Entry<P, V> getEntry(final P pt) {
+ public Entry<P, V> getEntry(final P pt) {
return findEntryByPoint(pt);
}
@@ -118,9 +144,9 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
/** {@inheritDoc} */
@Override
public V put(final P key, final V value) {
- GeometryInternalUtils.validatePointMapKey(key);
+ GeometryInternalUtils.requireFinite(key);
- Entry<P, V> entry = findEntryByPoint(key);
+ final Entry<P, V> entry = findEntryByPoint(key);
if (entry != null) {
return entry.setValue(value);
}
@@ -165,16 +191,84 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
/** {@inheritDoc} */
@Override
public Set<Entry<P, V>> entrySet() {
- return new EntrySet<>(this);
+ if (entrySetInstance == null) {
+ entrySetInstance = new EntrySet();
+ }
+ return entrySetInstance;
}
/** {@inheritDoc} */
@Override
public void clear() {
- root = createNode(null);
+ 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
@@ -183,19 +277,21 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
*/
protected abstract boolean pointsEq(P a, P b);
- /** Get the configured precision for the instance.
- * @return precision object
+ /** 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 Precision.DoubleEquivalence getPrecision() {
- return precision;
- }
+ protected abstract int disambiguatePointComparison(P a, P b);
/** Construct a new node instance.
- * @param parent parent node; will be null or the tree root
+ * @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) {
- return nodeFactory.apply(this, parent);
+ 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.
@@ -205,11 +301,11 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
if (!root.isLeaf() && secondaryRoot == null) {
secondaryRoot = root;
- root = createNode(null);
+ root = createNode(null, DEFAULT_CHILD_INDEX);
}
migrateSecondaryEntry();
- checkSecondaryRoot();
+ checkRemoveSecondaryRoot();
}
/** Method called when an entry is removed from the tree.
@@ -217,7 +313,7 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
private void entryRemoved() {
++version;
- checkSecondaryRoot();
+ checkRemoveSecondaryRoot();
}
/** Create a list for storing map entries.
@@ -298,13 +394,72 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
/** Remove the secondary root if empty.
*/
- private void checkSecondaryRoot() {
+ 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
@@ -331,6 +486,9 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
/** Parent node. */
private BucketNode<P, V> parent;
+ /** Index of this node in its parent child list. */
+ private int childIndex;
+
/** Child nodes. */
private List<BucketNode<P, V>> children;
@@ -343,18 +501,38 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
/** 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 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 parent node or null if one does not exist.
+ * @return parent node or null if one does not exist.
+ */
+ public BucketNode<P, V> getParent() {
+ return parent;
+ }
+
+ /** 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
@@ -441,7 +619,7 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
* subtree. No check is made as to whether or not the entry already exists.
* @param entry entry to insert
*/
- public void insertEntry(final Map.Entry<P, V> entry) {
+ 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
@@ -508,6 +686,125 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
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;
+ } else {
+ // internal node; 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
@@ -567,6 +864,7 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
public void destroy() {
this.map = null;
this.parent = null;
+ this.childIndex = DEFAULT_CHILD_INDEX;
this.children = null;
this.entries = null;
this.entryCount = 0;
@@ -585,7 +883,7 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
* @return iterator for accessing the entries stored in this node
*/
@Override
- public Iterator<Map.Entry<P, V>> iterator() {
+ public Iterator<Entry<P, V>> iterator() {
return iterator(0);
}
@@ -596,14 +894,14 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
* @return iterator for accessing the entries stored in this node, starting with the entry at
* the given index
*/
- private Iterator<Map.Entry<P, V>> iterator(final int idx) {
- final List<Map.Entry<P, V>> iteratedList = idx == 0 ?
+ 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<Map.Entry<P, V>> it = iteratedList.iterator();
+ final Iterator<Entry<P, V>> it = iteratedList.iterator();
- return new Iterator<Map.Entry<P, V>>() {
+ return new Iterator<Entry<P, V>>() {
@Override
public boolean hasNext() {
@@ -651,7 +949,7 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
*/
protected abstract int getSearchLocation(P pt);
- /** Get an int encoding the insert location of {@code pt} relative to the
+ /** 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
@@ -667,6 +965,25 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
*/
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
*/
@@ -746,7 +1063,7 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
private BucketNode<P, V> getOrCreateChild(final int idx) {
BucketNode<P, V> child = children.get(idx);
if (child == null) {
- child = map.createNode(this);
+ child = map.createNode(this, idx);
children.set(idx, child);
}
return child;
@@ -835,36 +1152,36 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
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.
- * @param <P> Point type
- * @param <V> Value type
*/
- private static final class EntrySet<P extends Point<P>, V>
- extends AbstractSet<Map.Entry<P, V>> {
-
- /** Owning map. */
- private final AbstractBucketPointMap<P, V> map;
-
- /** Construct a new instance for the given map.
- * @param map map instance
- */
- EntrySet(final AbstractBucketPointMap<P, V> map) {
- this.map = map;
- }
+ private final class EntrySet
+ extends AbstractSet<Entry<P, V>> {
/** {@inheritDoc} */
@SuppressWarnings("unchecked")
@Override
public boolean contains(final Object obj) {
- if (obj instanceof Map.Entry) {
- final Map.Entry<?, ?> search = (Map.Entry<?, ?>) obj;
+ if (obj instanceof Entry) {
+ final Entry<?, ?> search = (Entry<?, ?>) obj;
final Object key = search.getKey();
- final Map.Entry<P, V> actual = map.findEntry(key);
+ final Entry<P, V> actual = findEntry(key);
if (actual != null) {
- return map.pointsEq(actual.getKey(), (P) search.getKey()) &&
+ return pointsEq(actual.getKey(), (P) search.getKey()) &&
Objects.equals(actual.getValue(), search.getValue());
}
}
@@ -874,31 +1191,26 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
/** {@inheritDoc} */
@Override
public Iterator<Entry<P, V>> iterator() {
- return new EntryIterator<>(map);
+ return new EntryIterator();
}
/** {@inheritDoc} */
@Override
public int size() {
- return map.size();
+ return AbstractBucketPointMap.this.size();
}
}
/** Iterator for iterating through each entry in the map.
- * @param <P> Point type
- * @param <V> Value type
*/
- private static final class EntryIterator<P extends Point<P>, V>
- implements Iterator<Map.Entry<P, V>> {
-
- /** Owning map. */
- private final AbstractBucketPointMap<P, V> 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<Map.Entry<P, V>> nextEntryIterator;
+ private Iterator<Entry<P, V>> nextEntryIterator;
/** Index of the entry that will be returned next from the iterator. */
private int nextIdx;
@@ -906,12 +1218,10 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
/** Expected map modification version. */
private int expectedVersion;
- /** Construct a new instance for the given map.
- * @param map map instance
+ /** Simple constructor.
*/
- EntryIterator(final AbstractBucketPointMap<P, V> map) {
- this.map = map;
- this.size = map.size();
+ EntryIterator() {
+ this.size = AbstractBucketPointMap.this.size();
updateExpectedVersion();
}
@@ -936,7 +1246,7 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
nextEntryIterator = findIterator();
}
- final Map.Entry<P, V> result = nextEntryIterator.next();
+ final Entry<P, V> result = nextEntryIterator.next();
++nextIdx;
return result;
@@ -961,16 +1271,16 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
*/
private Iterator<Entry<P, V>> findIterator() {
int offset = 0;
- if (map.secondaryRoot != null) {
- final Iterator<Entry<P, V>> secondaryIt = findIteratorRecursive(map.secondaryRoot, offset);
+ if (secondaryRoot != null) {
+ final Iterator<Entry<P, V>> secondaryIt = findIteratorRecursive(secondaryRoot, offset);
if (secondaryIt != null) {
return secondaryIt;
}
- offset += map.secondaryRoot.getEntryCount();
+ offset += secondaryRoot.getEntryCount();
}
- return findIteratorRecursive(map.root, offset);
+ return findIteratorRecursive(root, offset);
}
/** Find the next map entry iterator recursively in the subtree rooted at {@code node}.
@@ -1019,7 +1329,7 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
* not match the expected version.
*/
private void checkVersion() {
- if (map.version != expectedVersion) {
+ if (expectedVersion != version) {
throw new ConcurrentModificationException();
}
}
@@ -1028,7 +1338,272 @@ public abstract class AbstractBucketPointMap<P extends Point<P>, V>
* whenever the map is changed through this instance.
*/
private void updateExpectedVersion() {
- expectedVersion = map.version;
+ 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(b, a, 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));
+ }
+ }
}
}
}
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/AbstractPointMap1D.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/AbstractPointMap1D.java
index 8270c204..4aa31b9f 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/AbstractPointMap1D.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/AbstractPointMap1D.java
@@ -16,15 +16,18 @@
*/
package org.apache.commons.geometry.core.internal;
+import java.util.AbstractCollection;
import java.util.AbstractMap.SimpleEntry;
import java.util.Collection;
-import java.util.Comparator;
+import java.util.Iterator;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;
+import java.util.function.ToDoubleFunction;
import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.collection.PointMap;
+import org.apache.commons.numbers.core.Precision;
/** Abstract base class for 1D {@link PointMap} implementations. This class delegates
* entry storage to an internal {@link TreeMap} instance. Simple methods, such as
@@ -36,15 +39,23 @@ import org.apache.commons.geometry.core.collection.PointMap;
public abstract class AbstractPointMap1D<P extends Point<P>, V>
implements PointMap<P, V> {
+ /** Precision context. */
+ private final Precision.DoubleEquivalence precision;
+
/** Underlying map. */
private final NavigableMap<P, V> map;
- /** Construct a new instance that uses the given comparator in the
- * underlying {@link TreeMap}.
- * @param cmp tree map comparator
+ /** Construct a new instance that uses the given precision and coordinate accessor
+ * function to sort elements.
+ * @param precision precision object used for floating point comparisons
+ * @param coordinateFn function used to obtain coordinate values from point instance
*/
- protected AbstractPointMap1D(final Comparator<P> cmp) {
- this.map = new TreeMap<>(cmp);
+ protected AbstractPointMap1D(
+ final Precision.DoubleEquivalence precision,
+ final ToDoubleFunction<P> coordinateFn) {
+ this.precision = precision;
+ this.map = new TreeMap<>(
+ (a, b) -> precision.compare(coordinateFn.applyAsDouble(a), coordinateFn.applyAsDouble(b)));
}
/** {@inheritDoc} */
@@ -65,24 +76,23 @@ public abstract class AbstractPointMap1D<P extends Point<P>, V>
return map.containsValue(value);
}
-
/** {@inheritDoc} */
@Override
- public Map.Entry<P, V> getEntry(final P key) {
+ public Entry<P, V> getEntry(final P key) {
return exportEntry(getEntryInternal(key));
}
/** {@inheritDoc} */
@Override
public V put(final P key, final V value) {
- GeometryInternalUtils.validatePointMapKey(key);
+ GeometryInternalUtils.requireFinite(key);
return putInternal(key, value);
}
/** {@inheritDoc} */
@Override
public void putAll(final Map<? extends P, ? extends V> m) {
- for (final Map.Entry<? extends P, ? extends V> entry : m.entrySet()) {
+ for (final Entry<? extends P, ? extends V> entry : m.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
@@ -93,6 +103,54 @@ public abstract class AbstractPointMap1D<P extends Point<P>, V>
return map.values();
}
+ /** {@inheritDoc} */
+ @Override
+ public Entry<P, V> nearestEntry(final P pt) {
+ GeometryInternalUtils.requireFinite(pt);
+
+ final Iterator<Entry<P, V>> it = nearToFarIterator(pt);
+ return it.hasNext() ?
+ it.next() :
+ null;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Entry<P, V> farthestEntry(final P pt) {
+ GeometryInternalUtils.requireFinite(pt);
+
+ final Iterator<Entry<P, V>> it = farToNearIterator(pt);
+ return it.hasNext() ?
+ it.next() :
+ 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 nearToFarIterator(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 farToNearIterator(pt);
+ }
+ };
+ }
+
/** {@inheritDoc} */
@Override
public int hashCode() {
@@ -144,6 +202,29 @@ public abstract class AbstractPointMap1D<P extends Point<P>, V>
null;
}
+ /** Get the configured precision for the instance.
+ * @return precision object
+ */
+ protected Precision.DoubleEquivalence getPrecision() {
+ return precision;
+ }
+
+ /** Get an iterator for accessing map entries in order of nearest to farthest
+ * from {@code pt}.
+ * @param pt reference point
+ * @return iterator for accessing map entries in order of nearest to farthest
+ * f from {@code pt}.
+ */
+ protected abstract Iterator<Entry<P, V>> nearToFarIterator(P pt);
+
+ /** Get an iterator for accessing map entries in order of farthest to nearest
+ * from {@code pt}.
+ * @param pt reference point
+ * @return iterator for accessing map entries in order of farthest to nearest
+ * f from {@code pt}.
+ */
+ protected abstract Iterator<Entry<P, V>> farToNearIterator(P pt);
+
/** {@link Map.Entry} subclass that adds support for the {@link Map.Entry#setValue(Object)}.
*/
private final class MutableEntryWrapper extends SimpleEntry<P, V> {
@@ -168,4 +249,15 @@ public abstract class AbstractPointMap1D<P extends Point<P>, V>
return super.setValue(value);
}
}
+
+ /** 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 AbstractPointMap1D.this.size();
+ }
+ }
}
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/DistancedValue.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/DistancedValue.java
new file mode 100644
index 00000000..076fb025
--- /dev/null
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/DistancedValue.java
@@ -0,0 +1,82 @@
+/*
+ * 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.Comparator;
+
+/** Class combining a value with a distance.
+ * @param <V> Value type
+ */
+public final class DistancedValue<V> {
+
+ /** Value object. */
+ private final V value;
+
+ /** Distance value. */
+ private final double distance;
+
+ /** Simple constructor.
+ * @param value value
+ * @param distance distance
+ */
+ private DistancedValue(final V value, final double distance) {
+ this.value = value;
+ this.distance = distance;
+ }
+
+ /** Get the value.
+ * @return the value
+ */
+ public V getValue() {
+ return value;
+ }
+
+ /** Get the distance.
+ * @return the distance
+ */
+ public double getDistance() {
+ return distance;
+ }
+
+ /** Construct a new instance.
+ * @param <V> Value type
+ * @param value value
+ * @param distance distance
+ * @return new instance
+ */
+ public static <V> DistancedValue<V> of(final V value, final double distance) {
+ return new DistancedValue<>(value, distance);
+ }
+
+ /** Return a {@link Comparator} that orders {@link DistancedValue} instances in
+ * ascending distance order.
+ * @param <V> Value type
+ * @return comparator that places instances in ascending distance order
+ */
+ public static <V> Comparator<DistancedValue<V>> ascendingDistance() {
+ return (a, b) -> Double.compare(a.distance, b.distance);
+ }
+
+ /** Return a {@link Comparator} that orders {@link DistancedValue} instances in
+ * descending distance order.
+ * @param <V> Value type
+ * @return comparator that places instances in descending distance order
+ */
+ public static <V> Comparator<DistancedValue<V>> descendingDistance() {
+ return (a, b) -> Double.compare(b.distance, a.distance);
+ }
+}
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/GeometryInternalUtils.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/GeometryInternalUtils.java
index 2856fb9c..bb600c30 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/GeometryInternalUtils.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/GeometryInternalUtils.java
@@ -39,17 +39,19 @@ public final class GeometryInternalUtils {
return a == b;
}
- /** Throw an exception if the given point cannot be used as a key in a
- * {@link org.apache.commons.geometry.core.collection.PointMap PointMap}.
+ /** Throw an exception if the given point is not finite.
* @param <P> Point type
* @param pt point to check
+ * @return point given as the argument
* @throws NullPointerException if the point is null
* @throws IllegalArgumentException if the point is not finite
*/
- public static <P extends Point<P>> void validatePointMapKey(final P pt) {
+ public static <P extends Point<P>> P requireFinite(final P pt) {
Objects.requireNonNull(pt);
if (!pt.isFinite()) {
- throw new IllegalArgumentException("Non-finite map key: " + pt);
+ throw new IllegalArgumentException("Non-finite point: " + pt);
}
+
+ return pt;
}
}
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/PointMapAsSetAdapter.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/PointMapAsSetAdapter.java
index a841645a..ee5da342 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/PointMapAsSetAdapter.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/PointMapAsSetAdapter.java
@@ -16,9 +16,11 @@
*/
package org.apache.commons.geometry.core.internal;
+import java.util.AbstractCollection;
import java.util.AbstractSet;
+import java.util.Collection;
import java.util.Iterator;
-import java.util.Map;
+import java.util.Map.Entry;
import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.collection.PointMap;
@@ -51,10 +53,7 @@ public class PointMapAsSetAdapter<P extends Point<P>, M extends PointMap<P, Obje
/** {@inheritDoc} */
@Override
public P get(final P pt) {
- final Map.Entry<P, Object> entry = map.getEntry(pt);
- return entry != null ?
- entry.getKey() :
- null;
+ return getKey(map.getEntry(pt));
}
/** {@inheritDoc} */
@@ -93,4 +92,93 @@ public class PointMapAsSetAdapter<P extends Point<P>, M extends PointMap<P, Obje
public void clear() {
map.clear();
}
+
+ /** {@inheritDoc} */
+ @Override
+ public P nearest(final P pt) {
+ return getKey(map.nearestEntry(pt));
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public P farthest(final P pt) {
+ return getKey(map.farthestEntry(pt));
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Collection<P> nearToFar(final P pt) {
+ GeometryInternalUtils.requireFinite(pt);
+
+ return new AbstractElementCollection() {
+ @Override
+ public Iterator<P> iterator() {
+ return new EntryIteratorWrapper<P>(map.entriesNearToFar(pt).iterator());
+ }
+ };
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Collection<P> farToNear(final P pt) {
+ GeometryInternalUtils.requireFinite(pt);
+
+ return new AbstractElementCollection() {
+ @Override
+ public Iterator<P> iterator() {
+ return new EntryIteratorWrapper<P>(map.entriesFarToNear(pt).iterator());
+ }
+ };
+ }
+
+ /** Get the entry key or {@code null} if {@code entry} is {@code null}.
+ * @param <P> Point type
+ * @param entry map entry
+ * @return entry key or {@code null} if {@code entry} is {@code null}
+ */
+ private static <P extends Point<P>> P getKey(final Entry<P, ?> entry) {
+ return entry != null ?
+ entry.getKey() :
+ null;
+ }
+
+ /** Abstract type representing a collection over the elements in the set.
+ */
+ private abstract class AbstractElementCollection extends AbstractCollection<P> {
+
+ /** {@inheritDoc} */
+ @Override
+ public int size() {
+ return map.size();
+ }
+ }
+
+ /** Iterator that converts from a map entry iterator to a key iteration.
+ * @param <P> Point type
+ */
+ private static final class EntryIteratorWrapper<P extends Point<P>>
+ implements Iterator<P> {
+
+ /** Underlying entry iterator. */
+ private final Iterator<Entry<P, Object>> entryIterator;
+
+ /** Construct a new instance wrapping the given entry iterator.
+ * @param entryIterator map entry iterator
+ */
+ EntryIteratorWrapper(final Iterator<Entry<P, Object>> entryIterator) {
+ this.entryIterator = entryIterator;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean hasNext() {
+ return entryIterator.hasNext();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public P next() {
+ return entryIterator.next().getKey();
+ }
+ }
}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointCollectionTestBase.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointCollectionTestBase.java
index c7071e47..ea8da3c5 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointCollectionTestBase.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointCollectionTestBase.java
@@ -20,7 +20,9 @@ import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.ArrayList;
+import java.util.Collection;
import java.util.Collections;
+import java.util.Comparator;
import java.util.List;
import java.util.Random;
@@ -92,6 +94,13 @@ public abstract class PointCollectionTestBase<P extends Point<P>> {
*/
protected abstract boolean eq(P a, P b, Precision.DoubleEquivalence precision);
+ /** Compare two points with equal distances computed during a "closest first" ordering.
+ * @param a first point
+ * @param b second point
+ * @return comparison of the two points
+ */
+ protected abstract int disambiguateNearToFarOrder(P a, P b);
+
/** Assert that {@code a} and {@code b} are equivalent using the given precision context.
* @param a first point
* @param b second point
@@ -109,4 +118,57 @@ public abstract class PointCollectionTestBase<P extends Point<P>> {
protected void assertNotEq(final P a, final P b, final Precision.DoubleEquivalence precision) {
assertFalse(eq(a, b, precision), () -> "Expected " + a + " and " + b + " to not be equivalent");
}
+
+ /** Create a comparator for use in testing "near to far" ordering.
+ * @param refPt reference point
+ * @return comparator for use in testing "near to far" ordering
+ */
+ protected Comparator<P> createNearToFarComparator(final P refPt) {
+ final Comparator<P> cmp = (a, b) -> Double.compare(a.distance(refPt), b.distance(refPt));
+ return cmp.thenComparing(this::disambiguateNearToFarOrder);
+ }
+
+ /** Create a comparator for use in testing "far to near" ordering.
+ * @param refPt reference point
+ * @return comparator for use in testing "far to near" ordering
+ */
+ protected Comparator<P> createFarToNearComparator(final P refPt) {
+ return createNearToFarComparator(refPt).reversed();
+ }
+
+ /** Find the element in {@code list} farthest away from {@code refPt}.
+ * @param refPt reference point
+ * @param list list to search
+ * @return element in {@code list} farthest from {@code refPt}
+ */
+ protected P findFarthest(final P refPt, final List<P> list) {
+ final Comparator<P> cmp = createFarToNearComparator(refPt);
+
+ P result = null;
+ for (final P pt : list) {
+ if (result == null || cmp.compare(pt, result) < 0) {
+ result = pt;
+ }
+ }
+
+ return result;
+ }
+
+ /** Return the maximum distance from {@code refPt} to the points in {@code pts}.
+ * @param <P> Point type
+ * @param refPt reference point
+ * @param pts test points
+ * @return maximum distance from {@code refPt} to the points in {@code pts}
+ */
+ protected double findMaxDistance(final P refPt, final Collection<P> pts) {
+ double maxDist = 0d;
+ for (final P pt : pts) {
+ final double dist = pt.distance(refPt);
+ if (maxDist > dist) {
+ maxDist = dist;
+ }
+ }
+
+ return maxDist;
+ }
}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointMapTestBase.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointMapTestBase.java
index 4cb74779..c7398e58 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointMapTestBase.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointMapTestBase.java
@@ -21,11 +21,13 @@ 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.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
+import java.util.Map.Entry;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;
@@ -607,6 +609,394 @@ public abstract class PointMapTestBase<P extends Point<P>>
checker.check();
}
+ @Test
+ void testNearestEntry_empty() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final P pt = getTestPoints(1, EPS).get(0);
+
+ // act/assert
+ Assertions.assertNull(map.nearestEntry(pt));
+ }
+
+ @Test
+ void testNearestEntry_small() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final double keySpacing = 7 * EPS;
+ final double testPointSpacing = 3 * EPS;
+
+ int maxCnt = 5;
+ for (int cnt = 1; cnt <= maxCnt; ++cnt) {
+ final List<P> pts = getTestPoints(cnt, keySpacing, new Random(cnt));
+
+ map.clear();
+ insertPoints(pts, map);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ final P pt = pts.get(i);
+
+ for (final P refPt : getTestPointsAtDistance(pt, testPointSpacing)) {
+ Assertions.assertNull(map.get(refPt));
+
+ final Map.Entry<P, Integer> closest = map.nearestEntry(refPt);
+
+ Assertions.assertEquals(pt, closest.getKey());
+ Assertions.assertEquals(i, closest.getValue());
+ }
+ }
+ }
+ }
+
+ @Test
+ void testNearestEntry_large() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final double keySpacing = 7 * EPS;
+ final double testPointSpacing = 3 * EPS;
+
+ final int cnt = 1000;
+ final List<P> pts = getTestPoints(cnt, keySpacing, new Random(5L));
+ insertPoints(pts, map);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ final P pt = pts.get(i);
+
+ for (final P refPt : getTestPointsAtDistance(pt, testPointSpacing)) {
+ Assertions.assertNull(map.get(refPt));
+
+ final Map.Entry<P, Integer> nearest = map.nearestEntry(refPt);
+
+ Assertions.assertEquals(pt, nearest.getKey());
+ Assertions.assertEquals(i, nearest.getValue());
+ }
+ }
+ }
+
+ @Test
+ void testNearestEntry_invalidArgs() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final P infPt = getInfPoints().get(0);
+
+ // act/assert
+ Assertions.assertThrows(NullPointerException.class, () -> map.nearestEntry(null));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> map.nearestEntry(infPt));
+ }
+
+ @Test
+ void testFarthestEntry_empty() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final P pt = getTestPoints(1, EPS).get(0);
+
+ // act/assert
+ Assertions.assertNull(map.farthestEntry(pt));
+ }
+
+ @Test
+ void testFarthestEntry_small() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final double keySpacing = 7 * EPS;
+ final double testPointSpacing = 3 * EPS;
+
+ int maxCnt = 5;
+ for (int cnt = 1; cnt <= maxCnt; ++cnt) {
+ final List<P> pts = getTestPoints(cnt, keySpacing, new Random(cnt));
+
+ map.clear();
+ insertPoints(pts, map);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ final P pt = pts.get(i);
+
+ for (final P refPt : getTestPointsAtDistance(pt, testPointSpacing)) {
+ Assertions.assertNull(map.get(refPt));
+
+ final Map.Entry<P, Integer> farthest = map.farthestEntry(refPt);
+
+ Assertions.assertEquals(findFarthest(refPt, pts), farthest.getKey());
+ }
+ }
+ }
+ }
+
+ @Test
+ void testFarthestEntry_large() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final double keySpacing = 7 * EPS;
+ final double testPointSpacing = 3 * EPS;
+
+ final int cnt = 1000;
+ final List<P> pts = getTestPoints(cnt, keySpacing, new Random(5L));
+ insertPoints(pts, map);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ final P pt = pts.get(i);
+
+ for (final P refPt : getTestPointsAtDistance(pt, testPointSpacing)) {
+ Assertions.assertNull(map.get(refPt));
+
+ final Map.Entry<P, Integer> farthest = map.farthestEntry(refPt);
+
+ Assertions.assertEquals(findFarthest(refPt, pts), farthest.getKey());
+ }
+ }
+ }
+
+ @Test
+ void testFarthestEntry_invalidArgs() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final P infPt = getInfPoints().get(0);
+
+ // act/assert
+ Assertions.assertThrows(NullPointerException.class, () -> map.farthestEntry(null));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> map.farthestEntry(infPt));
+ }
+
+ @Test
+ void testEntriesNearToFar_empty() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final P pt = getTestPoints(1, EPS).get(0);
+ final List<P> ordered = new ArrayList<>();
+
+ // act
+ final Collection<Entry<P, Integer>> coll = map.entriesNearToFar(pt);
+
+ // assert
+ Assertions.assertEquals(0, coll.size());
+
+ for (final Map.Entry<P, Integer> entry : coll) {
+ ordered.add(entry.getKey());
+ }
+ Assertions.assertEquals(0, ordered.size());
+ }
+
+ @Test
+ void testEntriesNearToFar_small() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ int maxCnt = 5;
+ for (int cnt = 1; cnt <= maxCnt; ++cnt) {
+ final List<P> pts = getTestPoints(cnt, EPS, new Random(cnt));
+
+ map.clear();
+ insertPoints(pts, map);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ for (final P refPt : getTestPointsAtDistance(pts.get(i), 2.1 * EPS)) {
+ assertCollectionOrder(
+ pts,
+ createNearToFarComparator(refPt),
+ map.entriesNearToFar(refPt));
+ }
+ }
+ }
+ }
+
+ @Test
+ void testEntriesNearToFar_large() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ int cnt = 1000;
+ final List<P> pts = getTestPoints(cnt, EPS, new Random(6L));
+ insertPoints(pts, map);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ for (final P refPt : getTestPointsAtDistance(pts.get(i), 2.1 * EPS)) {
+ assertCollectionOrder(
+ pts,
+ createNearToFarComparator(refPt),
+ map.entriesNearToFar(refPt));
+ }
+ }
+ }
+
+ @Test
+ void testEntriesNearToFar_iteratorBehavior() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final List<P> pts = getTestPoints(2, EPS);
+ insertPoints(pts, map);
+
+ // act/assert
+ final Iterator<Map.Entry<P, Integer>> it = map.entriesNearToFar(pts.get(0)).iterator();
+ Assertions.assertTrue(it.hasNext());
+ Assertions.assertEquals(new SimpleEntry<>(pts.get(0), 0), it.next());
+ Assertions.assertThrows(UnsupportedOperationException.class, () -> it.remove());
+
+ Assertions.assertTrue(it.hasNext());
+ Assertions.assertEquals(new SimpleEntry<>(pts.get(1), 1), it.next());
+
+ Assertions.assertFalse(it.hasNext());
+
+ Assertions.assertThrows(NoSuchElementException.class, () -> it.next());
+ }
+
+ @Test
+ void testEntriesNearToFar_concurrentModification() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final List<P> pts = getTestPoints(2, EPS);
+ insertPoints(pts, map);
+
+ // act
+ final Iterator<Map.Entry<P, Integer>> it = map.entriesNearToFar(pts.get(0)).iterator();
+ map.remove(pts.get(0));
+
+ // assert
+ Assertions.assertThrows(ConcurrentModificationException.class, () -> it.next());
+ }
+
+ @Test
+ void testEntriesNearToFar_invalidArgs() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final P infPt = getInfPoints().get(0);
+
+ // act/assert
+ Assertions.assertThrows(NullPointerException.class, () -> map.entriesNearToFar(null));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> map.entriesNearToFar(infPt));
+ }
+
+ @Test
+ void testEntriesFarToNear_empty() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final P pt = getTestPoints(1, EPS).get(0);
+ final List<P> ordered = new ArrayList<>();
+
+ // act
+ final Collection<Entry<P, Integer>> coll = map.entriesFarToNear(pt);
+
+ // assert
+ Assertions.assertEquals(0, coll.size());
+
+ for (final Map.Entry<P, Integer> entry : coll) {
+ ordered.add(entry.getKey());
+ }
+ Assertions.assertEquals(0, ordered.size());
+ }
+
+ @Test
+ void testEntriesFarToNear_small() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ int maxCnt = 5;
+ for (int cnt = 1; cnt <= maxCnt; ++cnt) {
+ final List<P> pts = getTestPoints(cnt, EPS, new Random(cnt));
+
+ map.clear();
+ insertPoints(pts, map);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ for (final P refPt : getTestPointsAtDistance(pts.get(i), 2.1 * EPS)) {
+ assertCollectionOrder(
+ pts,
+ createFarToNearComparator(refPt),
+ map.entriesFarToNear(refPt));
+ }
+ }
+ }
+ }
+
+ @Test
+ void testEntriesFarToNear_large() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ int cnt = 1000;
+ final List<P> pts = getTestPoints(cnt, EPS, new Random(6L));
+ insertPoints(pts, map);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ for (final P refPt : getTestPointsAtDistance(pts.get(i), 2.1 * EPS)) {
+ assertCollectionOrder(
+ pts,
+ createFarToNearComparator(refPt),
+ map.entriesFarToNear(refPt));
+ }
+ }
+ }
+
+ @Test
+ void testEntriesFarToNear_iteratorBehavior() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final List<P> pts = getTestPoints(2, EPS);
+ insertPoints(pts, map);
+
+ // act/assert
+ final Iterator<Map.Entry<P, Integer>> it = map.entriesFarToNear(pts.get(0)).iterator();
+ Assertions.assertTrue(it.hasNext());
+ Assertions.assertEquals(new SimpleEntry<>(pts.get(1), 1), it.next());
+ Assertions.assertThrows(UnsupportedOperationException.class, () -> it.remove());
+
+ Assertions.assertTrue(it.hasNext());
+ Assertions.assertEquals(new SimpleEntry<>(pts.get(0), 0), it.next());
+
+ Assertions.assertFalse(it.hasNext());
+
+ Assertions.assertThrows(NoSuchElementException.class, () -> it.next());
+ }
+
+ @Test
+ void testEntriesFarToNear_concurrentModification() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final List<P> pts = getTestPoints(3, EPS);
+ insertPoints(pts, map);
+
+ // act
+ final Iterator<Map.Entry<P, Integer>> it = map.entriesFarToNear(pts.get(0)).iterator();
+ map.remove(pts.get(0));
+
+ // assert
+ Assertions.assertThrows(ConcurrentModificationException.class, () -> it.next());
+ }
+
+ @Test
+ void testEntriesFarToNear_invalidArgs() {
+ // arrange
+ final PointMap<P, Integer> map = getMap(PRECISION);
+
+ final P infPt = getInfPoints().get(0);
+
+ // act/assert
+ Assertions.assertThrows(NullPointerException.class, () -> map.entriesFarToNear(null));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> map.entriesFarToNear(infPt));
+ }
+
@Test
void testHashCode() {
// arrange
@@ -1360,6 +1750,12 @@ public abstract class PointMapTestBase<P extends Point<P>>
// Helpers -----------------------------------
+ protected <V> Comparator<Entry<P, V>> createNearToFarEntryComparator(final P refPt) {
+ final Comparator<Entry<P, V>> cmp =
+ (a, b) -> Double.compare(a.getKey().distance(refPt), b.getKey().distance(refPt));
+ return cmp.thenComparing((a, b) -> disambiguateNearToFarOrder(a.getKey(), b.getKey()));
+ }
+
private <V> void assertCollectionAddUnsupported(final Collection<V> coll, final V value) {
Assertions.assertThrows(UnsupportedOperationException.class, () -> coll.add(value));
@@ -1614,6 +2010,58 @@ public abstract class PointMapTestBase<P extends Point<P>>
Assertions.assertThrows(ConcurrentModificationException.class, () -> it.next());
}
+ /** Assert that {@code collection} returns entries with the same keys in the same order as
+ * {@code list} when sorted with {@code cmp}.
+ * @param <P> Point type
+ * @param <V> Value type
+ * @param list expected key list
+ * @param cmp comparator producing the expected order
+ * @param iterable iterable to test
+ */
+ public static <P extends Point<P>, V> void assertCollectionOrder(
+ final List<P> list,
+ final Comparator<P> cmp,
+ final Collection<Map.Entry<P, V>> collection) {
+
+ Assertions.assertEquals(list.size(), collection.size(), "Unexpected collection size");
+
+ final List<P> expected = new ArrayList<>(list);
+ Collections.sort(expected, cmp);
+
+ int i = -1;
+ for (final Map.Entry<P, V> actualEntry : collection) {
+ final P expectedKey = expected.get(++i);
+ final P actualKey = actualEntry.getKey();
+
+ Assertions.assertEquals(expectedKey, actualKey, "Unexpected point at index " + i);
+ }
+
+ Assertions.assertEquals(i, expected.size() - 1, "Unexpected iteration count");
+ }
+
+ /** Assert that {@code iterable} returns entries with the same keys in the same order as
+ * {@code list}.
+ * @param <P> Point type
+ * @param <V> Value type
+ * @param expected expected key list
+ * @param iterable iterable to test
+ */
+ public static <P extends Point<P>, V> void assertIterableOrder(
+ final List<P> expected,
+ final Iterable<Map.Entry<P, V>> iterable) {
+
+ int i = 0;
+ for (final Map.Entry<P, V> actualEntry : iterable) {
+ final P expectedKey = expected.get(i);
+ final P actualKey = actualEntry.getKey();
+
+ Assertions.assertEquals(expectedKey, actualKey, "Unexpected point at index " + i);
+ ++i;
+ }
+
+ Assertions.assertEquals(i, expected.size(), "Unexpected iteration count");
+ }
+
/** Insert the given list of points into {@code map}. The value of each key is the index of the key
* in {@code pts}.
* @param <P> Point type
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointSetTestBase.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointSetTestBase.java
index 54102fb6..20420674 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointSetTestBase.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/collection/PointSetTestBase.java
@@ -18,7 +18,10 @@ package org.apache.commons.geometry.core.collection;
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.HashSet;
import java.util.Iterator;
import java.util.List;
@@ -642,6 +645,383 @@ public abstract class PointSetTestBase<P extends Point<P>>
}
}
+ @Test
+ void testNearest_empty() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final P pt = getTestPoints(1, EPS).get(0);
+
+ // act/assert
+ Assertions.assertNull(set.nearest(pt));
+ }
+
+ @Test
+ void testNearest_small() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final double keySpacing = 7 * EPS;
+ final double testPointSpacing = 3 * EPS;
+
+ int maxCnt = 5;
+ for (int cnt = 1; cnt <= maxCnt; ++cnt) {
+ final List<P> pts = getTestPoints(cnt, keySpacing, new Random(cnt));
+
+ set.clear();
+ set.addAll(pts);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ final P pt = pts.get(i);
+
+ for (final P refPt : getTestPointsAtDistance(pt, testPointSpacing)) {
+ Assertions.assertNull(set.get(refPt));
+
+ final P nearest = set.nearest(refPt);
+
+ Assertions.assertEquals(pt, nearest);
+ }
+ }
+ }
+ }
+
+ @Test
+ void testNearest_large() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final double keySpacing = 7 * EPS;
+ final double testPointSpacing = 3 * EPS;
+
+ final int cnt = 1000;
+ final List<P> pts = getTestPoints(cnt, keySpacing, new Random(5L));
+ set.addAll(pts);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ final P pt = pts.get(i);
+
+ for (final P refPt : getTestPointsAtDistance(pt, testPointSpacing)) {
+ Assertions.assertNull(set.get(refPt));
+
+ final P nearest = set.nearest(refPt);
+
+ Assertions.assertEquals(pt, nearest);
+ }
+ }
+ }
+
+ @Test
+ void testNearest_invalidArgs() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+ final P infPt = getInfPoints().get(0);
+
+ // act/assert
+ Assertions.assertThrows(NullPointerException.class, () -> set.nearest(null));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> set.nearest(infPt));
+ }
+
+ @Test
+ void testFarthest_empty() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final P pt = getTestPoints(1, EPS).get(0);
+
+ // act/assert
+ Assertions.assertNull(set.farthest(pt));
+ }
+
+ @Test
+ void testFarthest_small() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final double keySpacing = 7 * EPS;
+ final double testPointSpacing = 3 * EPS;
+
+ int maxCnt = 5;
+ for (int cnt = 1; cnt <= maxCnt; ++cnt) {
+ final List<P> pts = getTestPoints(cnt, keySpacing, new Random(cnt));
+
+ set.clear();
+ set.addAll(pts);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ final P pt = pts.get(i);
+
+ for (final P refPt : getTestPointsAtDistance(pt, testPointSpacing)) {
+ Assertions.assertNull(set.get(refPt));
+
+ final P farthest = set.farthest(refPt);
+
+ Assertions.assertEquals(findFarthest(refPt, pts), farthest);
+ }
+ }
+ }
+ }
+
+ @Test
+ void testFarthest_large() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final double keySpacing = 7 * EPS;
+ final double testPointSpacing = 3 * EPS;
+
+ final int cnt = 1000;
+ final List<P> pts = getTestPoints(cnt, keySpacing, new Random(5L));
+ set.addAll(pts);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ final P pt = pts.get(i);
+
+ for (final P refPt : getTestPointsAtDistance(pt, testPointSpacing)) {
+ Assertions.assertNull(set.get(refPt));
+
+ final P farthest = set.farthest(refPt);
+
+ Assertions.assertEquals(findFarthest(refPt, pts), farthest);
+ }
+ }
+ }
+
+ @Test
+ void testFarthest_invalidArgs() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+ final P infPt = getInfPoints().get(0);
+
+ // act/assert
+ Assertions.assertThrows(NullPointerException.class, () -> set.farthest(null));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> set.farthest(infPt));
+ }
+
+ @Test
+ void testNearToFar_empty() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final P pt = getTestPoints(1, EPS).get(0);
+ final List<P> ordered = new ArrayList<>();
+
+ // act
+ for (final P nearest : set.nearToFar(pt)) {
+ ordered.add(nearest);
+ }
+
+ // assert
+ Assertions.assertEquals(0, ordered.size());
+ }
+
+ @Test
+ void testNearToFar_small() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final int maxCnt = 5;
+ for (int cnt = 1; cnt <= maxCnt; ++cnt) {
+ final List<P> pts = getTestPoints(cnt, EPS, new Random(cnt));
+
+ set.clear();
+ set.addAll(pts);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ for (final P refPt : getTestPointsAtDistance(pts.get(i), 2 * EPS)) {
+
+ assertCollectionOrder(
+ pts,
+ createNearToFarComparator(refPt),
+ set.nearToFar(refPt));
+ }
+ }
+ }
+ }
+
+ @Test
+ void testNearToFar_large() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ int cnt = 1000;
+ final List<P> pts = getTestPoints(cnt, EPS, new Random(5L));
+ set.addAll(pts);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ for (final P refPt : getTestPointsAtDistance(pts.get(i), 2 * EPS)) {
+ assertCollectionOrder(
+ pts,
+ createNearToFarComparator(refPt),
+ set.nearToFar(refPt));
+ }
+ }
+ }
+
+ @Test
+ void testNearToFar_iteratorBehavior() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final List<P> pts = getTestPoints(2, EPS);
+ set.addAll(pts);
+
+ // act/assert
+ final Iterator<P> it = set.nearToFar(pts.get(0)).iterator();
+ Assertions.assertTrue(it.hasNext());
+ Assertions.assertEquals(pts.get(0), it.next());
+ Assertions.assertThrows(UnsupportedOperationException.class, () -> it.remove());
+
+ Assertions.assertTrue(it.hasNext());
+ Assertions.assertEquals(pts.get(1), it.next());
+
+ Assertions.assertFalse(it.hasNext());
+
+ Assertions.assertThrows(NoSuchElementException.class, () -> it.next());
+ }
+
+ @Test
+ void testNearToFar_concurrentModification() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final List<P> pts = getTestPoints(2, EPS);
+ set.addAll(pts);
+
+ // act
+ final Iterator<P> it = set.nearToFar(pts.get(0)).iterator();
+ set.remove(pts.get(0));
+
+ // assert
+ Assertions.assertThrows(ConcurrentModificationException.class, () -> it.next());
+ }
+
+ @Test
+ void testNearToFar_invalidArgs() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+ final P infPt = getInfPoints().get(0);
+
+ // act/assert
+ Assertions.assertThrows(NullPointerException.class, () -> set.nearToFar(null));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> set.nearToFar(infPt));
+ }
+
+ @Test
+ void testFarToNear_empty() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final P pt = getTestPoints(1, EPS).get(0);
+ final List<P> ordered = new ArrayList<>();
+
+ // act
+ for (final P element : set.farToNear(pt)) {
+ ordered.add(element);
+ }
+
+ // assert
+ Assertions.assertEquals(0, ordered.size());
+ }
+
+ @Test
+ void testFarToNear_small() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ int maxCnt = 5;
+ for (int cnt = 1; cnt <= maxCnt; ++cnt) {
+ final List<P> pts = getTestPoints(cnt, EPS, new Random(cnt));
+
+ set.clear();
+ set.addAll(pts);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ for (final P refPt : getTestPointsAtDistance(pts.get(i), 2.1 * EPS)) {
+ assertCollectionOrder(
+ pts,
+ createFarToNearComparator(refPt),
+ set.farToNear(refPt));
+ }
+ }
+ }
+ }
+
+ @Test
+ void testFarToNear_large() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ int cnt = 1000;
+ final List<P> pts = getTestPoints(cnt, EPS, new Random(6L));
+ set.addAll(pts);
+
+ // act/ assert
+ for (int i = 0; i < cnt; ++i) {
+ for (final P refPt : getTestPointsAtDistance(pts.get(i), 2.1 * EPS)) {
+ assertCollectionOrder(
+ pts,
+ createFarToNearComparator(refPt),
+ set.farToNear(refPt));
+ }
+ }
+ }
+
+ @Test
+ void testFarToNear_iteratorBehavior() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final List<P> pts = getTestPoints(2, EPS);
+ set.addAll(pts);
+
+ // act/assert
+ final Iterator<P> it = set.farToNear(pts.get(0)).iterator();
+ Assertions.assertTrue(it.hasNext());
+ Assertions.assertEquals(pts.get(1), it.next());
+ Assertions.assertThrows(UnsupportedOperationException.class, () -> it.remove());
+
+ Assertions.assertTrue(it.hasNext());
+ Assertions.assertEquals(pts.get(0), it.next());
+
+ Assertions.assertFalse(it.hasNext());
+
+ Assertions.assertThrows(NoSuchElementException.class, () -> it.next());
+ }
+
+ @Test
+ void testFarToNear_concurrentModification() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+
+ final List<P> pts = getTestPoints(2, EPS);
+ set.addAll(pts);
+
+ // act
+ final Iterator<P> it = set.farToNear(pts.get(0)).iterator();
+ set.remove(pts.get(0));
+
+ // assert
+ Assertions.assertThrows(ConcurrentModificationException.class, () -> it.next());
+ }
+
+ @Test
+ void testFarToNear_invalidArgs() {
+ // arrange
+ final PointSet<P> set = getSet(PRECISION);
+ final P infPt = getInfPoints().get(0);
+
+ // act/assert
+ Assertions.assertThrows(NullPointerException.class, () -> set.farToNear(null));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> set.farToNear(infPt));
+ }
+
@Test
void testHashCode() {
// arrange
@@ -728,6 +1108,33 @@ public abstract class PointSetTestBase<P extends Point<P>>
.check();
}
+ /** Assert that {@code coll} returns the same elements in the same order as
+ * {@code list} when sorted with {@code cmp}.
+ * @param <P> Point type
+ * @param list expected point list
+ * @param cmp comparator producing the expected order
+ * @param coll collection to test
+ */
+ public static <P extends Point<P>, V> void assertCollectionOrder(
+ final List<P> list,
+ final Comparator<P> cmp,
+ final Collection<P> coll) {
+
+ Assertions.assertEquals(list.size(), coll.size(), "Unexpected collection size");
+
+ final List<P> expectedList = new ArrayList<>(list);
+ Collections.sort(expectedList, cmp);
+
+ int i = 0;
+ for (final P actual : coll) {
+ final P expected = expectedList.get(i++);
+
+ Assertions.assertEquals(expected, actual, "Unexpected point at index " + i);
+ }
+
+ Assertions.assertEquals(i, expectedList.size(), "Unexpected iteration count");
+ }
+
/** Class designed to assist with performing assertions on the state
* of a point set.
*/
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/AbstractBucketPointMapTest.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/AbstractBucketPointMapTest.java
index c61f0d62..748f94bd 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/AbstractBucketPointMapTest.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/AbstractBucketPointMapTest.java
@@ -50,6 +50,60 @@ class AbstractBucketPointMapTest extends PointMapTestBase<TestPoint1D> {
Assertions.assertEquals(101, map.get(pt));
}
+ @Test
+ void testEntriesNearToFar_pointsAtEqualDistances() {
+ // arrange
+ TestBucketPointMap1D<Integer> map = getMap(PRECISION);
+
+ final List<TestPoint1D> pts = Arrays.asList(
+ new TestPoint1D(-2),
+ new TestPoint1D(-1),
+ new TestPoint1D(0),
+ new TestPoint1D(1),
+ new TestPoint1D(2));
+
+ insertPoints(pts, map);
+
+ final List<TestPoint1D> expected = Arrays.asList(
+ new TestPoint1D(0),
+ new TestPoint1D(-1),
+ new TestPoint1D(1),
+ new TestPoint1D(-2),
+ new TestPoint1D(2));
+
+ // act/assert
+ assertIterableOrder(
+ expected,
+ map.entriesNearToFar(new TestPoint1D(0)));
+ }
+
+ @Test
+ void testEntriesFarToNear_pointsAtEqualDistances() {
+ // arrange
+ TestBucketPointMap1D<Integer> map = getMap(PRECISION);
+
+ final List<TestPoint1D> pts = Arrays.asList(
+ new TestPoint1D(-2),
+ new TestPoint1D(-1),
+ new TestPoint1D(0),
+ new TestPoint1D(1),
+ new TestPoint1D(2));
+
+ insertPoints(pts, map);
+
+ final List<TestPoint1D> expected = Arrays.asList(
+ new TestPoint1D(2),
+ new TestPoint1D(-2),
+ new TestPoint1D(1),
+ new TestPoint1D(-1),
+ new TestPoint1D(0));
+
+ // act/assert
+ assertIterableOrder(
+ expected,
+ map.entriesFarToNear(new TestPoint1D(0)));
+ }
+
/** {@inheritDoc} */
@Override
protected <V> TestBucketPointMap1D<V> getMap(final Precision.DoubleEquivalence precision) {
@@ -118,4 +172,10 @@ class AbstractBucketPointMapTest extends PointMapTestBase<TestPoint1D> {
return new TestPoint1D(sum / pts.size());
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final TestPoint1D a, final TestPoint1D b) {
+ return Double.compare(a.getX(), b.getX());
+ }
}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/AbstractPointMap1DTest.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/AbstractPointMap1DTest.java
index 60166cd3..2ee64493 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/AbstractPointMap1DTest.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/AbstractPointMap1DTest.java
@@ -18,17 +18,29 @@ package org.apache.commons.geometry.core.internal;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Iterator;
import java.util.List;
-import java.util.Map;
import java.util.NavigableMap;
+import java.util.NoSuchElementException;
import java.util.Set;
import org.apache.commons.geometry.core.collection.PointMapTestBase;
import org.apache.commons.geometry.core.partitioning.test.TestPoint1D;
import org.apache.commons.numbers.core.Precision;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
class AbstractPointMap1DTest extends PointMapTestBase<TestPoint1D> {
+ @Test
+ void testGetPrecision() {
+ // arrange
+ final TestPointMap1D<Integer> map = getMap(PRECISION);
+
+ // act/assert
+ Assertions.assertSame(PRECISION, map.getPrecision());
+ }
+
/** {@inheritDoc} */
@Override
protected <V> TestPointMap1D<V> getMap(final Precision.DoubleEquivalence precision) {
@@ -76,6 +88,12 @@ class AbstractPointMap1DTest extends PointMapTestBase<TestPoint1D> {
return precision.eq(a.getX(), b.getX());
}
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final TestPoint1D a, final TestPoint1D b) {
+ return Double.compare(a.getX(), b.getX());
+ }
+
private static List<TestPoint1D> createPointList(final double start, final double delta, final int cnt) {
final List<TestPoint1D> pts = new ArrayList<>(cnt);
@@ -92,7 +110,7 @@ class AbstractPointMap1DTest extends PointMapTestBase<TestPoint1D> {
private static final class TestPointMap1D<V> extends AbstractPointMap1D<TestPoint1D, V> {
TestPointMap1D(final Precision.DoubleEquivalence precision) {
- super((a, b) -> precision.compare(a.getX(), b.getX()));
+ super(precision, TestPoint1D::getX);
}
/** {@inheritDoc} */
@@ -135,7 +153,7 @@ class AbstractPointMap1DTest extends PointMapTestBase<TestPoint1D> {
@Override
protected Entry<TestPoint1D, V> getEntryInternal(final TestPoint1D key) {
final NavigableMap<TestPoint1D, V> map = getMap();
- final Map.Entry<TestPoint1D, V> floor = map.floorEntry(key);
+ final Entry<TestPoint1D, V> floor = map.floorEntry(key);
if (floor != null &&
map.comparator().compare(floor.getKey(), key) == 0) {
return floor;
@@ -148,5 +166,158 @@ class AbstractPointMap1DTest extends PointMapTestBase<TestPoint1D> {
protected V putInternal(final TestPoint1D key, final V value) {
return getMap().put(key, value);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected Iterator<Entry<TestPoint1D, V>> nearToFarIterator(final TestPoint1D pt) {
+ return new NearToFarIterator(pt);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Iterator<Entry<TestPoint1D, V>> farToNearIterator(final TestPoint1D pt) {
+ return new FarToNearIterator(pt);
+ }
+
+ private final class NearToFarIterator
+ implements Iterator<Entry<TestPoint1D, V>> {
+
+ private final TestPoint1D refPt;
+
+ private final Iterator<Entry<TestPoint1D, V>> low;
+
+ private final Iterator<Entry<TestPoint1D, V>> high;
+
+ private DistancedValue<Entry<TestPoint1D, V>> lowEntry;
+
+ private DistancedValue<Entry<TestPoint1D, V>> highEntry;
+
+ NearToFarIterator(final TestPoint1D refPt) {
+ this.refPt = refPt;
+
+ this.low = getMap().descendingMap().tailMap(refPt, false)
+ .entrySet().iterator();
+ this.high = getMap().tailMap(refPt).entrySet().iterator();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean hasNext() {
+ if (lowEntry == null) {
+ lowEntry = getNextEntry(low);
+ }
+ if (highEntry == null) {
+ highEntry = getNextEntry(high);
+ }
+
+ return lowEntry != null || highEntry != null;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Entry<TestPoint1D, V> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+
+ final DistancedValue<Entry<TestPoint1D, V>> result;
+ if (lowEntry != null &&
+ (highEntry == null || lowEntry.getDistance() <= highEntry.getDistance())) {
+ result = lowEntry;
+ lowEntry = null;
+ } else {
+ result = highEntry;
+ highEntry = null;
+ }
+
+ return result != null ?
+ result.getValue() :
+ null;
+ }
+
+ private DistancedValue<Entry<TestPoint1D, V>> getNextEntry(final Iterator<Entry<TestPoint1D, V>> it) {
+ if (it.hasNext()) {
+ final Entry<TestPoint1D, V> entry = it.next();
+ return DistancedValue.of(entry, refPt.distance(entry.getKey()));
+ }
+ return null;
+ }
+ }
+
+ private final class FarToNearIterator
+ implements Iterator<Entry<TestPoint1D, V>> {
+
+ private final TestPoint1D refPt;
+
+ private Iterator<Entry<TestPoint1D, V>> low;
+
+ private Iterator<Entry<TestPoint1D, V>> high;
+
+ private DistancedValue<Entry<TestPoint1D, V>> lowEntry;
+
+ private DistancedValue<Entry<TestPoint1D, V>> highEntry;
+
+ private double lastLowValue = Double.NEGATIVE_INFINITY;
+
+ private double lastHighValue = Double.POSITIVE_INFINITY;
+
+ FarToNearIterator(final TestPoint1D refPt) {
+ this.refPt = refPt;
+
+ this.low = getMap().entrySet().iterator();
+ this.high = getMap().descendingMap().entrySet().iterator();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean hasNext() {
+ if (lowEntry == null && low != null && low.hasNext()) {
+ final Entry<TestPoint1D, V> entry = low.next();
+ lastLowValue = entry.getKey().getX();
+
+ if (entry.getKey().getX() >= lastHighValue) {
+ // we've crossed over the value returned by the high iterator
+ low = null;
+ } else {
+ lowEntry = DistancedValue.of(entry, refPt.distance(entry.getKey()));
+ }
+ }
+ if (highEntry == null && high != null && high.hasNext()) {
+ final Entry<TestPoint1D, V> entry = high.next();
+ lastHighValue = entry.getKey().getX();
+
+ if (entry.getKey().getX() <= lastLowValue) {
+ // we've crossed over the values returned by the low iterator
+ high = null;
+ } else {
+ highEntry = DistancedValue.of(entry, refPt.distance(entry.getKey()));
+ }
+ }
+
+ return lowEntry != null || highEntry != null;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Entry<TestPoint1D, V> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+
+ final DistancedValue<Entry<TestPoint1D, V>> result;
+ if (lowEntry != null &&
+ (highEntry == null || lowEntry.getDistance() >= highEntry.getDistance())) {
+ result = lowEntry;
+ lowEntry = null;
+ } else {
+ result = highEntry;
+ highEntry = null;
+ }
+
+ return result != null ?
+ result.getValue() :
+ null;
+ }
+ }
}
}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/PointMapAsSetAdapterTest.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/PointMapAsSetAdapterTest.java
index 2fdbae1c..02e1d404 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/PointMapAsSetAdapterTest.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/PointMapAsSetAdapterTest.java
@@ -75,6 +75,12 @@ class PointMapAsSetAdapterTest extends PointSetTestBase<TestPoint1D> {
return precision.eq(a.getX(), b.getX());
}
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final TestPoint1D a, final TestPoint1D b) {
+ return Double.compare(a.getX(), b.getX());
+ }
+
private static List<TestPoint1D> createPointList(final double start, final double delta, final int cnt) {
final List<TestPoint1D> pts = new ArrayList<>(cnt);
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/TestBucketPointMap1D.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/TestBucketPointMap1D.java
index 49d9004d..7294350b 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/TestBucketPointMap1D.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/internal/TestBucketPointMap1D.java
@@ -43,7 +43,14 @@ public class TestBucketPointMap1D<V> extends AbstractBucketPointMap<TestPoint1D,
return getPrecision().eq(a.getX(), b.getX());
}
- private static final class TestNode1D<V> extends AbstractBucketPointMap.BucketNode<TestPoint1D, V> {
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguatePointComparison(final TestPoint1D a, final TestPoint1D b) {
+ return Double.compare(a.getX(), b.getX());
+ }
+
+ private static final class TestNode1D<V>
+ extends AbstractBucketPointMap.BucketNode<TestPoint1D, V> {
/** Negative half-space flag. */
private static final int NEG = 1 << 1;
@@ -61,8 +68,9 @@ public class TestBucketPointMap1D<V> extends AbstractBucketPointMap<TestPoint1D,
TestNode1D(
final AbstractBucketPointMap<TestPoint1D, V> map,
- final BucketNode<TestPoint1D, V> parent) {
- super(map, parent);
+ final BucketNode<TestPoint1D, V> parent,
+ final int childIndex) {
+ super(map, parent, childIndex);
}
/** {@inheritDoc} */
@@ -94,5 +102,26 @@ public class TestBucketPointMap1D<V> extends AbstractBucketPointMap<TestPoint1D,
final int childLoc = CHILD_LOCATIONS[childIdx];
return (childLoc & loc) == childLoc;
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getMinChildDistance(final int childIdx, final TestPoint1D pt, final int ptLoc) {
+ return ptLoc == CHILD_LOCATIONS[childIdx] ?
+ 0d :
+ Math.abs(pt.getX() - split);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getMaxChildDistance(final int childIdx, final TestPoint1D pt, final int ptLoc) {
+ final TestNode1D<V> parent = (TestNode1D<V>) getParent();
+ if (parent != null &&
+ childIdx != getChildIndex()) {
+
+ return getMaxDistance(pt.getX(), parent.split, split);
+ }
+
+ return Double.POSITIVE_INFINITY;
+ }
}
}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/test/TestPoint1D.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/test/TestPoint1D.java
index 6d892d67..b6c8e15d 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/test/TestPoint1D.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/test/TestPoint1D.java
@@ -69,6 +69,23 @@ public final class TestPoint1D implements Point<TestPoint1D> {
return Math.abs(this.x - p.x);
}
+ /** {@inheritDoc} */
+ @Override
+ public int hashCode() {
+ return Double.hashCode(x);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean equals(final Object obj) {
+ if (!(obj instanceof TestPoint1D)) {
+ return false;
+ }
+
+ final TestPoint1D other = (TestPoint1D) obj;
+ return Double.compare(x, other.x) == 0;
+ }
+
/** {@inheritDoc} */
@Override
public String toString() {
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap1DImpl.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap1DImpl.java
index 1525d1ac..295d629b 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap1DImpl.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap1DImpl.java
@@ -16,11 +16,13 @@
*/
package org.apache.commons.geometry.euclidean;
-import java.util.Map;
+import java.util.Iterator;
import java.util.NavigableMap;
+import java.util.NoSuchElementException;
import java.util.Set;
import org.apache.commons.geometry.core.internal.AbstractPointMap1D;
+import org.apache.commons.geometry.core.internal.DistancedValue;
import org.apache.commons.geometry.euclidean.oned.Vector1D;
import org.apache.commons.numbers.core.Precision;
@@ -36,7 +38,7 @@ final class PointMap1DImpl<V>
* @param precision precision context
*/
PointMap1DImpl(final Precision.DoubleEquivalence precision) {
- super((a, b) -> precision.compare(a.getX(), b.getX()));
+ super(precision, Vector1D::getX);
}
/** {@inheritDoc} */
@@ -77,9 +79,10 @@ final class PointMap1DImpl<V>
/** {@inheritDoc} */
@Override
- protected Map.Entry<Vector1D, V> getEntryInternal(final Vector1D key) {
+ protected Entry<Vector1D, V> getEntryInternal(final Vector1D key) {
final NavigableMap<Vector1D, V> map = getMap();
- final Map.Entry<Vector1D, V> floor = map.floorEntry(key);
+
+ final Entry<Vector1D, V> floor = map.floorEntry(key);
if (floor != null &&
map.comparator().compare(floor.getKey(), key) == 0) {
return floor;
@@ -92,4 +95,188 @@ final class PointMap1DImpl<V>
protected V putInternal(final Vector1D key, final V value) {
return getMap().put(key, value);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected Iterator<Entry<Vector1D, V>> nearToFarIterator(final Vector1D pt) {
+ return new NearToFarIterator(pt);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Iterator<Entry<Vector1D, V>> farToNearIterator(final Vector1D pt) {
+ return new FarToNearIterator(pt);
+ }
+
+ /** Iterator that returns entries in order of ascending distance from
+ * a given reference point.
+ */
+ private final class NearToFarIterator
+ implements Iterator<Entry<Vector1D, V>> {
+
+ /** Reference point to measure distances against. */
+ private final Vector1D refPt;
+
+ /** Low entry iterator. */
+ private final Iterator<Entry<Vector1D, V>> low;
+
+ /** High entry iterator. */
+ private final Iterator<Entry<Vector1D, V>> high;
+
+ /** Low-valued entry. */
+ private DistancedValue<Entry<Vector1D, V>> lowEntry;
+
+ /** High-valued entry. */
+ private DistancedValue<Entry<Vector1D, V>> highEntry;
+
+ /** Construct a new instance with the given reference point.
+ * @param refPt reference point
+ */
+ NearToFarIterator(final Vector1D refPt) {
+ this.refPt = refPt;
+
+ this.low = getMap().descendingMap().tailMap(refPt, false)
+ .entrySet().iterator();
+ this.high = getMap().tailMap(refPt).entrySet().iterator();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean hasNext() {
+ if (lowEntry == null) {
+ lowEntry = getNextEntry(low);
+ }
+ if (highEntry == null) {
+ highEntry = getNextEntry(high);
+ }
+
+ return lowEntry != null || highEntry != null;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Entry<Vector1D, V> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+
+ final DistancedValue<Entry<Vector1D, V>> result;
+ if (lowEntry != null &&
+ (highEntry == null || lowEntry.getDistance() <= highEntry.getDistance())) {
+ result = lowEntry;
+ lowEntry = null;
+ } else {
+ result = highEntry;
+ highEntry = null;
+ }
+
+ return result != null ?
+ result.getValue() :
+ null;
+ }
+
+ /** Get a {@link DistancedValue} instance containing the next entry from the given
+ * iterator.
+ * @param it iterator to get the next value from
+ * @return distanced value containing the next entry from the iterator or null if the iterator
+ * does not contain any more elements
+ */
+ private DistancedValue<Entry<Vector1D, V>> getNextEntry(final Iterator<Entry<Vector1D, V>> it) {
+ if (it.hasNext()) {
+ final Entry<Vector1D, V> entry = it.next();
+ return DistancedValue.of(entry, refPt.distance(entry.getKey()));
+ }
+ return null;
+ }
+ }
+
+ /** Iterator that returns entries in order of descending distance from
+ * a given reference point.
+ */
+ private final class FarToNearIterator
+ implements Iterator<Entry<Vector1D, V>> {
+
+ /** Reference point to measure distances against. */
+ private final Vector1D refPt;
+
+ /** Low entry iterator. */
+ private Iterator<Entry<Vector1D, V>> low;
+
+ /** High entry iterator. */
+ private Iterator<Entry<Vector1D, V>> high;
+
+ /** Low-valued entry. */
+ private DistancedValue<Entry<Vector1D, V>> lowEntry;
+
+ /** High-valued entry. */
+ private DistancedValue<Entry<Vector1D, V>> highEntry;
+
+ /** The last value returned by the low iterator. */
+ private double lastLowValue = Double.NEGATIVE_INFINITY;
+
+ /** The last value returned by the high iterator. */
+ private double lastHighValue = Double.POSITIVE_INFINITY;
+
+ /** Construct a new instance that measures distances against the given
+ * reference point.
+ * @param refPt reference point
+ */
+ FarToNearIterator(final Vector1D refPt) {
+ this.refPt = refPt;
+
+ this.low = getMap().entrySet().iterator();
+ this.high = getMap().descendingMap().entrySet().iterator();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean hasNext() {
+ if (lowEntry == null && low != null && low.hasNext()) {
+ final Entry<Vector1D, V> entry = low.next();
+ lastLowValue = entry.getKey().getX();
+
+ if (entry.getKey().getX() >= lastHighValue) {
+ // we've crossed over the value returned by the high iterator
+ low = null;
+ } else {
+ lowEntry = DistancedValue.of(entry, refPt.distance(entry.getKey()));
+ }
+ }
+ if (highEntry == null && high != null && high.hasNext()) {
+ final Entry<Vector1D, V> entry = high.next();
+ lastHighValue = entry.getKey().getX();
+
+ if (entry.getKey().getX() <= lastLowValue) {
+ // we've crossed over the values returned by the low iterator
+ high = null;
+ } else {
+ highEntry = DistancedValue.of(entry, refPt.distance(entry.getKey()));
+ }
+ }
+
+ return lowEntry != null || highEntry != null;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Entry<Vector1D, V> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+
+ final DistancedValue<Entry<Vector1D, V>> result;
+ if (lowEntry != null &&
+ (highEntry == null || lowEntry.getDistance() > highEntry.getDistance())) {
+ result = lowEntry;
+ lowEntry = null;
+ } else {
+ result = highEntry;
+ highEntry = null;
+ }
+
+ return result != null ?
+ result.getValue() :
+ null;
+ }
+ }
}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap2DImpl.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap2DImpl.java
index 472d6cab..63592099 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap2DImpl.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap2DImpl.java
@@ -48,6 +48,12 @@ final class PointMap2DImpl<V>
/** Y positive quadrant flag. */
private static final int YPOS = 1;
+ /** Bit mask for x location. */
+ private static final int XMASK = XNEG | XPOS;
+
+ /** Bit mask for y location. */
+ private static final int YMASK = YNEG | YPOS;
+
/** Quadtree location flags for child nodes. */
private static final int[] CHILD_LOCATIONS = {
XNEG | YNEG,
@@ -73,6 +79,12 @@ final class PointMap2DImpl<V>
return a.eq(b, getPrecision());
}
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguatePointComparison(final Vector2D a, final Vector2D b) {
+ return Vector2D.COORDINATE_ASCENDING_ORDER.compare(a, b);
+ }
+
/** Tree node class for {@link PointMap2DImpl}.
* @param <V> Map value type
*/
@@ -84,10 +96,13 @@ final class PointMap2DImpl<V>
/** Construct a new instance.
* @param map owning map
* @param parent parent node; set to null for the root node
+ * @param childIndex index of this node in its parent's child list;
+ * set to {@code -1} for the root node
*/
MapNode2D(final AbstractBucketPointMap<Vector2D, V> map,
- final BucketNode<Vector2D, V> parent) {
- super(map, parent);
+ final BucketNode<Vector2D, V> parent,
+ final int childIndex) {
+ super(map, parent, childIndex);
}
/** {@inheritDoc} */
@@ -147,5 +162,52 @@ final class PointMap2DImpl<V>
split = null;
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getMinChildDistance(final int childIdx, final Vector2D pt, final int ptLoc) {
+ final int childLoc = CHILD_LOCATIONS[childIdx];
+
+ final boolean sameX = (ptLoc & XMASK) == (childLoc & XMASK);
+ final boolean sameY = (ptLoc & YMASK) == (childLoc & YMASK);
+
+ final Vector2D diff = pt.subtract(split);
+
+ if (sameX) {
+ return sameY ?
+ 0d :
+ Math.abs(diff.getY());
+ } else if (sameY) {
+ return Math.abs(diff.getX());
+ }
+
+ return diff.norm();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getMaxChildDistance(final int childIdx, final Vector2D pt, final int ptLoc) {
+ final MapNode2D<V> grandParent = (MapNode2D<V>) getParent();
+ if (grandParent != null) {
+ final int nodeLoc = CHILD_LOCATIONS[getChildIndex()];
+ final int childLoc = CHILD_LOCATIONS[childIdx];
+
+ final boolean oppositeX = (nodeLoc & XMASK) != (childLoc & XMASK);
+ final boolean oppositeY = (nodeLoc & YMASK) != (childLoc & YMASK);
+
+ if (oppositeX && oppositeY) {
+ // the grandparent and parent splits form a completely enclosed region,
+ // meaning that we can determine a max distance
+ final Vector2D diff = Vector2D.of(
+ getMaxDistance(pt.getX(), grandParent.split.getX(), split.getX()),
+ getMaxDistance(pt.getY(), grandParent.split.getY(), split.getY())
+ );
+
+ return diff.norm();
+ }
+ }
+
+ return Double.POSITIVE_INFINITY;
+ }
}
}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap3DImpl.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap3DImpl.java
index eae192a7..c754b1cb 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap3DImpl.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap3DImpl.java
@@ -20,6 +20,7 @@ import java.util.List;
import org.apache.commons.geometry.core.collection.PointMap;
import org.apache.commons.geometry.core.internal.AbstractBucketPointMap;
+import org.apache.commons.geometry.euclidean.internal.Vectors;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
import org.apache.commons.numbers.core.Precision;
@@ -59,6 +60,15 @@ final class PointMap3DImpl<V>
/** Z positive octant flag. */
private static final int ZPOS = 1;
+ /** Bit mask for x location. */
+ private static final int XMASK = XNEG | XPOS;
+
+ /** Bit mask for y location. */
+ private static final int YMASK = YNEG | YPOS;
+
+ /** Bit mask for z location. */
+ private static final int ZMASK = ZNEG | ZPOS;
+
/** Octant location flags for child nodes. */
private static final int[] CHILD_LOCATIONS = {
XNEG | YNEG | ZNEG,
@@ -89,6 +99,12 @@ final class PointMap3DImpl<V>
return a.eq(b, getPrecision());
}
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguatePointComparison(final Vector3D a, final Vector3D b) {
+ return Vector3D.COORDINATE_ASCENDING_ORDER.compare(a, b);
+ }
+
/** Tree node class for {@link PointMap3DImpl}.
* @param <V> Map value type
*/
@@ -100,10 +116,13 @@ final class PointMap3DImpl<V>
/** Construct a new instance.
* @param map owning map
* @param parent parent node; set to null for the root node
+ * @param childIndex index of this node in its parent's child list;
+ * set to {@code -1} for the root node
*/
MapNode3D(final AbstractBucketPointMap<Vector3D, V> map,
- final BucketNode<Vector3D, V> parent) {
- super(map, parent);
+ final BucketNode<Vector3D, V> parent,
+ final int childIndex) {
+ super(map, parent, childIndex);
}
/** {@inheritDoc} */
@@ -171,5 +190,64 @@ final class PointMap3DImpl<V>
split = null;
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getMinChildDistance(final int childIdx, final Vector3D pt, final int ptLoc) {
+ final int childLoc = CHILD_LOCATIONS[childIdx];
+
+ final boolean sameX = (ptLoc & XMASK) == (childLoc & XMASK);
+ final boolean sameY = (ptLoc & YMASK) == (childLoc & YMASK);
+ final boolean sameZ = (ptLoc & ZMASK) == (childLoc & ZMASK);
+
+ final Vector3D diff = pt.subtract(split);
+
+ if (sameX) {
+ if (sameY) {
+ return sameZ ?
+ 0d :
+ Math.abs(diff.getZ());
+ }
+ return sameZ ?
+ Math.abs(diff.getY()) :
+ Vectors.norm(diff.getY(), diff.getZ());
+ } else if (sameY) {
+ return sameZ ?
+ Math.abs(diff.getX()) :
+ Vectors.norm(diff.getX(), diff.getZ());
+ } else if (sameZ) {
+ return Vectors.norm(diff.getX(), diff.getY());
+ }
+
+ return diff.norm();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getMaxChildDistance(final int childIdx, final Vector3D pt, final int ptLoc) {
+ final MapNode3D<V> grandParent = (MapNode3D<V>) getParent();
+ if (grandParent != null) {
+ final int nodeLoc = CHILD_LOCATIONS[getChildIndex()];
+ final int childLoc = CHILD_LOCATIONS[childIdx];
+
+ final boolean oppositeX = (nodeLoc & XMASK) != (childLoc & XMASK);
+ final boolean oppositeY = (nodeLoc & YMASK) != (childLoc & YMASK);
+ final boolean oppositeZ = (nodeLoc & ZMASK) != (childLoc & ZMASK);
+
+ if (oppositeX && oppositeY && oppositeZ) {
+ // the grandparent and parent splits form a completely enclosed region,
+ // meaning that we can determine a max distance
+ final Vector3D diff = Vector3D.of(
+ getMaxDistance(pt.getX(), grandParent.split.getX(), split.getX()),
+ getMaxDistance(pt.getY(), grandParent.split.getY(), split.getY()),
+ getMaxDistance(pt.getZ(), grandParent.split.getZ(), split.getZ())
+ );
+
+ return diff.norm();
+ }
+ }
+
+ return Double.POSITIVE_INFINITY;
+ }
}
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/PointMap1DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/PointMap1DTest.java
index 683b7cea..ee7e93e7 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/PointMap1DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/PointMap1DTest.java
@@ -18,10 +18,12 @@ package org.apache.commons.geometry.euclidean.oned;
import static org.junit.jupiter.api.Assertions.assertEquals;
+import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
+import java.util.Random;
import org.apache.commons.geometry.core.collection.PointMap;
import org.apache.commons.geometry.core.collection.PointMapTestBase;
@@ -61,6 +63,56 @@ class PointMap1DTest extends PointMapTestBase<Vector1D> {
}
}
+ @Test
+ void testNearesAndFarthesttEntry_equalDistances() {
+ // arrange
+ final PointMap<Vector1D, Integer> map = getMap(PRECISION);
+
+ int i = 0;
+
+ map.put(Vector1D.Unit.MINUS, ++i);
+ map.put(Vector1D.Unit.PLUS, ++i);
+
+ // act/assert
+ Assertions.assertEquals(new SimpleEntry<>(Vector1D.Unit.MINUS, 1), map.nearestEntry(Vector1D.ZERO));
+ Assertions.assertEquals(new SimpleEntry<>(Vector1D.Unit.PLUS, 2), map.farthestEntry(Vector1D.ZERO));
+ }
+
+ @Test
+ void testEntryDistanceOrder_random() {
+ // arrange
+ final PointMap<Vector1D, Integer> map = getMap(PRECISION);
+
+ final Random rnd = new Random(3L);
+ final int testCnt = 5;
+ final int pointCnt = 1_000;
+ final double range = 1e10;
+
+ final List<Vector1D> pts = new ArrayList<>();
+
+ for (int i = 0; i < pointCnt; ++i) {
+ final Vector1D pt = randomPoint(rnd, range);
+ pts.add(pt);
+
+ map.put(pt, i);
+ }
+
+ // act/assert
+ for (int i = 0; i < testCnt; ++i) {
+ final Vector1D refPt = randomPoint(rnd, range);
+
+ assertCollectionOrder(
+ pts,
+ createNearToFarComparator(refPt),
+ map.entriesNearToFar(refPt));
+
+ assertCollectionOrder(
+ pts,
+ createFarToNearComparator(refPt),
+ map.entriesFarToNear(refPt));
+ }
+ }
+
/** {@inheritDoc} */
@Override
protected <V> PointMap<Vector1D, V> getMap(final Precision.DoubleEquivalence precision) {
@@ -117,4 +169,19 @@ class PointMap1DTest extends PointMapTestBase<Vector1D> {
protected boolean eq(final Vector1D a, final Vector1D b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Vector1D a, final Vector1D b) {
+ return Vector1D.COORDINATE_ASCENDING_ORDER.compare(a, b);
+ }
+
+ /** Create a random point with coordinate values in the range {@code [-range/2, range/2)}.
+ * @param rnd random source
+ * @param range distance between min and max coordinate values
+ * @return random point
+ */
+ private static Vector1D randomPoint(final Random rnd, final double range) {
+ return Vector1D.of((rnd.nextDouble() - 0.5) * range);
+ }
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/PointSet1DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/PointSet1DTest.java
index b57e0e8f..ffb5ddd1 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/PointSet1DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/PointSet1DTest.java
@@ -84,4 +84,10 @@ class PointSet1DTest extends PointSetTestBase<Vector1D> {
protected boolean eq(final Vector1D a, final Vector1D b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Vector1D a, final Vector1D b) {
+ return Vector1D.COORDINATE_ASCENDING_ORDER.compare(a, b);
+ }
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PointMap3DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PointMap3DTest.java
index 37e3b1d6..509429e4 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PointMap3DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PointMap3DTest.java
@@ -18,9 +18,11 @@ package org.apache.commons.geometry.euclidean.threed;
import static org.junit.jupiter.api.Assertions.assertEquals;
+import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
+import java.util.Random;
import org.apache.commons.geometry.core.collection.PointMap;
import org.apache.commons.geometry.core.collection.PointMapTestBase;
@@ -84,6 +86,62 @@ class PointMap3DTest extends PointMapTestBase<Vector3D> {
}
}
+ @Test
+ void testNearesAndFarthesttEntry_equalDistances() {
+ // arrange
+ final PointMap<Vector3D, Integer> map = getMap(PRECISION);
+
+ int i = 0;
+
+ map.put(Vector3D.Unit.MINUS_Z, ++i);
+ map.put(Vector3D.Unit.PLUS_Z, ++i);
+
+ map.put(Vector3D.Unit.MINUS_X, ++i);
+ map.put(Vector3D.Unit.PLUS_X, ++i);
+
+ map.put(Vector3D.Unit.MINUS_Y, ++i);
+ map.put(Vector3D.Unit.PLUS_Y, ++i);
+
+ // act/assert
+ Assertions.assertEquals(new SimpleEntry<>(Vector3D.Unit.MINUS_X, 3), map.nearestEntry(Vector3D.ZERO));
+ Assertions.assertEquals(new SimpleEntry<>(Vector3D.Unit.PLUS_X, 4), map.farthestEntry(Vector3D.ZERO));
+ }
+
+ @Test
+ void testEntryDistanceOrder_random() {
+ // arrange
+ final PointMap<Vector3D, Integer> map = getMap(PRECISION);
+
+ final Random rnd = new Random(2L);
+ final int testCnt = 5;
+ final int pointCnt = 1_000;
+ final double range = 1e10;
+
+ final List<Vector3D> pts = new ArrayList<>();
+
+ for (int i = 0; i < pointCnt; ++i) {
+ final Vector3D pt = randomPoint(rnd, range);
+ pts.add(pt);
+
+ map.put(pt, i);
+ }
+
+ // act/assert
+ for (int i = 0; i < testCnt; ++i) {
+ final Vector3D refPt = randomPoint(rnd, range);
+
+ assertCollectionOrder(
+ pts,
+ createNearToFarComparator(refPt),
+ map.entriesNearToFar(refPt));
+
+ assertCollectionOrder(
+ pts,
+ createFarToNearComparator(refPt),
+ map.entriesFarToNear(refPt));
+ }
+ }
+
/** {@inheritDoc} */
@Override
protected <V> PointMap<Vector3D, V> getMap(final Precision.DoubleEquivalence precision) {
@@ -172,4 +230,22 @@ class PointMap3DTest extends PointMapTestBase<Vector3D> {
protected boolean eq(final Vector3D a, final Vector3D b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Vector3D a, final Vector3D b) {
+ return Vector3D.COORDINATE_ASCENDING_ORDER.compare(a, b);
+ }
+
+ /** Create a random point with coordinate values in the range {@code [-range/2, range/2)}.
+ * @param rnd random source
+ * @param range distance between min and max coordinate values
+ * @return random point
+ */
+ private static Vector3D randomPoint(final Random rnd, final double range) {
+ return Vector3D.of(
+ (rnd.nextDouble() - 0.5) * range,
+ (rnd.nextDouble() - 0.5) * range,
+ (rnd.nextDouble() - 0.5) * range);
+ }
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PointSet3DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PointSet3DTest.java
index e6bf8909..23164d1b 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PointSet3DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PointSet3DTest.java
@@ -115,4 +115,10 @@ class PointSet3DTest extends PointSetTestBase<Vector3D> {
protected boolean eq(final Vector3D a, final Vector3D b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Vector3D a, final Vector3D b) {
+ return Vector3D.COORDINATE_ASCENDING_ORDER.compare(a, b);
+ }
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PointMap2DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PointMap2DTest.java
index 0a06826e..896d3c52 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PointMap2DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PointMap2DTest.java
@@ -18,9 +18,11 @@ package org.apache.commons.geometry.euclidean.twod;
import static org.junit.jupiter.api.Assertions.assertEquals;
+import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
+import java.util.Random;
import org.apache.commons.geometry.core.collection.PointMap;
import org.apache.commons.geometry.core.collection.PointMapTestBase;
@@ -85,6 +87,59 @@ class PointMap2DTest extends PointMapTestBase<Vector2D> {
}
}
+ @Test
+ void testNearesAndFarthesttEntry_equalDistances() {
+ // arrange
+ final PointMap<Vector2D, Integer> map = getMap(PRECISION);
+
+ int i = 0;
+
+ map.put(Vector2D.Unit.MINUS_Y, ++i);
+ map.put(Vector2D.Unit.PLUS_Y, ++i);
+
+ map.put(Vector2D.Unit.MINUS_X, ++i);
+ map.put(Vector2D.Unit.PLUS_X, ++i);
+
+ // act/assert
+ Assertions.assertEquals(new SimpleEntry<>(Vector2D.Unit.MINUS_X, 3), map.nearestEntry(Vector2D.ZERO));
+ Assertions.assertEquals(new SimpleEntry<>(Vector2D.Unit.PLUS_X, 4), map.farthestEntry(Vector2D.ZERO));
+ }
+
+ @Test
+ void testEntryDistanceOrder_random() {
+ // arrange
+ final PointMap<Vector2D, Integer> map = getMap(PRECISION);
+
+ final Random rnd = new Random(3L);
+ final int testCnt = 5;
+ final int pointCnt = 1_000;
+ final double range = 1e10;
+
+ final List<Vector2D> pts = new ArrayList<>();
+
+ for (int i = 0; i < pointCnt; ++i) {
+ final Vector2D pt = randomPoint(rnd, range);
+ pts.add(pt);
+
+ map.put(pt, i);
+ }
+
+ // act/assert
+ for (int i = 0; i < testCnt; ++i) {
+ final Vector2D refPt = randomPoint(rnd, range);
+
+ assertCollectionOrder(
+ pts,
+ createNearToFarComparator(refPt),
+ map.entriesNearToFar(refPt));
+
+ assertCollectionOrder(
+ pts,
+ createFarToNearComparator(refPt),
+ map.entriesFarToNear(refPt));
+ }
+ }
+
/** {@inheritDoc} */
@Override
protected <V> PointMap<Vector2D, V> getMap(final DoubleEquivalence precision) {
@@ -163,4 +218,21 @@ class PointMap2DTest extends PointMapTestBase<Vector2D> {
protected boolean eq(final Vector2D a, final Vector2D b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Vector2D a, final Vector2D b) {
+ return Vector2D.COORDINATE_ASCENDING_ORDER.compare(a, b);
+ }
+
+ /** Create a random point with coordinate values in the range {@code [-range/2, range/2)}.
+ * @param rnd random source
+ * @param range distance between min and max coordinate values
+ * @return random point
+ */
+ private static Vector2D randomPoint(final Random rnd, final double range) {
+ return Vector2D.of(
+ (rnd.nextDouble() - 0.5) * range,
+ (rnd.nextDouble() - 0.5) * range);
+ }
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PointSet2DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PointSet2DTest.java
index de793146..009e6def 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PointSet2DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PointSet2DTest.java
@@ -106,4 +106,10 @@ class PointSet2DTest extends PointSetTestBase<Vector2D> {
protected boolean eq(final Vector2D a, final Vector2D b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Vector2D a, final Vector2D b) {
+ return Vector2D.COORDINATE_ASCENDING_ORDER.compare(a, b);
+ }
}
diff --git a/commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/PointMap3DPerformance.java b/commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/PointMap3DPerformance.java
index 01d38023..168ea203 100644
--- a/commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/PointMap3DPerformance.java
+++ b/commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/PointMap3DPerformance.java
@@ -23,7 +23,9 @@ import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
import java.util.concurrent.TimeUnit;
+import java.util.function.BiFunction;
+import org.apache.commons.geometry.core.collection.PointMap;
import org.apache.commons.geometry.euclidean.EuclideanCollections;
import org.apache.commons.geometry.euclidean.threed.Bounds3D;
import org.apache.commons.geometry.euclidean.threed.SphericalCoordinates;
@@ -61,13 +63,12 @@ public class PointMap3DPerformance {
/** Value inserted into maps during runs. */
private static final Integer VAL = Integer.valueOf(1);
- /** Base input class for point map benchmarks. */
- @State(Scope.Thread)
- public static class PointMapInput {
+ /** Maximum number of iterable instances used during iterable benchmarks. */
+ private static final int MAX_ITERABLES = 100;
- /** Data structure implementation. */
- @Param({"treemap", "pointmap3d"})
- private String impl;
+ /** Abstract base class for point map benchmark input. */
+ @State(Scope.Thread)
+ public abstract static class AbstractPointMapInput {
/** Point list shape. */
@Param({"block", "line", "sphere"})
@@ -81,9 +82,6 @@ public class PointMap3DPerformance {
@Param({"1"})
private int randomSeed;
- /** Map instance for the run. */
- private Map<Vector3D, Integer> map;
-
/** List of points for the run. */
private List<Vector3D> points;
@@ -94,8 +92,6 @@ public class PointMap3DPerformance {
@Setup(Level.Iteration)
public void setup() {
random = new Random(randomSeed);
-
- map = createMap();
points = createPoints();
switch (dist) {
@@ -115,9 +111,7 @@ public class PointMap3DPerformance {
/** Get the map instance under test.
* @return map instance
*/
- public Map<Vector3D, Integer> getMap() {
- return map;
- }
+ public abstract Map<Vector3D, Integer> getMap();
/** Get the points for the run.
* @return list of points
@@ -133,29 +127,6 @@ public class PointMap3DPerformance {
return random;
}
- /** Create the map implementation for the run.
- * @return map instance
- */
- private Map<Vector3D, Integer> createMap() {
- switch (impl.toLowerCase()) {
- case "treemap":
- return new TreeMap<>((a, b) -> {
- int cmp = PRECISION.compare(a.getX(), b.getX());
- if (cmp == 0) {
- cmp = PRECISION.compare(a.getY(), b.getY());
- if (cmp == 0) {
- cmp = PRECISION.compare(a.getZ(), b.getZ());
- }
- }
- return cmp;
- });
- case "pointmap3d":
- return EuclideanCollections.pointMap3D(PRECISION);
- default:
- throw new IllegalArgumentException("Unknown map implementation: " + impl);
- }
- }
-
/** Create the list of points for the run.
* @return list of points
*/
@@ -168,14 +139,15 @@ public class PointMap3DPerformance {
case "sphere":
return createPointSphere(5, 5, 10);
default:
- throw new IllegalArgumentException("Unknown point distribution " + impl);
+ throw new IllegalArgumentException("Unknown point distribution " + shape);
}
}
}
/** Input class containing pre-inserted points. */
@State(Scope.Thread)
- public static class PreInsertedPointMapInput extends PointMapInput {
+ public abstract static class AbstractPreInsertedPointMapInput
+ extends AbstractPointMapInput {
/** List of test points. */
private List<Vector3D> testPoints;
@@ -221,6 +193,73 @@ public class PointMap3DPerformance {
}
}
+ /** Input class containing a {@link PointMap} instance.
+ */
+ @State(Scope.Thread)
+ public static class PointMapInput extends AbstractPointMapInput {
+
+ /** {@inheritDoc} */
+ @Override
+ public PointMap<Vector3D, Integer> getMap() {
+ return EuclideanCollections.pointMap3D(PRECISION);
+ }
+ }
+
+ /** Input class containing a {@link PointMap} instance with pre-inserted points.
+ */
+ @State(Scope.Thread)
+ public static class PreInsertedPointMapInput extends AbstractPreInsertedPointMapInput {
+
+ /** {@inheritDoc} */
+ @Override
+ public PointMap<Vector3D, Integer> getMap() {
+ return EuclideanCollections.pointMap3D(PRECISION);
+ }
+ }
+
+ /** Input class that uses a {@link TreeMap} to store points.
+ */
+ @State(Scope.Thread)
+ public static class TreeMapInput extends AbstractPointMapInput {
+
+ /** {@inheritDoc} */
+ @Override
+ public Map<Vector3D, Integer> getMap() {
+ return createTreeMap();
+ }
+ }
+
+ /** Input class that uses a {@link TreeMap} with pre-inserted points.
+ */
+ @State(Scope.Thread)
+ public static class PreInsertedTreeMapInput extends AbstractPreInsertedPointMapInput {
+
+ /** {@inheritDoc} */
+ @Override
+ public Map<Vector3D, Integer> getMap() {
+ return createTreeMap();
+ }
+ }
+
+ /** Create a {@link TreeMap} configured to compare points using the precision
+ * context for the benchmarks. This map is only intended to be used as a baseline
+ * for a well-performing tree structure. It does not properly
+ * partition the input points.
+ * @return a new {@link TreeMap} instance
+ */
+ private static Map<Vector3D, Integer> createTreeMap() {
+ return new TreeMap<>((a, b) -> {
+ int cmp = PRECISION.compare(a.getX(), b.getX());
+ if (cmp == 0) {
+ cmp = PRECISION.compare(a.getY(), b.getY());
+ if (cmp == 0) {
+ cmp = PRECISION.compare(a.getZ(), b.getZ());
+ }
+ }
+ return cmp;
+ });
+ }
+
/** Create a solid block of points.
* @param pointsPerSide number of points along each side
* @param spacing spacing between each point
@@ -289,13 +328,12 @@ public class PointMap3DPerformance {
return points;
}
- /** Benchmark that inserts each point in the input into the target map.
+ /** Run a benchmark using the {@link Map#put(Object, Object)} method.
* @param input input for the run
* @param bh blackhole instance
* @return input instance
*/
- @Benchmark
- public PointMapInput put(final PointMapInput input, final Blackhole bh) {
+ private static AbstractPointMapInput doPut(final AbstractPointMapInput input, final Blackhole bh) {
final Map<Vector3D, Integer> map = input.getMap();
for (final Vector3D p : input.getPoints()) {
@@ -305,29 +343,27 @@ public class PointMap3DPerformance {
return input;
}
- /** Benchmark that retrieves each point in the input from the target map.
+ /** Run a benchmark using the {@link Map#get(Object)} method.
* @param input input for the run
* @param bh blackhole instance
* @return input instance
*/
- @Benchmark
- public PointMapInput get(final PreInsertedPointMapInput input, final Blackhole bh) {
+ private static AbstractPointMapInput doGet(final AbstractPointMapInput input, final Blackhole bh) {
final Map<Vector3D, Integer> map = input.getMap();
- for (final Vector3D p : input.getTestPoints()) {
+ for (final Vector3D p : input.getPoints()) {
bh.consume(map.get(p));
}
return input;
}
- /** Benchmark that remove each point in the input from the target map.
+ /** Run a benchmark using the {@link Map#remove(Object)} method.
* @param input input for the run
* @param bh blackhole instance
* @return input instance
*/
- @Benchmark
- public PointMapInput remove(final PreInsertedPointMapInput input, final Blackhole bh) {
+ private static AbstractPointMapInput doRemove(final AbstractPointMapInput input, final Blackhole bh) {
final Map<Vector3D, Integer> map = input.getMap();
for (final Vector3D p : input.getPoints()) {
@@ -336,4 +372,211 @@ public class PointMap3DPerformance {
return input;
}
+
+ /** Run a benchmark for a distance-ordered map iteration.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @param count maximum number of elements to iterate through for each test point
+ * @param iterableFactory function to create the iterable instance for each test point
+ * @return input instance
+ */
+ private static PreInsertedPointMapInput doDistanceIteration(
+ final PreInsertedPointMapInput input,
+ final Blackhole bh,
+ final int count,
+ final BiFunction<
+ PointMap<Vector3D, Integer>,
+ Vector3D,
+ Iterable<?>> iterableFactory) {
+
+ final PointMap<Vector3D, Integer> map = input.getMap();
+
+ int i = 0;
+ for (final Vector3D pt : input.getTestPoints()) {
+ int cnt = 0;
+ for (final Object element : iterableFactory.apply(map, pt)) {
+ bh.consume(element);
+
+ if (++cnt >= cnt) {
+ break;
+ }
+ }
+
+ if (++i >= MAX_ITERABLES) {
+ break;
+ }
+ }
+
+ return input;
+ }
+
+ /** Run a benchmark for a distance select operation.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @param selectFn function used to select from the map
+ * @return input instance
+ */
+ private static PreInsertedPointMapInput doDistanceSelect(
+ final PreInsertedPointMapInput input,
+ final Blackhole bh,
+ final BiFunction<
+ PointMap<Vector3D, Integer>,
+ Vector3D,
+ Map.Entry<Vector3D, Integer>> selectFn) {
+ final PointMap<Vector3D, Integer> map = input.getMap();
+
+ for (final Vector3D pt : input.getTestPoints()) {
+ bh.consume(selectFn.apply(map, pt));
+ }
+
+ return input;
+ }
+
+ /** Baseline benchmark for {@link Map#put(Object, Object)} using a {@link TreeMap}.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object putTreeMapBaseline(final TreeMapInput input, final Blackhole bh) {
+ return doPut(input, bh);
+ }
+
+ /** Benchmark that inserts each point in the input into the target map.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object put(final TreeMapInput input, final Blackhole bh) {
+ return doPut(input, bh);
+ }
+
+ /** Baseline benchmark for {@link Map#get(Object)} using a {@link TreeMap}.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object getTreeMapBaseline(final PreInsertedTreeMapInput input, final Blackhole bh) {
+ return doGet(input, bh);
+ }
+
+ /** Benchmark that retrieves each point in the input from the target map.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object get(final PreInsertedPointMapInput input, final Blackhole bh) {
+ return doGet(input, bh);
+ }
+
+ /** Baseline benchmark for {@link Map#remove(Object)} using a {@link TreeMap}.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object removeTreeMapBaseline(final PreInsertedTreeMapInput input, final Blackhole bh) {
+ return doGet(input, bh);
+ }
+
+ /** Benchmark that removes each point in the input from the target map.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object remove(final PreInsertedPointMapInput input, final Blackhole bh) {
+ return doRemove(input, bh);
+ }
+
+ /** Benchmark for the {@link PointMap#entriesNearToFar(org.apache.commons.geometry.core.Point)} method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object entriesNearToFar(final PreInsertedPointMapInput input, final Blackhole bh) {
+ return doDistanceIteration(
+ input,
+ bh,
+ input.getPoints().size(),
+ PointMap::entriesNearToFar);
+ }
+
+ /** Benchmark for iterating through a portion of the elements returned by the
+ * {@link PointMap#entriesNearToFar(org.apache.commons.geometry.core.Point)} method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object entriesNearToFarPartial(final PreInsertedPointMapInput input, final Blackhole bh) {
+ final int cnt = input.getPoints().size() / 2;
+
+ return doDistanceIteration(
+ input,
+ bh,
+ cnt,
+ PointMap::entriesNearToFar);
+ }
+
+ /** Benchmark for the {@link PointMap#nearestEntry(org.apache.commons.geometry.core.Point)} method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object nearestEntry(final PreInsertedPointMapInput input, final Blackhole bh) {
+ return doDistanceSelect(
+ input,
+ bh,
+ PointMap::nearestEntry);
+ }
+
+ /** Benchmark for the {@link PointMap#entriesFarToNear(org.apache.commons.geometry.core.Point)} method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object entriesFarToNear(final PreInsertedPointMapInput input, final Blackhole bh) {
+ return doDistanceIteration(
+ input,
+ bh,
+ input.getPoints().size(),
+ PointMap::entriesFarToNear);
+ }
+
+ /** Benchmark for iterating through a portion of the results of the
+ * {@link PointMap#entriesFarToNear(org.apache.commons.geometry.core.Point)} method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object entriesFarToNearPartial(final PreInsertedPointMapInput input, final Blackhole bh) {
+ final int cnt = input.getPoints().size() / 2;
+
+ return doDistanceIteration(
+ input,
+ bh,
+ cnt,
+ PointMap::entriesFarToNear);
+ }
+
+ /** Benchmark for the {@link PointMap#farthestEntry(org.apache.commons.geometry.core.Point)} method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return input instance
+ */
+ @Benchmark
+ public Object farthestEntry(final PreInsertedPointMapInput input, final Blackhole bh) {
+ return doDistanceSelect(
+ input,
+ bh,
+ PointMap::farthestEntry);
+ }
}
diff --git a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/PointMap1SImpl.java b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/PointMap1SImpl.java
index 879a2177..f144a675 100644
--- a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/PointMap1SImpl.java
+++ b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/PointMap1SImpl.java
@@ -17,13 +17,15 @@
package org.apache.commons.geometry.spherical;
import java.util.AbstractSet;
+import java.util.ConcurrentModificationException;
import java.util.Iterator;
-import java.util.Map;
import java.util.NavigableMap;
+import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
import org.apache.commons.geometry.core.internal.AbstractPointMap1D;
+import org.apache.commons.geometry.core.internal.DistancedValue;
import org.apache.commons.geometry.spherical.oned.Point1S;
import org.apache.commons.numbers.angle.Angle;
import org.apache.commons.numbers.core.Precision;
@@ -36,22 +38,21 @@ import org.apache.commons.numbers.core.Precision;
final class PointMap1SImpl<V>
extends AbstractPointMap1D<Point1S, V> {
- /** Precision context used to determine floating point equality. */
- private final Precision.DoubleEquivalence precision;
-
/** Minimum key in the map, or null if not known. */
private Point1S minKey;
/** Maximum key in the map, or null if not known. */
private Point1S maxKey;
+ /** Modification version of the map. */
+ private int version;
+
/** Construct a new instance using the given precision object to determine
* floating point equality.
* @param precision object used to determine floating point equality
*/
PointMap1SImpl(final Precision.DoubleEquivalence precision) {
- super((a, b) -> precision.compare(a.getNormalizedAzimuth(), b.getNormalizedAzimuth()));
- this.precision = precision;
+ super(precision, Point1S::getNormalizedAzimuth);
}
/** {@inheritDoc} */
@@ -69,7 +70,7 @@ final class PointMap1SImpl<V>
/** {@inheritDoc} */
@Override
public V remove(final Object key) {
- final Map.Entry<Point1S, V> entry = getEntryInternal((Point1S) key);
+ final Entry<Point1S, V> entry = getEntryInternal((Point1S) key);
if (entry != null) {
final V result = getMap().remove(entry.getKey());
@@ -102,10 +103,22 @@ final class PointMap1SImpl<V>
/** {@inheritDoc} */
@Override
- protected Map.Entry<Point1S, V> getEntryInternal(final Point1S pt) {
+ protected Iterator<Entry<Point1S, V>> nearToFarIterator(final Point1S pt) {
+ return new NearToFarIterator(pt);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Iterator<Entry<Point1S, V>> farToNearIterator(final Point1S pt) {
+ return new NearToFarIterator(pt.antipodal());
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Entry<Point1S, V> getEntryInternal(final Point1S pt) {
final NavigableMap<Point1S, V> map = getMap();
- final Map.Entry<Point1S, V> floor = map.floorEntry(pt);
+ final Entry<Point1S, V> floor = map.floorEntry(pt);
if (floor != null && keyEq(pt, floor)) {
return floor;
} else {
@@ -125,7 +138,7 @@ final class PointMap1SImpl<V>
protected V putInternal(final Point1S key, final V value) {
final NavigableMap<Point1S, V> map = getMap();
- final Map.Entry<Point1S, V> entry = getEntryInternal(key);
+ final Entry<Point1S, V> entry = getEntryInternal(key);
if (entry != null) {
return map.put(entry.getKey(), value);
}
@@ -141,6 +154,8 @@ final class PointMap1SImpl<V>
private void mapUpdated() {
minKey = null;
maxKey = null;
+
+ ++version;
}
/** Return true if {@code pt} is directly equivalent to the key for {@code entry},
@@ -150,8 +165,8 @@ final class PointMap1SImpl<V>
* @return true if {@code pt} is directly equivalent to the key for {@code entry},
* without considering wrap around
*/
- private boolean keyEq(final Point1S pt, final Map.Entry<Point1S, V> entry) {
- return precision.eq(pt.getNormalizedAzimuth(), entry.getKey().getNormalizedAzimuth());
+ private boolean keyEq(final Point1S pt, final Entry<Point1S, V> entry) {
+ return getPrecision().eq(pt.getNormalizedAzimuth(), entry.getKey().getNormalizedAzimuth());
}
/** Return true if the given point wraps around the zero point from high to low
@@ -167,7 +182,7 @@ final class PointMap1SImpl<V>
}
final double adjustedAz = pt.getNormalizedAzimuth() - Angle.TWO_PI;
- return precision.eq(adjustedAz, minKey.getNormalizedAzimuth());
+ return getPrecision().eq(adjustedAz, minKey.getNormalizedAzimuth());
}
return false;
@@ -186,7 +201,7 @@ final class PointMap1SImpl<V>
}
final double adjustedAz = pt.getNormalizedAzimuth() + Angle.TWO_PI;
- return precision.eq(adjustedAz, maxKey.getNormalizedAzimuth());
+ return getPrecision().eq(adjustedAz, maxKey.getNormalizedAzimuth());
}
return false;
@@ -197,7 +212,7 @@ final class PointMap1SImpl<V>
* @param entry map entry
* @return map value or null if {@code entry} is null
*/
- private static <V> V getValue(final Map.Entry<?, V> entry) {
+ private static <V> V getValue(final Entry<?, V> entry) {
return entry != null ?
entry.getValue() :
null;
@@ -230,18 +245,18 @@ final class PointMap1SImpl<V>
/** Entry set view of the map.
*/
private final class EntrySet
- extends AbstractSet<Map.Entry<Point1S, V>> {
+ extends AbstractSet<Entry<Point1S, V>> {
/** {@inheritDoc} */
@Override
public boolean contains(final Object obj) {
- if (obj instanceof Map.Entry) {
- final Map.Entry<?, ?> search = (Map.Entry<?, ?>) obj;
+ if (obj instanceof Entry) {
+ final Entry<?, ?> search = (Entry<?, ?>) obj;
final Object key = search.getKey();
- final Map.Entry<Point1S, V> actual = getEntry((Point1S) key);
+ final Entry<Point1S, V> actual = getEntry((Point1S) key);
if (actual != null) {
- return actual.getKey().eq((Point1S) search.getKey(), precision) &&
+ return actual.getKey().eq((Point1S) search.getKey(), getPrecision()) &&
Objects.equals(actual.getValue(), search.getValue());
}
}
@@ -296,4 +311,121 @@ final class PointMap1SImpl<V>
mapUpdated();
}
}
+
+ /** Iterator that returns the entries in order of ascending distance from
+ * a given reference point.
+ */
+ private final class NearToFarIterator
+ implements Iterator<Entry<Point1S, V>> {
+
+ /** Reference point to measure distances against. */
+ private final Point1S refPt;
+
+ /** Low entry iterator. */
+ private Iterator<Entry<Point1S, V>> low;
+
+ /** High entry iterator. */
+ private Iterator<Entry<Point1S, V>> high;
+
+ /** Low-valued entry. */
+ private DistancedValue<Entry<Point1S, V>> lowEntry;
+
+ /** High-valued entry. */
+ private DistancedValue<Entry<Point1S, V>> highEntry;
+
+ /** Number of entries remaining to retrieve from each iterator. */
+ private int remaining;
+
+ /** Expected modification version of the map. */
+ private int expectedVersion;
+
+ /** Construct a new instance with the given reference point.
+ * @param refPt reference point
+ */
+ NearToFarIterator(final Point1S refPt) {
+ this.refPt = refPt;
+
+ this.low = getMap().descendingMap().tailMap(refPt, false)
+ .entrySet().iterator();
+ this.high = getMap().tailMap(refPt).entrySet().iterator();
+
+ this.remaining = getMap().size();
+
+ this.expectedVersion = version;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean hasNext() {
+ if (lowEntry == null && remaining > 0) {
+ lowEntry = getNextEntry(low);
+
+ if (lowEntry == null) {
+ low = getMap().descendingMap().entrySet().iterator();
+
+ lowEntry = getNextEntry(low);
+ }
+ }
+ if (highEntry == null && remaining > 0) {
+ highEntry = getNextEntry(high);
+
+ if (highEntry == null) {
+ high = getMap().entrySet().iterator();
+
+ highEntry = getNextEntry(high);
+ }
+ }
+
+ return lowEntry != null || highEntry != null;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Entry<Point1S, V> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+
+ checkVersion();
+
+ final DistancedValue<Entry<Point1S, V>> result;
+ if (lowEntry != null &&
+ (highEntry == null || lowEntry.getDistance() <= highEntry.getDistance())) {
+ result = lowEntry;
+ lowEntry = null;
+ } else {
+ result = highEntry;
+ highEntry = null;
+ }
+
+ return result != null ?
+ result.getValue() :
+ null;
+ }
+
+ /** Get a {@link DistancedValue} instance containing the next entry from the given
+ * iterator.
+ * @param it iterator to get the next value from
+ * @return distanced value containing the next entry from the iterator or null if the iterator
+ * does not contain any more elements
+ */
+ private DistancedValue<Entry<Point1S, V>> getNextEntry(final Iterator<Entry<Point1S, V>> it) {
+ if (it.hasNext()) {
+ --remaining;
+
+ final Entry<Point1S, V> entry = it.next();
+ return DistancedValue.of(entry, refPt.distance(entry.getKey()));
+ }
+ 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();
+ }
+ }
+ }
}
diff --git a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/PointMap2SImpl.java b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/PointMap2SImpl.java
index a3c34845..a65463a1 100644
--- a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/PointMap2SImpl.java
+++ b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/PointMap2SImpl.java
@@ -25,6 +25,7 @@ import org.apache.commons.geometry.euclidean.threed.Vector3D;
import org.apache.commons.geometry.spherical.twod.GreatCircle;
import org.apache.commons.geometry.spherical.twod.GreatCircles;
import org.apache.commons.geometry.spherical.twod.Point2S;
+import org.apache.commons.numbers.angle.Angle;
import org.apache.commons.numbers.core.Precision;
/** Internal {@link PointMap} implementation for 2D spherical space.
@@ -52,6 +53,12 @@ final class PointMap2SImpl<V>
/** Second positive quadrant flag. */
private static final int POS2 = 1;
+ /** Bit mask for first location. */
+ private static final int MASK1 = NEG1 | POS1;
+
+ /** Bit mask for second location. */
+ private static final int MASK2 = NEG2 | POS2;
+
/** Location flags for child nodes. */
private static final int[] CHILD_LOCATIONS = {
NEG1 | NEG2,
@@ -73,22 +80,38 @@ final class PointMap2SImpl<V>
return a.eq(b, getPrecision());
}
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguatePointComparison(final Point2S a, final Point2S b) {
+ return Point2S.POLAR_AZIMUTH_ASCENDING_ORDER.compare(a, b);
+ }
+
/** Tree node class for {@link PointMap2SImpl}.
* @param <V> Map value type
*/
private static final class MapNode2S<V>
extends BucketNode<Point2S, V> {
+ /** Primary intersection point of the splitting hyperplanes. */
+ private Point2S splitPoint;
+
/** First hyperplane split. */
- private GreatCircle firstSplit;
+ private GreatCircle firstSplitCircle;
/** Second hyperplane split. */
- private GreatCircle secondSplit;
+ private GreatCircle secondSplitCircle;
+ /** Construct a new instance.
+ * @param map owning map
+ * @param parent parent node; set to null for the root node
+ * @param childIndex index of this node in its parent's child list;
+ * set to {@code -1} for the root node
+ */
MapNode2S(
final AbstractBucketPointMap<Point2S, V> map,
- final BucketNode<Point2S, V> parent) {
- super(map, parent);
+ final BucketNode<Point2S, V> parent,
+ final int childIndex) {
+ super(map, parent, childIndex);
}
/** {@inheritDoc} */
@@ -100,7 +123,8 @@ final class PointMap2SImpl<V>
sum.add(entry.getKey().getVector());
}
- // construct an orthonormal basis
+ // construct an orthonormal basis with u pointing to the centroid
+ // of the points
Vector3D.Unit u = sum.get().multiply(1.0 / MAX_ENTRIES_PER_NODE)
.normalizeOrNull();
if (u == null) {
@@ -115,17 +139,21 @@ final class PointMap2SImpl<V>
}
final Vector3D.Unit w = u.cross(v).normalize();
- // construct the two great circles
- firstSplit = GreatCircles.fromPole(v.add(w), getPrecision());
- secondSplit = GreatCircles.fromPole(v.negate().add(w), getPrecision());
+ // set the split point
+ splitPoint = Point2S.from(u);
+
+ // construct the splitting hyperplanes as two great circles intersecting at
+ // the split point and with orthogonal poles
+ firstSplitCircle = GreatCircles.fromPoleAndU(v.add(w), u, getPrecision());
+ secondSplitCircle = GreatCircles.fromPoleAndU(v.negate().add(w), u, getPrecision());
}
/** {@inheritDoc} */
@Override
protected int getSearchLocation(final Point2S pt) {
- int loc = getSearchLocationValue(firstSplit.classify(pt), NEG1, POS1);
+ int loc = getSearchLocationValue(firstSplitCircle.classify(pt), NEG1, POS1);
- loc |= getSearchLocationValue(secondSplit.classify(pt), NEG2, POS2);
+ loc |= getSearchLocationValue(secondSplitCircle.classify(pt), NEG2, POS2);
return loc;
}
@@ -133,11 +161,11 @@ final class PointMap2SImpl<V>
/** {@inheritDoc} */
@Override
protected int getInsertLocation(final Point2S pt) {
- int loc = firstSplit.offset(pt) > 0.0 ?
+ int loc = firstSplitCircle.offset(pt) > 0.0 ?
POS1 :
NEG1;
- loc |= secondSplit.offset(pt) > 0.0 ?
+ loc |= secondSplitCircle.offset(pt) > 0.0 ?
POS2 :
NEG2;
@@ -156,8 +184,60 @@ final class PointMap2SImpl<V>
protected void makeLeaf(final List<Entry<Point2S, V>> leafEntries) {
super.makeLeaf(leafEntries);
- firstSplit = null;
- secondSplit = null;
+ splitPoint = null;
+ firstSplitCircle = null;
+ secondSplitCircle = null;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getMinChildDistance(final int childIdx, final Point2S pt, final int ptLoc) {
+ final int childLoc = CHILD_LOCATIONS[childIdx];
+
+ final boolean sameFirst = (ptLoc & MASK1) == (childLoc & MASK1);
+ final boolean sameSecond = (ptLoc & MASK2) == (childLoc & MASK2);
+
+ if (sameFirst) {
+ return sameSecond ?
+ 0d :
+ Math.abs(secondSplitCircle.offset(pt));
+ } else if (sameSecond) {
+ return Math.abs(firstSplitCircle.offset(pt));
+ }
+
+ // the reference point is in the opposite quadrant; this means that the
+ // closest point will be either the split point or the antipode of the
+ // split point
+ final double splitPointDist = pt.distance(splitPoint);
+ return splitPointDist > Angle.PI_OVER_TWO ?
+ Math.PI - splitPointDist :
+ splitPointDist;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getMaxChildDistance(final int childIdx, final Point2S pt, final int ptLoc) {
+ final int childLoc = CHILD_LOCATIONS[childIdx];
+
+ final boolean oppositeFirst = (ptLoc & MASK1) != (childLoc & MASK1);
+ final boolean oppositeSecond = (ptLoc & MASK2) != (childLoc & MASK2);
+
+
+ if (oppositeFirst) {
+ return oppositeSecond ?
+ Math.PI :
+ Math.PI - Math.abs(secondSplitCircle.offset(pt));
+ } else if (oppositeSecond) {
+ return Math.PI - Math.abs(firstSplitCircle.offset(pt));
+ }
+
+ // the reference point is in the same quadrant; this means that the
+ // farthest point will be either the split point or the antipode of the
+ // split point
+ final double splitPointDist = pt.distance(splitPoint);
+ return splitPointDist > Angle.PI_OVER_TWO ?
+ splitPointDist :
+ Math.PI - splitPointDist;
}
/** Get an encoded search location for the given hyperplane location.
diff --git a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/oned/PointMap1STest.java b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/oned/PointMap1STest.java
index 66449cc5..56f49df1 100644
--- a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/oned/PointMap1STest.java
+++ b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/oned/PointMap1STest.java
@@ -129,4 +129,10 @@ class PointMap1STest extends PointMapTestBase<Point1S> {
protected boolean eq(final Point1S a, final Point1S b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Point1S a, final Point1S b) {
+ return Point1S.NORMALIZED_AZIMUTH_ASCENDING_ORDER.compare(a, b);
+ }
}
diff --git a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/oned/PointSet1STest.java b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/oned/PointSet1STest.java
index ec5626ae..5b28ddd2 100644
--- a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/oned/PointSet1STest.java
+++ b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/oned/PointSet1STest.java
@@ -81,4 +81,10 @@ class PointSet1STest extends PointSetTestBase<Point1S> {
protected boolean eq(final Point1S a, final Point1S b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Point1S a, final Point1S b) {
+ return Point1S.NORMALIZED_AZIMUTH_ASCENDING_ORDER.compare(a, b);
+ }
}
diff --git a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/PointMap2STest.java b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/PointMap2STest.java
index ee3cd4e8..f9b67631 100644
--- a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/PointMap2STest.java
+++ b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/PointMap2STest.java
@@ -186,4 +186,10 @@ class PointMap2STest extends PointMapTestBase<Point2S> {
protected boolean eq(final Point2S a, final Point2S b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Point2S a, final Point2S b) {
+ return Point2S.POLAR_AZIMUTH_ASCENDING_ORDER.compare(a, b);
+ }
}
diff --git a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/PointSet2STest.java b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/PointSet2STest.java
index ee121b76..dda5be09 100644
--- a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/PointSet2STest.java
+++ b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/PointSet2STest.java
@@ -114,4 +114,10 @@ class PointSet2STest extends PointSetTestBase<Point2S> {
protected boolean eq(final Point2S a, final Point2S b, final Precision.DoubleEquivalence precision) {
return a.eq(b, precision);
}
+
+ /** {@inheritDoc} */
+ @Override
+ protected int disambiguateNearToFarOrder(final Point2S a, final Point2S b) {
+ return Point2S.POLAR_AZIMUTH_ASCENDING_ORDER.compare(a, b);
+ }
}