[GitHub] [commons-geometry] darkma773r commented on a change in pull request #194: GEOMETRY-142: PointMap and PointSet
darkma773r commented on a change in pull request #194:
URL: https://github.com/apache/commons-geometry/pull/194#discussion_r827563187
##
File path:
commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap3DImpl.java
##
@@ -0,0 +1,174 @@
+/*
+ * 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.euclidean;
+
+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.threed.Vector3D;
+import org.apache.commons.numbers.core.Precision;
+
+/** Internal {@link PointMap3D} implementation.
+ * @param Map value type
+ */
+final class PointMap3DImpl
+extends AbstractBucketPointMap
+implements PointMap {
+
+/** Number of children per node. */
+private static final int NODE_CHILD_COUNT = 8;
+
+/** Max entries per node. This value was determined empirically was chosen
to
Review comment:
Fixed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@commons.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
[GitHub] [commons-geometry] darkma773r commented on a change in pull request #194: GEOMETRY-142: PointMap and PointSet
darkma773r commented on a change in pull request #194:
URL: https://github.com/apache/commons-geometry/pull/194#discussion_r827563111
##
File path:
commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap3DImpl.java
##
@@ -0,0 +1,174 @@
+/*
+ * 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.euclidean;
+
+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.threed.Vector3D;
+import org.apache.commons.numbers.core.Precision;
+
+/** Internal {@link PointMap3D} implementation.
+ * @param Map value type
+ */
+final class PointMap3DImpl
+extends AbstractBucketPointMap
+implements PointMap {
+
+/** Number of children per node. */
+private static final int NODE_CHILD_COUNT = 8;
+
+/** Max entries per node. This value was determined empirically was chosen
to
+ * provide a balance between having a small number of entries in each node
when
+ * searching and having a large number of samples to provide a good split
point
+ * during insertion.
Review comment:
Good idea. Done.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@commons.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
[GitHub] [commons-geometry] darkma773r commented on a change in pull request #194: GEOMETRY-142: PointMap and PointSet
darkma773r commented on a change in pull request #194:
URL: https://github.com/apache/commons-geometry/pull/194#discussion_r827562722
##
File path:
commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/pointmap/RebuildingKDTree.java
##
@@ -0,0 +1,259 @@
+/*
+ * 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.examples.jmh.euclidean.pointmap;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+import org.apache.commons.geometry.euclidean.threed.Vector3D;
+import org.apache.commons.numbers.core.Precision.DoubleEquivalence;
+
+/** {@link KDTree} subclass that rebuilds the tree periodically in an
+ * attempt to restrict the overall height of the tree.
+ * @param Value type
+ */
+public class RebuildingKDTree extends KDTree {
+
+/** Default rebuild maximum. */
+private static final int DEFAULT_REBUILD_MAX = 16;
+
+/** Maximum size of the tree before it is rebuilt. */
+private int rebuildMax = DEFAULT_REBUILD_MAX;
+
+/** Minimum size of the tree before it is rebuilt. */
+private int rebuildMin;
+
+/** Construct a new instance.
+ * @param precision precision context
+ */
+public RebuildingKDTree(final DoubleEquivalence precision) {
+super(precision);
+}
+
+/** {@inheritDoc} */
+@Override
+public V put(final Vector3D key, final V value) {
+final V result = super.put(key, value);
+
+if (size() >= rebuildMax) {
+rebuild();
+}
+
+return result;
+}
+
+/** {@inheritDoc} */
+@Override
+public V remove(final Object key) {
+final V result = super.remove(key);
+
+if (size() <= rebuildMin) {
+rebuild();
+}
+
+return result;
+}
+
+/**
+ * Rebuild the tree, attempting to reduce the tree depth.
+ */
+public void rebuild() {
+int n = size();
+if (n > 0) {
+// construct an array list containing all of the tree nodes
+final List> nodes = collectNodes();
+
+// rebuild recursively and set the new root
+final KDTreeNode newRoot = rebuildRecursive(nodes, 0, n, 0);
+
+setRoot(newRoot);
+}
+
+rebuildMax = Math.max(DEFAULT_REBUILD_MAX, 2 * n);
+rebuildMin = n / 2;
+}
+
+/** Get a list containing all nodes in the tree. The node connections are
all cleared.
+ * @return list containing all nodes in the tree
+ */
+protected List> collectNodes() {
+final List> nodes = new ArrayList<>(size());
+collectNodesRecursive(getRoot(), nodes);
+
+return nodes;
+}
+
+/** Add nodes in the subtree rooted at {@code curr} to {@code nodes}. The
node connection
+ * references are all cleared.
+ * @param curr subtree root node
+ * @param nodes node list
+ */
+protected void collectNodesRecursive(final KDTreeNode curr, final
List> nodes) {
+if (curr != null) {
+collectNodesRecursive(curr.getLeft(), nodes);
+nodes.add(curr);
+collectNodesRecursive(curr.getRight(), nodes);
+
+curr.setParent(null);
+curr.setLeft(null);
+curr.setRight(null);
+}
+}
+
+/** Recursively rebuild the tree using the specified node sublist.
+ * @param nodes node list
+ * @param startIdx sub list start index (inclusive)
+ * @param endIdx sub list end index (exclusive)
+ * @param depth node depth
+ * @return the root of the subtree containing the nodes between {@code
startIdx} and {@code endIdx}
+ */
+protected KDTreeNode rebuildRecursive(final List> nodes,
final int startIdx, final int endIdx,
+final int depth) {
+final CutDimension cutDimension = getCutDimensionForDepth(depth);
+
+final KDTreeNode node;
+if ((endIdx - startIdx) < 2) {
+// only a single node here
+node = nodes.get(startIdx);
+} else {
+final int splitIdx = partition(nodes, startIdx, endIdx,
cutDimension);
+
+node = nodes.get(splitIdx);
+
+if
[GitHub] [commons-geometry] darkma773r commented on a change in pull request #194: GEOMETRY-142: PointMap and PointSet
darkma773r commented on a change in pull request #194:
URL: https://github.com/apache/commons-geometry/pull/194#discussion_r825459403
##
File path:
commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap2DImpl.java
##
@@ -0,0 +1,151 @@
+/*
+ * 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.euclidean;
+
+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.twod.Vector2D;
+import org.apache.commons.numbers.core.Precision;
+
+/** Internal {@link PointMap2D} implementation.
Review comment:
Darn. Those were extensions of `PointMap` specific to those spaces. I
ended up removing them since they didn't really add anything. I thought I
removed all of the references in the docs but I guess not.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@commons.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
[GitHub] [commons-geometry] darkma773r commented on a change in pull request #194: GEOMETRY-142: PointMap and PointSet
darkma773r commented on a change in pull request #194:
URL: https://github.com/apache/commons-geometry/pull/194#discussion_r825459133
##
File path:
commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/PointMap3DImpl.java
##
@@ -0,0 +1,174 @@
+/*
+ * 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.euclidean;
+
+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.threed.Vector3D;
+import org.apache.commons.numbers.core.Precision;
+
+/** Internal {@link PointMap3D} implementation.
+ * @param Map value type
+ */
+final class PointMap3DImpl
+extends AbstractBucketPointMap
+implements PointMap {
+
+/** Number of children per node. */
+private static final int NODE_CHILD_COUNT = 8;
+
+/** Max entries per node. This value was determined empirically was chosen
to
+ * provide a balance between having a small number of entries in each node
when
+ * searching and having a large number of samples to provide a good split
point
+ * during insertion.
+ */
+private static final int MAX_ENTRIES_PER_NODE = 32;
+
+/** X negative octant flag. */
+private static final int XNEG = 1 << 5;
+
+/** X postive octant flag. */
+private static final int XPOS = 1 << 4;
+
+/** Y negative octant flag. */
+private static final int YNEG = 1 << 3;
+
+/** Y positive octant flag. */
+private static final int YPOS = 1 << 2;
+
+/** Z negative octant flag. */
+private static final int ZNEG = 1 << 1;
+
+/** Z positive octant flag. */
+private static final int ZPOS = 1;
+
+/** Octant location flags for child nodes. */
+private static final int[] CHILD_LOCATIONS = {
+XNEG | YNEG | ZNEG,
+XNEG | YNEG | ZPOS,
+XNEG | YPOS | ZNEG,
+XNEG | YPOS | ZPOS,
+
+XPOS | YNEG | ZNEG,
+XPOS | YNEG | ZPOS,
+XPOS | YPOS | ZNEG,
+XPOS | YPOS | ZPOS
+};
+
+/** Construct a new instance using the given precision context to determine
+ * floating point equality.
+ * @param precision precision context
+ */
+PointMap3DImpl(final Precision.DoubleEquivalence precision) {
+super(MapNode3D::new,
Review comment:
Lol! It's one of my favorite tricks at the moment :-)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@commons.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
[GitHub] [commons-geometry] darkma773r commented on a change in pull request #194: GEOMETRY-142: PointMap and PointSet
darkma773r commented on a change in pull request #194:
URL: https://github.com/apache/commons-geometry/pull/194#discussion_r825458882
##
File path:
commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/PointMapAsSetAdapter.java
##
@@ -0,0 +1,89 @@
+/*
+ * 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.AbstractSet;
+import java.util.Iterator;
+
+import org.apache.commons.geometry.core.Point;
+import org.apache.commons.geometry.core.collection.PointMap;
+import org.apache.commons.geometry.core.collection.PointSet;
+
+/** Class that exposes a {@link PointMap} as a {@link PointSet}.
+ * @param Point type
+ * @param Map type
+ */
+public class PointMapAsSetAdapter, M extends PointMap>
+extends AbstractSet
+implements PointSet {
+
+/** Dummy map value used to indicate presence in the set. */
+private static final Object PRESENT = new Object();
+
+/** Backing map. */
+private final M map;
+
+/** Construct a new instance that use the argument as its backing map.
+ * @param backingMap backing map
+ */
+public PointMapAsSetAdapter(final M backingMap) {
+this.map = backingMap;
+}
+
+/** {@inheritDoc} */
+@Override
+public P resolve(final P pt) {
+return map.resolveKey(pt);
+}
+
+/** {@inheritDoc} */
+@Override
+public Iterator iterator() {
+return map.keySet().iterator();
+}
+
+/** {@inheritDoc} */
+@Override
+public int size() {
+return map.size();
+}
+
+/** {@inheritDoc} */
+@Override
+public boolean contains(final Object obj) {
+return map.containsKey(obj);
+}
+
+/** {@inheritDoc} */
+@Override
+public boolean add(final P pt) {
+return map.put(pt, PRESENT) == null;
+}
+
+/** {@inheritDoc} */
+@Override
+public boolean remove(final Object obj) {
+final Object prev = map.remove(obj);
+return GeometryInternalUtils.sameInstance(prev, PRESENT);
Review comment:
This would indeed cause an issue if a user followed your steps above.
I'm not picturing `PointMapAsSetAdapter` being used directly by users, hence
it's presence in the `internal` package in core. I should probably make that
explicit in the javadocs, though.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@commons.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
[GitHub] [commons-geometry] darkma773r commented on a change in pull request #194: GEOMETRY-142: PointMap and PointSet
darkma773r commented on a change in pull request #194:
URL: https://github.com/apache/commons-geometry/pull/194#discussion_r825304646
##
File path:
commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/AbstractBucketPointMap.java
##
@@ -0,0 +1,1063 @@
+/*
+ * 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.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Arrays;
+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.Set;
+import java.util.function.BiFunction;
+
+import org.apache.commons.geometry.core.Point;
+import org.apache.commons.geometry.core.collection.PointMap;
+import org.apache.commons.numbers.core.Precision;
+
+/** Abstract tree-based {@link PointMap} implementation that stores entries in
bucket nodes
+ * that are split once a certain entry count threshold is reached. The main
goal of this class
+ * is to provide a generic, multidimensional implementation that maintains
reasonable performance
+ * regardless of point count and insertion order. Like other tree data
structures, performance
+ * is tied closely to tree depth, which can vary depending on insertion order
for a given set of
+ * points. In order to help maintain performance in cases of non-optimal point
insertion order,
+ * this class uses a strategy of "point folding", implemented as follows:
+ *
+ * Two separate tree roots are maintained by the map: a primary root and
a secondary root.
+ * Entries are added to the primary root until the it reaches its
capacity and is split using
+ * an algorithm specific to the space and dimension. At this point, the
populated primary root
+ * becomes the secondary root and a new, empty primary root is
created.
+ * Points are inserted into the new primary root as before. However, for
each new point inserted,
+ * an existing point is removed from the secondary root and inserted into
the primary root.
+ * Points are moved from the secondary root and inserted into the primary
root in this way until the
+ * secondary root is empty. At this point, the primary root becomes the
secondary root and another
+ * primary root is created.
+ *
+ * In this way, previously inserted points can apply a balancing influence on
the low levels of the tree
+ * as new points are inserted.
+ * @param Point type
+ * @param Map value type
+ */
+public abstract class AbstractBucketPointMap, V>
Review comment:
Good point. I'll add that to the docs here and also to the factory
methods in `EuclideanCollections` and `SphericalCollections`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@commons.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
