LinePath.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.twod.path;

import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import org.apache.commons.geometry.core.Sized;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.euclidean.twod.BoundarySource2D;
import org.apache.commons.geometry.euclidean.twod.Line;
import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
import org.apache.commons.geometry.euclidean.twod.Lines;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.numbers.core.Precision;

/** Class representing a connected path of {@link LineConvexSubset line convex subsets}.
 * The elements in the path are connected end to end, with the end vertex of the previous
 * element equivalent to the start vertex of the next element. Elements are not required to
 * be finite. However, since path elements are connected, only the first element and/or last
 * element may be infinite.
 *
 * <p>Instances of this class are guaranteed to be immutable.</p>
 */
public class LinePath implements BoundarySource2D, Sized {
    /** Line path instance containing no elements. */
    private static final LinePath EMPTY = new LinePath(Collections.emptyList());

    /** The line convex subsets comprising the path. */
    private final List<LineConvexSubset> elements;

    /** Simple constructor. Callers are responsible for ensuring that the given list of
     * line subsets defines a valid path. No validation is performed.
     * @param elements elements defining the path.
     */
    LinePath(final List<LineConvexSubset> elements) {
        this.elements = Collections.unmodifiableList(elements);
    }

    /** {@inheritDoc} */
    @Override
    public Stream<LineConvexSubset> boundaryStream() {
        return getElements().stream();
    }

    /** Get the sequence of line subsets comprising the path.
     * @return the sequence of line subsets comprising the path
     */
    public List<LineConvexSubset> getElements() {
        return elements;
    }

    /** Get the line subset at the start of the path or null if the path is empty. If the
     * path consists of a single line subset, then the returned instance with be the same
     * as that returned by {@link #getEnd()}.
     * @return the line subset at the start of the path or null if the path is empty
     * @see #getEnd()
     */
    public LineConvexSubset getStart() {
        if (!isEmpty()) {
            return elements.get(0);
        }
        return null;
    }

    /** Get the line subset at the end of the path or null if the path is empty. If the
     * path consists of a single line subset, then the returned instance with be the same
     * as that returned by {@link #getStart()}.
     * @return the line subset at the end of the path or null if the path is empty
     * @see #getStart()
     */
    public LineConvexSubset getEnd() {
        if (!isEmpty()) {
            return elements.get(elements.size() - 1);
        }
        return null;
    }

    /** Get the sequence of vertices defined by the path. Vertices appear in the
     * list as many times as they are visited in the path. For example, the vertex
     * sequence for a closed path contains the start point at the beginning
     * of the list as well as the end.
     * @return the sequence of vertices defined by the path
     */
    public List<Vector2D> getVertexSequence() {
        final List<Vector2D> sequence = new ArrayList<>();

        Vector2D pt;

        // add the start point, if present
        pt = getStartVertex();
        if (pt != null) {
            sequence.add(pt);
        }

        // add end points
        for (final LineConvexSubset sub : elements) {
            pt = sub.getEndPoint();
            if (pt != null) {
                sequence.add(pt);
            }
        }

        return sequence;
    }

    /** Return true if the path has an element with infinite size.
     * @return true if the path is infinite
     */
    @Override
    public boolean isInfinite() {
        return !isEmpty() && (getStartVertex() == null || getEndVertex() == null);
    }

    /** Return true if the path has a finite size. This will be true if there are
     * no elements in the path or if all elements have a finite length.
     * @return true if the path is finite
     */
    @Override
    public boolean isFinite() {
        return !isInfinite();
    }

    /** {@inheritDoc}
     *
     * <p>The size of the path is defined as the sum of the sizes (lengths) of all path elements.</p>
     */
    @Override
    public double getSize() {
        double sum = 0.0;
        for (final LineConvexSubset element : elements) {
            sum += element.getSize();
        }

        return sum;
    }

    /** Return true if the path does not contain any elements.
     * @return true if the path does not contain any elements
     */
    public boolean isEmpty() {
        return elements.isEmpty();
    }

    /** Return true if the path is closed, meaning that the end point for the last
     * element is equivalent to the start point of the first.
     * @return true if the end point for the last element is equivalent to the
     *      start point for the first
     */
    public boolean isClosed() {
        final LineConvexSubset endElement = getEnd();

        if (endElement != null) {
            final Vector2D start = getStartVertex();
            final Vector2D end = endElement.getEndPoint();

            return start != null && end != null && start.eq(end, endElement.getPrecision());
        }

        return false;
    }

    /** Transform this instance with the argument, returning the result in a new instance.
     * @param transform the transform to apply
     * @return a new instance, transformed by the argument
     */
    public LinePath transform(final Transform<Vector2D> transform) {
        if (!isEmpty()) {
            final List<LineConvexSubset> transformed = elements.stream()
                .map(s -> s.transform(transform))
                .collect(Collectors.toCollection(ArrayList::new));

            return new LinePath(transformed);
        }

        return this;
    }

    /** Return a new instance with all line subset directions, and their order,
     * reversed. The last line subset in this instance will be the first in the
     * returned instance.
     * @return a new instance with the path reversed
     */
    public LinePath reverse() {
        if (!isEmpty()) {
            final List<LineConvexSubset> reversed = elements.stream()
                .map(LineConvexSubset::reverse)
                .collect(Collectors.toCollection(ArrayList::new));
            Collections.reverse(reversed);

            return new LinePath(reversed);
        }

        return this;
    }

    /** Simplify this path, if possible, by combining adjacent elements that lie on the
     * same line (as determined by {@link Line#equals(Object)}).
     * @return a simplified instance
     */
    public LinePath simplify() {
        final List<LineConvexSubset> simplified = new ArrayList<>();

        final int size = elements.size();

        LineConvexSubset current;
        Line currentLine;
        double end;

        int idx = 0;
        int testIdx;
        while (idx < size) {
            current = elements.get(idx);
            currentLine = current.getLine();
            end = current.getSubspaceEnd();

            // try to combine with forward neighbors
            testIdx = idx + 1;
            while (testIdx < size && currentLine.equals(elements.get(testIdx).getLine())) {
                end = Math.max(end, elements.get(testIdx).getSubspaceEnd());
                ++testIdx;
            }

            if (testIdx > idx + 1) {
                // we found something to merge
                simplified.add(Lines.subsetFromInterval(currentLine, current.getSubspaceStart(), end));
            } else {
                simplified.add(current);
            }

            idx = testIdx;
        }

        // combine the first and last items if needed
        if (isClosed() && simplified.size() > 2 && simplified.get(0).getLine().equals(
                simplified.get(simplified.size() - 1).getLine())) {

            final LineConvexSubset startElement = simplified.get(0);
            final LineConvexSubset endElement = simplified.remove(simplified.size() - 1);

            final LineConvexSubset combined = Lines.subsetFromInterval(
                    endElement.getLine(), endElement.getSubspaceStart(), startElement.getSubspaceEnd());

            simplified.set(0, combined);
        }

        return new SimplifiedLinePath(simplified);
    }

    /** Return a string representation of the path.
     *
     * <p>In order to keep the string representation short but useful, the exact format of the return
     * value depends on the properties of the path. See below for examples.
     *
     * <ul>
     *      <li>Empty path
     *          <ul>
     *              <li>{@code LinePath[empty= true]}</li>
     *          </ul>
     *      </li>
     *      <li>Single element
     *          <ul>
     *              <li>{@code LinePath[single= Segment[startPoint= (0.0, 0.0), endPoint= (1.0, 0.0)]]}</li>
     *          </ul>
     *      </li>
     *      <li>Path with infinite start element
     *          <ul>
     *              <li>{@code LinePath[startDirection= (1.0, 0.0), vertices= [(1.0, 0.0), (1.0, 1.0)]]}</li>
     *          </ul>
     *      </li>
     *      <li>Path with infinite end element
     *          <ul>
     *              <li>{@code LinePath[vertices= [(0.0, 1.0), (0.0, 0.0)], endDirection= (1.0, 0.0)]}</li>
     *          </ul>
     *      </li>
     *      <li>Path with infinite start and end elements
     *          <ul>
     *              <li>{@code LinePath[startDirection= (0.0, 1.0), vertices= [(0.0, 0.0)], endDirection= (1.0, 0.0)]}</li>
     *          </ul>
     *      </li>
     *      <li>Path with no infinite elements
     *          <ul>
     *              <li>{@code LinePath[vertices= [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0)]]}</li>
     *          </ul>
     *      </li>
     * </ul>
     */
    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        sb.append(this.getClass().getSimpleName())
            .append('[');

        if (elements.isEmpty()) {
            sb.append("empty= true");
        } else if (elements.size() == 1) {
            sb.append("single= ")
                .append(elements.get(0));
        } else {
            final LineConvexSubset startElement = getStart();
            if (startElement.getStartPoint() == null) {
                sb.append("startDirection= ")
                    .append(startElement.getLine().getDirection())
                    .append(", ");
            }

            sb.append("vertexSequence= ")
                .append(getVertexSequence());

            final LineConvexSubset endElement = getEnd();
            if (endElement.getEndPoint() == null) {
                sb.append(", endDirection= ")
                    .append(endElement.getLine().getDirection());
            }
        }

        sb.append(']');

        return sb.toString();
    }

    /** Get the start vertex for the path or null if the path is empty
     * or has an infinite start line subset.
     * @return the start vertex for the path or null if the path does
     *      not start with a vertex
     */
    private Vector2D getStartVertex() {
        final LineConvexSubset seg = getStart();
        return (seg != null) ? seg.getStartPoint() : null;
    }

    /** Get the end vertex for the path or null if the path is empty
     * or has an infinite end line subset.
     * @return the end vertex for the path or null if the path does
     *      not end with a vertex
     */
    private Vector2D getEndVertex() {
        final LineConvexSubset seg = getEnd();
        return (seg != null) ? seg.getEndPoint() : null;
    }

    /** Build a new path from the given line subsets.
     * @param subsets the line subsets to comprise the path
     * @return new path containing the given line subsets in order
     * @throws IllegalStateException if the line subsets do not form a connected path
     */
    public static LinePath from(final LineConvexSubset... subsets) {
        return from(Arrays.asList(subsets));
    }

    /** Build a new path from the given line subsets.
     * @param subsets the line subsets to comprise the path
     * @return new path containing the given line subsets in order
     * @throws IllegalStateException if the subsets do not form a connected path
     */
    public static LinePath from(final Collection<? extends LineConvexSubset> subsets) {
        final Builder builder = builder(null);

        for (final LineConvexSubset subset : subsets) {
            builder.append(subset);
        }

        return builder.build();
    }

    /** Build a new path from the given vertices. A line segment is created
     * from the last vertex to the first one, if the two vertices are not already
     * considered equal using the given precision context. This method is equivalent to
     * calling {@link #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
     * fromVertices(vertices, true, precision)}
     * @param vertices the vertices to construct the closed path from
     * @param precision precision context used to construct the line segment
     *      instances for the path
     * @return new closed path constructed from the given vertices
     * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
     * @see #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
     */
    public static LinePath fromVertexLoop(final Collection<Vector2D> vertices,
            final Precision.DoubleEquivalence precision) {

        return fromVertices(vertices, true, precision);
    }

    /** Build a new path from the given vertices. No additional segment is added
     * from the last vertex to the first. This method is equivalent to calling
     * {@link #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
     * fromVertices(vertices, false, precision)}.
     * @param vertices the vertices to construct the path from
     * @param precision precision context used to construct the line segment
     *      instances for the path
     * @return new path constructed from the given vertices
     * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
     * @see #fromVertices(Collection, boolean, Precision.DoubleEquivalence)
     */
    public static LinePath fromVertices(final Collection<Vector2D> vertices,
            final Precision.DoubleEquivalence precision) {

        return fromVertices(vertices, false, precision);
    }

    /** Build a new path from the given vertices.
     * @param vertices the vertices to construct the path from
     * @param close if true, a line segment is created from the last vertex
     *      given to the first one, if the two vertices are not already considered
     *      equal using the given precision context.
     * @param precision precision context used to construct the line segment
     *      instances for the path
     * @return new path constructed from the given vertices
     * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
     */
    public static LinePath fromVertices(final Collection<Vector2D> vertices,
            final boolean close, final Precision.DoubleEquivalence precision) {

        return builder(precision)
                .appendVertices(vertices)
                .build(close);
    }

    /** Return a path containing no elements.
     * @return a path containing no elements
     */
    public static LinePath empty() {
        return EMPTY;
    }

    /** Return a {@link Builder} instance configured with the given precision
     * context. The precision context is used when building line segments from
     * vertices and may be omitted if raw vertices are not used.
     * @param precision precision context to use when building line segments from
     *      raw vertices; may be null if raw vertices are not used.
     * @return a new {@link Builder} instance
     */
    public static Builder builder(final Precision.DoubleEquivalence precision) {
        return new Builder(precision);
    }

    /** Class used to build line paths.
     */
    public static final class Builder {
        /** Line subsets appended to the path. */
        private List<LineConvexSubset> appended;

        /** Line subsets prepended to the path. */
        private List<LineConvexSubset> prepended;

        /** Precision context used when creating line segments directly from vertices. */
        private Precision.DoubleEquivalence precision;

        /** The current vertex at the start of the path. */
        private Vector2D startVertex;

        /** The current vertex at the end of the path. */
        private Vector2D endVertex;

        /** The precision context used when performing comparisons involving the current
         * end vertex.
         */
        private Precision.DoubleEquivalence endVertexPrecision;

        /** Construct a new instance configured with the given precision context. The
         * precision context is used when building line segments from vertices and
         * may be omitted if raw vertices are not used.
         * @param precision precision context to use when creating line segments
         *      from vertices
         */
        private Builder(final Precision.DoubleEquivalence precision) {
            setPrecision(precision);
        }

        /** Set the precision context. This context is used only when creating line segments
         * from appended or prepended vertices. It is not used when adding existing
         * {@link LineConvexSubset} instances since those contain their own precision contexts.
         * @param builderPrecision precision context to use when creating line segments
         *      from vertices
         * @return this instance
         */
        public Builder setPrecision(final Precision.DoubleEquivalence builderPrecision) {
            this.precision = builderPrecision;

            return this;
        }

        /** Get the line subset at the start of the path or null if it does not exist.
         * @return the line subset at the start of the path
         */
        public LineConvexSubset getStart() {
            LineConvexSubset start = getLast(prepended);
            if (start == null) {
                start = getFirst(appended);
            }
            return start;
        }

        /** Get the line subset at the end of the path or null if it does not exist.
         * @return the line subset at the end of the path
         */
        public LineConvexSubset getEnd() {
            LineConvexSubset end = getLast(appended);
            if (end == null) {
                end = getFirst(prepended);
            }
            return end;
        }

        /** Append a line subset to the end of the path.
         * @param subset line subset to append to the path
         * @return the current builder instance
         * @throws IllegalStateException if the path contains a previous element
         *      and the end vertex of the previous element is not equivalent to the
         *      start vertex of the argument
         */
        public Builder append(final LineConvexSubset subset) {
            validateConnected(getEnd(), subset);
            appendInternal(subset);

            return this;
        }

        /** Add a vertex to the end of this path. If the path already has an end vertex,
         * then a line segment is added between the previous end vertex and this vertex,
         * using the configured precision context.
         * @param vertex the vertex to add
         * @return this instance
         * @see #setPrecision(Precision.DoubleEquivalence)
         */
        public Builder append(final Vector2D vertex) {
            final Precision.DoubleEquivalence vertexPrecision = getAddVertexPrecision();

            if (endVertex == null) {
                // make sure that we're not adding to an infinite element
                final LineConvexSubset end = getEnd();
                if (end != null) {
                    throw new IllegalStateException(
                            MessageFormat.format("Cannot add vertex {0} after infinite line subset: {1}",
                                    vertex, end));
                }

                // this is the first vertex added
                startVertex = vertex;
                endVertex = vertex;
                endVertexPrecision = vertexPrecision;
            } else if (!endVertex.eq(vertex, endVertexPrecision)) {
                // only add the vertex if its not equal to the end point
                // of the last element
                appendInternal(Lines.segmentFromPoints(endVertex, vertex, endVertexPrecision));
            }

            return this;
        }

        /** Convenience method for appending a collection of vertices to the path in a single method call.
         * @param vertices the vertices to append
         * @return this instance
         * @see #append(Vector2D)
         */
        public Builder appendVertices(final Collection<? extends Vector2D> vertices) {
            for (final Vector2D vertex : vertices) {
                append(vertex);
            }

            return this;
        }

        /** Convenience method for appending multiple vertices to the path at once.
         * @param vertices the vertices to append
         * @return this instance
         * @see #append(Vector2D)
         */
        public Builder appendVertices(final Vector2D... vertices) {
            return appendVertices(Arrays.asList(vertices));
        }

        /** Prepend a line subset to the beginning of the path.
         * @param subset line subset to prepend to the path
         * @return the current builder instance
         * @throws IllegalStateException if the path contains a start element
         *      and the end vertex of the argument is not equivalent to the
         *      start vertex of the start element.
         */
        public Builder prepend(final LineConvexSubset subset) {
            validateConnected(subset, getStart());
            prependInternal(subset);

            return this;
        }

        /** Add a vertex to the front of this path. If the path already has a start vertex,
         * then a line segment is added between this vertex and the previous start vertex,
         * using the configured precision context.
         * @param vertex the vertex to add
         * @return this instance
         * @see #setPrecision(Precision.DoubleEquivalence)
         */
        public Builder prepend(final Vector2D vertex) {
            final Precision.DoubleEquivalence vertexPrecision = getAddVertexPrecision();

            if (startVertex == null) {
                // make sure that we're not adding to an infinite element
                final LineConvexSubset start = getStart();
                if (start != null) {
                    throw new IllegalStateException(
                            MessageFormat.format("Cannot add vertex {0} before infinite line subset: {1}",
                                    vertex, start));
                }

                // this is the first vertex added
                startVertex = vertex;
                endVertex = vertex;
                endVertexPrecision = vertexPrecision;
            } else if (!vertex.eq(startVertex, vertexPrecision)) {
                // only add if the vertex is not equal to the start
                // point of the first element
                prependInternal(Lines.segmentFromPoints(vertex, startVertex, vertexPrecision));
            }

            return this;
        }

        /** Convenience method for prepending a collection of vertices to the path in a single method call.
         * The vertices are logically prepended as a single group, meaning that the first vertex
         * in the given collection appears as the first vertex in the path after this method call.
         * Internally, this means that the vertices are actually passed to the {@link #prepend(Vector2D)}
         * method in reverse order.
         * @param vertices the vertices to prepend
         * @return this instance
         * @see #prepend(Vector2D)
         */
        public Builder prependVertices(final Collection<Vector2D> vertices) {
            return prependVertices(vertices.toArray(new Vector2D[0]));
        }

        /** Convenience method for prepending multiple vertices to the path in a single method call.
         * The vertices are logically prepended as a single group, meaning that the first vertex
         * in the given collection appears as the first vertex in the path after this method call.
         * Internally, this means that the vertices are actually passed to the {@link #prepend(Vector2D)}
         * method in reverse order.
         * @param vertices the vertices to prepend
         * @return this instance
         * @see #prepend(Vector2D)
         */
        public Builder prependVertices(final Vector2D... vertices) {
            for (int i = vertices.length - 1; i >= 0; --i) {
                prepend(vertices[i]);
            }

            return this;
        }

        /** Close the current path and build a new {@link LinePath} instance.  This method is equivalent
         * to {@code builder.build(true)}.
         * @return new closed path instance
         * @throws IllegalStateException if the builder was given only a single unique vertex
         */
        public LinePath close() {
            return build(true);
        }

        /** Build a {@link LinePath} instance from the configured path. This method is equivalent
         * to {@code builder.build(false)}.
         * @return new path instance
         * @throws IllegalStateException if the builder was given only a single unique vertex
         */
        public LinePath build() {
            return build(false);
        }

        /** Build a {@link LinePath} instance from the configured path.
         * @param close if true, the path will be closed by adding an end point equivalent to the
         *      start point
         * @return new path instance
         * @throws IllegalStateException if the builder was given only a single unique vertex
         */
        public LinePath build(final boolean close) {
            if (close) {
                closePath();
            }

            // combine all of the line subsets
            List<LineConvexSubset> result = null;

            if (prepended != null) {
                result = prepended;
                Collections.reverse(result);
            }

            if (appended != null) {
                if (result == null) {
                    result = appended;
                } else {
                    result.addAll(appended);
                }
            }

            if (result == null) {
                result = Collections.emptyList();
            }

            if (result.isEmpty() && startVertex != null) {
                throw new IllegalStateException(
                        MessageFormat.format("Unable to create line path; only a single unique vertex provided: {0} ",
                                startVertex));
            }

            // clear internal state
            appended = null;
            prepended = null;

            // build the final path instance, using the shared empty instance if
            // no line subsets are present

            return result.isEmpty() ? empty() : new LinePath(result);
        }

        /** Close the path by adding an end point equivalent to the path start point.
         * @throws IllegalStateException if the path cannot be closed
         */
        private void closePath() {
            final LineConvexSubset end = getEnd();

            if (end != null) {
                if (startVertex != null && endVertex != null) {
                    if (!endVertex.eq(startVertex, endVertexPrecision)) {
                        appendInternal(Lines.segmentFromPoints(endVertex, startVertex, endVertexPrecision));
                    }
                } else {
                    throw new IllegalStateException("Unable to close line path: line path is infinite");
                }
            }
        }

        /** Validate that the given line subsets  are connected, meaning that the end vertex of {@code previous}
         * is equivalent to the start vertex of {@code next}. The line subsets are considered valid if either
         * line subset is null.
         * @param previous previous line subset
         * @param next next line subset
         * @throws IllegalStateException if previous and next are not null and the end vertex of previous
         *      is not equivalent the start vertex of next
         */
        private void validateConnected(final LineConvexSubset previous, final LineConvexSubset next) {
            if (previous != null && next != null) {
                final Vector2D nextStartVertex = next.getStartPoint();
                final Vector2D previousEndVertex = previous.getEndPoint();
                final Precision.DoubleEquivalence previousPrecision = previous.getPrecision();

                if (nextStartVertex == null || previousEndVertex == null ||
                        !(nextStartVertex.eq(previousEndVertex, previousPrecision))) {

                    throw new IllegalStateException(
                            MessageFormat.format("Path line subsets are not connected: previous= {0}, next= {1}",
                                    previous, next));
                }
            }
        }

        /** Get the precision context used when adding raw vertices to the path. An exception is thrown
         * if no precision has been specified.
         * @return the precision context used when creating working with raw vertices
         * @throws IllegalStateException if no precision context is configured
         */
        private Precision.DoubleEquivalence getAddVertexPrecision() {
            if (precision == null) {
                throw new IllegalStateException("Unable to create line segment: no vertex precision specified");
            }

            return precision;
        }

        /** Append the given, validated line subsets to the path.
         * @param subset validated line subset to append
         */
        private void appendInternal(final LineConvexSubset subset) {
            if (appended == null) {
                appended = new ArrayList<>();
            }

            if (appended.isEmpty() &&
                    (prepended == null || prepended.isEmpty())) {
                startVertex = subset.getStartPoint();
            }

            endVertex = subset.getEndPoint();
            endVertexPrecision = subset.getPrecision();

            appended.add(subset);
        }

        /** Prepend the given, validated line subset to the path.
         * @param subset validated line subset to prepend
         */
        private void prependInternal(final LineConvexSubset subset) {
            if (prepended == null) {
                prepended = new ArrayList<>();
            }

            startVertex = subset.getStartPoint();

            if (prepended.isEmpty() &&
                    (appended == null || appended.isEmpty())) {
                endVertex = subset.getEndPoint();
                endVertexPrecision = subset.getPrecision();
            }

            prepended.add(subset);
        }

        /** Get the first element in the list or null if the list is null
         * or empty.
         * @param list the list to return the first item from
         * @return the first item from the given list or null if it does not exist
         */
        private LineConvexSubset getFirst(final List<? extends LineConvexSubset> list) {
            if (list != null && !list.isEmpty()) {
                return list.get(0);
            }
            return null;
        }

        /** Get the last element in the list or null if the list is null
         * or empty.
         * @param list the list to return the last item from
         * @return the last item from the given list or null if it does not exist
         */
        private LineConvexSubset getLast(final List<? extends LineConvexSubset> list) {
            if (list != null && !list.isEmpty()) {
                return list.get(list.size() - 1);
            }
            return null;
        }
    }

    /** Internal class returned when a line path is simplified to remove unnecessary line subset divisions.
     * The {@link #simplify()} method on this class simply returns the same instance.
     */
    private static final class SimplifiedLinePath extends LinePath {
        /** Create a new instance containing the given line subsets. No validation is
         * performed on the inputs. Caller must ensure that the given line subsets represent
         * a valid, simplified path.
         * @param elements line subsets comprising the path
         */
        private SimplifiedLinePath(final List<LineConvexSubset> elements) {
            super(elements);
        }

        /** {@inheritDoc} */
        @Override
        public SimplifiedLinePath simplify() {
            // already simplified
            return this;
        }
    }
}