126
theirrightendpoints,sothatthefinalrepresentationofaninterval(x,y)intheprioritiy
searchtreeisatuple(Y,x),whereY = (y, x, ID).
6.7 Puttingitalltogether
Nowwewillexaminesomeofthealgorithmsfortheoperationslistedatthebeginningof
thissection.Inthepseudo-codeinthissection,theauxiliarydatastructuresareused,but
notdescribedinfulltokeepthefocusonthedetailsofwhatmustbeupdatedandqueried
when.Specializedstructuredforaddresscomparisonandmaintenanceoftheinsertionseg-
mentindexaredescribedinfull.
6.7.1 Addresscomparison
Wheneverachangeisaddedtothedatabase,theaddressesitcontainstoarestoredand
givenintegerlabels.Theselabelsareupdatedasnewaddressesareaddedtothedatabaseby
oneoftherenumberingalgorithmsgivenin(DietzandSleator1987),anddiscussedabove.
Palimpsestaddresscomparisoniscomplexandtheintegerlabelsservethefunctionofena-
blingconstant-timecomparisonofmanyaddresses,savingtimeonacommonoperation.
Addresseswithinmoveandcopydestinationsmayhavelongpaths.Inthedefinitionof
theorderingforPalimpsestaddresses,orderingquestionsarefrequentlyresolvedbyreducing
themtoquestionsonaddresseswithshorterpaths.Thesearegenerallynotstoredorlabeled,
astheyarenotusuallyreferencedbyotheroperations.Onlythoseaddressesarestoredthat
correspondtotheendpointsofranges(fordelete,copyandmove),ordestinations(forall
operations).
Tofindthecorrectpositioninthegloballistofstoredaddresses,acomparisonoperation
isneeded.Figure6.5showsthebasicmethodforastoredaddresstocompareitselftoan
arbitraryaddress.Notethatthedestinationaddressesofanychangesmustalreadyhave
beenstored,andarethusdirectlycomparablebymeansoflabels.Thefollowingauxiliary
methodsareusedinthecomparisonalgorithm:

127
1. AddresssRecord.getOperationInList()returnstheoperationintheglobal
segmentlistrepresentingthisaddress.
2. AddressRecord.getComparisonLabel()returnstheintegerlabelforagivenad-
dressrecord.
3. Operation.getDestination()returnsthedestinationaddressforagivenopera-
tion.
4. Insertion.getIndex()returnstheindexofaninsertionsegment.
5. Insertion.getNextChunk()returnsthenextsegmentrepresentinganaddresssin
thisinsertion.
6. Insertion.getAddress()returnstheinitialaddressofthisinsertionsegment.
7. AddressfindSegment(path,index)findsthestoredaddressrepresentingthe
positionafterwhich(path,index)isfound.
Thisalgorithmhasafewsomewhatsubtlepoints.Theremovalofthecommonprefixre-
flectsthefactthatidenticalmoveandcopyoperationsdonotcontributetoorderingtheir
addresses.Trickieristhehandlingofaddressesoftheform(I,i).Thiskindofaddresscon-
sistsoftheIDofasingleinsertionandanindexwithinthatinsertion.Aninsertionmay
haveseveralvalidsegmentswithdifferentstartingindices,interruptedbyinterveningdesti-
nationaddresses.UnlikeaddresseswithmovesandcopyIDsintheirpaths,twoaddressesof
theform(I,i)cannotbecomparedintermsoftheirdestinationsortheirindices(exceptin
thespecialcasewheretheyhaveequalpaths).Intheformaldefinitions,thiswasreflected
bytranslatinginsertionstotheirultimatedestinationsintheirgreatestcausalancestor.The
explicitdeterminationofcommonancestorsdoesnotneedtobeperformedintheindex,
sincethelabelsallowustocomparethepositionofsegmentsdirectly.Similarly,thetransi-
tiveclosureofthedestinationrelationisalreadyimplicitlycalculatedbecausethedestina-
tionsarealreadyinsertedintothesegmentlist.