// --------------------------------------------------------------------
// The path object
// --------------------------------------------------------------------
/*

    This file is part of the extensible drawing editor Ipe.
    Copyright (C) 1993-2004  Otfried Cheong

    Ipe is free software; you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    As a special exception, you have permission to link Ipe with the
    CGAL library and distribute executables, as long as you follow the
    requirements of the Gnu General Public License in regard to all of
    the software in the executable aside from CGAL.

    Ipe is distributed in the hope that it will be useful, but WITHOUT
    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
    License for more details.

    You should have received a copy of the GNU General Public License
    along with Ipe; if not, you can find it at
    "http://www.gnu.org/copyleft/gpl.html", or write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

*/

#include "ipepath.h"
#include "ipevisitor.h"
#include "ipepainter.h"

// --------------------------------------------------------------------

static void SnapSegment(const IpeVector &mouse, const IpeSegment &seg,
			IpeVector &pos, double &bound)
{
  if (IpeRect(seg.iP, seg.iQ).CertainClearance(mouse, bound))
    return;
  IpeVector v;
  if (seg.Project(mouse, v)) {
    double d = (mouse - v).Len();
    if (d < bound) {
      pos = v;
      bound = d;
    }
  } else
    IpeObject::SnapVertex(mouse, seg.iQ, pos, bound);
}

static void SnapBezier(const IpeVector &mouse, const IpeBezier &bez,
		       IpeVector &pos, double &bound)
{
  IpeRect box;
  box.AddPoint(bez.iV[0]);
  box.AddPoint(bez.iV[1]);
  box.AddPoint(bez.iV[2]);
  box.AddPoint(bez.iV[3]);
  if (box.CertainClearance(mouse, bound))
    return;

  if (bez.Straight(1.0)) {
    IpeVector prj;
    if (IpeSegment(bez.iV[0], bez.iV[3]).Project(mouse, prj)) {
      // XXX div by zero?
      double t = (prj - bez.iV[0]).Len() / (bez.iV[3] - bez.iV[0]).Len();
      IpeVector v = bez.Point(t);
      double d = (mouse - v).Len();
      if (d < bound) {
	bound = d;
	pos = v;
      }
    } else
      IpeObject::SnapVertex(mouse, bez.iV[3], pos, bound);
  } else {
    IpeBezier l, r;
    bez.Subdivide(l, r);
    SnapBezier(mouse, l, pos, bound);
    SnapBezier(mouse, r, pos, bound);
  }
}

// --------------------------------------------------------------------

/*! \class IpePathSegment
  \ingroup obj
  \brief A segment on an IpeSubPath.

  A segment is either an elliptic arc, a straight segment, a quadratic
  Bezier spline, a cubic Bezier spline, or a B-spline curve, depending
  on its Type().  This is a lightweight object, created on the fly by
  IpeSegmentSubPath::Segment().  There is no public constructor, so the only
  way to create such an object is through that method.

  The Type() is one of the following:

  - \c ESegment: the segment has two control points, and represents a
    line segment.

  - \c EQuad: a quadratic Bezier spline with three control points.

  - \c EBezier: a cubic Bezier spline with four control points.

  - \c ESpline: a B-spline curve with n control points.  The first and
    last control point's knot value is repeated three times, so the
    curve begins and ends in these points.

  - \c EArc: an elliptic arc, with begin and end point.  The
    supporting ellipse is defined by the Matrix(), it is the image
    under the affine transformation Matrix() of the unit circle.
    Matrix() is such that its inverse transforms both start and end
    position to points (nearly) on the unit circle. The arc is the
    image of the positively (counter-clockwise) directed arc from the
    pre-image of the start position to the pre-image of the end
    position.  Whether this is a positively or negatively oriented arc
    in user space depends on the matrix.

*/

//! Create a segment.
/*! Matrix \a m defaults to null, for all segments but arcs. */
IpePathSegment::IpePathSegment(TType type, int num, const IpeVector *cp,
			       const IpeMatrix *m)
  : iType(type), iCP(cp), iNumCP(num), iM(m)
{
  // nothing
}

//! Return segment as IpeBezier.
/*! Panics if segment is not a quadratic or cubic Bezier spline. */
IpeBezier IpePathSegment::Bezier() const
{
  switch (Type()) {
  case EBezier:
    return IpeBezier(CP(0), CP(1), CP(2), CP(3));
  case EQuad:
    return IpeBezier::QuadBezier(CP(0), CP(1), CP(2));
  default:
    assert(false);
    return IpeBezier(); // satisfy compiler
  }
}

//! Return segment as IpeArc.
/*! Panics if segment is not an arc. */
IpeArc IpePathSegment::Arc() const
{
  assert(Type() == EArc);
  return IpeArc(*iM, CP(0), CP(1));
}

//! Convert B-spline to a sequence of Bezier splines.
void IpePathSegment::Beziers(std::vector<IpeBezier> &bez) const
{
  IpeBezier::Spline(NumCP(), iCP, bez);
}

//! Draw the segment.
/*! Current position of the \a painter is already on first control
  point. */
void IpePathSegment::Draw(IpePainter &painter) const
{
  switch (Type()) {
  case ESegment:
    painter.LineTo(CP(1));
    break;
  case EQuad:
  case EBezier:
    painter.CurveTo(Bezier());
    break;
  case ESpline: {
    std::vector<IpeBezier> bez;
    Beziers(bez);
    for (uint i = 0; i < bez.size(); ++i)
      painter.CurveTo(bez[i]);}
    break;
  case EArc: {
    painter.Push();
    painter.Transform(Matrix());
    IpeArc arc = Arc();
    painter.Transform(IpeLinear(arc.iAlpha));
    painter.DrawArc(arc.iBeta - arc.iAlpha);
    painter.Pop();
    break; }
  }
}

//! Add segment to bounding box.
/*! Does not assume that first control point has already been added. */
void IpePathSegment::AddToBBox(IpeRect &box, const IpeMatrix &m) const
{
  switch (Type()) {
  case ESegment:
    box.AddPoint(m * CP(0));
    box.AddPoint(m * CP(1));
    break;
  case EBezier:
  case EQuad:
    box.AddRect((m * Bezier()).BBox());
    break;
  case EArc:
    box.AddRect((m * Arc()).BBox());
    break;
  case ESpline: {
    std::vector<IpeBezier> bez;
    Beziers(bez);
    for (uint i = 0; i < bez.size(); ++i)
      box.AddRect((m * bez[i]).BBox());
    break; }
  }
}

//! Return distance to the segment.
double IpePathSegment::Distance(const IpeVector &v, const IpeMatrix &m,
				double bound) const
{
  switch (Type()) {
  case ESegment:
    return IpeSegment(m * CP(0), m * CP(1)).Distance(v, bound);
  case EBezier:
  case EQuad:
    return (m * Bezier()).Distance(v, bound);
  case EArc:
    return (m * Arc()).Distance(v, bound);
  case ESpline: {
    std::vector<IpeBezier> bez;
    Beziers(bez);
    double d = bound;
    double d1;
    for (uint i = 0; i < bez.size(); ++i) {
      if ((d1 = (m * bez[i]).Distance(v, d)) < d)
	d = d1;
    }
    return d; }
  default: // make compiler happy
    return bound;
  }
}

//! Snap to vertex of the segment.
/*! The method assumes that the first control point has already been
  tested. */
void IpePathSegment::SnapVtx(const IpeVector &mouse, const IpeMatrix &m,
			     IpeVector &pos, double &bound) const
{
  switch (Type()) {
  case ESegment:
    IpeObject::SnapVertex(mouse, m * CP(1), pos, bound);
    break;
  case EQuad:
    IpeObject::SnapVertex(mouse, m * CP(2), pos, bound);
    break;
  case EBezier:
    IpeObject::SnapVertex(mouse, m * CP(3), pos, bound);
    break;
  case EArc:
    // snap to center and endpoints
    IpeObject::SnapVertex(mouse, m * CP(1), pos, bound);
    IpeObject::SnapVertex(mouse, m * CP(0), pos, bound);
    IpeObject::SnapVertex(mouse, m * CP(2), pos, bound);
    break;
  case ESpline:
    // only end point to test
    IpeObject::SnapVertex(mouse, m * CP(NumCP() - 1), pos, bound);
    break;
  }
}

void IpePathSegment::SnapBnd(const IpeVector &mouse, const IpeMatrix &m,
			     IpeVector &pos, double &bound) const
{
  switch (Type()) {
  case ESegment:
    SnapSegment(mouse, IpeSegment(m * CP(0), m * CP(1)), pos, bound);
    break;
  case EBezier:
  case EQuad:
    SnapBezier(mouse, m * Bezier(), pos, bound);
    break;
  case EArc: {
    IpeArc arc = m * Arc();
    IpeVector pos1;
    IpeAngle angle;
    double d1 = arc.Distance(mouse, bound, pos1, angle);
    if (d1 < bound) {
      bound = d1;
      pos = pos1;
    }
    break; }
  case ESpline: {
    std::vector<IpeBezier> bez;
    Beziers(bez);
    for (uint i = 0; i < bez.size(); ++i)
      SnapBezier(mouse, m * bez[i], pos, bound);
    break; }
  }
}

// --------------------------------------------------------------------

/*! \class IpeSubPath
  \ingroup obj
  \brief A subpath of an IpePath.

  A subpath is either open, or closed.  There are two special kinds of
  closed subpaths, namely ellipses and closed B-splines.
*/

//! Implementation of pure virtual destructor.
IpeSubPath::~IpeSubPath()
{
  // nothing
}

//! Is this subpath closed?
/*! Default implementation returns \c true. */
bool IpeSubPath::Closed() const
{
  return true;
}

//! Return this object as an IpeEllipse, or 0 if it's not an ellipse.
const IpeEllipse *IpeSubPath::AsEllipse() const
{
  return 0;
}

//! Return this object as an IpeEllipse, or 0 if it's not an ellipse.
IpeEllipse *IpeSubPath::AsEllipse()
{
  return 0;
}

//! Return this object as an IpeClosedSpline, or 0 if it's not a closed spline.
const IpeClosedSpline *IpeSubPath::AsClosedSpline() const
{
  return 0;
}

//! Return this object as an IpeClosedSpline, or 0 if it's not a closed spline.
IpeClosedSpline *IpeSubPath::AsClosedSpline()
{
  return 0;
}

//! Return this object as an IpeSegmentSubPath, or else 0.
const IpeSegmentSubPath *IpeSubPath::AsSegs() const
{
  return 0;
}

//! Return this object as an IpeSegmentSubPath, or else 0.
IpeSegmentSubPath *IpeSubPath::AsSegs()
{
  return 0;
}

// --------------------------------------------------------------------

/*! \class IpeEllipse
  \ingroup obj
  \brief An ellipse subpath
*/

IpeEllipse::IpeEllipse(const IpeMatrix &m)
  : iM(m)
{
  // nothing
}

IpeSubPath::TType IpeEllipse::Type() const
{
  return EEllipse;
}

const IpeEllipse *IpeEllipse::AsEllipse() const
{
  return this;
}

//! Return this object as an IpeEllipse, or 0 if it's not an ellipse.
IpeEllipse *IpeEllipse::AsEllipse()
{
  return this;
}

IpeSubPath *IpeEllipse::Clone() const
{
  return new IpeEllipse(*this);
}

IpeSubPath *IpeEllipse::Transform(const IpeMatrix &m) const
{
  return new IpeEllipse(m * iM);
}

void IpeEllipse::SaveAsXml(IpeStream &stream) const
{
  stream << Matrix() << " e\n";
}

void IpeEllipse::Draw(IpePainter &painter) const
{
  painter.Push();
  painter.Transform(iM);
  painter.DrawEllipse();
  painter.Pop();
}

void IpeEllipse::AddToBBox(IpeRect &box, const IpeMatrix &m) const
{
  box.AddRect(IpeArc(m * iM).BBox());
}

double IpeEllipse::Distance(const IpeVector &v, const IpeMatrix &m,
			    double bound) const
{
  IpeArc arc(m * iM);
  return arc.Distance(v, bound);
}

//! Snaps to center of ellipse.
void IpeEllipse::SnapVtx(const IpeVector &mouse, const IpeMatrix &m,
			 IpeVector &pos, double &bound) const
{
  IpeObject::SnapVertex(mouse, (m * iM).Translation(), pos, bound);
}

void IpeEllipse::SnapBnd(const IpeVector &mouse, const IpeMatrix &m,
			 IpeVector &pos, double &bound) const
{
  IpeArc arc(m * iM);
  IpeVector pos1;
  IpeAngle angle;
  double d1 = arc.Distance(mouse, bound, pos1, angle);
  if (d1 < bound) {
    bound = d1;
    pos = pos1;
  }
}

// --------------------------------------------------------------------

/*! \class IpeClosedSpline
  \ingroup obj
  \brief A closed B-spline curve.
*/

IpeClosedSpline::IpeClosedSpline(const std::vector<IpeVector> &v)
{
  assert(v.size() >= 3);
  std::copy(v.begin(), v.end(), std::back_inserter(iCP));
}

IpeSubPath::TType IpeClosedSpline::Type() const
{
  return EClosedSpline;
}

const IpeClosedSpline *IpeClosedSpline::AsClosedSpline() const
{
  return this;
}

//! Return this object as an IpeClosedSpline, or 0 if it's not a closed spline.
IpeClosedSpline *IpeClosedSpline::AsClosedSpline()
{
  return this;
}

IpeSubPath *IpeClosedSpline::Clone() const
{
  return new IpeClosedSpline(*this);
}

IpeSubPath *IpeClosedSpline::Transform(const IpeMatrix &m) const
{
  IpeClosedSpline *csp = new IpeClosedSpline(iCP);
  for (uint i = 0; i < csp->iCP.size(); ++i)
    csp->iCP[i] = m * csp->iCP[i];
  return csp;
}

void IpeClosedSpline::SaveAsXml(IpeStream &stream) const
{
  for (uint i = 0; i < iCP.size() - 1; ++i)
    stream << iCP[i] << "\n";
  stream << iCP.back() << " u\n";
}

void IpeClosedSpline::Draw(IpePainter &painter) const
{
  std::vector<IpeBezier> bez;
  Beziers(bez);
  painter.MoveTo(bez.front().iV[0]);
  for (uint i = 0; i < bez.size(); ++i)
    painter.CurveTo(bez[i]);
  painter.ClosePath();
}

void IpeClosedSpline::AddToBBox(IpeRect &box, const IpeMatrix &m) const
{
  std::vector<IpeBezier> bez;
  Beziers(bez);
  for (uint i = 0; i < bez.size(); ++i)
    box.AddRect((m * bez[i]).BBox());
}

double IpeClosedSpline::Distance(const IpeVector &v, const IpeMatrix &m,
				 double bound) const
{
  std::vector<IpeBezier> bez;
  Beziers(bez);
  double d = bound;
  double d1;
  for (uint i = 0; i < bez.size(); ++i) {
    if ((d1 = (m * bez[i]).Distance(v, d)) < d)
      d = d1;
  }
  return d;
}

void IpeClosedSpline::Beziers(std::vector<IpeBezier> &bez) const
{
  IpeBezier::ClosedSpline(iCP.size(), &iCP.front(), bez);
}

void IpeClosedSpline::SnapVtx(const IpeVector &, const IpeMatrix &,
			      IpeVector &, double &) const
{
  // Closed spline has no vertices to snap to
}

void IpeClosedSpline::SnapBnd(const IpeVector &mouse, const IpeMatrix &m,
			      IpeVector &pos, double &bound) const
{
  std::vector<IpeBezier> bez;
  Beziers(bez);
  for (uint i = 0; i < bez.size(); ++i)
    SnapBezier(mouse, m * bez[i], pos, bound);
}

// --------------------------------------------------------------------

/*! \class IpeSegmentSubPath
  \ingroup obj
  \brief Subpath consisting of a sequence of IpePathSegment's.
*/

//! Create an empty, open subpath
IpeSegmentSubPath::IpeSegmentSubPath()
{
  iClosed = false;
}

int IpeSegmentSubPath::BeginCP(int seg) const
{
  int cpbg = 0;
  if (seg > 0)
    cpbg = iSeg[seg-1].iLastCP;
  return cpbg;
}

//! Append a segment (from a different path) to the subpath.
void IpeSegmentSubPath::Append(const IpePathSegment &seg)
{
  if (iSeg.empty())
    iCP.push_back(seg.CP(0));
  assert(seg.CP(0) == iCP.back());
  for (int i = 1; i < seg.NumCP(); ++i)
    iCP.push_back(seg.CP(i));
  if (seg.Type() == IpePathSegment::EArc)
    iM.push_back(seg.Matrix());
  Seg segm;
  segm.iType = seg.Type();
  segm.iLastCP = iCP.size() - 1;
  segm.iMatrix = iM.size() - 1;
  iSeg.push_back(segm);
}

//! Append a segment to the subpath, reversing its orientation.
void IpeSegmentSubPath::AppendReversed(const IpePathSegment &seg)
{
  if (iSeg.empty())
    iCP.push_back(seg.CP(0));
  assert(seg.Last() == iCP.back());
  for (int i = seg.NumCP() - 2; i >= 0; --i)
    iCP.push_back(seg.CP(i));
  if (seg.Type() == IpePathSegment::EArc)
    iM.push_back(seg.Matrix() * IpeLinear(1, 0, 0, -1));
  Seg segm;
  segm.iType = seg.Type();
  segm.iLastCP = iCP.size() - 1;
  segm.iMatrix = iM.size() - 1;
  iSeg.push_back(segm);
}

//! Append a straight segment to the subpath.
void IpeSegmentSubPath::AppendSegment(const IpeVector &v0, const IpeVector &v1)
{
  if (iSeg.empty())
    iCP.push_back(v0);
  assert(v0 == iCP.back());
  iCP.push_back(v1);
  Seg seg;
  seg.iType = IpePathSegment::ESegment;
  seg.iLastCP = iCP.size() - 1;
  seg.iMatrix = iM.size() - 1;
  iSeg.push_back(seg);
}

//! Append elliptic arc to the subpath.
void IpeSegmentSubPath::AppendArc(const IpeMatrix &m, const IpeVector &v0,
				  const IpeVector &v1)
{
  if (iSeg.empty())
    iCP.push_back(v0);
  assert(v0 == iCP.back());
  iCP.push_back(v1);
  iM.push_back(m);
  Seg seg;
  seg.iType = IpePathSegment::EArc;
  seg.iLastCP = iCP.size() - 1;
  seg.iMatrix = iM.size() - 1;
  iSeg.push_back(seg);
}

//! Append quadratic Bezier spline.
void IpeSegmentSubPath::AppendQuad(const IpeVector &v0, const IpeVector &v1,
				   const IpeVector &v2)
{
  if (iSeg.empty())
    iCP.push_back(v0);
  assert(v0 == iCP.back());
  iCP.push_back(v1);
  iCP.push_back(v2);
  Seg seg;
  seg.iType = IpePathSegment::EQuad;
  seg.iLastCP = iCP.size() - 1;
  seg.iMatrix = iM.size() - 1;
  iSeg.push_back(seg);
}

//! Append cubic Bezier spline.
void IpeSegmentSubPath::AppendBezier(const IpeVector &v0, const IpeVector &v1,
				     const IpeVector &v2, const IpeVector &v3)
{
  if (iSeg.empty())
    iCP.push_back(v0);
  assert(v0 == iCP.back());
  iCP.push_back(v1);
  iCP.push_back(v2);
  iCP.push_back(v3);
  Seg seg;
  seg.iType = IpePathSegment::EBezier;
  seg.iLastCP = iCP.size() - 1;
  seg.iMatrix = iM.size() - 1;
  iSeg.push_back(seg);
}

//! Append B-spline curve.
void IpeSegmentSubPath::AppendSpline(const std::vector<IpeVector> &v)
{
  if (iSeg.empty())
    iCP.push_back(v[0]);
  assert(v[0] == iCP.back());
  for (uint i = 1; i < v.size(); ++i)
    iCP.push_back(v[i]);
  Seg seg;
  seg.iType = IpePathSegment::ESpline;
  seg.iLastCP = iCP.size() - 1;
  seg.iMatrix = iM.size() - 1;
  iSeg.push_back(seg);
}

//! Set whether subpath is closed or not.
void IpeSegmentSubPath::SetClosed(bool closed)
{
  iClosed = closed;
}

//! Move control point \a cp of segment \a cp to position \a pos.
/*! If \a seg or \a cp are negative, they count from the end. */
void IpeSegmentSubPath::MoveCP(int seg, int cp, const IpeVector &pos)
{
  if (seg < 0)
    seg += iSeg.size();
  int j = BeginCP(seg) + cp;
  if (cp < 0)
    j = iSeg[seg].iLastCP + 1 + cp;
  iCP[j] = pos;
  if (iSeg[seg].iType == IpePathSegment::EArc)
    RecomputeMatrix(seg);
  if (j == BeginCP(seg) && seg > 0 &&
      iSeg[seg - 1].iType == IpePathSegment::EArc)
    RecomputeMatrix(seg - 1);
  else if (j == iSeg[seg].iLastCP && seg + 1 < int(iSeg.size()) &&
	   iSeg[seg + 1].iType == IpePathSegment::EArc)
    RecomputeMatrix(seg + 1);
}

//! Recompute matrix of an arc segment after a CP has been moved.
void IpeSegmentSubPath::RecomputeMatrix(int seg)
{
  int i = iSeg[seg].iLastCP - 1;
  IpeMatrix m = iM[iSeg[seg].iMatrix];
  IpeMatrix inv = m.Inverse();
  IpeVector v0 = inv * iCP[i];
  IpeVector v1 = inv * iCP[i + 1];
  IpeLine l(0.5 * (v0 + v1), (v1 - v0).Normalized().Orthogonal());
  IpeVector c = l.Project(IpeVector::Zero);
  double r = (v0 - c).Len();
  IpeMatrix m1(r, 0, 0, r, c.iX, c.iY);
  iM[iSeg[seg].iMatrix] = m * m1;
}

//! Insert a control point into a spline segment.
/*! If \a seg is negative, counts from the end.
  If \a cp is negative, append to segment. */
void IpeSegmentSubPath::InsertCP(int seg, int cp, const IpeVector &pos)
{
  if (seg < 0)
    seg += iSeg.size();
  assert(iSeg[seg].iType == IpePathSegment::ESpline);
  if (cp < 0)
    cp = iSeg[seg].iLastCP + 1;
  else
    cp = BeginCP(seg) + cp;
  iCP.insert(iCP.begin() + cp, pos);
  for (uint i = seg; i < iSeg.size(); ++i)
    iSeg[i].iLastCP++;
}

//! Delete a control point from a spline segment.
/*! If \a seg or \a cp are negative, count from the end.
  This cannot be used to remove the first or last CP of a spline curve,
  unless the spline is the first or last segment of the subpath.
  If the spline has only two vertices, it is simply deleted. */
void IpeSegmentSubPath::DeleteCP(int seg, int cp)
{
  if (Segment(seg).NumCP() == 2) {
    DeleteSegment(seg);
    return;
  }

  if (seg < 0)
    seg += iSeg.size();
  assert(iSeg[seg].iType == IpePathSegment::ESpline);
  if (cp < 0)
    cp = iSeg[seg].iLastCP + 1 + cp;
  else
    cp = BeginCP(seg) + cp;
  iCP.erase(iCP.begin() + cp);
  for (uint i = seg; i < iSeg.size(); ++i)
    iSeg[i].iLastCP--;
}

//! Insert a zero-length segment before segment \a seg.
/*! If \a seg is negative, it counts from the end.  */
void IpeSegmentSubPath::InsertSegment(int seg)
{
  if (seg < 0)
    seg += iSeg.size();
  int beg = BeginCP(seg);
  IpeVector v = iCP[beg];
  // duplicate CP
  iCP.insert(iCP.begin() + beg, v);
  for (uint i = seg; i < iSeg.size(); ++i)
    iSeg[i].iLastCP++;
  Seg segm;
  segm.iType = IpePathSegment::ESegment;
  segm.iLastCP = beg + 1;
  segm.iMatrix = (seg > 0) ? iSeg[seg-1].iMatrix : 0;
  iSeg.insert(iSeg.begin() + seg, segm);
}

//! Delete a segment from the subpath.
/*! If \a seg is negative, it counts from the end.  If a segment in
  the middle is deleted, the first and last control point must be
  identical. */
void IpeSegmentSubPath::DeleteSegment(int seg)
{
  if (iSeg.size() == 1) {
    // only one segment, make path empty
    iCP.clear();
    iM.clear();
    iSeg.clear();
    return;
  }
  if (seg < 0)
    seg += iSeg.size();
  int beg = BeginCP(seg);
  int fin = iSeg[seg].iLastCP;
  if (0 < seg && seg + 1 < int(iSeg.size()))
    assert(iCP[beg] == iCP[fin]);
  if (seg + 1 == int(iSeg.size())) {
    beg++;
    fin++;
  }
  int cpDiff = fin - beg;
  iCP.erase(iCP.begin() + beg, iCP.begin() + fin);
  for (uint i = seg + 1; i < iSeg.size(); ++i)
    iSeg[i].iLastCP -= cpDiff;
  if (iSeg[seg].iType == IpePathSegment::EArc) {
    iM.erase(iM.begin() + iSeg[seg].iMatrix);
    for (uint i = seg + 1; i < iSeg.size(); ++i)
      iSeg[i].iMatrix--;
  }
  iSeg.erase(iSeg.begin() + seg);
}

//! Replace segment by a straight segment.
/*! If \a seg is negative, counts from the end. */
void IpeSegmentSubPath::Straighten(int seg)
{
  if (seg < 0)
    seg += iSeg.size();
  int beg = BeginCP(seg);
  int fin = iSeg[seg].iLastCP;
  // need to remove control points from beg + 1 to fin
  int cpDiff = fin - beg - 1;
  iCP.erase(iCP.begin() + beg + 1, iCP.begin() + fin);
  for (uint i = seg; i < iSeg.size(); ++i)
    iSeg[i].iLastCP -= cpDiff;
  if (iSeg[seg].iType == IpePathSegment::EArc) {
    iM.erase(iM.begin() + iSeg[seg].iMatrix);
    for (uint i = seg + 1; i < iSeg.size(); ++i)
      iSeg[i].iMatrix--;
  }
  iSeg[seg].iType = IpePathSegment::ESegment;
}

//! Change the matrix of arc segment.
/*! If \a seg is negative, counts from the end. */
void IpeSegmentSubPath::SetMatrix(int seg, const IpeMatrix &m)
{
  if (seg < 0)
    seg += iSeg.size();
  assert(iSeg[seg].iType == IpePathSegment::EArc);
  iM[iSeg[seg].iMatrix] = m;
}

IpeSubPath::TType IpeSegmentSubPath::Type() const
{
  return ESegments;
}

const IpeSegmentSubPath *IpeSegmentSubPath::AsSegs() const
{
  return this;
}

IpeSegmentSubPath *IpeSegmentSubPath::AsSegs()
{
  return this;
}

//! Return segment.
/*! If \a i is negative, elements from the end are returned.  The
  closing segment of a closed path is not accessible this way (use
  ClosingSegment instead)!
*/
IpePathSegment IpeSegmentSubPath::Segment(int i) const
{
  if (i < 0)
    i += iSeg.size();
  const Seg &seg = iSeg[i];
  const IpeMatrix *m = &iM[seg.iMatrix];
  int cpbg = BeginCP(i);
  const IpeVector *cp = &iCP[cpbg];
  return IpePathSegment(seg.iType, seg.iLastCP - cpbg + 1, cp, m);
}

IpeSubPath *IpeSegmentSubPath::Clone() const
{
  return new IpeSegmentSubPath(*this);
}

IpeSubPath *IpeSegmentSubPath::Transform(const IpeMatrix &m) const
{
  IpeSegmentSubPath* sp = new IpeSegmentSubPath(*this);
  for (uint i = 0; i < sp->iCP.size(); ++i)
    sp->iCP[i] = m * sp->iCP[i];
  for (uint i = 0; i < sp->iM.size(); ++i)
    sp->iM[i] = m * sp->iM[i];
  return sp;
}

void IpeSegmentSubPath::SaveAsXml(IpeStream &stream) const
{
  // moveto first control point
  stream << iCP[0] << " m\n";
  int vtx = 1; // next control point
  int mat = 0;
  for (std::vector<Seg>::const_iterator it = iSeg.begin();
       it != iSeg.end(); ++it) {
    switch (it->iType) {
    case IpePathSegment::ESegment:
      assert(vtx == it->iLastCP);
      stream << iCP[vtx++] << " l\n";
      break;
    case IpePathSegment::EBezier:
      assert(vtx + 2 == it->iLastCP);
      stream << iCP[vtx] << " " << iCP[vtx+1] << " " << iCP[vtx+2] << " c\n";
      vtx += 3;
      break;
    case IpePathSegment::EQuad:
      assert(vtx + 1 == it->iLastCP);
      stream << iCP[vtx] << " " << iCP[vtx+1] << " q\n";
      vtx += 2;
      break;
    case IpePathSegment::EArc:
      assert(vtx == it->iLastCP && mat == it->iMatrix);
      stream << iM[mat++] << " " << iCP[vtx++] << " a\n";
      break;
    case IpePathSegment::ESpline:
      while (vtx < it->iLastCP)
	stream << iCP[vtx++] << "\n";
      stream << iCP[vtx++] << " s\n";
      break;
    }
  }
  if (Closed())
    stream << "h\n";
}

void IpeSegmentSubPath::Draw(IpePainter &painter) const
{
  painter.MoveTo(iCP[0]);
  for (int i = 0; i < NumSegments(); ++i) {
    Segment(i).Draw(painter);
  }
  if (Closed())
    painter.ClosePath();
}

void IpeSegmentSubPath::AddToBBox(IpeRect &box, const IpeMatrix &m) const
{
  for (int i = 0; i < NumSegments(); ++i)
    Segment(i).AddToBBox(box, m);
}

double IpeSegmentSubPath::Distance(const IpeVector &v, const IpeMatrix &m,
				   double bound) const
{
  double d = bound;
  for (int i = 0; i < NumSegments(); ++i) {
    double d1 = Segment(i).Distance(v, m, d);
    if (d1 < d)
      d = d1;
  }
  if (Closed()) {
    IpeVector u[2];
    double d1 = ClosingSegment(u).Distance(v, m , d);
    if (d1 < d)
      d = d1;
  }
  return d;
}

void IpeSegmentSubPath::SnapVtx(const IpeVector &mouse, const IpeMatrix &m,
				IpeVector &pos, double &bound) const
{
  IpeObject::SnapVertex(mouse, m * Segment(0).CP(0), pos, bound);
  for (int i = 0; i < NumSegments(); ++i)
    Segment(i).SnapVtx(mouse, m, pos, bound);
}

void IpeSegmentSubPath::SnapBnd(const IpeVector &mouse, const IpeMatrix &m,
				IpeVector &pos, double &bound) const
{
  IpeObject::SnapVertex(mouse, m * Segment(0).CP(0), pos, bound);
  for (int i = 0; i < NumSegments(); ++i)
    Segment(i).SnapBnd(mouse, m, pos, bound);
  if (Closed()) {
    IpeVector u[2];
    ClosingSegment(u).SnapBnd(mouse, m, pos, bound);
  }
}

//! Returns the closing segment of a closed path.
/*! Since the closing segment isn't actually stored inside this
  object, you have to provide a length-2 vector for the control points.
*/
IpePathSegment IpeSegmentSubPath::ClosingSegment(IpeVector u[2]) const
{
  assert(iClosed);
  u[0] = iCP.back();
  u[1] = iCP.front();
  return IpePathSegment(IpePathSegment::ESegment, 2, u, 0);
}

// --------------------------------------------------------------------

/*! \class IpePath
  \ingroup obj
  \brief The path object (polylines, polygons, and generalizations).

  This object follows the PDF rendering model, but is actually a bit
  more complicated since we add new subtypes: arcs, parabolas, uniform
  B-splines (in PDF, all of these are converted to cubic Bezier
  splines).  Unlike Ipe 5, we can now represent objects consisting of
  more than one subpath. Note that Ipe 5's spline and arc
  objects are now represented as IpePath objects.

  A path object consists of a set of subpaths (IpeSubPath), each of
  which is either open or closed, and which are rendered by stroking
  and filling as a whole. The distinction between open and closed is
  meaningful for stroking only, for filling any open subpath is
  implicitely closed.  Stroking a set of subpaths is identical to
  stroking them individually.  This is not true for filling: using
  several subpaths, one can construct objects with holes, and more
  complicated pattern.  The filling algorithm is the <b>even-odd
  rule</b> of PDF: To determine whether a point lies inside the filled
  shape, draw a ray from that point in any direction, and count the
  number of path segments that cross the ray.  If this number is odd,
  the point is inside; if even, the point is outside. (IpePath objects
  can also render using the <b>winding fill rule</b> by setting the
  StrokeStyle attribute.  This isn't really supported by the Ipe user
  interface, which doesn't show the orientation of paths.)

  A subpath consists of a sequence of segments.  (A complete ellipse
  and a closed B-spline curve can appear as special cases of subpaths
  that cannot be further decomposed into segments.)  Segments are
  either straight, a quadratic Bezier spline, a cubic Bezier spline,
  an elliptic arc, or a uniform cubic B-spline.  The segmented subpath
  class IpeSegmentSubPath returns segments as IpePathSegment (but they are
  not internally stored that way).

*/

static IpeVector GetVector(std::vector<double> &args)
{
  IpeVector v;
  v.iX = args[0];
  v.iY = args[1];
  args.erase(args.begin(), args.begin() + 2);
  return v;
}

static IpeMatrix GetMatrix(std::vector<double> &args)
{
  IpeMatrix m;
  for (int i = 0; i < 6; ++i)
    m.iA[i] = args[i];
  args.erase(args.begin(), args.begin() + 6);
  return m;
}

//! Construct from XML data.
IpePath::IpePath(IpeRepository *rep, const IpeXmlAttributes &attr,
		 IpeString data)
  : IpeFillable(rep, attr)
{
  iForwardArrow = rep->MakeScalar(IpeAttribute::EArrowSize, attr["arrow"]);
  iBackwardArrow =
    rep->MakeScalar(IpeAttribute::EArrowSize, attr["backarrow"]);

  iImp = new Imp;
  iImp->iRefCount = 1;

  IpeLex stream(data);
  IpeString word;
  IpeString type;
  IpeSegmentSubPath *sp = 0;
  IpeVector org;
  std::vector<double> args;
  do {
    if (stream.Token() == "h") { // closing path
      assert(sp);
      stream.NextToken(); // eat token
      sp->SetClosed(true);
      sp=0;
    } else if (stream.Token() == "m") {
      assert(args.size() == 2);
      stream.NextToken(); // eat token
      // begin new subpath
      sp = new IpeSegmentSubPath;
      iImp->iSubPaths.push_back(sp);
      org = GetVector(args);
    } else if (stream.Token() == "l") {
      assert(sp && args.size() > 0 && (args.size() % 2 == 0));
      stream.NextToken(); // eat token
      while (!args.empty()) {
	IpeVector v = GetVector(args);
	sp->AppendSegment(org, v);
	org = v;
      }
    } else if (stream.Token() == "q") {
      assert(sp && args.size() == 4);
      stream.NextToken();
      IpeVector v1 = GetVector(args);
      IpeVector v2 = GetVector(args);
      sp->AppendQuad(org, v1, v2);
      org = v2;
    } else if (stream.Token() == "c") {
      assert(sp && args.size() >= 6 && (args.size() % 6 == 0));
      stream.NextToken();
      while (!args.empty()) {
	IpeVector v1 = GetVector(args);
	IpeVector v2 = GetVector(args);
	IpeVector v3 = GetVector(args);
	sp->AppendBezier(org, v1, v2, v3);
	org = v3;
      }
    } else if (stream.Token() == "a") {
      assert(sp && args.size() == 8);
      stream.NextToken();
      IpeMatrix m = GetMatrix(args);
      IpeVector v1 = GetVector(args);
      sp->AppendArc(m, org, v1);
      org = v1;
    } else if (stream.Token() == "s") {
      assert(sp && args.size() >= 2 && (args.size() % 2 == 0));
      stream.NextToken();
      std::vector<IpeVector> v;
      v.push_back(org);
      while (!args.empty())
	v.push_back(GetVector(args));
      sp->AppendSpline(v);
      org = v.back();
    } else if (stream.Token() == "e") {
      assert(args.size() == 6);
      stream.NextToken();
      sp = 0;
      IpeEllipse *e = new IpeEllipse(GetMatrix(args));
      iImp->iSubPaths.push_back(e);
    } else if (stream.Token() == "u") {
      assert(args.size() >= 6 && (args.size() % 2 == 0));
      stream.NextToken();
      sp = 0;
      std::vector<IpeVector> v;
      while (!args.empty())
	v.push_back(GetVector(args));
      IpeClosedSpline *e = new IpeClosedSpline(v);
      iImp->iSubPaths.push_back(e);
    } else { // must be a number
      double num;
      stream >> num;
      args.push_back(num);
    }
    stream.SkipWhitespace();
  } while (!stream.Eos());
  MakeArrowData();
}

//! Create empty path object, and null/default attributes.
IpePath::IpePath(const IpeAllAttributes &attr)
  : IpeFillable(attr)
{
  if (attr.iForwardArrow)
    iForwardArrow = attr.iArrowSize;
  if (attr.iBackwardArrow)
    iBackwardArrow = attr.iArrowSize;
  iImp = new Imp;
  iImp->iRefCount = 1;
}

//! Create a rectangle.
IpePath::IpePath(const IpeAllAttributes &attr, const IpeRect &rect)
  : IpeFillable(attr)
{
  iImp = new Imp;
  iImp->iRefCount = 1;
  IpeVector v[4];
  v[0] = rect.Min();
  v[1] = rect.BottomRight();
  v[2] = rect.Max();
  v[3] = rect.TopLeft();
  IpeSegmentSubPath *sp = new IpeSegmentSubPath;
  sp->AppendSegment(v[0], v[1]);
  sp->AppendSegment(v[1], v[2]);
  sp->AppendSegment(v[2], v[3]);
  sp->SetClosed(true);
  iImp->iSubPaths.push_back(sp);
  MakeArrowData();
}

//! Create a single line segment from \c seg.iP to \c seg.iQ.
IpePath::IpePath(const IpeAllAttributes &attr,
		 const IpeSegment &seg)
  : IpeFillable(attr)
{
  if (attr.iForwardArrow)
    iForwardArrow = attr.iArrowSize;
  if (attr.iBackwardArrow)
    iBackwardArrow = attr.iArrowSize;
  iImp = new Imp;
  iImp->iRefCount = 1;
  IpeSegmentSubPath *sp = new IpeSegmentSubPath;
  sp->AppendSegment(seg.iP, seg.iQ);
  iImp->iSubPaths.push_back(sp);
  MakeArrowData();
}

//! Create circle with \a center and \a radius.
IpePath::IpePath(const IpeAllAttributes &attr,
		 const IpeVector &center, double radius)
  : IpeFillable(attr)
{
  iImp = new Imp;
  iImp->iRefCount = 1;
  IpeEllipse *e = new IpeEllipse(IpeMatrix(radius, 0.0, 0.0, radius,
					   center.iX, center.iY));
  iImp->iSubPaths.push_back(e);
  MakeArrowData();
}

//! Create circular arc with \a center, \a radius, between given angles.
/*! If \a alpha1 is larger than \a alpha0, the arc is oriented positively,
  otherwise negatively. */
IpePath::IpePath(const IpeAllAttributes &attr,
		 const IpeVector &center, double radius,
		 double alpha0, double alpha1)
  : IpeFillable(attr)
{
  if (attr.iForwardArrow)
    iForwardArrow = attr.iArrowSize;
  if (attr.iBackwardArrow)
    iBackwardArrow = attr.iArrowSize;
  iImp = new Imp;
  iImp->iRefCount = 1;
  IpeMatrix m = IpeMatrix(radius, 0, 0, radius, center.iX, center.iY);
  IpeVector v0 = m * IpeVector(IpeAngle(alpha0));
  IpeVector v1 = m * IpeVector(IpeAngle(alpha1));
  if (alpha1 < alpha0)
    // negative orientation
    m = m * IpeLinear(1, 0, 0, -1);
  IpeSegmentSubPath *sp = new IpeSegmentSubPath;
  sp->AppendArc(m, v0, v1);
  iImp->iSubPaths.push_back(sp);
  MakeArrowData();
}

//! Return a clone (constant-time).
IpeObject *IpePath::Clone() const
{
  return new IpePath(*this);
}

//! Copy constructor (takes care of reference counting).
IpePath::IpePath(const IpePath &rhs)
  : IpeFillable(rhs)
{
  iForwardArrow = rhs.iForwardArrow;
  iBackwardArrow = rhs.iBackwardArrow;
  iImp = rhs.iImp;
  iImp->iRefCount++;
}

//! Destructor (takes care of reference counting).
IpePath::~IpePath()
{
  if (iImp->iRefCount == 1)
    delete iImp;
  else
    iImp->iRefCount--;
}

IpePath::Imp::~Imp()
{
  // delete the subpaths
  for (IpeSubPathSeq::iterator it = iSubPaths.begin();
       it != iSubPaths.end(); ++it) {
    delete *it;
    *it = 0;
  }
}

//! Assignment operator (constant-time).
IpePath &IpePath::operator=(const IpePath &rhs)
{
  if (this != &rhs) {
    if (iImp->iRefCount == 1)
      delete iImp;
    else
      iImp->iRefCount--;
    iImp = rhs.iImp;
    iImp->iRefCount++;
    iForwardArrow = rhs.iForwardArrow;
    iBackwardArrow = rhs.iBackwardArrow;
    IpeFillable::operator=(rhs);
  }
  return *this;
}

//! Compute the arrow information.
void IpePath::MakeArrowData()
{
  assert(NumSubPaths() > 0);
  if (NumSubPaths() > 1 || SubPath(0)->Closed()) {
    iBackwardArrow = IpeAttribute();
    iForwardArrow = IpeAttribute();
    iImp->iForward.iOk = false;
    iImp->iBackward.iOk = false;
  } else {
    IpePathSegment seg = SubPath(0)->AsSegs()->Segment(0);
    iImp->iBackward.iOk = true;
    iImp->iBackward.iPos = seg.CP(0);
    if (seg.Type() == IpePathSegment::EArc) {
      IpeAngle alpha = (seg.Matrix().Inverse() * seg.CP(0)).Angle();
      iImp->iBackward.iDir = (seg.Matrix().Linear() *
			      IpeVector(IpeAngle(alpha - IpeHalfPi))).Angle();
    } else {
      if (seg.CP(1) == seg.CP(0))
	iImp->iBackward.iOk = false;
      else
	iImp->iBackward.iDir = (iImp->iBackward.iPos - seg.CP(1)).Angle();
    }

    seg = SubPath(0)->AsSegs()->Segment(-1);
    iImp->iForward.iOk = true;
    iImp->iForward.iPos = seg.Last();
    if (seg.Type() == IpePathSegment::EArc) {
      IpeAngle alpha = (seg.Matrix().Inverse() * seg.CP(1)).Angle();
      iImp->iForward.iDir = (seg.Matrix().Linear() *
			      IpeVector(IpeAngle(alpha + IpeHalfPi))).Angle();
    } else {
      if (seg.CP(seg.NumCP() - 2) == seg.Last())
	iImp->iForward.iOk = false;
      else
	iImp->iForward.iDir =
	  (iImp->iForward.iPos - seg.CP(seg.NumCP() - 2)).Angle();
    }
  }
}

//! Return pointer to this object.
IpePath *IpePath::AsPath()
{
  return this;
}

//! Call VisitPath of visitor.
void IpePath::Accept(IpeVisitor &visitor) const
{
  visitor.VisitPath(this);
}

void IpePath::SaveAsXml(IpePainter &painter, IpeStream &stream,
			IpeString layer) const
{
  stream << "<path";
  SaveAttributesAsXml(painter, stream, layer);
  SaveFillAttributesAsXml(painter, stream);
  const IpeRepository *rep = painter.Repository();
  if (!iForwardArrow.IsNull())
    stream << " arrow=\"" << rep->String(iForwardArrow) << "\"";
  if (!iBackwardArrow.IsNull())
    stream << " backarrow=\"" << rep->String(iBackwardArrow) << "\"";
  stream << ">\n";
  for (int i = 0; i < NumSubPaths(); ++i)
    SubPath(i)->SaveAsXml(stream);
  stream << "</path>\n";
}

//! Draw an arrow of \a size with tip at \a v1 directed from \a v0 to \a v1.
void IpePath::DrawArrow(IpePainter &painter,
			IpeVector pos, IpeAngle angle,
			IpeAttribute size)
{
  IpeAttribute absSize = painter.StyleSheet()->Find(size);

  // draw in fill color if stroke color is void.
  IpeAttribute color = painter.Stroke();
  if (color.IsNullOrVoid())
    color = painter.Fill();

  // check whether arrow needs to be drawn at all
  if (color.IsNullOrVoid() || !absSize)
    return;

  double siz = painter.Repository()->ToScalar(absSize).ToDouble();

  painter.Push();
  painter.SetFill(color);
  painter.SetStroke(color);
  painter.SetDashStyle(IpeAttribute::Solid());
  painter.Translate(pos);
  painter.Transform(IpeLinear(angle));
  painter.Untransform(true);
  painter.NewPath();
  painter.MoveTo(IpeVector::Zero);
  painter.LineTo(IpeVector(-siz, siz/3.0));
  painter.LineTo(IpeVector(-siz, -siz/3.0));
  painter.ClosePath();
  painter.DrawPath();
  painter.Pop();
}

//! Add a subpath to object.
/*! This can only be used directly after the creation of this path
  object.  Once the object has been copied or assigned, this method will
  panic.

  IpePath takes ownership of the subpath.
*/
void IpePath::AddSubPath(IpeSubPath *sp)
{
  assert(iImp->iRefCount == 1);
  iImp->iSubPaths.push_back(sp);
  MakeArrowData();
}

void IpePath::Draw(IpePainter &painter) const
{
  ApplyAttributes(painter);
  painter.NewPath();
  for (int i = 0; i < NumSubPaths(); ++i)
    SubPath(i)->Draw(painter);
  painter.DrawPath();
  // Draw arrows
  if (iImp->iForward.iOk)
    DrawArrow(painter, iImp->iForward.iPos, iImp->iForward.iDir,
	      ForwardArrow());
  if (iImp->iBackward.iOk)
    DrawArrow(painter, iImp->iBackward.iPos, iImp->iBackward.iDir,
	      BackwardArrow());
  painter.Pop();
}

void IpePath::AddToBBox(IpeRect &box, const IpeMatrix &m) const
{
  IpeMatrix m1 = m * Matrix();
  for (int i = 0; i < NumSubPaths(); ++i)
    SubPath(i)->AddToBBox(box, m1);
}

double IpePath::Distance(const IpeVector &v, const IpeMatrix &m,
			 double bound) const
{
  IpeMatrix m1 = m * Matrix();
  double d = bound;
  for (int i = 0; i < NumSubPaths(); ++i) {
    double d1 = SubPath(i)->Distance(v, m1, d);
    if (d1 < d)
      d = d1;
  }
  return d;
}

void IpePath::SnapVtx(const IpeVector &mouse, const IpeMatrix &m,
		      IpeVector &pos, double &bound) const
{
  IpeMatrix m1 = m * Matrix();
  for (int i = 0; i < NumSubPaths(); ++i)
    SubPath(i)->SnapVtx(mouse, m1, pos, bound);
}

void IpePath::SnapBnd(const IpeVector &mouse, const IpeMatrix &m,
		      IpeVector &pos, double &bound) const
{
  IpeMatrix m1 = m * Matrix();
  for (int i = 0; i < NumSubPaths(); ++i)
    SubPath(i)->SnapBnd(mouse, m1, pos, bound);
}

//! Set forward arrow (if the object can take it).
void IpePath::SetForwardArrow(IpeAttribute size)
{
  if (iImp->iForward.iOk)
    iForwardArrow = size;
}

//! Set backward arrow (if the object can take it).
void IpePath::SetBackwardArrow(IpeAttribute size)
{
  if (iImp->iBackward.iOk)
    iBackwardArrow = size;
}

void IpePath::CheckStyle(const IpeStyleSheet *sheet,
			 IpeAttributeSeq &seq) const
{
  IpeFillable::CheckStyle(sheet, seq);
  CheckSymbol(iForwardArrow, sheet, seq);
  CheckSymbol(iBackwardArrow, sheet, seq);
}

// --------------------------------------------------------------------