kinow commented on a change in pull request #194: URL: https://github.com/apache/commons-geometry/pull/194#discussion_r825277494
########## 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: + * <ul> + * <li>Two separate tree roots are maintained by the map: a primary root and a secondary root.</li> + * <li>Entries are added to the primary root until the it reaches its capacity and is split using + * an algorithm specific to the space and dimension. At this point, the populated primary root + * becomes the secondary root and a new, empty primary root is created.</li> + * <li>Points are inserted into the new primary root as before. However, for each new point inserted, + * an existing point is removed from the secondary root and inserted into the primary root.</li> + * <li>Points are moved from the secondary root and inserted into the primary root in this way until the + * secondary root is empty. At this point, the primary root becomes the secondary root and another + * primary root is created.</li> + * </ul> + * In this way, previously inserted points can apply a balancing influence on the low levels of the tree + * as new points are inserted. + * @param <P> Point type + * @param <V> Map value type + */ +public abstract class AbstractBucketPointMap<P extends Point<P>, V> Review comment: Maybe indicate in the docs whether this class or its implementations are thread-safe? -- 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
