--Rope.mesa,"Thick"stringdefinitions--RussAtkinson,August27,198211:51am--TableofContents:--***Part1:Basicoperationsanddefinitions--***Part2:Extendedoperationsanddefinitions--***Part3:Miscellaneousdefinitions--ARopeis(nominally)animmutableobjectcontaingasequenceofcharactersindexedstartingat0forSizecharacters.Therepresentationallowscertainoperationstobeperformedwithoutcopyingallofthecharactersattheexpenseofaddingadditionalnodestotheobject.--NOTE:thebitpatternofthetextvariantisGUARANTEEDtobeconsistentwiththebuilt-inCedartypeTEXT,althoughthetypeswillnotagreeeitheratcompile-timeorruntime.ThismeansthatonecanuseobjectsoftypeTextorTEXTinterchangeablyprovidedthattheruntimetypeisnotexamined,andprovidedthatthecompilercanbefooled(viaLOOPHOLE).SinceREFTEXTisroughlycompatiblewithMesaLONGSTRING,thisisameansforpassingRoperefstoPilotroutinesthatexpectLONGSTRING.ForshortSTRINGyouareonyourown(seeConvertUnsafe).DIRECTORYEnvironmentUSING[Comparison];Rope:CEDARDEFINITIONS--***Part1:Basicoperationsanddefinitions***--=BEGINROPE:TYPE=REFRopeRep;NoRope:ERROR;--signalledifropeisinvalidvariant--usuallyindicatessevereillnessintheworld--Note:BoundsFault=Runtime.BoundsFault--ItisraisedbymanyoftheRopeoperationsCat:PROC[r1,r2,r3,r4,r5,r6:ROPE_NIL]RETURNS[ROPE];--returnstheconcatenationofuptosixropes(limitbasedonevalstackdepth)--BoundsFaultoccursiftheresultgetstoolargeConcat:PROC[base,rest:ROPE_NIL]RETURNS[ROPE];--thetwo-rope(faster)versionofCat--BoundsFaultoccursiftheresultgetstoolargeCompare:PROC[s1,s2:ROPE,case:BOOL_TRUE]RETURNS[Environment.Comparison];--basedonCHARcollatingsequence--case=>caseofcharactersissignificantEqual:PROC[s1,s2:ROPE,case:BOOL_TRUE]RETURNS[BOOL];--contentsequalityofs1ands2--case=>caseofcharactersissignificant1p b& c w y` ?fC $H y]5 ^ y[ D i yY DG "f yXC D  yT r[ "'&+,2j4 :}?DpFGI ySR r  5$L( /H029=BDF yQ  &A*+- yNa ;C %2& 1!24 :=@D yL ^N"G%)+Y 3N5:=B#DG yK K(."03@8H;-<>Em yIpu"% /386:<9A$ G yG! @"h$)P,/d1 4[9=theropesizeFind:PROC[s1,s2:ROPE,pos1:INT_0,case:BOOL_TRUE]RETURNS[INT];--likeIndex,returnspositionins1wheres2occurs(startslookingatpos1)--returns-1ifnotfound--case=>caseofcharactersissignificantIndex:PROC[s1:ROPE,pos1:INT_0,s2:ROPE,case:BOOL_TRUE]RETURNS[INT];--ReturnsthesmallestcharacterpositionNsuchthat--s2occursins1atNandN>=pos1.Ifs2doesnot--occurins1atorafterpos1,s1.lengthisreturned.--case=>caseofcharactersissignificantIsEmpty:PROC[r:ROPE]RETURNS[BOOL];--returnsLength[r]=0Length:PROC[base:ROPE]RETURNS[INT];--returnsthelengthoftherope(Length[NIL]=0)Replace:PROC[base:ROPE,start:INT_0,len:INT_MaxLen,with:ROPE_NIL]RETURNS[ROPE];--returnsropewithgivenrangereplacedbynew--BoundsFaultoccursifrangeinvalidorresulttoolongSize:PROC[base:ROPE]RETURNS[INT];--Size[base]=Length[base]Substr:PROC[base:ROPE,start:INT_0,len:INT_MaxLen]RETURNS[ROPE];--returnsasubropeofthebase--BoundsFaultoccursiftherangegivenisnotvalid--characterconversions(RRAsez:whyaretheyhere?)Control:PROC[ch:CHAR]RETURNS[CHAR]=INLINE{RETURN[IFchIN['A..'Z]THENch-controlOffsetELSEch]};Upper:PROC[ch:CHAR]RETURNS[CHAR]=INLINE{RETURN[IFchIN['a..'z]THENch-caseOffsetELSEch]};Lower:PROC[ch:CHAR]RETURNS[CHAR]=INLINE{RETURN[IFchIN['A..'Z]THENch+caseOffsetELSEch]};Letter:PROC[ch:CHAR]RETURNS[BOOL]=INLINE{RETURN[chIN['A..'Z]ORchIN['a..'z]]};Digit:PROC[ch:CHAR]RETURNS[BOOL]=INLINE{2rs b! ^b!rb!qb!b!rhb!b!q_b!3b!rpb!Lb!qb!b!r"b!#b!q%*b!%b!r+b!+b!q-b!-b!r0pb!0b!p `{ `{vyd $.rp ^ ^ %{3 #5%(rs [ ^[r,[q*[[r[[+q][1[rn[K[q[i[r!u[#[$q'[([r+[q-[-[r0D[q1+[1[r7[q7[r9[9[p Y Y A!%'+/46grp X> X>Frp V Vt  rs SM SMrSMqSMwSMr Qq(QQr9QQqQ4Qr?QQYqQ _Qr"Q#yQq&Q'Qr*vQq,Q,Qr/.Qq0Q0Qr6Qq6jQr8vQ8Qp P P^ m%|'*1rp N\ N\H)!V%L&(+rp L LR i$&$rp K Kt  rs G Gr_Gq\GGrGLGqGGrGqGGr Gq!Gr$FG$Gp F Frs B iBrBqBSBr8BBq/BBrABq(BBr"Bq"|Br$B$Bp A. A. (*rs = =r3=q1==r <<q<<]<<r<<w<<q<<j<<ru<<<<q!\<<!<<r#<<%^<<+:q.<</<<r2I<<q3<<4<<r5<<q :f:r:q:r:[:p 8 8$%4'rp 7K 7K %{>#%_)+lrs 4 ^4r4q44r44q4V4r4q{4O4r l4q 4r"4#>4p 2Z 2Z  rs / ^/rV/qT//r/D/q//r//qN//r!/#Q/$q'/(/r* /+/q1/2g/r7/q7/r:/;\/p -i -ifrp + + %{!%&(rp (w (w   #%(rs %, t%,r%,q%,%,r%,%,qT%,%,r%,q%,h%,r!%,q!%,r%@%,&(%,q( %,(w%,r,%,q # ^#r#q?#r#g#q##rn##q##r# M#!" q*#+#r.#.# !s  rqr ql7rqr q!r$Y%@q'&'r+q  ^rq?rgqrnqXr ! q(s)-r+,C Is  ir5q3r#qMrqr q!r$o%Vq';'r+q X ^XrXq?XrXgXqXXrnXXqXXrX MX!#~ q* X*Xr-?X-X s g igr*gq(ggrggqxgBgrgqggr gq! gr$7g%gq'g'mgr+gq  ^r?q%rDq{Wr0q{r 7  s r q * r r q  r* q  r  q f r# $y q&^ & r* t)TVm$RETURN[chIN['0..'9]]}; --***Part2:Extendedoperationsanddefinitions***--Run:PROC[s1:ROPE,pos1:INT_0,s2:ROPE,pos2:INT_0,case:BOOL_TRUE]RETURNS[INT];--ReturnslargestnumberofcharsNsuchthats1startingatpos1--isequaltos2startingatpos2forNchars.Moreformally:--FORiIN[0..N):s1[pos1+i]=s2[pos2+i]--Ifcaseistrue,thencasematters.Match:PROC[pattern,object:ROPE,case:BOOL_TRUE]RETURNS[BOOL];--ReturnsTRUEiffobjectmatchesthepattern,wherethepatternmaycontain--*toindicatethat0ormorecharacterswillmatch.--Ifcaseistrue,thencasematters.SkipTo:PROC[s:ROPE,pos:INT_0,skip:ROPE]RETURNS[INT];--ReturnthelowestpositionNinssuchthats[N]isintheskiprope--andN>=pos.Ifnosuchcharacteroccursins,thenreturns.length.SkipOver:PROC[s:ROPE,pos:INT_0,skip:ROPE]RETURNS[INT];--ReturnthelowestpositionNinssuchthats[N]isNOTintheskiprope--andN>=pos.Ifnosuchcharacteroccursins,thenreturns.length.Map:PROC[base:ROPE,start:INT_0,len:INT_MaxLen,action:ActionType]RETURNS[BOOL];--Appliestheactiontothegivenrangeofcharactersintherope--ReturnsTRUEwhensomeactionreturnsTRUE--BoundsFaultoccursonattemptingtofetchacharacternotintheropeTranslate:PROC[base:ROPE,start:INT_0,len:INT_MaxLen,translator:TranslatorType_NIL]RETURNS[new:ROPE];--appliesthetranslationtogetanewrope--iftheresultingsize>0,thennewdoesnotsharewiththeoriginalrope!--iftranslator=NIL,theidentitytranslationisperformedFlatten:PROC[base:ROPE,start:INT_0,len:INT_MaxLen]RETURNS[Text];--Returnsaflatropefromthegivenrangeofcharacters--BoundsFaultoccursiftheresultinglengthwouldbe>LAST[NAT]FromProc:PROC[len:INT,p:PROCRETURNS[CHAR],maxPiece:INT_MaxLen]RETURNS[ROPE];--returnsanewropegivenaproctoapplyforeachCHARFromRefText:PROC[s:REFREADONLYTEXT]RETURNS[Text];--makesaropefromaREFREADONLYTEXT--causescopyingToRefText:PROC[base:ROPE]RETURNS[REFTEXT];--makesaREFTEXTfromarope3rq b! ^b!rb!?b!q%b!b!rb!Db! `{ ]/p ]/ ]/ "X$ +.rs Y Yr YqYYrX>qX>X>rX>X>qNX>X>rX>QX>q X> X>r#!X>#X>q'X>(X>r*'X>+X>-Aq0X>1bX>r4>X>q5X>6X>r8X>qVVrVqkVrvVVp T TmR!##&@)*/1_rp SM SMl jZ "@#(I+rp Q Q {c " rp P P} rs L LrlLqjLLrLZLqqLLr!L!Lq%XL&Lr(Lq*zL+3Lr-Lq.L/aLr4~Lq4Lr8 L8pLp K KF5"f$)-/47orp Ij Ij5 %(rp G G} rs Dy ^DyrDyqDyDyrfDyDyqKDyDyr\Dy9Dyq=DyDyrDy!?Dy"q&3Dy'Dyr)EDyq*,Dy+Dyr0Dyq0Dyr2Dy2Dyp B B!4"=%Z(,+$,.603erp A. A.<$(*v+.2rs = ^=r=q==r==q=T=r=n=qr==r ="t=$q'h=(<=r*z=q+a=,5=r1R=q1=r3=4$=p << <<!4"=%Z(,+$,0"146rp : :<$(*v+.2rs 7K 7KrC7Kq@7K7Kr5q55r55q55r55q!5"J5r$V5%5+0P q44r4qk4r44p 2Z 2Z' $f& ,y.0krp 0 0m"'rp / / % "$v').1O25Ars + u+r&+q$++r*q**r**q**r**q!*"J*r$V*%*+ 2V ;q=*>g*r?*q(w(wr(wk(wq(w(wr(wG(wp & &| .n #hrp %, %,W-"`%d'+\.X05rp # #W {`*" (*2rs ; ^ ;r ;q ;j ;rO ; ;qF ; ;rW ;3 ;q ; & ;r"2 ;# ;%Lq( ;( ;r* ;, ;q2 ;2 ;r7 ;8V ;p  FK"&(= rp   %{#Q'o+\-+.`rs  ^r}q{#r q,rqorqPr"# #q**r,.q4i5=r:Zq:r=>1p X X"W![#&(+rs  ^ r q 5 r } q  #r& q' (k r- - p g g2fj.&rp  0rs v u vr vq v vr v vq vd vr vq v] vr$z vq$ v'r* v* vp  2f9nt)TVm$--causescopyingFromChar:PROC[c:CHAR]RETURNS[Text];--makesaropefromacharacterMakeRope:PROC[base:REF,size:INT,fetch:FetchType,map:MapType_NIL,pieceMap:PieceMapType_NIL]RETURNS[ROPE];--Returnsaropeusinguser-suppliedproceduresanddata--theuserproceduresMUSTsurviveaslongastheropedoes!PieceMap:PROC[base:ROPE,start:INT_0,len:INT_MaxLen,action:PieceActionType,mapUser:BOOL_TRUE]RETURNS[BOOL];--Appliestheactiontothegivensubropeinpieces(maxof1piece/Substr,--2pieces/Concat,3pieces/Replace,either1piece/MakeRopeoruseuser's--routine).ReturnsTRUEwhensomeactionreturnsTRUE.--BoundsFaultoccursonattemptingtofetchacharacternotintheropeContainingPiece:PROC[ref:ROPE,index:INT_0]RETURNS[base:ROPE,start:INT,len:INT];--Findthelargestpiececontaingthegivenindexsuchthattheresultis--eitheratextoranobjectvariant.--(NIL,0,0)isreturnediftheindexisNOTinthegivenropeBalance:PROC[base:ROPE,start:INT_0,len:INT_MaxLen,flat:INT_FlatMax]RETURNS[ROPE];--Returnsabalancedrope,possiblywithmuchcopyingofcomponents--flat_MIN[MAX[flat,FlatMax],LAST[NAT]]--len_MIN[MAX[len,0],Size[base]-start]--start<0ORstart>Size[base]=>boundsfault--theresultingmaxDepthwillbelimitedby2+log2[len/flat]VerifyStructure:PROC[s:ROPE]RETURNS[leaves,nodes,maxDepth:INT];--traversethestructureofthegivenrope;returnthenumberofleaves,--nodesandthemaxdepthoftheropeextracheckingisperformedtoverify--invariantsaleafisatextorobjectvariantanodeisanon-NIL,--non-leafvariantsharedleavesandnodesaremultiplycountedVerifyFailed:ERROR;--occurswhenVerifyStructurefindsabadegg--shouldnothappen,ofcourse --***Part3:Miscellaneousdefinitions***--controlOffset:NAT=100B;caseOffset:NAT='a-'A;FetchType:TYPE=PROC[data:REF,index:INT]RETURNS[CHAR];--typeoffetchroutineusedtomakeauserropeMapType:TYPE=PROC[base:REF,start,len:INT,action:ActionType]RETURNS[quit:BOOL_FALSE];4rp b4 b40rs ^ ^^r^q^9^r^^q^^rr^qZ^.^r"K^"^p ]C ]C2fjrs Y YrYqYYrXQqXQXQrTXQ0XQqUXQXQr`XQ=XQ* &h)0Gq1XQ2XQr3XQVk q ]V!EVr"hVq#PV$$Vr)AVq)Vr,V-Vp U UFJ " ),Frp S` S`M1 #$')+.rs P iPr~Pq{P#PrNoqNoNorNoNoqNoNorNoNoq!No"JNor$VNo%No+0PLqLLrLqLLrILq0LLr$"Lq$Lr'L(Lp K# K#' %'?+,.0Z1 rp I~ I~5 S#&( 24D6rp G G z $e(w-rp F2 F2 % "$v').1O25Ars B tB r9q<99r7^q7^7^r7^7^q7^7^r7^7^q!7^"J7^r$V7^%7^+q.7^/7^r1"7^27^q55r5qk5r|55p 4 4F@"J%E(-/ rp 2m 2mx! rp 0 0Brp /" /"S;p #['rp -| -|Mt  %X'2rs *0 t*0 r*0q*0S*0r8*0*0q*0*0r/*0q*0*0r%*0%j*0).q5]*05*0r7h*07*0p ( (O"l%),H1-2rp & &gr!a$e'-/5_7rp %? %? =qz3#!'(,*-.rp # #I$ "&w(.r N q N Nr Np  7# $B&rp  .2r p    %'r k qLk4kr+kk  qprgLs z ^zrzqzzr!zqzzrzzqtz Hzr!z"zq&z'Ezr(zq)z*zr/zq0"zr3{z3zp  7"$&rs r2 q/  r q  r  q f r  q S r %c q-F . r37 3 q6 7 r: q< < r? @ t)TVm$--typeofuserroutineusedtomapoverasubrope--returnsTRUEifsomeactionreturnsTRUEActionType:TYPE=PROC[c:CHAR]RETURNS[quit:BOOL_FALSE];--typeofroutineappliedwhenmapping--returnsTRUEtoquitfromMapTranslatorType:TYPE=PROC[old:CHAR]RETURNS[new:CHAR];--typeofroutinesuppliedtoTranslatePieceMapType:TYPE=PROC[base:REF,start,len:INT,action:PieceActionType]RETURNS[quit:BOOL_FALSE];--typeofroutineusedtopiecewisemapoverasubrope--returnsTRUEifsomeactionreturnsTRUEPieceActionType:TYPE=PROC[base:ROPE,start:INT,len:INT]RETURNS[quit:BOOL_FALSE];--typeofroutineappliedwhenmappingpieces--returnsTRUEtoquitfromPieceMapRopeRep:PRIVATETYPE=RECORD[SELECTtag:*FROMtext=>[length:NAT,text:PACKEDSEQUENCEmax:CARDINALOFCHAR],node=>[SELECTcase:*FROMsubstr=>[size:INT,base:ROPE,start:INT,depth:INTEGER],concat=>[size:INT,base,rest:ROPE,pos:INT,depth:INTEGER],replace=>[size:INT,base,replace:ROPE,start,oldPos,newPos:INT,depth:INTEGER],object=>[size:INT,base:REF,fetch:FetchType,map:MapType,pieceMap:PieceMapType]ENDCASE]ENDCASE];MaxLen:INT=LAST[INT];FlatMax:CARDINAL=24;Text:TYPE=REFTextRep;--thesmall,flatvarianthandleTextRep:TYPE=RopeRep[text];--usefulforcreatingnewtextvariantsEND.Forthosewhocare,thisistheofficialexplanationoftheRopeRepvariants:Note:NILisallowedasavalidROPE.Note:ALLintegercomponentsoftherepresentationmustbenon-negative.SELECTx:xFROMtext=>{--[0..x.length)istherangeofcharindexes--[0..x.max)isthenumberofcharsofstoragereserved--allRopeoperationscreatingnewtextobjectsinitx.length=x.max5rp b& b&n!!$%rp ` `^$qrs ]5 t]5r\]5qY]5]5r]5q]5=]5r"]5]5q]5]5r!v]5q"^]5#2]5r(O]5(]5q,]5,]5r/]5q11]51]5r4]552]5p [ [,Urp Y Yrrs V uV rVqVfVrVqVVrvVVq!V"Vr%Vq%V&Vr+V,PVq/V0Vr3V3sVp T T,crs Q iQ rmQqjQ#QrQq P:PrPPqPPr\P9PqnPPr yP!VP%qNaoNarNaNaqMNaNarNaqoNa(Nar! Na!pNap L L,<!$'(rp K K^$qrs G iG rGqGMGrGq F$:F$rF$F$qF$F$r'F$F$qF$F$rF$uF$q"BF$"F$r$MF$q%5F$& F$r+&F$+F$q.F$/F$r2{F$q4F$4F$r7F$8 F$p D~ D~,U$rp B Brr ?q%??r?q = ^=r {SELECTx:xFROMsubstr=>{--[0..x.size)istherangeofcharindexes--x.basecontainscharsindexedby[0..x.size)--[0..x.size)inx==>[x.start..x.start+x.size)inx.base--Size[x.base]>=x.start+x.base};concat=>{--[0..x.size)istherangeofcharindexes--x.basecontainscharsindexedby[0..x.pos)--[0..x.pos)inx==>[0..x.pos)inx.base--x.restcontainsthecharsindexedby[x.pos..x.size)--[x.pos..x.size)inx==>[0..x.size-x.pos)inx.base--x.pos=Size[x.base]ANDx.size=x.pos+Size[x.rest]};replace=>{--[0..x.size)istherangeofcharindexes--x.basecontainscharsindexedby[0..x.start),[x.newPos..x.size)--[0..x.start)inx==>[0..x.start)inx.base--[x.newPos..x.size)inx==>[x.oldPos..Size[x.base])inx.base--x.restcontainsthecharsindexedby[x.start..x.newPos)--[x.start..x.newPos)inx=>[0..x.newPos-x.start)inx.base--x.size>=x.newPos>=x.startANDx.oldPos>=x.start--x.size-x.newPos=Size[x.base]-x.oldPos};object=>{--[0..x.size)istherangeofcharindexes--x.baseifthedataneededbytheuser-suppliedoperations--x.fetch[x.base,i]shouldfetchtheithcharANDx.fetch#NIL--x.map[x.base,st,len,action]--implementsMap[x,st,len,action]--x.pieceMap[x.base,st,len,action]shouldbehave--implementsPieceMap[x,st,len,action,TRUE]--itisOKtohavex.map=NILORx.pieceMap=NIL};ENDCASE=>ERRORNoRope}ENDCASE=>ERRORNoRope};6rpb&b&irp``1} C"?*,03u r^ ]5 [q [^[rw['[q[[rY XCp XC8XC5 >\!mrp V V -!" rp T T  +,,rp SR SR ~P6r Q P Nap Na8Na5 >\!mrp L L -!" rp K K  "$Arp Ip Ip a"$rp G Go`V(*rp F$ F$ w #U%:(* r D~ BH A3p A38A35 >\!mrp ? ? -!" )rp = = =~ $%rp \!mrp / / -I #"o * rp -n -n 9 #!%5(F+0d2Irp + + Zrp *" *" " Rrp (} (} |#'rp & & "  #m'rp %1 %1 am9S8"^$ ,0.r #q !rr!!q!!r!!q @ C @rr @ @q @ @r @ @t)0TVm$ HELVETICA TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN? -  ' 0R6j/97)l Rope.mesa16-Dec-82 16:25:16