124
However, since the typical deletion will be small compared to the total size of the se-
quence, an incremental rebuilding strategy is more sensible. Each segment in the complete
deletion database that overlaps the undone operation is simply re-inserted into union seg-
ment index. For short deletions this is much faster, but in the worst case, the runtime for
the incremental strategy is still O(n log n). Up ton – 1segments might have to be inserted,
each at a cost of O(log n)time, if the deletion being undone overlaps all other deletions, and
they are totally disjoint.
6.6 Indexing move operations
Move operations very similar to deletion operations, but building an efficient index of
move source ranges is trickier problem, since move operations need to be compared with
each other for priority. When determining if a region has been moved elsewhere (so that it
should be ignored in the current context), we need to perform a more complex query than
simple segment intersection. When examining an address that is part of the result of a move
operation, we need to know not if the source range is question has been moved by anyop-
eration, but if it has been moved by any operation with a higher priority. The use of priori-
ties ensures that source regions are “greedy,” with each address in overlapping move scopes
being claimed by only one move operation.
If move priorities are completely arbitrary (as they were in the model definitions), then
this is a difficult multidimensional search problem on the start, end and priority of the move
operation. However, we observed in Section 3.3.3 that the choice of priority function is al-
most completely arbitrary, except that move sources that are completely contained within
another move source to should take priority over the containing region. This allows the
preservation of internal rearrangements even when a larger move shifts a long subsequence.
Giving priority to inner regions in nested source scopes can be assured by giving priority to
those source regions whose right endpoint is smaller. While overlapping regions that are not
However, since the typical deletion will be small compared to the total size of the se-
quence, an incremental rebuilding strategy is more sensible. Each segment in the complete
deletion database that overlaps the undone operation is simply re-inserted into union seg-
ment index. For short deletions this is much faster, but in the worst case, the runtime for
the incremental strategy is still O(n log n). Up ton – 1segments might have to be inserted,
each at a cost of O(log n)time, if the deletion being undone overlaps all other deletions, and
they are totally disjoint.
6.6 Indexing move operations
Move operations very similar to deletion operations, but building an efficient index of
move source ranges is trickier problem, since move operations need to be compared with
each other for priority. When determining if a region has been moved elsewhere (so that it
should be ignored in the current context), we need to perform a more complex query than
simple segment intersection. When examining an address that is part of the result of a move
operation, we need to know not if the source range is question has been moved by anyop-
eration, but if it has been moved by any operation with a higher priority. The use of priori-
ties ensures that source regions are “greedy,” with each address in overlapping move scopes
being claimed by only one move operation.
If move priorities are completely arbitrary (as they were in the model definitions), then
this is a difficult multidimensional search problem on the start, end and priority of the move
operation. However, we observed in Section 3.3.3 that the choice of priority function is al-
most completely arbitrary, except that move sources that are completely contained within
another move source to should take priority over the containing region. This allows the
preservation of internal rearrangements even when a larger move shifts a long subsequence.
Giving priority to inner regions in nested source scopes can be assured by giving priority to
those source regions whose right endpoint is smaller. While overlapping regions that are not
