src/ui/tool/node.cpp

   1 /** @file
   2  * Editable node - implementation
   3  */
   4 /* Authors:
   5  *   Krzysztof Kosiński <tweenk.pl@gmail.com>
   6  *
   7  * Copyright (C) 2009 Authors
   8  * Released under GNU GPL, read the file 'COPYING' for more information
   9  */
  10
  11 #include <iostream>
  12 #include <stdexcept>
  13 #include <boost/utility.hpp>
  14 #include <glib.h>
  15 #include <glib/gi18n.h>
  16 #include <2geom/bezier-utils.h>
  17 #include <2geom/transforms.h>
  18
  19 #include "display/sp-ctrlline.h"
  20 #include "display/sp-canvas.h"
  21 #include "display/sp-canvas-util.h"
  22 #include "desktop.h"
  23 #include "desktop-handles.h"
  24 #include "preferences.h"
  25 #include "snap.h"
  26 #include "snap-preferences.h"
  27 #include "sp-metrics.h"
  28 #include "sp-namedview.h"
  29 #include "ui/tool/control-point-selection.h"
  30 #include "ui/tool/event-utils.h"
  31 #include "ui/tool/multi-path-manipulator.h"
  32 #include "ui/tool/node.h"
  33 #include "ui/tool/path-manipulator.h"
  34
  35 namespace Inkscape {
  36 namespace UI {
  37
  38 static SelectableControlPoint::ColorSet node_colors = {
  39     {
  40         {0xbfbfbf00, 0x000000ff}, // normal fill, stroke
  41         {0xff000000, 0x000000ff}, // mouseover fill, stroke
  42         {0xff000000, 0x000000ff}  // clicked fill, stroke
  43     },
  44     {0x0000ffff, 0x000000ff}, // normal fill, stroke when selected
  45     {0xff000000, 0x000000ff}, // mouseover fill, stroke when selected
  46     {0xff000000, 0x000000ff}  // clicked fill, stroke when selected
  47 };
  48
  49 static ControlPoint::ColorSet handle_colors = {
  50     {0xffffffff, 0x000000ff}, // normal fill, stroke
  51     {0xff000000, 0x000000ff}, // mouseover fill, stroke
  52     {0xff000000, 0x000000ff}  // clicked fill, stroke
  53 };
  54
  55 std::ostream &operator<<(std::ostream &out, NodeType type)
  56 {
  57     switch(type) {
  58     case NODE_CUSP: out << 'c'; break;
  59     case NODE_SMOOTH: out << 's'; break;
  60     case NODE_AUTO: out << 'a'; break;
  61     case NODE_SYMMETRIC: out << 'z'; break;
  62     default: out << 'b'; break;
  63     }
  64     return out;
  65 }
  66
  67 /** Computes an unit vector of the direction from first to second control point */
  68 static Geom::Point direction(Geom::Point const &first, Geom::Point const &second) {
  69     return Geom::unit_vector(second - first);
  70 }
  71
  72 /**
  73  * @class Handle
  74  * @brief Control point of a cubic Bezier curve in a path.
  75  *
  76  * Handle keeps the node type invariant only for the opposite handle of the same node.
  77  * Keeping the invariant on node moves is left to the %Node class.
  78  */
  79
  80 Geom::Point Handle::_saved_other_pos(0, 0);
  81 double Handle::_saved_length = 0.0;
  82 bool Handle::_drag_out = false;
  83
  84 Handle::Handle(NodeSharedData const &data, Geom::Point const &initial_pos, Node *parent)
  85     : ControlPoint(data.desktop, initial_pos, Gtk::ANCHOR_CENTER, SP_CTRL_SHAPE_CIRCLE, 7.0,
  86         &handle_colors, data.handle_group)
  87     , _parent(parent)
  88     , _degenerate(true)
  89 {
  90     _cset = &handle_colors;
  91     _handle_line = sp_canvas_item_new(data.handle_line_group, SP_TYPE_CTRLLINE, NULL);
  92     setVisible(false);
  93 }
  94 Handle::~Handle()
  95 {
  96     //sp_canvas_item_hide(_handle_line);
  97     gtk_object_destroy(GTK_OBJECT(_handle_line));
  98 }
  99
 100 void Handle::setVisible(bool v)
 101 {
 102     ControlPoint::setVisible(v);
 103     if (v) sp_canvas_item_show(_handle_line);
 104     else sp_canvas_item_hide(_handle_line);
 105 }
 106
 107 void Handle::move(Geom::Point const &new_pos)
 108 {
 109     Handle *other, *towards, *towards_second;
 110     Node *node_towards; // node in direction of this handle
 111     Node *node_away; // node in the opposite direction
 112     if (this == &_parent->_front) {
 113         other = &_parent->_back;
 114         node_towards = _parent->_next();
 115         node_away = _parent->_prev();
 116         towards = node_towards ? &node_towards->_back : 0;
 117         towards_second = node_towards ? &node_towards->_front : 0;
 118     } else {
 119         other = &_parent->_front;
 120         node_towards = _parent->_prev();
 121         node_away = _parent->_next();
 122         towards = node_towards ? &node_towards->_front : 0;
 123         towards_second = node_towards ? &node_towards->_back : 0;
 124     }
 125
 126     if (Geom::are_near(new_pos, _parent->position())) {
 127         // The handle becomes degenerate. If the segment between it and the node
 128         // in its direction becomes linear and there are smooth nodes
 129         // at its ends, make their handles colinear with the segment
 130         if (towards && towards->isDegenerate()) {
 131             if (node_towards->type() == NODE_SMOOTH) {
 132                 towards_second->setDirection(*_parent, *node_towards);
 133             }
 134             if (_parent->type() == NODE_SMOOTH) {
 135                 other->setDirection(*node_towards, *_parent);
 136             }
 137         }
 138         setPosition(new_pos);
 139         return;
 140     }
 141
 142     if (_parent->type() == NODE_SMOOTH && Node::_is_line_segment(_parent, node_away)) {
 143         // restrict movement to the line joining the nodes
 144         Geom::Point direction = _parent->position() - node_away->position();
 145         Geom::Point delta = new_pos - _parent->position();
 146         // project the relative position on the direction line
 147         Geom::Point new_delta = (Geom::dot(delta, direction)
 148             / Geom::L2sq(direction)) * direction;
 149         setRelativePos(new_delta);
 150         return;
 151     }
 152
 153     switch (_parent->type()) {
 154     case NODE_AUTO:
 155         _parent->setType(NODE_SMOOTH, false);
 156         // fall through - auto nodes degrade into smooth nodes
 157     case NODE_SMOOTH: {
 158         /* for smooth nodes, we need to rotate the other handle so that it's colinear
 159          * with the dragged one while conserving length. */
 160         other->setDirection(new_pos, *_parent);
 161         } break;
 162     case NODE_SYMMETRIC:
 163         // for symmetric nodes, place the other handle on the opposite side
 164         other->setRelativePos(-(new_pos - _parent->position()));
 165         break;
 166     default: break;
 167     }
 168
 169     setPosition(new_pos);
 170 }
 171
 172 void Handle::setPosition(Geom::Point const &p)
 173 {
 174     ControlPoint::setPosition(p);
 175     sp_ctrlline_set_coords(SP_CTRLLINE(_handle_line), _parent->position(), position());
 176
 177     // update degeneration info and visibility
 178     if (Geom::are_near(position(), _parent->position()))
 179         _degenerate = true;
 180     else _degenerate = false;
 181     if (_parent->_handles_shown && _parent->visible() && !_degenerate) {
 182         setVisible(true);
 183     } else {
 184         setVisible(false);
 185     }
 186     // If both handles become degenerate, convert to parent cusp node
 187     if (_parent->isDegenerate()) {
 188         _parent->setType(NODE_CUSP, false);
 189     }
 190 }
 191
 192 void Handle::setLength(double len)
 193 {
 194     if (isDegenerate()) return;
 195     Geom::Point dir = Geom::unit_vector(relativePos());
 196     setRelativePos(dir * len);
 197 }
 198
 199 void Handle::retract()
 200 {
 201     setPosition(_parent->position());
 202 }
 203
 204 void Handle::setDirection(Geom::Point const &from, Geom::Point const &to)
 205 {
 206     setDirection(to - from);
 207 }
 208
 209 void Handle::setDirection(Geom::Point const &dir)
 210 {
 211     Geom::Point unitdir = Geom::unit_vector(dir);
 212     setRelativePos(unitdir * length());
 213 }
 214
 215 char const *Handle::handle_type_to_localized_string(NodeType type)
 216 {
 217     switch(type) {
 218     case NODE_CUSP: return _("Cusp node handle");
 219     case NODE_SMOOTH: return _("Smooth node handle");
 220     case NODE_SYMMETRIC: return _("Symmetric node handle");
 221     case NODE_AUTO: return _("Auto-smooth node handle");
 222     default: return "";
 223     }
 224 }
 225
 226 bool Handle::grabbed(GdkEventMotion *)
 227 {
 228     _saved_other_pos = other().position();
 229     _saved_length = _drag_out ? 0 : length();
 230     _pm()._handleGrabbed();
 231     return false;
 232 }
 233
 234 void Handle::dragged(Geom::Point &new_pos, GdkEventMotion *event)
 235 {
 236     Geom::Point parent_pos = _parent->position();
 237     Geom::Point origin = _last_drag_origin();
 238     SnapManager &sm = _desktop->namedview->snap_manager;
 239     bool snap = sm.someSnapperMightSnap();
 240
 241     // with Alt, preserve length
 242     if (held_alt(*event)) {
 243         new_pos = parent_pos + Geom::unit_vector(new_pos - parent_pos) * _saved_length;
 244         snap = false;
 245     }
 246     // with Ctrl, constrain to M_PI/rotationsnapsperpi increments from vertical
 247     // and the original position.
 248     if (held_control(*event)) {
 249         Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 250         int snaps = 2 * prefs->getIntLimited("/options/rotationsnapsperpi/value", 12, 1, 1000);
 251
 252         // note: if snapping to the original position is only desired in the original
 253         // direction of the handle, change to Ray instead of Line
 254         Geom::Line original_line(parent_pos, origin);
 255         Geom::Point snap_pos = parent_pos + Geom::constrain_angle(
 256             Geom::Point(0,0), new_pos - parent_pos, snaps, Geom::Point(1,0));
 257         Geom::Point orig_pos = original_line.pointAt(original_line.nearestPoint(new_pos));
 258
 259         if (Geom::distance(snap_pos, new_pos) < Geom::distance(orig_pos, new_pos)) {
 260             new_pos = snap_pos;
 261         } else {
 262             new_pos = orig_pos;
 263         }
 264         snap = false;
 265     }
 266
 267     std::vector<Inkscape::SnapCandidatePoint> unselected;
 268     if (snap) {
 269         typedef ControlPointSelection::Set Set;
 270         Set &nodes = _parent->_selection.allPoints();
 271         for (Set::iterator i = nodes.begin(); i != nodes.end(); ++i) {
 272             Node *n = static_cast<Node*>(*i);
 273             Inkscape::SnapCandidatePoint p(n->position(), n->_snapSourceType(), n->_snapTargetType());
 274             unselected.push_back(p);
 275         }
 276         sm.setupIgnoreSelection(_desktop, true, &unselected);
 277
 278         Node *node_away = (this == &_parent->_front ? _parent->_prev() : _parent->_next());
 279         if (_parent->type() == NODE_SMOOTH && Node::_is_line_segment(_parent, node_away)) {
 280             Inkscape::Snapper::ConstraintLine cl(_parent->position(),
 281                 _parent->position() - node_away->position());
 282             Inkscape::SnappedPoint p;
 283             p = sm.constrainedSnap(Inkscape::SnapCandidatePoint(new_pos, SNAPSOURCE_NODE_HANDLE), cl);
 284             if (p.getSnapped()) {
 285                 p.getPoint(new_pos);
 286             }
 287         } else {
 288             sm.freeSnapReturnByRef(new_pos, SNAPSOURCE_NODE_HANDLE);
 289         }
 290     }
 291
 292     // with Shift, if the node is cusp, rotate the other handle as well
 293     if (_parent->type() == NODE_CUSP && !_drag_out) {
 294         if (held_shift(*event)) {
 295             Geom::Point other_relpos = _saved_other_pos - parent_pos;
 296             other_relpos *= Geom::Rotate(Geom::angle_between(origin - parent_pos, new_pos - parent_pos));
 297             other().setRelativePos(other_relpos);
 298         } else {
 299             // restore the position
 300             other().setPosition(_saved_other_pos);
 301         }
 302     }
 303     move(new_pos); // needed for correct update, even though it's redundant
 304     _pm().update();
 305 }
 306
 307 void Handle::ungrabbed(GdkEventButton *event)
 308 {
 309     // hide the handle if it's less than dragtolerance away from the node
 310     // TODO is this actually desired?
 311     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 312     int drag_tolerance = prefs->getIntLimited("/options/dragtolerance/value", 0, 0, 100);
 313
 314     Geom::Point dist = _desktop->d2w(_parent->position()) - _desktop->d2w(position());
 315     if (dist.length() <= drag_tolerance) {
 316         move(_parent->position());
 317     }
 318
 319     // HACK: If the handle was dragged out, call parent's ungrabbed handler,
 320     // so that transform handles reappear
 321     if (_drag_out) {
 322         _parent->ungrabbed(event);
 323     }
 324     _drag_out = false;
 325
 326     _pm()._handleUngrabbed();
 327 }
 328
 329 bool Handle::clicked(GdkEventButton *event)
 330 {
 331     _pm()._handleClicked(this, event);
 332     return true;
 333 }
 334
 335 Handle &Handle::other()
 336 {
 337     if (this == &_parent->_front) return _parent->_back;
 338     return _parent->_front;
 339 }
 340
 341 static double snap_increment_degrees() {
 342     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 343     int snaps = prefs->getIntLimited("/options/rotationsnapsperpi/value", 12, 1, 1000);
 344     return 180.0 / snaps;
 345 }
 346
 347 Glib::ustring Handle::_getTip(unsigned state)
 348 {
 349     char const *more;
 350     bool can_shift_rotate = _parent->type() == NODE_CUSP && !other().isDegenerate();
 351     if (can_shift_rotate) {
 352         more = C_("Path handle tip", "more: Shift, Ctrl, Alt");
 353     } else {
 354         more = C_("Path handle tip", "more: Ctrl, Alt");
 355     }
 356     if (state_held_alt(state)) {
 357         if (state_held_control(state)) {
 358             if (state_held_shift(state) && can_shift_rotate) {
 359                 return format_tip(C_("Path handle tip",
 360                     "<b>Shift+Ctrl+Alt</b>: preserve length and snap rotation angle to %g° "
 361                     "increments while rotating both handles"),
 362                     snap_increment_degrees());
 363             } else {
 364                 return format_tip(C_("Path handle tip",
 365                     "<b>Ctrl+Alt</b>: preserve length and snap rotation angle to %g° increments"),
 366                     snap_increment_degrees());
 367             }
 368         } else {
 369             if (state_held_shift(state) && can_shift_rotate) {
 370                 return C_("Path handle tip",
 371                     "<b>Shift+Alt:</b> preserve handle length and rotate both handles");
 372             } else {
 373                 return C_("Path handle tip",
 374                     "<b>Alt:</b> preserve handle length while dragging");
 375             }
 376         }
 377     } else {
 378         if (state_held_control(state)) {
 379             if (state_held_shift(state) && can_shift_rotate) {
 380                 return format_tip(C_("Path handle tip",
 381                     "<b>Shift+Ctrl:</b> snap rotation angle to %g° increments and rotate both handles"),
 382                     snap_increment_degrees());
 383             } else {
 384                 return format_tip(C_("Path handle tip",
 385                     "<b>Ctrl:</b> snap rotation angle to %g° increments, click to retract"),
 386                     snap_increment_degrees());
 387             }
 388         } else if (state_held_shift(state) && can_shift_rotate) {
 389             return C_("Path hande tip",
 390                 "<b>Shift</b>: rotate both handles by the same angle");
 391         }
 392     }
 393
 394     switch (_parent->type()) {
 395     case NODE_AUTO:
 396         return format_tip(C_("Path handle tip",
 397             "<b>Auto node handle:</b> drag to convert to smooth node (%s)"), more);
 398     default:
 399         return format_tip(C_("Path handle tip",
 400             "<b>%s:</b> drag to shape the segment (%s)"),
 401             handle_type_to_localized_string(_parent->type()), more);
 402     }
 403 }
 404
 405 Glib::ustring Handle::_getDragTip(GdkEventMotion */*event*/)
 406 {
 407     Geom::Point dist = position() - _last_drag_origin();
 408     // report angle in mathematical convention
 409     double angle = Geom::angle_between(Geom::Point(-1,0), position() - _parent->position());
 410     angle += M_PI; // angle is (-M_PI...M_PI] - offset by +pi and scale to 0...360
 411     angle *= 360.0 / (2 * M_PI);
 412     GString *x = SP_PX_TO_METRIC_STRING(dist[Geom::X], _desktop->namedview->getDefaultMetric());
 413     GString *y = SP_PX_TO_METRIC_STRING(dist[Geom::Y], _desktop->namedview->getDefaultMetric());
 414     GString *len = SP_PX_TO_METRIC_STRING(length(), _desktop->namedview->getDefaultMetric());
 415     Glib::ustring ret = format_tip(C_("Path handle tip",
 416         "Move handle by %s, %s; angle %.2f°, length %s"), x->str, y->str, angle, len->str);
 417     g_string_free(x, TRUE);
 418     g_string_free(y, TRUE);
 419     g_string_free(len, TRUE);
 420     return ret;
 421 }
 422
 423 /**
 424  * @class Node
 425  * @brief Curve endpoint in an editable path.
 426  *
 427  * The method move() keeps node type invariants during translations.
 428  */
 429
 430 Node::Node(NodeSharedData const &data, Geom::Point const &initial_pos)
 431     : SelectableControlPoint(data.desktop, initial_pos, Gtk::ANCHOR_CENTER,
 432         SP_CTRL_SHAPE_DIAMOND, 9.0, *data.selection, &node_colors, data.node_group)
 433     , _front(data, initial_pos, this)
 434     , _back(data, initial_pos, this)
 435     , _type(NODE_CUSP)
 436     , _handles_shown(false)
 437 {
 438     // NOTE we do not set type here, because the handles are still degenerate
 439 }
 440
 441 // NOTE: not using iterators won't make this much quicker because iterators can be 100% inlined.
 442 Node *Node::_next()
 443 {
 444     NodeList::iterator n = NodeList::get_iterator(this).next();
 445     if (n) return n.ptr();
 446     return NULL;
 447 }
 448 Node *Node::_prev()
 449 {
 450     NodeList::iterator p = NodeList::get_iterator(this).prev();
 451     if (p) return p.ptr();
 452     return NULL;
 453 }
 454
 455 void Node::move(Geom::Point const &new_pos)
 456 {
 457     // move handles when the node moves.
 458     Geom::Point old_pos = position();
 459     Geom::Point delta = new_pos - position();
 460     setPosition(new_pos);
 461     _front.setPosition(_front.position() + delta);
 462     _back.setPosition(_back.position() + delta);
 463
 464     // if the node has a smooth handle after a line segment, it should be kept colinear
 465     // with the segment
 466     _fixNeighbors(old_pos, new_pos);
 467 }
 468
 469 void Node::transform(Geom::Matrix const &m)
 470 {
 471     Geom::Point old_pos = position();
 472     setPosition(position() * m);
 473     _front.setPosition(_front.position() * m);
 474     _back.setPosition(_back.position() * m);
 475
 476     /* Affine transforms keep handle invariants for smooth and symmetric nodes,
 477      * but smooth nodes at ends of linear segments and auto nodes need special treatment */
 478     _fixNeighbors(old_pos, position());
 479 }
 480
 481 Geom::Rect Node::bounds()
 482 {
 483     Geom::Rect b(position(), position());
 484     b.expandTo(_front.position());
 485     b.expandTo(_back.position());
 486     return b;
 487 }
 488
 489 void Node::_fixNeighbors(Geom::Point const &old_pos, Geom::Point const &new_pos)
 490 {
 491     /* This method restores handle invariants for neighboring nodes,
 492      * and invariants that are based on positions of those nodes for this one. */
 493
 494     /* Fix auto handles */
 495     if (_type == NODE_AUTO) _updateAutoHandles();
 496     if (old_pos != new_pos) {
 497         if (_next() && _next()->_type == NODE_AUTO) _next()->_updateAutoHandles();
 498         if (_prev() && _prev()->_type == NODE_AUTO) _prev()->_updateAutoHandles();
 499     }
 500
 501     /* Fix smooth handles at the ends of linear segments.
 502      * Rotate the appropriate handle to be colinear with the segment.
 503      * If there is a smooth node at the other end of the segment, rotate it too. */
 504     Handle *handle, *other_handle;
 505     Node *other;
 506     if (_is_line_segment(this, _next())) {
 507         handle = &_back;
 508         other = _next();
 509         other_handle = &_next()->_front;
 510     } else if (_is_line_segment(_prev(), this)) {
 511         handle = &_front;
 512         other = _prev();
 513         other_handle = &_prev()->_back;
 514     } else return;
 515
 516     if (_type == NODE_SMOOTH && !handle->isDegenerate()) {
 517         handle->setDirection(other->position(), new_pos);
 518     }
 519     // also update the handle on the other end of the segment
 520     if (other->_type == NODE_SMOOTH && !other_handle->isDegenerate()) {
 521         other_handle->setDirection(new_pos, other->position());
 522     }
 523 }
 524
 525 void Node::_updateAutoHandles()
 526 {
 527     // Recompute the position of automatic handles.
 528     // For endnodes, retract both handles. (It's only possible to create an end auto node
 529     // through the XML editor.)
 530     if (isEndNode()) {
 531         _front.retract();
 532         _back.retract();
 533         return;
 534     }
 535
 536     // Auto nodes automaticaly adjust their handles to give an appearance of smoothness,
 537     // no matter what their surroundings are.
 538     Geom::Point vec_next = _next()->position() - position();
 539     Geom::Point vec_prev = _prev()->position() - position();
 540     double len_next = vec_next.length(), len_prev = vec_prev.length();
 541     if (len_next > 0 && len_prev > 0) {
 542         // "dir" is an unit vector perpendicular to the bisector of the angle created
 543         // by the previous node, this auto node and the next node.
 544         Geom::Point dir = Geom::unit_vector((len_prev / len_next) * vec_next - vec_prev);
 545         // Handle lengths are equal to 1/3 of the distance from the adjacent node.
 546         _back.setRelativePos(-dir * (len_prev / 3));
 547         _front.setRelativePos(dir * (len_next / 3));
 548     } else {
 549         // If any of the adjacent nodes coincides, retract both handles.
 550         _front.retract();
 551         _back.retract();
 552     }
 553 }
 554
 555 void Node::showHandles(bool v)
 556 {
 557     _handles_shown = v;
 558     if (!_front.isDegenerate()) _front.setVisible(v);
 559     if (!_back.isDegenerate()) _back.setVisible(v);
 560 }
 561
 562 /** Sets the node type and optionally restores the invariants associated with the given type.
 563  * @param type The type to set
 564  * @param update_handles Whether to restore invariants associated with the given type.
 565  *                       Passing false is useful e.g. wen initially creating the path,
 566  *                       and when making cusp nodes during some node algorithms.
 567  *                       Pass true when used in response to an UI node type button.
 568  */
 569 void Node::setType(NodeType type, bool update_handles)
 570 {
 571     if (type == NODE_PICK_BEST) {
 572         pickBestType();
 573         updateState(); // The size of the control might have changed
 574         return;
 575     }
 576
 577     // if update_handles is true, adjust handle positions to match the node type
 578     // handle degenerate handles appropriately
 579     if (update_handles) {
 580         switch (type) {
 581         case NODE_CUSP:
 582             // if the existing type is also NODE_CUSP, retract handles
 583             if (_type == NODE_CUSP) {
 584                 _front.retract();
 585                 _back.retract();
 586             }
 587             break;
 588         case NODE_AUTO:
 589             // auto handles make no sense for endnodes
 590             if (isEndNode()) return;
 591             _updateAutoHandles();
 592             break;
 593         case NODE_SMOOTH: {
 594             // rotate handles to be colinear
 595             // for degenerate nodes set positions like auto handles
 596             bool prev_line = _is_line_segment(_prev(), this);
 597             bool next_line = _is_line_segment(this, _next());
 598             if (_type == NODE_SMOOTH) {
 599                 // for a node that is already smooth and has a degenerate handle,
 600                 // drag out the second handle to 1/3 the length of the linear segment
 601                 if (_front.isDegenerate()) {
 602                     double dist = Geom::distance(_next()->position(), position());
 603                     _front.setRelativePos(Geom::unit_vector(-_back.relativePos()) * dist / 3);
 604                 }
 605                 if (_back.isDegenerate()) {
 606                     double dist = Geom::distance(_prev()->position(), position());
 607                     _back.setRelativePos(Geom::unit_vector(-_front.relativePos()) * dist / 3);
 608                 }
 609             } else if (isDegenerate()) {
 610                 _updateAutoHandles();
 611             } else if (_front.isDegenerate()) {
 612                 // if the front handle is degenerate and this...next is a line segment,
 613                 // make back colinear; otherwise pull out the other handle
 614                 // to 1/3 of distance to prev
 615                 if (next_line) {
 616                     _back.setDirection(*_next(), *this);
 617                 } else if (_prev()) {
 618                     Geom::Point dir = direction(_back, *this);
 619                     _front.setRelativePos(Geom::distance(_prev()->position(), position()) / 3 * dir);
 620                 }
 621             } else if (_back.isDegenerate()) {
 622                 if (prev_line) {
 623                     _front.setDirection(*_prev(), *this);
 624                 } else if (_next()) {
 625                     Geom::Point dir = direction(_front, *this);
 626                     _back.setRelativePos(Geom::distance(_next()->position(), position()) / 3 * dir);
 627                 }
 628             } else {
 629                 // both handles are extended. make colinear while keeping length
 630                 // first make back colinear with the vector front ---> back,
 631                 // then make front colinear with back ---> node
 632                 // (not back ---> front because back's position was changed in the first call)
 633                 _back.setDirection(_front, _back);
 634                 _front.setDirection(_back, *this);
 635             }
 636             } break;
 637         case NODE_SYMMETRIC:
 638             if (isEndNode()) return; // symmetric handles make no sense for endnodes
 639             if (isDegenerate()) {
 640                 // similar to auto handles but set the same length for both
 641                 Geom::Point vec_next = _next()->position() - position();
 642                 Geom::Point vec_prev = _prev()->position() - position();
 643                 double len_next = vec_next.length(), len_prev = vec_prev.length();
 644                 double len = (len_next + len_prev) / 6; // take 1/3 of average
 645                 if (len == 0) return;
 646
 647                 Geom::Point dir = Geom::unit_vector((len_prev / len_next) * vec_next - vec_prev);
 648                 _back.setRelativePos(-dir * len);
 649                 _front.setRelativePos(dir * len);
 650             } else {
 651                 // Both handles are extended. Compute average length, use direction from
 652                 // back handle to front handle. This also works correctly for degenerates
 653                 double len = (_front.length() + _back.length()) / 2;
 654                 Geom::Point dir = direction(_back, _front);
 655                 _front.setRelativePos(dir * len);
 656                 _back.setRelativePos(-dir * len);
 657             }
 658             break;
 659         default: break;
 660         }
 661     }
 662     _type = type;
 663     _setShape(_node_type_to_shape(type));
 664     updateState();
 665 }
 666
 667 /** Pick the best type for this node, based on the position of its handles.
 668  * This is what assigns types to nodes created using the pen tool. */
 669 void Node::pickBestType()
 670 {
 671     _type = NODE_CUSP;
 672     bool front_degen = _front.isDegenerate();
 673     bool back_degen = _back.isDegenerate();
 674     bool both_degen = front_degen && back_degen;
 675     bool neither_degen = !front_degen && !back_degen;
 676     do {
 677         // if both handles are degenerate, do nothing
 678         if (both_degen) break;
 679         // if neither are degenerate, check their respective positions
 680         if (neither_degen) {
 681             Geom::Point front_delta = _front.position() - position();
 682             Geom::Point back_delta = _back.position() - position();
 683             // for now do not automatically make nodes symmetric, it can be annoying
 684             /*if (Geom::are_near(front_delta, -back_delta)) {
 685                 _type = NODE_SYMMETRIC;
 686                 break;
 687             }*/
 688             if (Geom::are_near(Geom::unit_vector(front_delta),
 689                 Geom::unit_vector(-back_delta)))
 690             {
 691                 _type = NODE_SMOOTH;
 692                 break;
 693             }
 694         }
 695         // check whether the handle aligns with the previous line segment.
 696         // we know that if front is degenerate, back isn't, because
 697         // both_degen was false
 698         if (front_degen && _next() && _next()->_back.isDegenerate()) {
 699             Geom::Point segment_delta = Geom::unit_vector(_next()->position() - position());
 700             Geom::Point handle_delta = Geom::unit_vector(_back.position() - position());
 701             if (Geom::are_near(segment_delta, -handle_delta)) {
 702                 _type = NODE_SMOOTH;
 703                 break;
 704             }
 705         } else if (back_degen && _prev() && _prev()->_front.isDegenerate()) {
 706             Geom::Point segment_delta = Geom::unit_vector(_prev()->position() - position());
 707             Geom::Point handle_delta = Geom::unit_vector(_front.position() - position());
 708             if (Geom::are_near(segment_delta, -handle_delta)) {
 709                 _type = NODE_SMOOTH;
 710                 break;
 711             }
 712         }
 713     } while (false);
 714     _setShape(_node_type_to_shape(_type));
 715     updateState();
 716 }
 717
 718 bool Node::isEndNode()
 719 {
 720     return !_prev() || !_next();
 721 }
 722
 723 /** Move the node to the bottom of its canvas group. Useful for node break, to ensure that
 724  * the selected nodes are above the unselected ones. */
 725 void Node::sink()
 726 {
 727     sp_canvas_item_move_to_z(_canvas_item, 0);
 728 }
 729
 730 NodeType Node::parse_nodetype(char x)
 731 {
 732     switch (x) {
 733     case 'a': return NODE_AUTO;
 734     case 'c': return NODE_CUSP;
 735     case 's': return NODE_SMOOTH;
 736     case 'z': return NODE_SYMMETRIC;
 737     default: return NODE_PICK_BEST;
 738     }
 739 }
 740
 741 /** Customized event handler to catch scroll events needed for selection grow/shrink. */
 742 bool Node::_eventHandler(GdkEvent *event)
 743 {
 744     static NodeList::iterator origin;
 745     static int dir;
 746
 747     switch (event->type)
 748     {
 749     case GDK_SCROLL:
 750         if (event->scroll.direction == GDK_SCROLL_UP) {
 751             dir = 1;
 752         } else if (event->scroll.direction == GDK_SCROLL_DOWN) {
 753             dir = -1;
 754         } else break;
 755         if (held_control(event->scroll)) {
 756             _selection.spatialGrow(this, dir);
 757         } else {
 758             _linearGrow(dir);
 759         }
 760         return true;
 761     default:
 762         break;
 763     }
 764     return ControlPoint::_eventHandler(event);
 765 }
 766
 767 // TODO Move this to 2Geom!
 768 static double bezier_length (Geom::Point a0, Geom::Point a1, Geom::Point a2, Geom::Point a3)
 769 {
 770     double lower = Geom::distance(a0, a3);
 771     double upper = Geom::distance(a0, a1) + Geom::distance(a1, a2) + Geom::distance(a2, a3);
 772
 773     if (upper - lower < Geom::EPSILON) return (lower + upper)/2;
 774
 775     Geom::Point // Casteljau subdivision
 776         b0 = a0,
 777         c0 = a3,
 778         b1 = 0.5*(a0 + a1),
 779         t0 = 0.5*(a1 + a2),
 780         c1 = 0.5*(a2 + a3),
 781         b2 = 0.5*(b1 + t0),
 782         c2 = 0.5*(t0 + c1),
 783         b3 = 0.5*(b2 + c2); // == c3
 784     return bezier_length(b0, b1, b2, b3) + bezier_length(b3, c2, c1, c0);
 785 }
 786
 787 /** Select or deselect a node in this node's subpath based on its path distance from this node.
 788  * @param dir If negative, shrink selection by one node; if positive, grow by one node */
 789 void Node::_linearGrow(int dir)
 790 {
 791     // Interestingly, we do not need any help from PathManipulator when doing linear grow.
 792     // First handle the trivial case of growing over an unselected node.
 793     if (!selected() && dir > 0) {
 794         _selection.insert(this);
 795         return;
 796     }
 797
 798     NodeList::iterator this_iter = NodeList::get_iterator(this);
 799     NodeList::iterator fwd = this_iter, rev = this_iter;
 800     double distance_back = 0, distance_front = 0;
 801
 802     // Linear grow is simple. We find the first unselected nodes in each direction
 803     // and compare the linear distances to them.
 804     if (dir > 0) {
 805         if (!selected()) {
 806             _selection.insert(this);
 807             return;
 808         }
 809
 810         // find first unselected nodes on both sides
 811         while (fwd && fwd->selected()) {
 812             NodeList::iterator n = fwd.next();
 813             distance_front += bezier_length(*fwd, fwd->_front, n->_back, *n);
 814             fwd = n;
 815             if (fwd == this_iter)
 816                 // there is no unselected node in this cyclic subpath
 817                 return;
 818         }
 819         // do the same for the second direction. Do not check for equality with
 820         // this node, because there is at least one unselected node in the subpath,
 821         // so we are guaranteed to stop.
 822         while (rev && rev->selected()) {
 823             NodeList::iterator p = rev.prev();
 824             distance_back += bezier_length(*rev, rev->_back, p->_front, *p);
 825             rev = p;
 826         }
 827
 828         NodeList::iterator t; // node to select
 829         if (fwd && rev) {
 830             if (distance_front <= distance_back) t = fwd;
 831             else t = rev;
 832         } else {
 833             if (fwd) t = fwd;
 834             if (rev) t = rev;
 835         }
 836         if (t) _selection.insert(t.ptr());
 837
 838     // Linear shrink is more complicated. We need to find the farthest selected node.
 839     // This means we have to check the entire subpath. We go in the direction in which
 840     // the distance we traveled is lower. We do this until we run out of nodes (ends of path)
 841     // or the two iterators meet. On the way, we store the last selected node and its distance
 842     // in each direction (if any). At the end, we choose the one that is farther and deselect it.
 843     } else {
 844         // both iterators that store last selected nodes are initially empty
 845         NodeList::iterator last_fwd, last_rev;
 846         double last_distance_back = 0, last_distance_front = 0;
 847
 848         while (rev || fwd) {
 849             if (fwd && (!rev || distance_front <= distance_back)) {
 850                 if (fwd->selected()) {
 851                     last_fwd = fwd;
 852                     last_distance_front = distance_front;
 853                 }
 854                 NodeList::iterator n = fwd.next();
 855                 if (n) distance_front += bezier_length(*fwd, fwd->_front, n->_back, *n);
 856                 fwd = n;
 857             } else if (rev && (!fwd || distance_front > distance_back)) {
 858                 if (rev->selected()) {
 859                     last_rev = rev;
 860                     last_distance_back = distance_back;
 861                 }
 862                 NodeList::iterator p = rev.prev();
 863                 if (p) distance_back += bezier_length(*rev, rev->_back, p->_front, *p);
 864                 rev = p;
 865             }
 866             // Check whether we walked the entire cyclic subpath.
 867             // This is initially true because both iterators start from this node,
 868             // so this check cannot go in the while condition.
 869             // When this happens, we need to check the last node, pointed to by the iterators.
 870             if (fwd && fwd == rev) {
 871                 if (!fwd->selected()) break;
 872                 NodeList::iterator fwdp = fwd.prev(), revn = rev.next();
 873                 double df = distance_front + bezier_length(*fwdp, fwdp->_front, fwd->_back, *fwd);
 874                 double db = distance_back + bezier_length(*revn, revn->_back, rev->_front, *rev);
 875                 if (df > db) {
 876                     last_fwd = fwd;
 877                     last_distance_front = df;
 878                 } else {
 879                     last_rev = rev;
 880                     last_distance_back = db;
 881                 }
 882                 break;
 883             }
 884         }
 885
 886         NodeList::iterator t;
 887         if (last_fwd && last_rev) {
 888             if (last_distance_front >= last_distance_back) t = last_fwd;
 889             else t = last_rev;
 890         } else {
 891             if (last_fwd) t = last_fwd;
 892             if (last_rev) t = last_rev;
 893         }
 894         if (t) _selection.erase(t.ptr());
 895     }
 896 }
 897
 898 void Node::_setState(State state)
 899 {
 900     // change node size to match type and selection state
 901     switch (_type) {
 902     case NODE_AUTO:
 903     case NODE_CUSP:
 904         if (selected()) _setSize(11);
 905         else _setSize(9);
 906         break;
 907     default:
 908         if(selected()) _setSize(9);
 909         else _setSize(7);
 910         break;
 911     }
 912     SelectableControlPoint::_setState(state);
 913 }
 914
 915 bool Node::grabbed(GdkEventMotion *event)
 916 {
 917     if (SelectableControlPoint::grabbed(event))
 918         return true;
 919
 920     // Dragging out handles with Shift + drag on a node.
 921     if (!held_shift(*event)) return false;
 922
 923     Handle *h;
 924     Geom::Point evp = event_point(*event);
 925     Geom::Point rel_evp = evp - _last_click_event_point();
 926
 927     // This should work even if dragtolerance is zero and evp coincides with node position.
 928     double angle_next = HUGE_VAL;
 929     double angle_prev = HUGE_VAL;
 930     bool has_degenerate = false;
 931     // determine which handle to drag out based on degeneration and the direction of drag
 932     if (_front.isDegenerate() && _next()) {
 933         Geom::Point next_relpos = _desktop->d2w(_next()->position())
 934             - _desktop->d2w(position());
 935         angle_next = fabs(Geom::angle_between(rel_evp, next_relpos));
 936         has_degenerate = true;
 937     }
 938     if (_back.isDegenerate() && _prev()) {
 939         Geom::Point prev_relpos = _desktop->d2w(_prev()->position())
 940             - _desktop->d2w(position());
 941         angle_prev = fabs(Geom::angle_between(rel_evp, prev_relpos));
 942         has_degenerate = true;
 943     }
 944     if (!has_degenerate) return false;
 945     h = angle_next < angle_prev ? &_front : &_back;
 946
 947     h->setPosition(_desktop->w2d(evp));
 948     h->setVisible(true);
 949     h->transferGrab(this, event);
 950     Handle::_drag_out = true;
 951     return true;
 952 }
 953
 954 void Node::dragged(Geom::Point &new_pos, GdkEventMotion *event)
 955 {
 956     // For a note on how snapping is implemented in Inkscape, see snap.h.
 957     SnapManager &sm = _desktop->namedview->snap_manager;
 958     bool snap = sm.someSnapperMightSnap();
 959     std::vector<Inkscape::SnapCandidatePoint> unselected;
 960     if (snap) {
 961         /* setup
 962          * TODO We are doing this every time a snap happens. It should once be done only once
 963          *      per drag - maybe in the grabbed handler?
 964          * TODO Unselected nodes vector must be valid during the snap run, because it is not
 965          *      copied. Fix this in snap.h and snap.cpp, then the above.
 966          * TODO Snapping to unselected segments of selected paths doesn't work yet. */
 967
 968         // Build the list of unselected nodes.
 969         typedef ControlPointSelection::Set Set;
 970         Set &nodes = _selection.allPoints();
 971         for (Set::iterator i = nodes.begin(); i != nodes.end(); ++i) {
 972             if (!(*i)->selected()) {
 973                 Node *n = static_cast<Node*>(*i);
 974                 Inkscape::SnapCandidatePoint p(n->position(), n->_snapSourceType(), n->_snapTargetType());
 975                 unselected.push_back(p);
 976             }
 977         }
 978         sm.setupIgnoreSelection(_desktop, false, &unselected);
 979     }
 980
 981     if (held_control(*event)) {
 982         Geom::Point origin = _last_drag_origin();
 983         Inkscape::SnappedPoint fp, bp;
 984         if (held_alt(*event)) {
 985             // with Ctrl+Alt, constrain to handle lines
 986             // project the new position onto a handle line that is closer
 987             boost::optional<Geom::Point> front_point, back_point;
 988             boost::optional<Inkscape::Snapper::ConstraintLine> line_front, line_back;
 989             if (_front.isDegenerate()) {
 990                 if (_is_line_segment(this, _next()))
 991                     front_point = _next()->position() - origin;
 992             } else {
 993                 front_point = _front.relativePos();
 994             }
 995             if (_back.isDegenerate()) {
 996                 if (_is_line_segment(_prev(), this))
 997                     back_point = _prev()->position() - origin;
 998             } else {
 999                 back_point = _back.relativePos();
1000             }
1001             if (front_point)
1002                 line_front = Inkscape::Snapper::ConstraintLine(origin, *front_point);
1003             if (back_point)
1004                 line_back = Inkscape::Snapper::ConstraintLine(origin, *back_point);
1005
1006             // TODO: combine the snap and non-snap branches by modifying snap.h / snap.cpp
1007             if (snap) {
1008                 if (line_front) {
1009                     fp = sm.constrainedSnap(Inkscape::SnapCandidatePoint(new_pos,
1010                         _snapSourceType()), *line_front);
1011                 }
1012                 if (line_back) {
1013                     bp = sm.constrainedSnap(Inkscape::SnapCandidatePoint(new_pos,
1014                         _snapSourceType()), *line_back);
1015                 }
1016             }
1017             if (fp.getSnapped() || bp.getSnapped()) {
1018                 if (fp.isOtherSnapBetter(bp, false)) {
1019                     fp = bp;
1020                 }
1021                 fp.getPoint(new_pos);
1022                 _desktop->snapindicator->set_new_snaptarget(fp);
1023             } else {
1024                 boost::optional<Geom::Point> pos;
1025                 if (line_front) {
1026                     pos = line_front->projection(new_pos);
1027                 }
1028                 if (line_back) {
1029                     Geom::Point pos2 = line_back->projection(new_pos);
1030                     if (!pos || (pos && Geom::distance(new_pos, *pos) > Geom::distance(new_pos, pos2)))
1031                         pos = pos2;
1032                 }
1033                 if (pos) {
1034                     new_pos = *pos;
1035                 } else {
1036                     new_pos = origin;
1037                 }
1038             }
1039         } else {
1040             // with Ctrl, constrain to axes
1041             // TODO combine the two branches
1042             if (snap) {
1043                 Inkscape::Snapper::ConstraintLine line_x(origin, Geom::Point(1, 0));
1044                 Inkscape::Snapper::ConstraintLine line_y(origin, Geom::Point(0, 1));
1045                 fp = sm.constrainedSnap(Inkscape::SnapCandidatePoint(new_pos, _snapSourceType()), line_x);
1046                 bp = sm.constrainedSnap(Inkscape::SnapCandidatePoint(new_pos, _snapSourceType()), line_y);
1047             }
1048             if (fp.getSnapped() || bp.getSnapped()) {
1049                 if (fp.isOtherSnapBetter(bp, false)) {
1050                     fp = bp;
1051                 }
1052                 fp.getPoint(new_pos);
1053                 if (fp.getTarget() != SNAPTARGET_CONSTRAINT) {
1054                     _desktop->snapindicator->set_new_snaptarget(fp);
1055                 }
1056             } else {
1057                 Geom::Point origin = _last_drag_origin();
1058                 Geom::Point delta = new_pos - origin;
1059                 Geom::Dim2 d = (fabs(delta[Geom::X]) < fabs(delta[Geom::Y])) ? Geom::X : Geom::Y;
1060                 new_pos[d] = origin[d];
1061             }
1062         }
1063     } else if (snap) {
1064         Inkscape::SnappedPoint p = sm.freeSnap(Inkscape::SnapCandidatePoint(new_pos, _snapSourceType()));
1065         if (p.getSnapped()) {
1066             p.getPoint(new_pos);
1067             _desktop->snapindicator->set_new_snaptarget(p);
1068         }
1069     }
1070
1071     SelectableControlPoint::dragged(new_pos, event);
1072 }
1073
1074 bool Node::clicked(GdkEventButton *event)
1075 {
1076     if(_pm()._nodeClicked(this, event))
1077         return true;
1078     return SelectableControlPoint::clicked(event);
1079 }
1080
1081 Inkscape::SnapSourceType Node::_snapSourceType()
1082 {
1083     if (_type == NODE_SMOOTH || _type == NODE_AUTO)
1084         return SNAPSOURCE_NODE_SMOOTH;
1085     return SNAPSOURCE_NODE_CUSP;
1086 }
1087 Inkscape::SnapTargetType Node::_snapTargetType()
1088 {
1089     if (_type == NODE_SMOOTH || _type == NODE_AUTO)
1090         return SNAPTARGET_NODE_SMOOTH;
1091     return SNAPTARGET_NODE_CUSP;
1092 }
1093
1094 Glib::ustring Node::_getTip(unsigned state)
1095 {
1096     if (state_held_shift(state)) {
1097         bool can_drag_out = (_next() && _front.isDegenerate()) || (_prev() && _back.isDegenerate());
1098         if (can_drag_out) {
1099             /*if (state_held_control(state)) {
1100                 return format_tip(C_("Path node tip",
1101                     "<b>Shift+Ctrl:</b> drag out a handle and snap its angle "
1102                     "to %f° increments"), snap_increment_degrees());
1103             }*/
1104             return C_("Path node tip",
1105                 "<b>Shift:</b> drag out a handle, click to toggle selection");
1106         }
1107         return C_("Path node tip", "<b>Shift:</b> click to toggle selection");
1108     }
1109
1110     if (state_held_control(state)) {
1111         if (state_held_alt(state)) {
1112             return C_("Path node tip", "<b>Ctrl+Alt:</b> move along handle lines, click to delete node");
1113         }
1114         return C_("Path node tip",
1115             "<b>Ctrl:</b> move along axes, click to change node type");
1116     }
1117
1118     // assemble tip from node name
1119     char const *nodetype = node_type_to_localized_string(_type);
1120     if (_selection.transformHandlesEnabled() && selected()) {
1121         if (_selection.size() == 1) {
1122             return format_tip(C_("Path node tip",
1123                 "<b>%s:</b> drag to shape the path (more: Shift, Ctrl, Alt)"), nodetype);
1124         }
1125         return format_tip(C_("Path node tip",
1126             "<b>%s:</b> drag to shape the path, click to toggle scale/rotation handles (more: Shift, Ctrl, Alt)"), nodetype);
1127     }
1128     return format_tip(C_("Path node tip",
1129         "<b>%s:</b> drag to shape the path, click to select only this node (more: Shift, Ctrl, Alt)"), nodetype);
1130 }
1131
1132 Glib::ustring Node::_getDragTip(GdkEventMotion */*event*/)
1133 {
1134     Geom::Point dist = position() - _last_drag_origin();
1135     GString *x = SP_PX_TO_METRIC_STRING(dist[Geom::X], _desktop->namedview->getDefaultMetric());
1136     GString *y = SP_PX_TO_METRIC_STRING(dist[Geom::Y], _desktop->namedview->getDefaultMetric());
1137     Glib::ustring ret = format_tip(C_("Path node tip", "Move node by %s, %s"),
1138         x->str, y->str);
1139     g_string_free(x, TRUE);
1140     g_string_free(y, TRUE);
1141     return ret;
1142 }
1143
1144 char const *Node::node_type_to_localized_string(NodeType type)
1145 {
1146     switch (type) {
1147     case NODE_CUSP: return _("Cusp node");
1148     case NODE_SMOOTH: return _("Smooth node");
1149     case NODE_SYMMETRIC: return _("Symmetric node");
1150     case NODE_AUTO: return _("Auto-smooth node");
1151     default: return "";
1152     }
1153 }
1154
1155 /** Determine whether two nodes are joined by a linear segment. */
1156 bool Node::_is_line_segment(Node *first, Node *second)
1157 {
1158     if (!first || !second) return false;
1159     if (first->_next() == second)
1160         return first->_front.isDegenerate() && second->_back.isDegenerate();
1161     if (second->_next() == first)
1162         return second->_front.isDegenerate() && first->_back.isDegenerate();
1163     return false;
1164 }
1165
1166 SPCtrlShapeType Node::_node_type_to_shape(NodeType type)
1167 {
1168     switch(type) {
1169     case NODE_CUSP: return SP_CTRL_SHAPE_DIAMOND;
1170     case NODE_SMOOTH: return SP_CTRL_SHAPE_SQUARE;
1171     case NODE_AUTO: return SP_CTRL_SHAPE_CIRCLE;
1172     case NODE_SYMMETRIC: return SP_CTRL_SHAPE_SQUARE;
1173     default: return SP_CTRL_SHAPE_DIAMOND;
1174     }
1175 }
1176
1177
1178 /**
1179  * @class NodeList
1180  * @brief An editable list of nodes representing a subpath.
1181  *
1182  * It can optionally be cyclic to represent a closed path.
1183  * The list has iterators that act like plain node iterators, but can also be used
1184  * to obtain shared pointers to nodes.
1185  */
1186
1187 NodeList::NodeList(SubpathList &splist)
1188     : _list(splist)
1189     , _closed(false)
1190 {
1191     this->ln_list = this;
1192     this->ln_next = this;
1193     this->ln_prev = this;
1194 }
1195
1196 NodeList::~NodeList()
1197 {
1198     clear();
1199 }
1200
1201 bool NodeList::empty()
1202 {
1203     return ln_next == this;
1204 }
1205
1206 NodeList::size_type NodeList::size()
1207 {
1208     size_type sz = 0;
1209     for (ListNode *ln = ln_next; ln != this; ln = ln->ln_next) ++sz;
1210     return sz;
1211 }
1212
1213 bool NodeList::closed()
1214 {
1215     return _closed;
1216 }
1217
1218 /** A subpath is degenerate if it has no segments - either one node in an open path
1219  * or no nodes in a closed path */
1220 bool NodeList::degenerate()
1221 {
1222     return closed() ? empty() : ++begin() == end();
1223 }
1224
1225 NodeList::iterator NodeList::before(double t, double *fracpart)
1226 {
1227     double intpart;
1228     *fracpart = std::modf(t, &intpart);
1229     int index = intpart;
1230
1231     iterator ret = begin();
1232     std::advance(ret, index);
1233     return ret;
1234 }
1235
1236 // insert a node before i
1237 NodeList::iterator NodeList::insert(iterator i, Node *x)
1238 {
1239     ListNode *ins = i._node;
1240     x->ln_next = ins;
1241     x->ln_prev = ins->ln_prev;
1242     ins->ln_prev->ln_next = x;
1243     ins->ln_prev = x;
1244     x->ln_list = this;
1245     return iterator(x);
1246 }
1247
1248 void NodeList::splice(iterator pos, NodeList &list)
1249 {
1250     splice(pos, list, list.begin(), list.end());
1251 }
1252
1253 void NodeList::splice(iterator pos, NodeList &list, iterator i)
1254 {
1255     NodeList::iterator j = i;
1256     ++j;
1257     splice(pos, list, i, j);
1258 }
1259
1260 void NodeList::splice(iterator pos, NodeList &/*list*/, iterator first, iterator last)
1261 {
1262     ListNode *ins_beg = first._node, *ins_end = last._node, *at = pos._node;
1263     for (ListNode *ln = ins_beg; ln != ins_end; ln = ln->ln_next) {
1264         ln->ln_list = this;
1265     }
1266     ins_beg->ln_prev->ln_next = ins_end;
1267     ins_end->ln_prev->ln_next = at;
1268     at->ln_prev->ln_next = ins_beg;
1269
1270     ListNode *atprev = at->ln_prev;
1271     at->ln_prev = ins_end->ln_prev;
1272     ins_end->ln_prev = ins_beg->ln_prev;
1273     ins_beg->ln_prev = atprev;
1274 }
1275
1276 void NodeList::shift(int n)
1277 {
1278     // 1. make the list perfectly cyclic
1279     ln_next->ln_prev = ln_prev;
1280     ln_prev->ln_next = ln_next;
1281     // 2. find new begin
1282     ListNode *new_begin = ln_next;
1283     if (n > 0) {
1284         for (; n > 0; --n) new_begin = new_begin->ln_next;
1285     } else {
1286         for (; n < 0; ++n) new_begin = new_begin->ln_prev;
1287     }
1288     // 3. relink begin to list
1289     ln_next = new_begin;
1290     ln_prev = new_begin->ln_prev;
1291     new_begin->ln_prev->ln_next = this;
1292     new_begin->ln_prev = this;
1293 }
1294
1295 void NodeList::reverse()
1296 {
1297     for (ListNode *ln = ln_next; ln != this; ln = ln->ln_prev) {
1298         std::swap(ln->ln_next, ln->ln_prev);
1299         Node *node = static_cast<Node*>(ln);
1300         Geom::Point save_pos = node->front()->position();
1301         node->front()->setPosition(node->back()->position());
1302         node->back()->setPosition(save_pos);
1303     }
1304     std::swap(ln_next, ln_prev);
1305 }
1306
1307 void NodeList::clear()
1308 {
1309     for (iterator i = begin(); i != end();) erase (i++);
1310 }
1311
1312 NodeList::iterator NodeList::erase(iterator i)
1313 {
1314     // some gymnastics are required to ensure that the node is valid when deleted;
1315     // otherwise the code that updates handle visibility will break
1316     Node *rm = static_cast<Node*>(i._node);
1317     ListNode *rmnext = rm->ln_next, *rmprev = rm->ln_prev;
1318     ++i;
1319     delete rm;
1320     rmprev->ln_next = rmnext;
1321     rmnext->ln_prev = rmprev;
1322     return i;
1323 }
1324
1325 // TODO this method is very ugly!
1326 // converting SubpathList to an intrusive list might allow us to get rid of it
1327 void NodeList::kill()
1328 {
1329     for (SubpathList::iterator i = _list.begin(); i != _list.end(); ++i) {
1330         if (i->get() == this) {
1331             _list.erase(i);
1332             return;
1333         }
1334     }
1335 }
1336
1337 NodeList &NodeList::get(Node *n) {
1338     return n->nodeList();
1339 }
1340 NodeList &NodeList::get(iterator const &i) {
1341     return *(i._node->ln_list);
1342 }
1343
1344
1345 /**
1346  * @class SubpathList
1347  * @brief Editable path composed of one or more subpaths
1348  */
1349
1350 } // namespace UI
1351 } // namespace Inkscape
1352
1353 /*
1354   Local Variables:
1355   mode:c++
1356   c-file-style:"stroustrup"
1357   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1358   indent-tabs-mode:nil
1359   fill-column:99
1360   End:
1361 */
1362 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :