133
interdependence of the changes involved. We revisited this idea in Section 6.4, and de-
scribed the storage of insertions at destinations at their ultimate origin. The reason for this
should now be clear. All addresses described above in item 1 are at the destination of a move
or copy, and are found during traversal of the source region. By storing the addresses de-
scribed in item 2 there as well, the traversal process is actually simplified. Otherwise, extra
work would be required to locate those addresses (and their segments) while traversing the
segment list at the source of the operation.
Random access to the contents of a P-sequence at a particular address is facilitated by the
ability to access the initial segment of any insertion given its change ID. This also allows
easy access to moved data, as the initial path of the address provides the information for the
move copy stack that should be used at the point of the insertion. The data itself can be di-
rectly located by the insertion address at the end of the path.
6.7.3 Comparison of P-sequences
Comparison of VTML documents is easy since the relationships between portions of VTML
documents are very simple. A region of any version of a VTML document is either present in
both versions in the same sequential order, or is deleted in one of the two. In a Palimpsest
document, however, more-complex relationships are possible.
The simplest comparison relationship in a VTML document is identity. Some segments ap-
pear in both documents, and they appear in the same relative order in each. The only other
possible relationship is deletion. In VTML, there is even a clear and obvious notion of the
“position” of a deleted string in other versions of a document. In Palimpsest, this notion
needs careful analysis, since data in a subsequence may be moved or duplicated in another
context. In the result of a Palimpsest comparison, the proper location of a deleted sequence
in another version is the address that would have been its final destination had it not been
deleted.
interdependence of the changes involved. We revisited this idea in Section 6.4, and de-
scribed the storage of insertions at destinations at their ultimate origin. The reason for this
should now be clear. All addresses described above in item 1 are at the destination of a move
or copy, and are found during traversal of the source region. By storing the addresses de-
scribed in item 2 there as well, the traversal process is actually simplified. Otherwise, extra
work would be required to locate those addresses (and their segments) while traversing the
segment list at the source of the operation.
Random access to the contents of a P-sequence at a particular address is facilitated by the
ability to access the initial segment of any insertion given its change ID. This also allows
easy access to moved data, as the initial path of the address provides the information for the
move copy stack that should be used at the point of the insertion. The data itself can be di-
rectly located by the insertion address at the end of the path.
6.7.3 Comparison of P-sequences
Comparison of VTML documents is easy since the relationships between portions of VTML
documents are very simple. A region of any version of a VTML document is either present in
both versions in the same sequential order, or is deleted in one of the two. In a Palimpsest
document, however, more-complex relationships are possible.
The simplest comparison relationship in a VTML document is identity. Some segments ap-
pear in both documents, and they appear in the same relative order in each. The only other
possible relationship is deletion. In VTML, there is even a clear and obvious notion of the
“position” of a deleted string in other versions of a document. In Palimpsest, this notion
needs careful analysis, since data in a subsequence may be moved or duplicated in another
context. In the result of a Palimpsest comparison, the proper location of a deleted sequence
in another version is the address that would have been its final destination had it not been
deleted.