Zones, Fragments etc

[jgraley]

New terms

• A zone is a multi-terminated subtree
• A fragment is part of a zone between neighbouring terminii

An n-zone (n>=0) is formed by taking a base subtree and specifying n links inside that subtree as terminii. The zone then includes every node that is in the base subtree but not in the subtree under any terminus. It includes every link in the base subtree and the terminus links but not their child nodes. Every terminus must be in the base subtree and not in the subtree under any other terminus.

A tree is a subtree. A subtree is a 0-zone.

An n-zone has n+1 fragments. The links in a fragment are defines as those reached on a depth-first walk, either from base to the first-reached terminus, or a terminus to the next-reached one, or last-reached terminus (otherwise base) to the end of the base subtree. The base link is in the first fragment and not the last. Terminii links themselves are not included in fragments.

A 0-zone has one fragment which is everything in the zone.

Thoughts

It looks like we could have a "zone math". I think a tree minus a subtree is a 1-zone. Tree minus n subtrees is an n-zone. Tree minus a n-zone is a 1-zone and n 0-zones.

Zone math won't always be well-defined eg in case zones overlap. Where we need eg disjointedness criteria, we should be able to test these at run-time. Hopefully, such checks will be log-complexity by following parentage.

[jgraley]

I have begun to differentiate between a FreeZone and TreeZone. The former has a TreePtr<Node> for a base, and the latter an XLink.

FreeZone is for:

• newly created/duplicated zone
  • Important: since a free zone cam be a duplicate of X tree nodes, it can include an identifier node that is still in the X tree. We rely on identity semantics to make this safe.
• potentially, a zone that has been removed from the tree but not deleted

TreeZone is for:

• any part of the current X domain
• including root, because we insist that there is always a "root XLink".
• and including domain extensions

Thoughts:

• Basically, a TreeZone has a base that is in the domain the the CSP solver works on, and hence must have a unique XLink - it keeps track of that XLink.
  • It should not be possible to exit the domain by going parent to child. Thus every subtree under a domain xlink is in the domain, and the whole of a TreeZone is in the domain
• Duplicate( TreeZone ) would be a FreeZone.
• It's possible that "zone math" might model TreeZone as absolute and FreeZone as relative?

[jgraley]

Stuff agent permits matching zero levels, in which case terminus matches base. How to represent?

I think that if one terminus coincides with base then all must, due to the definition of an n-zone given above. So there would only be one since we use a set. Since a zone excludes children of terminus links, there are no nodes in such a zone, and zones are not nullable objects, such a FreeZone could be represented as

• base is a NULL TreePtr<Node>
• terminii contains one XLink to that.

As for TreeZone in this case, no special rep is required: base and only-element-of(terminii) are the same.