2013/7/6 Shriramana Sharma <samjnaa@...400...>:
On Tue, Apr 23, 2013 at 9:29 PM, Krzysztof Kosiński
> src/ui/tool/node.h and .cpp, class NodeList.
> Note that this is not a template. It's "based on"
> boost::intrusive::list in the sense that the structure is the same -
> it doesn't actually use it.
A few more questions regarding this:
1) A doubly-linked list is costly in terms of having to store the prev
and next pointers per item. This cost is justified if the item-size is
quite greater than the size of two pointers. Is that true in case of
the Inkscape path nodes? Other than the X, Y coords, what other data
would you store per node?
The trivial "cost" of two pointers is justified, because many
algorithms operating on the nodes require the ability to insert /
delete nodes at arbitrary positions and to splice two node lists
together. These operations are constant time on a list, but linear
time on a vector.
The nodes also store attributes related to their appearance and type.
2) From what I could learn from the code, it seems as if you store
off-curve i.e. handle points separately as part of the linked list and
not as adjuncts of on-curve points, i.e. for a single cubic bezier you
and not something like:
p1 (x, y, pre.x, pre.y, post.x, post.y, prev, next)
p2 (pre.x, pre.y, point.x, point.y, post.x, post.y, prev, next)
Is that right? This allows you to cut down the storage requirements in
case of linear segments but at significant cost (many more prev,next)
pointers in case of cubic segments. Was the tradeoff found acceptable?
No, you must have misunderstood the code. Each Inkscape::UI::Node has
two Inkscape::UI::Handle members, regardless of the type of the node.
Handles are not stored in the linked list.
Before 0.48, the old node tool did store the handles in a linked list
together with the nodes.