127
1. AddresssRecord.getOperationInList()returns the operation in the global
segment list representing this address.
2. AddressRecord.getComparisonLabel()returns the integer label for a given ad-
dress record.
3. Operation.getDestination()returns the destination address for a given opera-
tion.
4. Insertion.getIndex()returns the index of an insertion segment.
5. Insertion.getNextChunk()returns the next segment representing an addresss in
this insertion.
6. Insertion.getAddress()returns the initial address of this insertion segment.
7. Address findSegment(path, index)finds the stored address representing the
position after which (path, index) is found.
This algorithm has a few somewhat subtle points. The removal of the common prefix re-
flects the fact that identical move and copy operations do not contribute to ordering their
addresses. Trickier is the handling of addresses of the form (I, i). This kind of address con-
sists of the ID of a single insertion and an index within that insertion. An insertion may
have several valid segments with different starting indices, interrupted by intervening desti-
nation addresses. Unlike addresses with moves and copy IDs in their paths, two addresses of
the form (I, i)cannot be compared in terms of their destinations or their indices (except in
the special case where they have equal paths). In the formal definitions, this was reflected
by translating insertions to their ultimate destinations in their greatest causal ancestor. The
explicit determination of common ancestors does not need to be performed in the index,
since the labels allow us to compare the position of segments directly. Similarly, the transi-
tive closure of the destination relation is already implicitly calculated because the destina-
tions are already inserted into the segment list.
1. AddresssRecord.getOperationInList()returns the operation in the global
segment list representing this address.
2. AddressRecord.getComparisonLabel()returns the integer label for a given ad-
dress record.
3. Operation.getDestination()returns the destination address for a given opera-
tion.
4. Insertion.getIndex()returns the index of an insertion segment.
5. Insertion.getNextChunk()returns the next segment representing an addresss in
this insertion.
6. Insertion.getAddress()returns the initial address of this insertion segment.
7. Address findSegment(path, index)finds the stored address representing the
position after which (path, index) is found.
This algorithm has a few somewhat subtle points. The removal of the common prefix re-
flects the fact that identical move and copy operations do not contribute to ordering their
addresses. Trickier is the handling of addresses of the form (I, i). This kind of address con-
sists of the ID of a single insertion and an index within that insertion. An insertion may
have several valid segments with different starting indices, interrupted by intervening desti-
nation addresses. Unlike addresses with moves and copy IDs in their paths, two addresses of
the form (I, i)cannot be compared in terms of their destinations or their indices (except in
the special case where they have equal paths). In the formal definitions, this was reflected
by translating insertions to their ultimate destinations in their greatest causal ancestor. The
explicit determination of common ancestors does not need to be performed in the index,
since the labels allow us to compare the position of segments directly. Similarly, the transi-
tive closure of the destination relation is already implicitly calculated because the destina-
tions are already inserted into the segment list.
