Next: , Previous: Undo histories, Up: Transactions and topological sorting

6.3.3 Geometric dependencies and topological sorting

As mentioned before, every graphic object has several anchors which serve as “geometric input” and hangers which are “geometric output” devices. Every anchor is connected to exactly one hanger, while a hanger can hold arbitrarily many anchors. This creates a dependency structure of geometric objects within a page (no anchor can hang on a hanger from a different page).

In the following image you can see a dependency diagram with two graphic objects. The half-circles represent anchors and hangers: the black half-circles pointing up are anchors, the ones pointing down are hangers and the white half-circles are mouse-clicks.

An example of a dependency diagram.

When any geometric property of a graphic object is changed or when an anchor of the object is rehung on some other hanger, the object must be recomputed. But all the dependent objects – objects whose anchors hang on the object's hangers – must be recomputed as well. The recomputation must be done in the right order; we use the topological order which assures that every object is dependent on the previous objects only.

We will not describe the topological sorting algorithm, as it is well known; we only describe how the algorithm is used in the VRR kernel.

Every page contains a special data structure for the topological sort: a list of graphic objects tsort_list and a bitmask for flags. The flags have the following meaning:

The topological sorting algorithm is used for these activities as well:

All the other editing actions must be done when the topological sorting is not active, because they could change the dependency structure (by adding new dependent GOs or removing some, for example) and make the sorted list invalid.