122
sequence, such a move or copy destination is a signal to traverse the part of the insertion
segment structure corresponding to the source of the operation.
The segment list also provides a way to speed the comparison of Palimpsest addresses, by
making it easy to determine the relative ordering of the destinations of all operations. Each
destination has a place in the list of segments, and these relative locations can be used to
speed the comparison of destinations, by maintaining integer labels on the elements of the
list. Maintaining such labels on list items (to enable comparison in an unkeyed sequence) is
lnown as the order maintenance problemand it can be solved(Dietz and Sleator 1987) forn
segments in O(1)amortized time at the cost of some implementation complexity, or very
simply in O(log n)time. Each insertion into the segment list uses a variant of this algorithm
to maintain ordering labels on all addresses contained in stored changes.
6.5 Tracking deletions
Deletions must be stored so as enable quick determination of whether a particular posi-
tion is deleted, and after such an initial search, should provide quick enumeration of fol-
lowing deleted segments. Since deletions will be added and occasionally undone, the set of
intervals representing the deleted segments must be dynamic. Efficient interval overlap
testing is possible with a number of query structures.
One of the most flexible structures to maintain such information with good access time
is the priority search tree (McCreight 1985). The balanced variant of this data structure can
insert and delete in O(log n) time fornsegments and, given a query segment, can enumer-
ate all overlapping segments in O(log n + k) time forkresult segments. A priority search tree
can be used so that the first overlapping segment found in any search will be the one with
the largest right endpoint. This endpoint is a good starting point in searching for the next
deletion in the sequence. In the case of many overlapping regions, it is a problem to perform
sequence, such a move or copy destination is a signal to traverse the part of the insertion
segment structure corresponding to the source of the operation.
The segment list also provides a way to speed the comparison of Palimpsest addresses, by
making it easy to determine the relative ordering of the destinations of all operations. Each
destination has a place in the list of segments, and these relative locations can be used to
speed the comparison of destinations, by maintaining integer labels on the elements of the
list. Maintaining such labels on list items (to enable comparison in an unkeyed sequence) is
lnown as the order maintenance problemand it can be solved(Dietz and Sleator 1987) forn
segments in O(1)amortized time at the cost of some implementation complexity, or very
simply in O(log n)time. Each insertion into the segment list uses a variant of this algorithm
to maintain ordering labels on all addresses contained in stored changes.
6.5 Tracking deletions
Deletions must be stored so as enable quick determination of whether a particular posi-
tion is deleted, and after such an initial search, should provide quick enumeration of fol-
lowing deleted segments. Since deletions will be added and occasionally undone, the set of
intervals representing the deleted segments must be dynamic. Efficient interval overlap
testing is possible with a number of query structures.
One of the most flexible structures to maintain such information with good access time
is the priority search tree (McCreight 1985). The balanced variant of this data structure can
insert and delete in O(log n) time fornsegments and, given a query segment, can enumer-
ate all overlapping segments in O(log n + k) time forkresult segments. A priority search tree
can be used so that the first overlapping segment found in any search will be the one with
the largest right endpoint. This endpoint is a good starting point in searching for the next
deletion in the sequence. In the case of many overlapping regions, it is a problem to perform
