129
An interactive editing process can provide an address directly, along with the segment the
operation is affecting. The application will operate on that sequence, declaring operations in
terms of offsets in the P-sequence representing its current state. If there is an interface be-
tween the application and the Palimpsest store, it should maintain an index of the Palimp-
sest addresses (and their associated segments) in the current P-sequence. Then, when a new
operation needs to insert a new address into the segment list, the correct segment is avail-
able, enabling the insertion and the creation of a new, labeled address record a simple mat-
ter of direct list insertion. This strategy avoids even the cost of using the findSegment
function.
6.7.2 Sequence contents
Besides text segments, the text segment store also contains a number of different objects
and their address records: insertion points for moves and copies; move, copy and deletion
range endpoints; in some systems, perhaps the endpoints of hypertext link anchors. In addi-
tion to representing the address space, traversal of the segment list is how the contents of a
P-sequence are enumerated.
We now consider the sequential enumeration of the contents of a P-sequence represented
by a change set V. The following additional operations will be used to check the auxiliary
data structures associated with V:
1. isDeleted(V, address)checks the address to see if it is deleted by any of the
deletion changes in V. Takes time logarithmic in the number of deletions.
2. findDeletionFor(V, address)returns a deletion inVthat overlaps the given
address, or one of the deletions that starts at the leftmost address to the right of the
given address. Takes time logarithmic in the number of deletions.
3. getMoveRegion(V, address, changeID)return the longest higher-priority
move operation overlapping the given points, if any. If the changeID is null, any
An interactive editing process can provide an address directly, along with the segment the
operation is affecting. The application will operate on that sequence, declaring operations in
terms of offsets in the P-sequence representing its current state. If there is an interface be-
tween the application and the Palimpsest store, it should maintain an index of the Palimp-
sest addresses (and their associated segments) in the current P-sequence. Then, when a new
operation needs to insert a new address into the segment list, the correct segment is avail-
able, enabling the insertion and the creation of a new, labeled address record a simple mat-
ter of direct list insertion. This strategy avoids even the cost of using the findSegment
function.
6.7.2 Sequence contents
Besides text segments, the text segment store also contains a number of different objects
and their address records: insertion points for moves and copies; move, copy and deletion
range endpoints; in some systems, perhaps the endpoints of hypertext link anchors. In addi-
tion to representing the address space, traversal of the segment list is how the contents of a
P-sequence are enumerated.
We now consider the sequential enumeration of the contents of a P-sequence represented
by a change set V. The following additional operations will be used to check the auxiliary
data structures associated with V:
1. isDeleted(V, address)checks the address to see if it is deleted by any of the
deletion changes in V. Takes time logarithmic in the number of deletions.
2. findDeletionFor(V, address)returns a deletion inVthat overlaps the given
address, or one of the deletions that starts at the leftmost address to the right of the
given address. Takes time logarithmic in the number of deletions.
3. getMoveRegion(V, address, changeID)return the longest higher-priority
move operation overlapping the given points, if any. If the changeID is null, any
