120
moveandcopyinsertionpointsmustbeinactivewhenmovedintotheirownsource
region.Thisisessentialtoresolveglobalconflicts,asdiscussedinSection3.3.4.
3. Adeletionregionistheareacoveredbyadeletionoperation.Thesearerepresented
asrangesinthesetofPalimpsestaddresses.
4. Copysourceregionsneednospecialhandling,sincetheydonotexertanydirectef-
fectonthepartsofthesequencetheyoverlap.
5. Movesourceregionsaremorecomplexbecausetheydeletethecontentsoftheir
scope,butmustdeleteexactlythatportionnotdeletedbyahigher-prioritymove
operation.Amovesourceregionisanattemptto“sieze”thedatainitsscope;where
movesourcesoverlap,onlyonemovecanclaimthesharedregion.
ThegoalisquickaccesstoaparticularpointinaP-sequence,andthesubsequentenu-
merationofitscontentsfromthatpointon.Thisreflectstheneedsoftexteditorssince
mosttext-basedsequenceprocessingissequential,eventhoughrandomaccessisstillimpor-
tant(especiallyintheimplementationofmove,asweshallsee).
ThefollowingsectionsdescribetheimplementationofaPalimpseststorethatmaintains
severalauxiliarydatastructurestorepresent:
1. Thedatacontentofthesequence;
2. Thedestinationsofmoveandcopyoperations;
3. Theaddressesofthedestinationsofallchanges,insequentialorder;
4. Thesetofrangesthataredeletedbyachangeset;
5. Thesetofrangesthataremovedbysomeoperationinachangeset.
6.4 Sequencecontentstorage
AnimportantpartofrepresentingUistomaintainasinglestructurerepresentingthe
contentofthesequence.Thisisasequentiallistcontainingdatadirectlyinsertedbyinser-

121
tionoperations,andalsousedtotracktherelativepositionsofsignificantaddresses,which
areusedinaddresscomparison.ThecomparisonofaddressesisdiscussedinSection6.7.1.
TheapplicationstrategydiscussedinSection3.4.2aallowsapplicationstoincreasemerge
possibilitiesbyautomaticallytranslatingdestinationaddresseswithinmoveresultstotheir
ultimatesource.Suchanaddresshastheform(I
1 …I
n , i),whereI
1 …I
n–1 aremovesorcopies,
andI
n isaninsertionoperation.Suchadestinationisstoredasifitwereinsertedat(I
n , i),
toeasethetraversalofaP-sequence.Thealteredlocationcorrectlyreflectsitsorderingwith
respecttotheotherdatawithinthemovedorcopiedcontext.Theinsertionpoint,andits
actualaddress,(I
1 …I
n , i)mustalsobeindexedintheircorrectrelativepositionforaddress
comparison.
Inserteddataisrepresentedbyalogicallistofsubsequencesegments.Eachsegmentis
taggedwithitsinsertionoforigin.Whendataisinsertedintothemiddleofasegment,that
segmentissplit,andthenewdataistaggedwithitsowninsertiontag.Thefirstsegmentof
anyinsertionmaintainsapointertoitslastsegment.Thisallowsanabsentinsertiontobe
quicklytraversed,sincenodatainsertedinsideofitcanbepresentinaversionfromwhich
itisabsent.Thistrickforsequentialenumerationofsegmentsessentiallyskipsanyinserted
segmentsthatarecausallythananinsertionnotpresentintheversionofinterest.
Segmentsinsertedintopost-moveorpost-copycontextswillhavebeentranslatedback-
wardstothesourcesoftheircontext-definingoperations.Theyareadditionallytaggedwith
theIDofthemoveorcopychangestoindicatethattheyareonlyvalidwithinthedestina-
tionregionofaparticularsetofmoveorcopyoperations.Whenencounteredinothercon-
textstheyareignored,justlikeonesthatarenotpartofthecurrentversion.Thisstructure
alsocontainspointmarkersrepresentingthedestinationsofmoveandcopyoperations,
whoseIDsallowtheirsourceregionstobedetermined.Theseareessentiallytransclusion
linksinthesenseof(Nelson1987;Nelson1987).Theyrepresentthetransparentinclusionof
materialstoredelsewhere.WhentraversingasegmentlisttoenumeratethecontentsofaP-