[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]


Now that I've had some time to read the new information about the Ent, I'm slowly coming to the point that I have some ideas of the structure, and with those preliminary ideas I'm now finding additional questions. I still find the code rough going, because even with the basic idea in mind, there are a lot of additional features, some of which seem not to be complete.

As a reminder, I've put the new documents on Jeff's zWiki server, where they can be found by the interested.

The ideas as described in Mark Miller's outline confirm that the basic Enfilade is a balanced tree where each node contains the width (in the relevant coordinate system, integer or tumbler) of the subtree of which it is the root. versioning of enfilades is managed by copying of the tree, while sharing all possible substructures with the original.

The Ent adds upward links that branch at each node to indicate which parents it has in all versions that contain the node. My first question is the following:

It seems that one needs only two parent pointers, since any new node only introduces a single new global root version. Is this true?

It also seems that the Smalltalk Ent implementation does not combine upward pointers within nodes in this way, probably because it's hard to maintain balance in two directions (northward and southward).
Is this true?

It could also simply be that it's easier to add a new H-child, and have multi-way branching towards the H-leaves, than to bother encoding multiple derived versions of a node (O-parents, H-children) as binary H-trees.

I have some more questions and comments coming.

  -- David

David Durand
Chief Technical Officer
Dynamic Diagrams