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-
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-