What are the constraints for regenning the dB

[jgraley]

• domain None, it's just a set of nodes
• link table None really, a Free tree begins at a Node, and an open/NULL link can still have a fully valid link row
• node table The node row for the base of a free zone is broken, in the sense that it will show no parents, but can be fixed up easily on joining.
• category ordering None, the ordering is based on node type
• Simple Compare ordering SC "value" depends on the entire subtree under a node, so you'd need everything out to leaf level i.e. subtrees. Open/NULL links would cause uncertainty.
• depth-first ordering Joining a subtree inserts a contiguous range into DF order I think, no need too re-evaluate relation. But if we did re-evaluate relation, we'd need a path to the tree root. Maybe free subtrees only need to be locally correct, and can be joined using a hinted insert? No, there's no insert for ranges. Maybe set_union()? no it makes copies Looks like the options are:
  • Implement own container for the ordering
  • Keep the ordering correct by only preserving tree zones when they don't move relative to other tree zones #722
• domain extension Tricky. Based on XLinks in which case broken for Open/NULL and needs fixup on Join
  It would be nice of the stimulis were TreePtr<Node>, but they're not.

[jgraley]

To insert into an ordering, your new XLink needs to be compared with potentially any of those already there, and the whole idea is that the XLinks in the preserved tree zones stay in the orderings all the way through. So: all the XLinks in preserved tree zones must be fit for comparison on any ordering whenever anything is inserted:

• SC ordering requires that any element has subtree all the way to leaves and is not truncated by a "delete"
• DF ordering requires that any element has ancestors all the way to the root.

Conclusion is that if you want to insert into the orderings, you have to do so on a complete tree. Options for DB update then are:

• do all the tree changes leaving a complete tree with all tree zones in, then all the db updates
• do a series of { some tree changes leaving a complete tree with all tree zones in, then corresponding db updates }
  • eg once for each free zone

Implication is that TreeZones are always embedded in the tree and have ordering entries and we don't try to "remove" them from the tree, instead working around them on the free zones.

[jgraley]

Note different strategy for DF and SC ordering. Ordering dependencies:

• DF relation depends on relative locations of nodes - parent level changes can change the relation results
• SC relation depends on descendants - changing descendants of either can change the relation results

So, if some node or zone changes then:

• DF ordering can be invalidated for the entire sub-tree under the change - expensive
• SC ordering can be invalidated for all ancestors above the change - not so bad (log complexity)

Thus we accept differences in strategy:

• We'll never allow the DF ordering for preserved nodes to be invalidated
  • which means keeping them in the same relative order
  • handling swaps by duplicating one of them (hopefully the smaller)
• We'll allow the SC ordering for preserved nodes to be invalidated
  • Code already exists to go and fix up the parent nodes
  • Will arrange for this not to be needed for every node

Note that alternatives for the DF ordering constraint exist:

• For an OOO tree zone, it would be quicker to fix up the DF ordering rather than duplicate it into a free zone. Makes things more complicated though.
• A custom data structure for the DF ordering could permit subtree-level re-ordering. Eg a destructive set_union that knows about relative contiguity properties of its operands. Not doing either until the current algo is done.