Hi all,
I would like to know what structure do you use to store shapes in
Z-order. It seems to me that a simple linked list would perform
poorly for a large number of shapes, since it has a time complexity of
O(n) to find the index (the z-value) of a shape.
So, I was thinking at two other structures. The first one would be
similar to a linked list except that each node would store its own z
value. However, since the Z order is only a "less than or equal to"
relation, Z values don't need to be equal to their index in the list
or even be continuous. So, this class would not waste time to reuse
the indices from removed/moved shapes. Operations like add-last,
bring-to-front, send-to-back would allocate a new Z-value each time
they are called. And operations like remove would not adjust the
indices of the other nodes. So, all operations would perform in O(1)
time cost!
However there is a disavantage of not resuing indice. This class
cannot perform an illimited number of some operations (because these
operations allocate a new Z value each time they are called). However,
this should not be a limitation in real world applications, because
that I would be surprised that a user performs more than 2^31
operations (for an integer z value). Another disavantage is that it's
not possible to know the real value of the Z order; a Z value makes
sence only by comparing it with another.
The second structure doesn't have these limitations but it's more
complex to implement and a little bit less performant. This structure
is a balanced tree where the predicate to insert a node is the
in-order index in the tree. The main idea is that the index of a node
(thus it's Z value) can be computed by traversing the tree upward to
the root, thus in O(log n). So, the nodes don't have to keep its own
Z value, and don't need to adjust them. All other operations perform
in amortized O(1), since we may need to make some rotations to balance
the tree, which should be really fast in practice.
Note that these structures assume that a shape *is* a node, i.e.
having a reference on a shape means that we have a reference on the
node. Thus, we don't need to find the node corresponding to a given
shape.
What so you think of these structures? What structure InkScape actually uses?
Thanks for your comments,
Jean