132
wouldenableoptimizingtheoverallalgorithmbyusinganauxiliarycopyoftheelementse-
quencecontainingonlyitemsinthechangeset.Thisoptimizationwouldalsoeliminatethe
needforthefirstnestedif-statementatthestartofthecodeinFigure6.7,whichchecksfor
themembershipofaninsertionsegmentinthechangeset.
process(cur_seg,mc_stack,enumerate,version)
ifcur_seg.type()=insertion
ifthissegmentisinversion
ifcur_setismarkedaspartofamovedestination,and
thatdestinationisnotonmc_stackthen
returncur_seg.finalSegment().next()
enumerate(cur_seg)
returncur_seg.next()
else
returncur_seg.finalSegment().next()
endif
elseifcur_seg.type()==moveDestination
||cur_seg.type()==copyDestination
pushoperationonmc_stack
returncur_seg.getSource.start()
F F F F iii ig g g gu u u ur r r re e e e 6666....7777:::: AAAAuuuuxxxxiiiilllliiiiaaaarrrryyyy ffffuuuunnnnccccttttiiiioooonnnn ffffoooorrrr pppprrrroooocccceeeessssssssiiiinnnngggg aaaa sssseeeeggggmmmmeeeennnntttt dddduuuurrrriiiinnnngggg eeeennnnuuuummmmeeeerrrraaaattttiiiioooonnnn
Thehandlingofmoveandcopyduringenumerationisperhapsnotobvious.Thestrategy
usedisbasedonthefactthatmovedsubsequencesnesthierarchicallyattheirdestination,
becausetheentireregionofaddressescreatedbyamoveorcopyisinsertedatoneplace.Of
course,othersubsequencesmayalsooccurwithinsucharegion.Therearetwosortsofsub-
sequencethatcanoccurinamovedestination:
1. Datainsertedinthesourcerangeofamoveorcopyalwayshasanaddresswhose
pathstartswiththeIDofthemoveorcopy.Allsuchaddresseshavecounterparts
withoutthispathprefix,atthesourceoftheoperation.
2. Datainsertedatthetargetofamoveorcopymayhaveanykindofaddress,de-
pendingonitssource(move,copy,orinsertion).
AsdiscussedinSection3.4.2a,addresseswithinmovedestinationsareusuallybestrepre-
sentedatthemove’ssourcebecauseitallowsadditionalmergepossibilitiesbyreducingthe

133
interdependenceofthechangesinvolved.WerevisitedthisideainSection6.4,andde-
scribedthestorageofinsertionsatdestinationsattheirultimateorigin.Thereasonforthis
shouldnowbeclear.Alladdressesdescribedaboveinitem1areatthedestinationofamove
orcopy,andarefoundduringtraversalofthesourceregion.Bystoringtheaddressesde-
scribedinitem2thereaswell,thetraversalprocessisactuallysimplified.Otherwise,extra
workwouldberequiredtolocatethoseaddresses(andtheirsegments)whiletraversingthe
segmentlistatthesourceoftheoperation.
RandomaccesstothecontentsofaP-sequenceataparticularaddressisfacilitatedbythe
abilitytoaccesstheinitialsegmentofanyinsertiongivenitschangeID.Thisalsoallows
easyaccesstomoveddata,astheinitialpathoftheaddressprovidestheinformationforthe
movecopystackthatshouldbeusedatthepointoftheinsertion.Thedataitselfcanbedi-
rectlylocatedbytheinsertionaddressattheendofthepath.
6.7.3 ComparisonofP-sequences
ComparisonofVTMLdocumentsiseasysincetherelationshipsbetweenportionsofVTML
documentsareverysimple.AregionofanyversionofaVTMLdocumentiseitherpresentin
bothversionsinthesamesequentialorder,orisdeletedinoneofthetwo.InaPalimpsest
document,however,more-complexrelationshipsarepossible.
ThesimplestcomparisonrelationshipinaVTMLdocumentisidentity.Somesegmentsap-
pearinbothdocuments,andtheyappearinthesamerelativeorderineach.Theonlyother
possiblerelationshipisdeletion.InVTML,thereisevenaclearandobviousnotionofthe
“position”ofadeletedstringinotherversionsofadocument.InPalimpsest,thisnotion
needscarefulanalysis,sincedatainasubsequencemaybemovedorduplicatedinanother
context.IntheresultofaPalimpsestcomparison,theproperlocationofadeletedsequence
inanotherversionistheaddressthatwouldhavebeenitsfinaldestinationhaditnotbeen
deleted.