2013/7/6 Shriramana Sharma <samjnaa@...400...>:
On Tue, Apr 23, 2013 at 9:29 PM, Krzysztof Kosiński <tweenk.pl@...847...0...> wrote:
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.
Hi Krzysztof,
A few more questions regarding this:
- 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.
- 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 would have:
p1 (x,y,prev,next) c1 (x,y,prev,next) c2 (x,y,prev,next) p2 (x,y,prev,next)
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.
Regards, Krzysztof