AbstractPathConnector.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.geometry.euclidean.internal;
import java.util.ArrayList;
import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;
/** Abstract base class for joining unconnected path elements into connected, directional
* paths. The connection algorithm is exposed as a set of protected methods, allowing subclasses
* to define their own public API. Implementations must supply their own subclass of {@link ConnectableElement}
* specific for the objects being connected.
*
* <p>The connection algorithm proceeds as follows:
* <ul>
* <li>Create a sorted list of {@link ConnectableElement}s.</li>
* <li>For each element, attempt to find other elements with start points next the
* first instance's end point by calling {@link ConnectableElement#getConnectionSearchKey()} and
* using the returned instance to locate a search start location in the sorted element list.</li>
* <li>Search up through the sorted list from the start location, testing each element for possible connectivity
* with {@link ConnectableElement#canConnectTo(AbstractPathConnector.ConnectableElement)}. Collect possible
* connections in a list. Terminate the search when
* {@link ConnectableElement#shouldContinueConnectionSearch(AbstractPathConnector.ConnectableElement, boolean)}
* returns false.
* <li>Repeat the previous step searching downward through the list from the start location.</li>
* <li>Select the best connection option from the list of possible connections, using
* {@link #selectPointConnection(AbstractPathConnector.ConnectableElement, List)}
* and/or {@link #selectConnection(AbstractPathConnector.ConnectableElement, List)} when multiple possibilities
* are found.</li>
* <li>Repeat the above steps for each element. When done, the elements represent a linked list
* of connected paths.</li>
* </ul>
*
* <p>This class is not thread-safe.</p>
*
* @param <E> Element type
* @see ConnectableElement
*/
public abstract class AbstractPathConnector<E extends AbstractPathConnector.ConnectableElement<E>> {
/** List of path elements. */
private final NavigableSet<E> pathElements = new TreeSet<>();
/** View of the path element set in descending order. */
private final NavigableSet<E> pathElementsDescending = pathElements.descendingSet();
/** List used to store possible connections for the current element. */
private final List<E> possibleConnections = new ArrayList<>();
/** List used to store possible point-like (zero-length) connections for the current element. */
private final List<E> possiblePointConnections = new ArrayList<>();
/** Add a collection of path elements to the connector and attempt to connect each new element
* with previously added ones.
* @param elements path elements to connect
*/
protected void connectPathElements(final Iterable<E> elements) {
elements.forEach(this::addPathElement);
for (final E element : elements) {
makeForwardConnection(element);
}
}
/** Add a single path element to the connector, leaving it unconnected until a later call to
* to {@link #connectPathElements(Iterable)} or {@link #computePathRoots()}.
* @param element value to add to the connector
* @see #connectPathElements(Iterable)
* @see #computePathRoots()
*/
protected void addPathElement(final E element) {
pathElements.add(element);
}
/** Compute all connected paths and return a list of path elements representing
* the roots (start locations) of each. Each returned element is the head of a
* (possibly circular) linked list that follows a connected path.
*
* <p>The connector is reset after this call. Further calls to add elements
* will result in new paths being generated.</p>
* @return a list of root elements for the computed connected paths
*/
protected List<E> computePathRoots() {
for (final E element : pathElements) {
followForwardConnections(element);
}
final List<E> rootEntries = new ArrayList<>();
E root;
for (final E element : pathElements) {
root = element.exportPath();
if (root != null) {
rootEntries.add(root);
}
}
pathElements.clear();
possibleConnections.clear();
possiblePointConnections.clear();
return rootEntries;
}
/** Find and follow forward connections from the given start element.
* @param start element to begin the connection operation with
*/
private void followForwardConnections(final E start) {
E current = start;
while (current != null && current.hasEnd() && !current.hasNext()) {
current = makeForwardConnection(current);
}
}
/** Connect the end point of the given element to the start point of another element. Returns
* the newly connected element or null if no forward connection was made.
* @param element element to connect
* @return the next element in the path or null if no connection was made
*/
private E makeForwardConnection(final E element) {
findPossibleConnections(element);
E next = null;
// select from all available connections, handling point-like segments first
if (!possiblePointConnections.isEmpty()) {
next = (possiblePointConnections.size() == 1) ?
possiblePointConnections.get(0) :
selectPointConnection(element, possiblePointConnections);
} else if (!possibleConnections.isEmpty()) {
next = (possibleConnections.size() == 1) ?
possibleConnections.get(0) :
selectConnection(element, possibleConnections);
}
if (next != null) {
element.connectTo(next);
}
return next;
}
/** Find possible connections for the given element and place them in the
* {@link #possibleConnections} and {@link #possiblePointConnections} lists.
* @param element the element to find connections for
*/
private void findPossibleConnections(final E element) {
possibleConnections.clear();
possiblePointConnections.clear();
if (element.hasEnd()) {
final E searchKey = element.getConnectionSearchKey();
// search up
for (final E candidate : pathElements.tailSet(searchKey)) {
if (!addPossibleConnection(element, candidate) &&
!element.shouldContinueConnectionSearch(candidate, true)) {
break;
}
}
// search down
for (final E candidate : pathElementsDescending.tailSet(searchKey, false)) {
if (!addPossibleConnection(element, candidate) &&
!element.shouldContinueConnectionSearch(candidate, false)) {
break;
}
}
}
}
/** Add the candidate to one of the connection lists if it represents a possible connection. Returns
* true if the candidate was added, otherwise false.
* @param element element to check for connections with
* @param candidate candidate connection element
* @return true if the candidate is a possible connection
*/
private boolean addPossibleConnection(final E element, final E candidate) {
if (element != candidate &&
!candidate.hasPrevious() &&
candidate.hasStart() &&
element.canConnectTo(candidate)) {
if (element.endPointsEq(candidate)) {
possiblePointConnections.add(candidate);
} else {
possibleConnections.add(candidate);
}
return true;
}
return false;
}
/** Method called to select a connection to use for a given element when multiple zero-length connections are
* available. The algorithm here attempts to choose the point most likely to produce a logical path by selecting
* the outgoing element with the smallest relative angle with the incoming element, with unconnected element
* preferred over ones that are already connected (thereby allowing other connections to occur in the path).
* @param incoming the incoming element
* @param outgoingList list of available outgoing point-like connections
* @return the connection to use
*/
protected E selectPointConnection(final E incoming, final List<E> outgoingList) {
double angle;
boolean isUnconnected;
double smallestAngle = 0.0;
E bestElement = null;
boolean bestIsUnconnected = false;
for (final E outgoing : outgoingList) {
angle = Math.abs(incoming.getRelativeAngle(outgoing));
isUnconnected = !outgoing.hasNext();
if (bestElement == null || (!bestIsUnconnected && isUnconnected) ||
(bestIsUnconnected == isUnconnected && angle < smallestAngle)) {
smallestAngle = angle;
bestElement = outgoing;
bestIsUnconnected = isUnconnected;
}
}
return bestElement;
}
/** Method called to select a connection to use for a given segment when multiple non-length-zero
* connections are available. In this case, the selection of the outgoing connection depends only
* on the desired characteristics of the connected path.
* @param incoming the incoming segment
* @param outgoing list of available outgoing connections; will always contain at least
* two elements
* @return the connection to use
*/
protected abstract E selectConnection(E incoming, List<E> outgoing);
/** Class used to represent connectable path elements for use with {@link AbstractPathConnector}.
* Subclasses must fulfill the following requirements in order for path connection operations
* to work correctly:
* <ul>
* <li>Implement {@link #compareTo(Object)} such that elements are sorted by their start
* point locations. Other criteria may be used as well but elements with start points in close
* proximity must be grouped together.</li>
* <li>Implement {@link #getConnectionSearchKey()} such that it returns an instance that will be placed
* next to elements with start points close to the current instance's end point when sorted with
* {@link #compareTo(Object)}.</li>
* <li>Implement {@link #shouldContinueConnectionSearch(AbstractPathConnector.ConnectableElement, boolean)}
* such that it returns false when the search for possible connections through a sorted list of elements
* may terminate.</li>
* </ul>
*
* @param <E> Element type
* @see AbstractPathConnector
*/
public abstract static class ConnectableElement<E extends ConnectableElement<E>>
implements Comparable<E> {
/** Next connected element. */
private E next;
/** Previous connected element. */
private E previous;
/** Flag set to true when this element has exported its value to a path. */
private boolean exported;
/** Return true if the instance is connected to another element's start point.
* @return true if the instance has a next element
*/
public boolean hasNext() {
return next != null;
}
/** Get the next connected element in the path, if any.
* @return the next connected segment in the path; may be null
*/
public E getNext() {
return next;
}
/** Set the next connected element for this path. This is intended for
* internal use only. Callers should use the {@link #connectTo(AbstractPathConnector.ConnectableElement)}
* method instead.
* @param next next path element
*/
protected void setNext(final E next) {
this.next = next;
}
/** Return true if another element is connected to this instance's start point.
* @return true if the instance has a previous element
*/
public boolean hasPrevious() {
return previous != null;
}
/** Get the previous connected element in the path, if any.
* @return the previous connected element in the path; may be null
*/
public E getPrevious() {
return previous;
}
/** Set the previous connected element for this path. This is intended for
* internal use only. Callers should use the {@link #connectTo(AbstractPathConnector.ConnectableElement)}
* method instead.
* @param previous previous path element
*/
protected void setPrevious(final E previous) {
this.previous = previous;
}
/** Connect this instance's end point to the given element's start point. No validation
* is performed in this method. The {@link #canConnectTo(AbstractPathConnector.ConnectableElement)}
* method must have been called previously.
* @param nextElement the next element in the path
*/
public void connectTo(final E nextElement) {
setNext(nextElement);
nextElement.setPrevious(getSelf());
}
/** Export the path that this element belongs to, returning the root
* segment. This method traverses all connected element, sets their
* exported flags to true, and returns the root element of the path
* (or this element in the case of a loop). Each path can only be
* exported once. Later calls to this method on this instance or any of its
* connected elements will return null.
* @return the root of the path or null if the path that this element
* belongs to has already been exported
*/
public E exportPath() {
if (markExported()) {
// export the connected portions of the path, moving both
// forward and backward
E current;
E root = getSelf();
// forward
current = next;
while (current != null && current.markExported()) {
current = current.getNext();
}
// backward
current = previous;
while (current != null && current.markExported()) {
root = current;
current = current.getPrevious();
}
return root;
}
return null;
}
/** Set the export flag for this instance to true. Returns true
* if the flag was changed and false otherwise.
* @return true if the flag was changed and false if it was
* already set to true
*/
protected boolean markExported() {
if (!exported) {
exported = true;
return true;
}
return false;
}
/** Return true if this instance has a start point that can be
* connected to another element's end point.
* @return true if this instance has a start point that can be
* connected to another element's end point
*/
public abstract boolean hasStart();
/** Return true if this instance has an end point that can be
* connected to another element's start point.
* @return true if this instance has an end point that can be
* connected to another element's start point
*/
public abstract boolean hasEnd();
/** Return true if the end point of this instance should be considered
* equivalent to the end point of the argument.
* @param other element to compare end points with
* @return true if this instance has an end point equivalent to that
* of the argument
*/
public abstract boolean endPointsEq(E other);
/** Return true if this instance's end point can be connected to
* the argument's start point.
* @param nextElement candidate for the next element in the path; this value
* is guaranteed to not be null and to contain a start point
* @return true if this instance's end point can be connected to
* the argument's start point
*/
public abstract boolean canConnectTo(E nextElement);
/** Return the relative angle between this element and the argument.
* @param other element to compute the angle with
* @return the relative angle between this element and the argument
*/
public abstract double getRelativeAngle(E other);
/** Get a new instance used as a search key to help locate other elements
* with start points matching this instance's end point. The only restriction
* on the returned instance is that it be compatible with the implementation
* class' {@link #compareTo(Object)} method.
* @return a new instance used to help locate other path elements with start
* points equivalent to this instance's end point
*/
public abstract E getConnectionSearchKey();
/** Return true if the search for possible connections should continue through
* the sorted set of possible path elements given the current candidate element
* and search direction. The search operation stops for the given direction
* when this method returns false.
* @param candidate last tested candidate connection element
* @param ascending true if the search is proceeding in an ascending direction;
* false otherwise
* @return true if the connection search should continue
*/
public abstract boolean shouldContinueConnectionSearch(E candidate, boolean ascending);
/** Return the current instance as the generic type.
* @return the current instance as the generic type.
*/
protected abstract E getSelf();
}
}