116
thelist,selectingonlyinformationcontainedinaninsertionthatispartoftheactivever-
sionandnotpartofadeletionintheactiveversion.
Comparisonoftwoversionsisquitesimple,sincetextalwaysappearsinthesameorderin
bothversions,althoughanyparticularsubstringmayappearineitherorbothversions,or
neitherone.Theresultsofacomparisoncanbesummarizedasanorderedsequenceofpairs
ofrangesinthetwoversions,withazerolengthsequenceinacorrespondenceindicatinga
deletedregion.Thisresultisaccumulatedbytraversingthestructure,enumeratingthecon-
tentsofbothversionstobecompared.Eachpointwillbecontainedbyone,both,orneither
ofthetwoversions.Thecomparisonresultcanbeaccumulatedbysimplystartinganewcor-
respondencepairanytimetheinclusionstatechangesineitherversion.Suchanindexis
sufficienttoallowparallelscrollingandhighlightingintwoversions(SeeFigure6.3).
F F F F iii ig g g gu u u ur r r re e e e 6666....3333:::: VVVVTTTTMMMMLLLL eeeeddddiiiittttoooorrrr ddddiiiiffffffff wwwwiiiinnnnddddoooowwww,,,, wwwwiiiitttthhhh ccccoooorrrrrrrreeeessssppppoooonnnnddddiiiinnnngggg ppppoooorrrrttttiiiioooonnnnssss hhhhiiiigggghhhhlllliiiigggghhhhtttteeeedddd

117
Asthedocumentandhistorybecomelarger,however,linearscanning(anditsO(N)run-
timeforadocumentcontainingNchanges)islessappealing.Onegoodstrategyistocache
versionsbyconstructingaseparateaccessstructurecontainingonlyinformationfromapar-
ticularversion.Cachedversionscancontaininformationononeversionorseveral.Alarge
numberofstrategiescanbeusedtocreatecachedversions:
• Anewcachecanbecreatedforeachnewversion.
• Anewcachevbecreatedperiodicallyforwheneveracertainnumberofversionshas
beencreatedonacertainlineofdevelopment.
• Acachecanbekeptforthemostrecentversionsonsomesetofbranchesoftheversion
tree.
Cachesincludetheirdatabyreference,sothatacachedversionhasasizerelatedtothe
numberofoperationscontributingtoit,notthesizeofthesequenceitrepresents.Since
versionsareimmutable,noupdateissuesneedtobeconsidered,andcachedversionscanbe
deletedatanytime.Acachedversioncan,however,speedupdatessignificantlyifitmain-
tainspointersbacktothefulldatastructure,byallowingthecorrectlocationfornewup-
datestobefoundinthesmallercachedstructure,ratherthanthefullstructure.
Whilecachingcanspeedtheretrievalofaversion,acachethatisalsoalinearlistdoes
notprovideforquickaccesstoaparticularpointwithinaversion.ForthecurrentVTMLim-
plementation,thisisnotaseriousproblem,becauseofitstargetenvironmentofserver-
basedaccessovertheWorldWideWeb.VTMLfileswithmanyversionsresideatserverma-
chines,notuserworkstations.
6.3 ImplementingPalimpsest
IncontrasttoVTML,whichisintendedasaclient-servercommunicationformat,Palimp-
sestchangestructuresareforusebylocalinstancesofcollaborativeapplications.Becauseit
musthandleonlineupdatesatindividualeditorinstances,aPalimpsestdatastructuremust