/** @file
 * @brief Path - a sequence of contiguous curves
 *//*
  * Authors:
  *   MenTaLguY <mental@rydia.net>
  *   Marco Cecchetti <mrcekets at gmail.com>
  *   Krzysztof Kosiński <tweenk.pl@gmail.com>
  *
  * Copyright 2007-2014 Authors
  *
  * This library is free software; you can redistribute it and/or
  * modify it either under the terms of the GNU Lesser General Public
  * License version 2.1 as published by the Free Software Foundation
  * (the "LGPL") or, at your option, under the terms of the Mozilla
  * Public License Version 1.1 (the "MPL"). If you do not alter this
  * notice, a recipient may use your version of this file under either
  * the MPL or the LGPL.
  *
  * You should have received a copy of the LGPL along with this library
  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  * You should have received a copy of the MPL along with this library
  * in the file COPYING-MPL-1.1
  *
  * The contents of this file are subject to the Mozilla Public License
  * Version 1.1 (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.mozilla.org/MPL/
  *
  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  * the specific language governing rights and limitations.
  */

#ifndef LIB2GEOM_SEEN_PATH_H
#define LIB2GEOM_SEEN_PATH_H

#include <cstddef>
#include <iterator>
#include <algorithm>
#include <iostream>
#include <memory>
#include <optional>
#include <utility>
#include <vector>

#include <boost/operators.hpp>
#include <boost/ptr_container/ptr_vector.hpp>

#include <2geom/intersection.h>
#include <2geom/curve.h>
#include <2geom/bezier-curve.h>
#include <2geom/transforms.h>

namespace Geom {

class Path;
class ConvexHull;

namespace PathInternal {

typedef boost::ptr_vector<Curve> Sequence;

struct PathData {
    Sequence curves;
    OptRect fast_bounds;
};

template <typename P>
class BaseIterator
    : public boost::random_access_iterator_helper
        < BaseIterator<P>
        , Curve const
        , std::ptrdiff_t
        , Curve const *
        , Curve const &
        >
{
  protected:
    BaseIterator(P &p, unsigned i) : path(&p), index(i) {}
    // default copy, default assign
    typedef BaseIterator<P> Self;

  public:
    BaseIterator() : path(NULL), index(0) {}

    bool operator<(BaseIterator const &other) const {
        return path == other.path && index < other.index;
    }
    bool operator==(BaseIterator const &other) const {
        return path == other.path && index == other.index;
    }
    Curve const &operator*() const {
        return (*path)[index];
    }

    Self &operator++() {
        ++index;
        return *this;
    }
    Self &operator--() {
        --index;
        return *this;
    }
    Self &operator+=(std::ptrdiff_t d) {
        index += d;
        return *this;
    }
    Self &operator-=(std::ptrdiff_t d) {
        index -= d;
        return *this;
    }
    std::ptrdiff_t operator-(Self const &other) const {
        assert(path == other.path);
        return (std::ptrdiff_t)index - (std::ptrdiff_t)other.index;
    }

  private:
    P *path;
    unsigned index;

    friend class ::Geom::Path;
};

}

/** @brief Generalized time value in the path.
 *
 * This class exists because when mapping the range of multiple curves onto the same interval
 * as the curve index, we lose some precision. For instance, a path with 16 curves will
 * have 4 bits less precision than a path with 1 curve. If you need high precision results
 * in long paths, either use this class and related methods instead of the standard methods
 * pointAt(), nearestTime() and so on, or use curveAt() to first obtain the curve, then
 * call the method again to obtain a high precision result.
 *
 * @ingroup Paths */
struct PathTime
    : boost::totally_ordered<PathTime>
{
    typedef PathInternal::Sequence::size_type size_type;

    Coord t; ///< Time value in the curve
    size_type curve_index; ///< Index of the curve in the path

    PathTime() : t(0), curve_index(0) {}
    PathTime(size_type idx, Coord tval) : t(tval), curve_index(idx) {}

    bool operator<(PathTime const &other) const {
        if (curve_index < other.curve_index) return true;
        if (curve_index == other.curve_index) {
            return t < other.t;
        }
        return false;
    }
    bool operator==(PathTime const &other) const {
        return curve_index == other.curve_index && t == other.t;
    }
    /// Convert times at or beyond 1 to 0 on the next curve.
    void normalizeForward(size_type path_size) {
        if (t >= 1) {
            curve_index = (curve_index + 1) % path_size;
            t = 0;
        }
    }
    /// Convert times at or before 0 to 1 on the previous curve.
    void normalizeBackward(size_type path_size) {
        if (t <= 0) {
            curve_index = (curve_index - 1) % path_size;
            t = 1;
        }
    }

    Coord asFlatTime() const { return curve_index + t; }
};

inline std::ostream &operator<<(std::ostream &os, PathTime const &pos) {
    os << pos.curve_index << ": " << format_coord_nice(pos.t);
    return os;
}


/** @brief Contiguous subset of the path's parameter domain.
 * This is a directed interval, which allows one to specify any contiguous subset
 * of the path's domain, including subsets that wrap around the initial point
 * of the path.
 * @ingroup Paths */
class PathInterval {
public:
    typedef PathInternal::Sequence::size_type size_type;

    /** @brief Default interval.
     * Default-constructed PathInterval includes only the initial point of the initial segment. */
    PathInterval();

    /** @brief Construct an interval in the path's parameter domain.
     * @param from Initial time
     * @param to Final time
     * @param cross_start If true, the interval will proceed from the initial to final
     *   time through the initial point of the path, wrapping around the closing segment;
     *   otherwise it will not wrap around the closing segment.
     * @param path_size Size of the path to which this interval applies, required
     *   to clean up degenerate cases */
    PathInterval(PathTime const &from, PathTime const &to, bool cross_start, size_type path_size);

    /// Get the time value of the initial point.
    PathTime const &initialTime() const { return _from; }
    /// Get the time value of the final point.
    PathTime const &finalTime() const { return _to; }

    PathTime const &from() const { return _from; }
    PathTime const &to() const { return _to; }

    /// Check whether the interval has only one point.
    bool isDegenerate() const { return _from == _to; }
    /// True if the interval goes in the direction of decreasing time values.
    bool reverse() const { return _reverse; }
    /// True if the interior of the interval contains the initial point of the path.
    bool crossesStart() const { return _cross_start; }

    /// Test a path time for inclusion.
    bool contains(PathTime const &pos) const;

    /// Get a time at least @a min_dist away in parameter space from the ends.
    /// If no such time exists, the middle point is returned.
    PathTime inside(Coord min_dist = EPSILON) const;

    /// Select one of two intervals with given endpoints by parameter direction.
    static PathInterval from_direction(PathTime const &from, PathTime const &to,
                                       bool reversed, size_type path_size);

    /// Select one of two intervals with given endpoints by whether it includes the initial point.
    static PathInterval from_start_crossing(PathTime const &from, PathTime const &to,
                                            bool cross_start, size_type path_size) {
        PathInterval result(from, to, cross_start, path_size);
        return result;
    }

    size_type pathSize() const { return _path_size; }
    size_type curveCount() const;

private:
    PathTime _from, _to;
    size_type _path_size;
    bool _cross_start, _reverse;
};

/// Create an interval in the direction of increasing time value.
/// @relates PathInterval
inline PathInterval forward_interval(PathTime const &from, PathTime const &to,
                                     PathInterval::size_type path_size)
{
    PathInterval result = PathInterval::from_direction(from, to, false, path_size);
    return result;
}

/// Create an interval in the direction of decreasing time value.
/// @relates PathInterval
inline PathInterval backward_interval(PathTime const &from, PathTime const &to,
                                      PathInterval::size_type path_size)
{
    PathInterval result = PathInterval::from_direction(from, to, true, path_size);
    return result;
}

/// Output an interval in the path's domain.
/// @relates PathInterval
inline std::ostream &operator<<(std::ostream &os, PathInterval const &ival) {
    os << "PathInterval[";
    if (ival.crossesStart()) {
        os << ival.from() << " -> 0: 0.0 -> " << ival.to();
    } else {
        os << ival.from() << " -> " << ival.to();
    }
    os << "]";
    return os;
}

typedef Intersection<PathTime> PathIntersection;

template <>
struct ShapeTraits<Path> {
    typedef PathTime TimeType;
    typedef PathInterval IntervalType;
    typedef Path AffineClosureType;
    typedef PathIntersection IntersectionType;
};

/** @brief Stores information about the extremum points on a path, with respect
 *         to one of the coordinate axes.
 *  @relates Path::extrema()
 */
struct PathExtrema {
    /** Points with the minimum and maximum value of a coordinate. */
    Point min_point, max_point;

    /** Directions in which the OTHER coordinates change at the extremum points.
     *
     * - equals +1.0 if the other coordinate increases,
     * - equals  0.0 if the other coordinate is constant (e.g., for an axis-aligned segment),
     * - equals -1.0 if the other coordinate decreases.
     */
    float glance_direction_at_min, glance_direction_at_max;

    /** Path times corresponding to minimum and maximum points. */
    PathTime min_time, max_time;
};

/** @brief Sequence of contiguous curves, aka spline.
 *
 * Path represents a sequence of contiguous curves, also known as a spline.
 * It corresponds to a "subpath" in SVG terminology. It can represent both
 * open and closed subpaths. The final point of each curve is exactly
 * equal to the initial point of the next curve.
 *
 * The path always contains a linear closing segment that connects
 * the final point of the last "real" curve to the initial point of the
 * first curve. This way the curves form a closed loop even for open paths.
 * If the closing segment has nonzero length and the path is closed, it is
 * considered a normal part of the path data. There are three distinct sets
 * of end iterators one can use to iterate over the segments:
 *
 * - Iterating between @a begin() and @a end() will iterate over segments
 *   which are part of the path.
 * - Iterating between @a begin() and @a end_closed()
 *   will always iterate over a closed loop of segments.
 * - Iterating between @a begin() and @a end_open() will always skip
 *   the final linear closing segment.
 *
 * If the final point of the last "real" segment coincides exactly with the initial
 * point of the first segment, the closing segment will be absent from both
 * [begin(), end_open()) and [begin(), end_closed()).
 *
 * Normally, an exception will be thrown when you try to insert a curve
 * that makes the path non-continuous. If you are working with unsanitized
 * curve data, you can call setStitching(true), which will insert line segments
 * to make the path continuous.
 *
 * Internally, Path uses copy-on-write data. This is done for two reasons: first,
 * copying a Curve requires calling a virtual function, so it's a little more expensive
 * that normal copying; and second, it reduces the memory cost of copying the path.
 * Therefore you can return Path and PathVector from functions without worrying
 * about temporary copies.
 *
 * Note that this class cannot represent arbitrary shapes, which may contain holes.
 * To do that, use PathVector, which is more generic.
 *
 * It's not very convenient to create a Path directly. To construct paths more easily,
 * use PathBuilder.
 *
 * @ingroup Paths */
class Path
    : boost::equality_comparable< Path >
{
public:
    typedef PathInternal::PathData PathData;
    typedef PathInternal::Sequence Sequence;
    typedef PathInternal::BaseIterator<Path> iterator;
    typedef PathInternal::BaseIterator<Path const> const_iterator;
    typedef Sequence::size_type size_type;
    typedef Sequence::difference_type difference_type;

    class ClosingSegment : public LineSegment {
      public:
        ClosingSegment() : LineSegment() {}
        ClosingSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
        Curve *duplicate() const override { return new ClosingSegment(*this); }
        Curve *reverse() const override { return new ClosingSegment((*this)[1], (*this)[0]); }
    };

    class StitchSegment : public LineSegment {
      public:
        StitchSegment() : LineSegment() {}
        StitchSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
        Curve *duplicate() const override { return new StitchSegment(*this); }
        Curve *reverse() const override { return new StitchSegment((*this)[1], (*this)[0]); }
    };

    // Path(Path const &other) - use default copy constructor

    /// Construct an empty path starting at the specified point.
    explicit Path(Point const &p = Point())
        : _data(new PathData())
        , _closing_seg(new ClosingSegment(p, p))
        , _closed(false)
        , _exception_on_stitch(true)
    {
        _data->curves.push_back(_closing_seg);
    }

    /// Construct a path containing a range of curves.
    template <typename Iter>
    Path(Iter first, Iter last, bool closed = false, bool stitch = false)
        : _data(new PathData())
        , _closed(closed)
        , _exception_on_stitch(!stitch)
    {
        for (Iter i = first; i != last; ++i) {
            _data->curves.push_back(i->duplicate());
        }
        if (!_data->curves.empty()) {
            _closing_seg = new ClosingSegment(_data->curves.back().finalPoint(),
                                              _data->curves.front().initialPoint());
        } else {
            _closing_seg = new ClosingSegment();
        }
        _data->curves.push_back(_closing_seg);
    }

    /// Create a path from a rectangle.
    explicit Path(Rect const &r);
    /// Create a path from a convex hull.
    explicit Path(ConvexHull const &);
    /// Create a path from a circle, using two elliptical arcs.
    explicit Path(Circle const &c);
    /// Create a path from an ellipse, using two elliptical arcs.
    explicit Path(Ellipse const &e);

    virtual ~Path() {}

    // Path &operator=(Path const &other) - use default assignment operator

    /** @brief Swap contents with another path
     * @todo Add noexcept specifiers for C++11 */
    void swap(Path &other) noexcept {
        using std::swap;
        swap(other._data, _data);
        swap(other._closing_seg, _closing_seg);
        swap(other._closed, _closed);
        swap(other._exception_on_stitch, _exception_on_stitch);
    }
    /** @brief Swap contents of two paths.
     * @relates Path */
    friend inline void swap(Path &a, Path &b) noexcept { a.swap(b); }

    /** @brief Access a curve by index */
    Curve const &operator[](size_type i) const { return _data->curves[i]; }
    /** @brief Access a curve by index */
    Curve const &at(size_type i) const { return _data->curves.at(i); }

    /** @brief Access the first curve in the path.
     * Since the curve always contains at least a degenerate closing segment,
     * it is always safe to use this method. */
    Curve const &front() const { return _data->curves.front(); }
    /// Alias for front().
    Curve const &initialCurve() const { return _data->curves.front(); }
    /** @brief Access the last curve in the path. */
    Curve const &back() const { return back_default(); }
    Curve const &back_open() const {
        if (empty()) return _data->curves.back();
        return _data->curves[_data->curves.size() - 2];
    }
    Curve const &back_closed() const {
        return _closing_seg->isDegenerate()
            ? _data->curves[_data->curves.size() - 2]
            : _data->curves[_data->curves.size() - 1];
    }
    Curve const &back_default() const {
        return _includesClosingSegment()
            ? back_closed()
            : back_open();
    }
    Curve const &finalCurve() const { return back_default(); }

    const_iterator begin() const { return const_iterator(*this, 0); }
    const_iterator end() const { return end_default(); }
    const_iterator end_default() const { return const_iterator(*this, size_default()); }
    const_iterator end_open() const { return const_iterator(*this, size_open()); }
    const_iterator end_closed() const { return const_iterator(*this, size_closed()); }
    iterator begin() { return iterator(*this, 0); }
    iterator end() { return end_default(); }
    iterator end_default() { return iterator(*this, size_default()); }
    iterator end_open() { return iterator(*this, size_open()); }
    iterator end_closed() { return iterator(*this, size_closed()); }

    /// Size without the closing segment, even if the path is closed.
    size_type size_open() const { return _data->curves.size() - 1; }

    /** @brief Size with the closing segment, if it makes a difference.
     * If the closing segment is degenerate, i.e. its initial and final points
     * are exactly equal, then it is not included in this size. */
    size_type size_closed() const {
        return _closing_seg->isDegenerate() ? _data->curves.size() - 1 : _data->curves.size();
    }

    /// Natural size of the path.
    size_type size_default() const {
        return _includesClosingSegment() ? size_closed() : size_open();
    }
    /// Natural size of the path.
    size_type size() const { return size_default(); }

    size_type max_size() const { return _data->curves.max_size() - 1; }

    /** @brief Check whether path is empty.
     * The path is empty if it contains only the closing segment, which according
     * to the continuity invariant must be degenerate. Note that unlike standard
     * containers, two empty paths are not necessarily identical, because the
     * degenerate closing segment may be at a different point, affecting the operation
     * of methods such as appendNew(). */
    bool empty() const { return (_data->curves.size() == 1); }

    /// Check whether the path is closed.
    bool closed() const { return _closed; }

    /** @brief Set whether the path is closed.
     * When closing a path where the last segment can be represented as a closing
     * segment, the last segment will be removed. When opening a path, the closing
     * segment will be erased. This means that closing and then opening a path
     * will not always give back the original path. */
    void close(bool closed = true);

    /** @brief Remove all curves from the path.
     * The initial and final points of the closing segment are set to (0,0).
     * The stitching flag remains unchanged. */
    void clear();

    /** @brief Get the approximate bounding box.
     * The rectangle returned by this method will contain all the curves, but it's not
     * guaranteed to be the smallest possible one */
    OptRect boundsFast() const;

    /** @brief Get a tight-fitting bounding box.
     * This will return the smallest possible axis-aligned rectangle containing
     * all the curves in the path. */
    OptRect boundsExact() const;

    Piecewise<D2<SBasis> > toPwSb() const;

    /// Test paths for exact equality.
    bool operator==(Path const &other) const;

    /// Apply a transform to each curve.
    template <typename T>
    Path &operator*=(T const &tr) {
        BOOST_CONCEPT_ASSERT((TransformConcept<T>));
        _unshare();
        for (std::size_t i = 0; i < _data->curves.size(); ++i) {
            _data->curves[i] *= tr;
        }
        return *this;
    }

    template <typename T>
    friend Path operator*(Path const &path, T const &tr) {
        BOOST_CONCEPT_ASSERT((TransformConcept<T>));
        Path result(path);
        result *= tr;
        return result;
    }

    /** @brief Get the allowed range of time values.
     * @return Values for which pointAt() and valueAt() yield valid results. */
    Interval timeRange() const;

    /** Get the curve at the specified time value.
     * @param t Time value
     * @param rest Optional storage for the corresponding time value in the curve */
    Curve const &curveAt(Coord t, Coord *rest = NULL) const;

    /// Get the closing segment of the path.
    LineSegment const &closingSegment() const { return *_closing_seg; }

    /** @brief Get the point at the specified time value.
     * Note that this method has reduced precision with respect to calling pointAt()
     * directly on the curve. If you want high precision results, use the version
     * that takes a PathTime parameter.
     *
     * Allowed time values range from zero to the number of curves; you can retrieve
     * the allowed range of values with timeRange(). */
    Point pointAt(Coord t) const;

    /// Get one coordinate (X or Y) at the specified time value.
    Coord valueAt(Coord t, Dim2 d) const;

    /// Get the curve at the specified path time.
    Curve const &curveAt(PathTime const &pos) const;
    /// Get the point at the specified path time.
    Point pointAt(PathTime const &pos) const;
    /// Get one coordinate at the specified path time.
    Coord valueAt(PathTime const &pos, Dim2 d) const;

    Point operator()(Coord t) const { return pointAt(t); }

    /** @brief Find the extrema of the specified coordinate.
     *
     * Returns a PathExtrema struct describing "witness" points on the path
     * where the specified coordinate attains its minimum and maximum values.
     */
    PathExtrema extrema(Dim2 d) const;

    /// Compute intersections with axis-aligned line.
    std::vector<PathTime> roots(Coord v, Dim2 d) const;

    /// Compute intersections with another path.
    std::vector<PathIntersection> intersect(Path const &other, Coord precision = EPSILON) const;

    /// Compute intersections of the path with itself.
    std::vector<PathIntersection> intersectSelf(Coord precision = EPSILON) const;

    /** @brief Determine the winding number at the specified point.
     *
     * The winding number is the number of full turns made by a ray that connects the passed
     * point and the path's value (i.e. the result of the pointAt() method) as the time increases
     * from 0 to the maximum valid value. Positive numbers indicate turns in the direction
     * of increasing angles.
     *
     * Winding numbers are often used as the definition of what is considered "inside"
     * the shape. Typically points with either nonzero winding or odd winding are
     * considered to be inside the path. */
    int winding(Point const &p) const;

    std::vector<Coord> allNearestTimes(Point const &p, Coord from, Coord to) const;
    std::vector<Coord> allNearestTimes(Point const &p) const {
        return allNearestTimes(p, 0, size_default());
    }

    PathTime nearestTime(Point const &p, Coord *dist = NULL) const;
    std::vector<Coord> nearestTimePerCurve(Point const &p) const;

    std::vector<Point> nodes() const;

    void appendPortionTo(Path &p, Coord f, Coord t) const;

    /** @brief Append a subset of this path to another path.
     * An extra stitching segment will be inserted if the start point of the portion
     * and the final point of the target path do not match exactly.
     * The closing segment of the target path will be modified. */
    void appendPortionTo(Path &p, PathTime const &from, PathTime const &to, bool cross_start = false) const {
        PathInterval ival(from, to, cross_start, size_closed());
        appendPortionTo(p, ival, std::nullopt, std::nullopt);
    }

    /** @brief Append a subset of this path to another path.
     * This version allows you to explicitly pass a PathInterval. */
    void appendPortionTo(Path &p, PathInterval const &ival) const {
        appendPortionTo(p, ival, std::nullopt, std::nullopt);
    }

    /** @brief Append a subset of this path to another path, specifying endpoints.
     * This method is for use in situations where endpoints of the portion segments
     * have to be set exactly, for instance when computing Boolean operations. */
    void appendPortionTo(Path &p, PathInterval const &ival,
                         std::optional<Point> const &p_from, std::optional<Point> const &p_to) const;

    Path portion(Coord f, Coord t) const {
        Path ret;
        ret.close(false);
        appendPortionTo(ret, f, t);
        return ret;
    }

    Path portion(Interval const &i) const { return portion(i.min(), i.max()); }

    /** @brief Get a subset of the current path with full precision.
     * When @a from is larger (later in the path) than @a to, the returned portion
     * will be reversed. If @a cross_start is true, the portion will be reversed
     * and will cross the initial point of the path. Therefore, when @a from is larger
     * than @a to and @a cross_start is true, the returned portion will not be reversed,
     * but will "wrap around" the end of the path. */
    Path portion(PathTime const &from, PathTime const &to, bool cross_start = false) const {
        Path ret;
        ret.close(false);
        appendPortionTo(ret, from, to, cross_start);
        return ret;
    }

    /** @brief Get a subset of the current path with full precision.
     * This version allows you to explicitly pass a PathInterval. */
    Path portion(PathInterval const &ival) const {
        Path ret;
        ret.close(false);
        appendPortionTo(ret, ival);
        return ret;
    }

    /** @brief Obtain a reversed version of the current path.
     * The final point of the current path will become the initial point
     * of the reversed path, unless it is closed and has a non-degenerate
     * closing segment. In that case, the new initial point will be the final point
     * of the last "real" segment. */
    Path reversed() const;

    void insert(iterator pos, Curve const &curve);

    template <typename Iter>
    void insert(iterator pos, Iter first, Iter last) {
        _unshare();
        Sequence::iterator seq_pos(seq_iter(pos));
        Sequence source;
        for (; first != last; ++first) {
            source.push_back(first->duplicate());
        }
        do_update(seq_pos, seq_pos, source);
    }

    void erase(iterator pos);
    void erase(iterator first, iterator last);

    // erase last segment of path
    void erase_last() { erase(iterator(*this, size() - 1)); }

    void start(Point const &p);

    /** @brief Get the first point in the path. */
    Point initialPoint() const { return (*_closing_seg)[1]; }

    /** @brief Get the last point in the path.
     * If the path is closed, this is always the same as the initial point. */
    Point finalPoint() const { return (*_closing_seg)[_closed ? 1 : 0]; }

    /** @brief Get the unit tangent vector at the start of the path,
     * or the zero vector if undefined. */
    Point initialUnitTangent() const {
        for (auto const &curve : *this) {
            if (!curve.isDegenerate()) {
                return curve.unitTangentAt(0.0);
            }
        }
        return Point();
    }

    /** @brief Get the unit tangent vector at the end of the path,
     * or the zero vector if undefined. */
    Point finalUnitTangent() const {
        for (auto it = end(); it != begin();) {
            --it;
            if (!it->isDegenerate()) {
                return it->unitTangentAt(1.0);
            }
        }
        return Point();
    }

    void setInitial(Point const &p) {
        _unshare();
        _closed = false;
        _data->curves.front().setInitial(p);
        _closing_seg->setFinal(p);
    }
    void setFinal(Point const &p) {
        _unshare();
        _closed = false;
        _data->curves[size_open() ? size_open() - 1 : 0].setFinal(p);
        _closing_seg->setInitial(p);
    }

    /** @brief Add a new curve to the end of the path.
     * This inserts the new curve right before the closing segment.
     * The path takes ownership of the passed pointer, which should not be freed. */
    void append(Curve *curve) {
        _unshare();
        stitchTo(curve->initialPoint());
        do_append(curve);
    }

    void append(Curve const &curve) {
        _unshare();
        stitchTo(curve.initialPoint());
        do_append(curve.duplicate());
    }
    void append(D2<SBasis> const &curve) {
        _unshare();
        stitchTo(Point(curve[X][0][0], curve[Y][0][0]));
        do_append(new SBasisCurve(curve));
    }
    void append(Path const &other) {
        replace(end_open(), other.begin(), other.end());
    }

    void replace(iterator replaced, Curve const &curve);
    void replace(iterator first, iterator last, Curve const &curve);
    void replace(iterator replaced, Path const &path);
    void replace(iterator first, iterator last, Path const &path);

    template <typename Iter>
    void replace(iterator replaced, Iter first, Iter last) {
        replace(replaced, replaced + 1, first, last);
    }

    template <typename Iter>
    void replace(iterator first_replaced, iterator last_replaced, Iter first, Iter last) {
        _unshare();
        Sequence::iterator seq_first_replaced(seq_iter(first_replaced));
        Sequence::iterator seq_last_replaced(seq_iter(last_replaced));
        Sequence source;
        for (; first != last; ++first) {
            source.push_back(first->duplicate());
        }
        do_update(seq_first_replaced, seq_last_replaced, source);
    }

    /** @brief Append a new curve to the path.
     *
     * This family of methods will automatically use the current final point of the path
     * as the first argument of the new curve's constructor. To call this method,
     * you'll need to write e.g.:
     * @code
       path.template appendNew<CubicBezier>(control1, control2, end_point);
       @endcode
     * It is important to note that the coordinates passed to appendNew should be finite!
     * If one of the coordinates is infinite, 2geom will throw a ContinuityError exception.
     */
    template <typename CurveType, typename... Args>
    void appendNew(Args&&... args) {
        _unshare();
        do_append(new CurveType(finalPoint(), std::forward<Args>(args)...));
    }

    /** @brief Reduce the closing segment to a point if it's shorter than precision.
     * Do this by moving the final point. */
    void snapEnds(Coord precision = EPSILON);

    /// Append a stitching segment ending at the specified point.
    void stitchTo(Point const &p);

    /** @brief Return a copy of the path without degenerate curves, except possibly for a
      * degenerate closing segment. */
    Path withoutDegenerateCurves() const;

    /** @brief Verify the continuity invariant.
     * If the path is not contiguous, this will throw a CountinuityError. */
    void checkContinuity() const;

    /** @brief Enable or disable the throwing of exceptions when stitching discontinuities.
     * Normally stitching will cause exceptions, but when you are working with unsanitized
     * curve data, you can disable these exceptions. */
    void setStitching(bool x) {
        _exception_on_stitch = !x;
    }

private:
    static Sequence::iterator seq_iter(iterator const &iter) {
        return iter.path->_data->curves.begin() + iter.index;
    }
    static Sequence::const_iterator seq_iter(const_iterator const &iter) {
        return iter.path->_data->curves.begin() + iter.index;
    }

    // whether the closing segment is part of the path
    bool _includesClosingSegment() const {
        return _closed && !_closing_seg->isDegenerate();
    }
    void _unshare() {
        // Called before every mutation.
        // Ensure we have our own copy of curve data and reset cached values
        if (_data.use_count() != 1) {
            _data.reset(new PathData(*_data));
            _closing_seg = static_cast<ClosingSegment*>(&_data->curves.back());
        }
        _data->fast_bounds = OptRect();
    }
    PathTime _factorTime(Coord t) const;

    void stitch(Sequence::iterator first_replaced, Sequence::iterator last_replaced, Sequence &sequence);
    void do_update(Sequence::iterator first, Sequence::iterator last, Sequence &source);

    // n.b. takes ownership of curve object
    void do_append(Curve *curve);

    std::shared_ptr<PathData> _data;
    ClosingSegment *_closing_seg;
    bool _closed;
    bool _exception_on_stitch;
}; // end class Path

Piecewise<D2<SBasis> > paths_to_pw(PathVector const &paths);

inline Coord nearest_time(Point const &p, Path const &c) {
    PathTime pt = c.nearestTime(p);
    return pt.curve_index + pt.t;
}

bool are_near(Path const &a, Path const &b, Coord precision = EPSILON);

/**
 * @brief Find the first point where two paths diverge away from one another.
 *
 * If the two paths have a common starting point, the algorithm follows them for as long as the
 * images of the paths coincide and finds the first point where they stop coinciding. Note that
 * only the images of paths in the plane are compared, and not their parametrizations, so this
 * is not a functional (parametric) coincidence. If you want to test parametric coincidence, use
 * bool are_near(Path const&, Path const&, Coord) instead.
 *
 * The function returns the point where the traces of the two paths finally diverge up to the
 * specified precision. If the traces (images) of the paths are nearly identical until the end,
 * the returned point is their (almost) common endpoint. If however the image of one of the paths
 * is completely contained in the image of the other path, the returned point is the endpoint of
 * the shorter path.
 *
 * If the paths have different starting points, then the returned intersection has the special
 * time values of -1.0 on both paths and the returned intersection point is the midpoint of the
 * line segment connecting the two starting points.
 *
 * @param first     The first path to follow; corresponds to .first in the return value.
 * @param second    The second path to follow; corresponds to .second in the return value.
 * @param precision How close the paths' images need to be in order to be considered as overlapping.
 * @return A path intersection specifying the point and path times where the two paths part ways.
 */
PathIntersection parting_point(Path const &first, Path const &second, Coord precision = EPSILON);

std::ostream &operator<<(std::ostream &out, Path const &path);

} // end namespace Geom


#endif // LIB2GEOM_SEEN_PATH_H

/*
  Local Variables:
  mode:c++
  c-file-style:"stroustrup"
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  indent-tabs-mode:nil
  fill-column:99
  End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :