OrderedSymbolTable.mesaOrderedSymbolTableisapackageformaintainingsymboltables(keytovaluemaps)withanorderingamongkeys.Theorderingallowsthetabletoperformsearchessuchas"findthesmallestiteminthetablethatislargerthanthisone,"aswellasexact-matchsearches.Thepackage'simplementationusesabinarytreerepresentationof2-3-4trees,calledred-blacktrees;thismeansthatanysearch,insertion,ordeletionfromatableofnitemstakesO(nlogn)time.AtablestoresitemsoftypeNodewithkeysoftypeKey,whereNodeandKeyaredefinedinadefinitionsmodulethatparameterizestheOrderedSymbolTableinterface.AuserofthepackagecreatesasuitabledefinitionsmoduletoparameterizeOrderedSymbolTable,thencompilesOrderedSymbolTableandRedBlackTreeImpl.Lasteditedby:MBrownonNovember10,19826:38pmDIRECTORYEnvironmentUSING[Comparison],ParticularTableUSING[Node,NodeRecord,Key,GetKey,CompareKeyToNode];OrderedSymbolTable:CEDARDEFINITIONSIMPORTSParticularTable=BEGINNode:TYPE=ParticularTable.Node;NodeRecord:TYPE=ParticularTable.NodeRecord;Key:TYPE=ParticularTable.Key;GetKey:PRIVATEPROC[n:Node]RETURNS[Key]=INLINE{RETURN[ParticularTable.GetKey[n]]};Compare:PRIVATEPROC[k:Key,n:Node]RETURNS[Environment.Comparison]=INLINE{RETURN[ParticularTable.CompareKeyToNode[k,n]]};Table:TYPE=RECORD[Node];TheRECORDtypeconstructorallowsmostproceduresbelowtobeinvokedusingobjectnotation.Error:ERROR[ec:ErrorType];ErrorType:TYPE={notInitialized,badTable};Allproceduresbelowwithaself:TableparameterraiseError[badTable]ifselfappearstobemalformed(itmightforinstancebeanormalNodethatwaspassedbymistake.)ProceduresInitialize:PROC[sentinel1,sentinel2:Node];Thisproceduremustbecalledbeforecallinganyproceduresbelow.Callersuppliesthepackageinstancewithtwonodesforitsinternaluse.(Thesenodesaregoneforever;weprovidenowaytoreclaimtheirspace.)CreateTable:PROC[header:Node]RETURNS[Table];!Error[notInitialized](ifInitializehasnotbeencalled.)Callersuppliesanodetorepresentatable.Theprocedurecreatesanemptytableandreturnsit.DestroyTable:PROC[self:Table];Makestableempty,asitwasjustafterCreateTable.Insert:PROC[self:Table,nodeToInsert:Node,insertKey:Key];!DuplicateKey(ifinsertKeyalreadypresentintable).CallerassertsthatCompare[insertKey,nodeToInsert]=equal.InsertsnodeToInsertintotable.ERRORsDuplicateKeyifCompare[insertKey,x]=equalforsomenodexalreadyinthetable.DuplicateKey:ERROR;1p aq ]X! )Y. 25A7:>BD4 [N+:I #%v*|/247:;?XBYCF< Z? 1!V (/17 AVD2E^ X e="*((+.2588< BD V *^U% " Tp r+T!T$h&(,#0 36I9;s@"AC R O) 0a25 69=>CAD Q! ) !/s319_F Oz ML" I!$r HsG r_GDGsGG EqrEqEqsEq=Eq d (,.1 BrWB"B &s,mB->B r6 B7Bs@lrV@l@ls@l@l> r>_>s>>=r=<=s==t;gs;gr;g0;gsu;g;gr";g#;gs(;g)";g 9r9n9s9r99s 9o9.t8s[8rX88sE88a"$xr(8)~8s.8.8 6cr6cn6cs6cr6c6cs 6co6c#574rh4"4s4r4y4s4`4q 3 u3 3 q)3 3  "&()g 0357V k!o&v).14%7c`CEGt  sFrDs44r!f":s'W'q>-Y #%'+&2fJ# $?(o+21^57;?AFXt  srsq9~$5"n% t sorls\` $( /qq5- gj$'(*o &wI%U ./4h8 A!C  T*,p.U147:<@BsDt 5 s 5r 5 5s 5v)TVm$wDelete:PROC[self:Table,deleteKey:Key]RETURNS[deletedNode:Node];Removesthe(unique)nodexintablesuchthatCompare[deleteKey,x]=equal,andreturnsit,orreturnsNILifnosuchnodeexists.LookupProc:TYPE=PROC[self:Table,lookupKey:Key]RETURNS[Node];ProceduresLookup,LookupNextLarger,LookupNextSmallercanallbeassignedtoavariableofthistype.Lookup:PROC[self:Table,lookupKey:Key]RETURNS[equalNode:Node];Returnsthe(unique)nodexintablesuchthatCompare[lookupKey,x]=equal,orNILifnosuchnodeexists.LookupSmallest:PROC[self:Table]RETURNS[smallestNode:Node];Returnstheitemintablewithsmallestkey,orNILiftisempty.LookupNextLarger:PROC[self:Table,lookupKey:Key]RETURNS[largerNode:Node];ReturnsthenodeintablewiththesmallestkeystrictlylargerthanlookupKey,orNILifnosuchitemexists.LookupLargest:PROC[self:Table]RETURNS[largestNode:Node];Returnstheitemintablewithlargestkey,orNILiftisempty.LookupNextSmaller:PROC[self:Table,lookupKey:Key]RETURNS[smallerNode:Node];ReturnsthenodeintablewiththelargestkeystrictlysmallerthanlookupKey,orNILifnosuchnodeexists.Lookup3:PROC[self:Table,lookupKey:Key]RETURNS[leftNode,equalNode,rightNode:Node];ThisLookupprocedurereturnsthreenodesintable:[LookupNextSmaller[self,lookupKey],Lookup[self,lookupKey],LookupNextLarger[self,lookupKey]].Notethatinanonemptytable,oneoftheresultsisguaranteed#NIL.(ThisprocedurewasHowardSturgis'idea.)EnumerateIncreasing:PROC[self:Table,procToApply:PROC[Node]RETURNS[--stop--BOOL]];Foreachitemxinthetable,inincreasingorderbykeyvalue,executesprocToApply[x].ReturnswhenprocToApplyreturnsTRUEorwhenallitemshavebeenenumerated.procToApplyisrestricted:itcannotcallotherproceduresinthisinterface.Inparticularitcannotexamineormodifythetablebeingenumerated.SuchenumerationscanbeimplementedusingLookupNextLargerorLookupNextSmaller.CheckTable:PROC[self:Table];ERRORsError[badTable]ifthered-blacktreerepresentingthetableisnotwell-formed.Usedbypackagetestprograms;maybeusedforclientdebuggingofunsafeprograms.RootNode:PRIVATEPROC[self:Table]RETURNS[rootNode:Node];Returnsthetherootofthered-blacktreerepresentingthetable.Usedbypackagetestprogramsonly.END.HowtouseCompilingthepackageThispackageiscompile-timetailorabletoaparticularapplication.Thistailoringisdonewithouteditingthesourcecodeofthepackage'sinterfaceorimplementation.Thisiseasyifonlyoneversionofthepackageistobepartoftheapplication,andsomewhatmoreinvolvediftwoormoreversionsofthepackagearetobepartoftheapplication.Intheformercasetheprocedureis:(1)createaParticularTabledefinitionsmodule,whichmustdefineNode,NodeRecord,Key,GetKey,andCompareKeyToNodeasfollows:2t asaraashaa #r&ca'7as,Ta,a 5Pq_U!$'*68:>A,EGt^-y Ct Z sOZrLZZsZrZ0ZsZyZ |$ ,Lr/Z0~Zs5Z5ZqY Y&3579m>@mAFWpzt UsUrU(Us UpUt $Dr'U(uUs-U-U 5zqT kR $K'h*:7 8:>@YCDRe=t P sPrPBCmE`It HD sHDrHDHDsHDHDr!2HD"HDs'#HD'HD /qFktm i$')a,-.0=t DsDrDDsDD$* +r/D/Ds5D5tD =qC/kP "'G).F26 =8>BCmE`A t ?s3?r0??s? ?$] $r(R?)&?s.C?.?4 $*V $Y()-=- <}  0, 5N8;s=>NDw:o_ !#'+b14.9Y>[t 7qs7qr7q)7qs7qq7q u$ r-7q.A7qs1'7q17qr57q67qs;7qq<7qr@J7qA7qsCv7qC7qq5!b '+Q-+/39C4c fu44q"4#;4$C')-M0t3 2f } $#&') 0W14 :< CD^0Jv # +/C 7:; C/t + s+r ++s++u*q**U &)B 03!6u7:D BkE([$ !$'*1 27t $s$r $$ms$]$ar#$$y$s)$)$0q#Ek4$s'" .1518:r?B8!r sp w q X U  !#$ * 25;t<@5E  !9="x$.E1>25t69<@BDL   W G w%).I/2+37M @TEG b 9 J(t"%( .7x/bq  '4|9 !&*.L2[6Z >qAF 5]v) TVm$%DIRECTORYEnvironmentUSING[Comparison],...;ParticularTable:DEFINITIONS=BEGINNode:TYPE=REFNodeRecord;NodeRecord:TYPE=...;Mustcontainfields"rbLLink","rbRLink",oftypeNode,and"rbColor",oftypeBOOL.ItislikelythattypeNodeRecordissimplyequatedtoarecordtypefromsomeotherdefsmodule.Key:TYPE=...;Anyoldtypethatallowsallowsthefollowingproceduretobedefined:GetKey:PROC[n:Node]RETURNS[k:Key];Extractsthekeyfromanode.ThisiscalledonlyfromtheprocedureCheckTablebelow,soitneednotbeimplementedifCheckTablewillnotbecalled.CompareKeyToNode:PROC[k:Key,n:Node]RETURNS[Environment.Comparison]...;Comparesabarekeytothekeyembeddedinanode.Result=lessmeanskfilenamecorrespondenceisnotone-to-one,compilercommand-lineparameterizationcontrolsthedifferentversions,asin:(3')xxxOrderedSymbolTable_OrderedSymbolTable[ParticularTable:xxxParticularTable](4')xxxRedBlackTreeImpl_RedBlackTreeImpl[OrderedSymbolTable:xxxOrderedSymbolTable]Aversionofthispackagethatdoesitsownstorageallocation,storesREFANYitems,andcanbeusedfordifferentapplicationswithoutrecompilingisavailableasOrderedSymbolTableRef.ConcurrencyTheimplementationofthispackageisamodulemonitor.Henceforeachinstanceofthispackage,atmostonetableoperationmaybeinprogressatatime.ObjectnotationClientsofthispackagemayuseobjectnotationtocallanyprocedurewhosefirstparameteris"self:Table".Forinstance,write"table.Insert[node,key]"insteadof"OrderedSymbolTable.Insert[table,node,key]".ChangeLogCreatedbyMBrownonMarch2,19824:14pmByeditingOrderedSymbolTableRef.ChangedbyMBrownonMarch8,198212:09pm3u b&q2b&%b& u8b&b&qRb&b& & ' `yu`y`y q:`yu`y`yq ^u^^qk^uP^^q^ ^ ] u]]q]h] [rW ! &l(*.1 8<9u<[r=[rq@[r Y d !|%*,S-147;8 X Vku;VkVkqVkVk T+!\'0-[/0 SuDSSqSGSuSSqS WS" QdpG!#P'1*--k/5 =d O 7j @ '),- N u&N N qN )N !"u&N 'N q,N -$N <>} L]J~%']( J.Gf #&(-;u I Iq pI F} mc"&(i+- C mF!X Ap m  )L*- > VN-2y4"68y; =o D[G =C 8' w#; : 2V$(*8.+ 57=dBDU 9!#/#2`5y:#<A|D1 7nP!6$w)J.2U469<5ADG; 5 k #( 1