OrderedSymbolTableRef.mesaOrderedSymbolTableRefisavariantoftheOrderedSymbolTablepackageformaintainingsymboltables(keytovaluemaps)withaninterestingorderingamongkeys.ThepackagestoresREFANYitems,andacceptsanitem-comparisonprocedureasaparameteratthetimeatableiscreated,soitdoesnotneedtoberecompiledtohandledifferenttypesofitems.Lasteditedby:MBrownonNovember17,198210:45amDIRECTORYEnvironmentUSING[Comparison];OrderedSymbolTableRef:CEDARDEFINITIONS=BEGINTable:TYPE=REFTableObject;TableObject:TYPE;Key,Item:TYPE=REFANY;Comparison:TYPE=Environment.Comparison;CompareProc:TYPE=PROC[r1,r2:Item]RETURNS[Comparison];ProceduresCreateTable:PROC[compareProc:CompareProc,nodeZone:ZONE_NIL,tableZone:ZONE_NIL]RETURNS[t:Table];Returnsanemptytablethatusesthegivencomparisonfunction.nodeZonewillbeusedtoallocatenodesforred-blacktree(7wordseach),tableZonewillbeusedtoallocateheaderfortree(11wordsplus3nodes);thesebothdefaulttothesystemzone.DestroyTable:PROC[t:Table];Deletesallitemsfromt,theninvalidatest.DeleteAllItems:PROC[t:Table];Makestabletempty(t.Size[]=0).Size:PROC[t:Table]RETURNS[nItems:INT];Returnsthenumberofitemsint.Insert:PROC[t:Table,insertItem:Item];Insertsitemxintotablet.ERRORsDuplicateKey(withmonitorreleased)ifcompareProc[x,y]=equalforsomeyinthetable.DuplicateKey:ERROR;Delete:PROC[t:Table,deleteKey:Item]RETURNS[deletedItem:Item];Removesthe(unique)itemyintsuchthatcompareProc[deleteKey,y]=equal,andreturnsit,orreturnsNILifnosuchitemispresent.Lookup:PROC[t:Table,lookupKey:Key]RETURNS[equalItem:Item];Returnsthe(unique)itemyintsuchthatcompareProc[lookupKey,y]=equal,orNILifnosuchitemexists.LookupSmallest:PROC[t:Table]RETURNS[smallestItem:Item];Returnstheitemintabletwithsmallestkey,orNILiftisempty.LookupNextLarger:PROC[t:Table,lookupKey:Key]RETURNS[largerItem:Item];ReturnstheitemintabletwiththesmallestkeystrictlylargerthanlookupKey,orNILifnosuchitemexists.Lookup3:PROC[t:Table,lookupKey:Key]RETURNS[leftItem,equalItem,rightItem:Item];ThisLookupprocedurereturnsthreenodesintable:[LookupNextSmaller[self,lookupKey],1p aq ]} "R$17 9j A E [  "(,039r=[=[?qB[C%[F Z8 "#*2+.)152m573<8=?PBWDG X '!M" VU- I!%Ns QtP s_PDPtPP LsLL u t({Ls*`L+LtKshK"KtKsKyKtUK s1D>D>tD>smD>D>tD> ]D>"n$s(JD>)D>t.;D>.D> p ?: u ; tF; sD; ; t; 4; )s0; 1; t4; s6; 7; t8); 9; s?; @; tC; sE$; F ; tG0; s 9ct9c$9cq7a3"$c' /58;~>?B6 "o$'+2E469;_@aD4c! $v',-/4Ku 2 t2s22t22[q0V &u /N t/Ns/N/Ntg/N/N7q-~!u *9t}*9sz*9"*9t*9j*9s*9*9t *9o*9s$z*9$*9t&*9&*9q(kP!&u &to&sl&&t&\& !q%%$ -505;V< FV#}f!u ! t!s!!t!u t s  th  7p !ns% % t+ +l  3|qiU]!-""%?(68(: >@E@Fy !yu ^t^s^(^t ^p^ "s& ^&^t+^,^^ 3Zqk !$'68?:$>?BDQFDu T tTsT<Tt!TTs 5T! Tt&&T&T .qktma!]&)er++q-../1Yu tfsc tS! )s,-t23B :iq?ktma!]#(+Y/36 =r??@?qB4?B?CE} u t3 s0  t   #]s& ' t, - 2 9y @q 5*V $Y()-=- v)TVm$Lookup[self,lookupKey],LookupNextLarger[self,lookupKey]].Notethatinanonemptytable,oneoftheresultsisguaranteed#NIL.(ThisprocedurewasHowardSturgis'idea.)EnumerateIncreasing:PROC[t:Table,procToApply:PROC[Item]RETURNS[BOOLEAN]];Foreachitemxinthetable,inincreasingorderbykeyvalue,executesprocToApply[x].ReturnswhenprocToApplyreturnsTRUEorwhenallitemshavebeenenumerated.TheprocedureprocToApplymaymakeanymodificationstothetablethatitlikes;EnumerateIncreasingisimplementedtosimulateonecallonLookupSmallest(tofindthefirstitem),andthenrepeatedcallstoLookupNextLarger(tofindthe"next"item),somodificationstothetableduringtheenumerationmaybeunderstoodintermsofthismodel.CheckTable:PROC[t:Table];ERRORsError[badTable]ifthered-blacktreerepresentingthetableisnotwell-formed.Usedbypackagetestprograms;maybeusedforclientdebuggingofunsafeprograms.BadTable:ERROR;RootItem:PROC[t:Table]RETURNS[rootItem:Item];Returnsthetherootofthered-blacktreerepresentingthetable.Usedbypackagetestprogramsonly.END.OrderedSymbolTablesHowtoacquirethepackageBringover/a/pTop>RedBlackTreeRef.dftoobtaintheinterfaceOrderedSymbolTableRef.bcdandtheimplementationRedBlackTreeRefImpl.bcd.Ifyoubindtheimplementationintoyourownconfiguration,you'llhavetoimportSafeStorageforitsuse.WritingCompareProcsThispackagetriestobeasgeneralaspossible,andhencetradessomeefficiencyforflexiblilty.ThepackagestoresREFANYitems,andperformscomparisonswithauser-suppliedprocedurecalledaCompareProc.ACompareProcmustbepreparedbothtocomparetwoitems(asinInsert,whereitcomparesinsertItemwithitemsalreadyinthetable),andtocompareakeytoanitem(asinLookup,whereitcompareslookupKeywithitemsalreadyinthetable).Onewayfortheclienttoaccomplishthisistomakekeysanditemsthesame,thatis,toembedakeyintoanitembeforecallingLookup.ThissimplifiestheCompareProcattheexpenseofcomplicatingthecallersofLookup.ThealternativeistoimplementaCompareProcthatispreparedtoseeabarekey(suchasaREFINToraROPE)asitsfirstargument.Thesecondargumenttoatable'sCompareProcisguaranteedtobeanitemstoredinthetable.Thereisnolawthatsaysthatallitemsinatablemusthavethesametype.Asyouaddvariabilitytoitemtypes,youaddcomplexitytotheCompareProc.CallingaCompareProccostsoneprocedurecall,plusthecostoftwoREFANYdiscriminations,plusthecostofactuallydoingthecomparison.Ifthecostofacomparisonishighanywaythenthisoverheadisprobablyacceptable.Ifcomparisonsaresimpleandefficiencyisimportant,youshouldbeusingtheOrderedSymbolTablepackage.ConcurrencyThetablesmaintainedbythispackageareobjectmonitors,soindividualcalls(excepttoEnumerateIncreasing)areatomic.2qb&  0, 5N8;s=>NDw`o_ !r#`$`q%`'S`*138=u ]*t]*s]*)]*t]*q]*# s,]*,]*t/]*/]*s3]*4p]*t9]*s9]*t?]*?]*q[!b '+Q-+/39CYc frYYq"Y#;Y$C')-M0t3 X- !%(5 0w24h7:;VJ %!&,#.1G3: =>?]B"DnT_i ".l03O5:=? GS7- "%' .k035b7u O tOs OOtOOirN7qN7N7U &)B 03!6u7:D BkEL$ !$'*1 27u JtJsJeJtJu I;tI;sI;GI;t,I;I;s?I;I;t"0I;"I;(qGk4$s'" .1518:r?B8Es D>tD>p ?DW&w ; q 7#()-0.5F 6"  &'* ,/& 8;4>3@ 4{ m X "[w 0T q - @ 1%r(+/2 8: ADL +Zr +Z+Z`q<+Z+Z!V &)+, 3=9i=J>~ ( ~  hG!#)&+/^13V7;=xC(Ce(q '4 &!V#/(*1,.04,68k>BCx %q%%t( $'*9,W.2>3 :=F>@CCF # ]52L #g%?(,,0k69 >A ">  q T"$f*?, 346=>E F  a#1f!(r"g #1 %q' (I )[r* +d q- . 02k5D<9?Cm   u !#p%@'3*<.4/2& q 0dA!#+$['*.0W37s9t<> DF  E S L" !%(+-w0W2r4L5L7|q:nL;LD.G#  |t !#%(*+ 3 47<?BhH#  i !P#(Z+@ 1z3( 9<AWCiGC Vw / q  /  &.)U.47f >rB`G 5cx 5v) TVm$ObjectnotationClientsofthispackagemayuseobjectnotationtocallanyprocedurewhosefirstparameteris"t:Table".Forinstance,write"table.Insert[node,key]"insteadof"OrderedSymbolTable.Insert[table,node,key]".ChangeLogCreatedbyMBrownonMBrownon11-Apr-8117:00:29ByeditingOrderedSymbolTable.ChangedbyMBrownonJune28,198211:31amCEDARinterface;addedDeleteAllItems.ChangedbyMBrownonNovember17,198210:44amCompareProcnowtakesnamedparameters.DuplicateKeyisanERROR,raisedwithmonitorunlocked.3w a?q ^4}!s&(|+-37:A#BD \ w $j)*!?CxFD\p Xx S '7q Qd ~x N"Z&r LnqULnLnY:x I X"%)q Gx kF% $ -J.06:q=mB~v)TVm$ TIMESROMAN TIMESROMANY HELVETICA TIMESROMANLAUREL TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN * GJj/OrderedSymbolTableRef.mesa17-Nov-82 10:56:52