126
their right endpoints, so that the final representation of an interval (x, y)in the prioritiy
search tree is a tuple (Y, x), whereY = (y, x, ID).
6.7 Putting it all together
Now we will examine some of the algorithms for the operations listed at the beginning of
this section. In the pseudo-code in this section, the auxiliary data structures are used, but
not described in full to keep the focus on the details of what must be updated and queried
when. Specialized structured for address comparison and maintenance of the insertion seg-
ment index are described in full.
6.7.1 Address comparison
Whenever a change is added to the database, the addresses it contains to are stored and
given integer labels. These labels are updated as new addresses are added to the database by
one of the renumbering algorithms given in (Dietz and Sleator 1987), and discussed above.
Palimpsest address comparison is complex and the integer labels serve the function of ena-
bling constant-time comparison of many addresses, saving time on a common operation.
Addresses within move and copy destinations may have long paths. In the definition of
the ordering for Palimpsest addresses, ordering questions are frequently resolved by reducing
them to questions on addresses with shorter paths. These are generally not stored or labeled,
as they are not usually referenced by other operations. Only those addresses are stored that
correspond to the endpoints of ranges (for delete, copy and move), or destinations (for all
operations).
To find the correct position in the global list of stored addresses, a comparison operation
is needed. Figure 6.5 shows the basic method for a stored address to compare itself to an
arbitrary address. Note that the destination addresses of any changes must already have
been stored, and are thus directly comparable by means of labels. The following auxiliary
methods are used in the comparison algorithm:
their right endpoints, so that the final representation of an interval (x, y)in the prioritiy
search tree is a tuple (Y, x), whereY = (y, x, ID).
6.7 Putting it all together
Now we will examine some of the algorithms for the operations listed at the beginning of
this section. In the pseudo-code in this section, the auxiliary data structures are used, but
not described in full to keep the focus on the details of what must be updated and queried
when. Specialized structured for address comparison and maintenance of the insertion seg-
ment index are described in full.
6.7.1 Address comparison
Whenever a change is added to the database, the addresses it contains to are stored and
given integer labels. These labels are updated as new addresses are added to the database by
one of the renumbering algorithms given in (Dietz and Sleator 1987), and discussed above.
Palimpsest address comparison is complex and the integer labels serve the function of ena-
bling constant-time comparison of many addresses, saving time on a common operation.
Addresses within move and copy destinations may have long paths. In the definition of
the ordering for Palimpsest addresses, ordering questions are frequently resolved by reducing
them to questions on addresses with shorter paths. These are generally not stored or labeled,
as they are not usually referenced by other operations. Only those addresses are stored that
correspond to the endpoints of ranges (for delete, copy and move), or destinations (for all
operations).
To find the correct position in the global list of stored addresses, a comparison operation
is needed. Figure 6.5 shows the basic method for a stored address to compare itself to an
arbitrary address. Note that the destination addresses of any changes must already have
been stored, and are thus directly comparable by means of labels. The following auxiliary
methods are used in the comparison algorithm:
