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],1���pî ìïa¶qî ìï]†îïî}�îÔî Œî"Rî$Àî1»î7 î9j îA îE·î ìï[ßî îÛîˆî£îÂîØ î"‘î(î,›î0Íî3³î9rî=ï[ß�î=Òï[ßî?ÊqîBÂï[ß�îC%ï[ßîFÊî ìïZ8î™îî²î àî"�î#Õî*2î+Úî.)î15�î2mî5Äî73î<8î=õî?PîBWîD¾îGêî ìïXî¼ î‚î'î…îãî!Mî"ðîýïVßîîîïU-îµî¨îîIî!Žî%NsîýïQÊtîïP sî_ïP�îDïPtîŽïP�îñïPîýïLµsîúïLµ�îÅïLµî u tî({ïLµ�sî*`ïLµ�î+ïLµtîïKsîhïK�î"ïKtîÀïK�sî¥ïK�îyïKtîUïK�î<ïK îïIRsîUïIR�îïIRtîBïIR�îïG¡îasî!ïG¡�îÚïG¡tîxïG¡�sî]ïG¡�î1ïG¡î tîïG¡�îïEï sîIïEï�îïEïtî ïEï�î…ïEïîïD>sî1ïD>�îêïD>tîˆïD>�sîmïD>�îïD>tîúïD>�î ]ïD>î"nî$ sî(JïD>�î)ïD>tî.;ïD>�î.žïD>pî ìï?: uîýï; tîFï; �sîDï; �îìï; tîÑï; �î4ï; î ôî)õsî0ðï; �î1©ï; tî4‘ï; �sî6ï; �î7ï; tî8)ï; �î9ï; sî?öï; �î@¯ï; tîC—ï; �sîE$ï; �îF ï; tîG0ï; �sîÐï9ctîÁï9c�î$ï9cî‘qîï7±îîîîaî3î"î$cî'ï î/î58î;~î>î?âîBóîáï6 îãî¦îÍîÀî"oî$î'òî+ëî2Eî4Úî6ªî9ºî;_î@aîD½îáï4cîîîîÃîœ�îÑî! î$vî'ˆî,î-«î/÷î4Kuîýï2±tîï2±�sîÿï2±�î¦ï2±tî‹ï2±�îîï2±î[qîï0ÿîÎîÉîVî”îàîë î&“uîýï/N tîÝï/N�sîÚï/N�î‚ï/Ntîgï/N�îÊï/Nî7qîï-œî~îÑ�îÅîÀîØ�î!½uîýï*9tî}ï*9�sîzï*9�î"ï*9tîï*9�îjï*9î×sîï*9�îïï*9tîï*9�îoï*9sî$zï*9�î$äï*9tî&…ï*9�î&èï*9�qîï(ˆîîkîPîôîî!&uîýï&Ötîoï&Ö�sîlï&Ö�îï&Ötîùï&Ö�î\ï&ÖîÉî î!qîï%%î„îŒ�îØîžîñîÂî$Êî-5î0ªî5»î;Vî<¬ îFVîáï#}�îÆîfîŽîø�î!îÇîuîýï!Ìtîï!Ì�sîÿï!Ì�î¸ï!Ìtîï!Ì�uîýï tîÞï �sîÛï �îƒï tîhï �îËï î7îp î!nsî%ï �î%ëï tî+ ï �î+lï î3|qîïiî¬îøîUî]�î‡î!-�î""î%?î(î6î8(�î: î>î@©îE@îFðîáïÁîyîžîõîèîî î!yuîýï^tî‚ï^�sî€ï^�î(ï^tî ï^�îpï^îÜî î"¬sî& ï^�î&Þï^tî+ûï^�î,^ï^ î3ZqîïîîkîÉîÑ�îûî ¡�î!•î$²î'„î6¨î8?�î:$î>î?ÕîBûîDQîFDîáïîêuîýïT tî—ïT�sî•ïT�î<ïTtî!ïT�î…ïTîñsî 5ïT�î! ïTtî&&ïT�î&‰ïTî.ûqîï¢îîkîtîîm�îaî!]î&‚î)erî+ï¢�î+ûï¢qî-£ï¢�î.ï¢�î.ù�î/îî1Yuîýïñtîfïñ�sîcïñ�îïñtîðïñ�îSïñîÀî!ù î)sî,îïñ�î-Âïñtî2ßïñ�î3Bïñ î:iqîï?îîkîtîîm�îaî!]î#©î(Îî+Yî/Íî3¹î6Ù î=örî?¯ï?�î@Œï?qîB4ï?�îB—ï?�îCŠîE}îáï ˜îêuîýïætî3ïæ�sî0ïæ�îØïæ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/p<Cedar>Top>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.2���qîáïb&î¥ î0î,Ñî5Nî8¢î;sî=�î>NîDwîáï`îoîî_î›î î!ò�rî#×ï`�î$³ï`qî%òï`�î'Sï`î*Üî1î3¨î8Òî=Ôuîýï]*tî„ï]*�sî‚ï]*�î)ï]*tîï]*�îqï]*îÞî#sî,ï]*�î,ªï]*tî/ï]*�î/òï]*sî3œï]*�î4pï]*tî9ï]*�sî9ðï]*tî?ï]*�î?óï]*qîï[î¤îËîÓ�îîÅîî¼î!b î'Éî+Qî-+î/·î3™î9îC„îáïYØîc îfrîþïYØ�î·ïYØqî"ŠïYØ�î#;ïYØ�î$Cî'Åî)Àî-Mî0tî3 îïX-îÒîý î�î!ðî%î(5î0wî2î4hî7»î:î;åîáïV†îÞîJ î%!î&Æî,#î.±î1Gî3: î=>î?]îB"îDnîáïTÞî»î_îiîÄî Þî"ƒî.lî0Šî3Oî5›î:î=ëî?¤îGæîáïS7î-îîÈî î"Öî%Çî'– î.kî0î3¿î5bî7ûuîýïOâ tîïOâ�sî ïOâ�î´ïOâtî™ïOâ�îüïOâîirîïN7qîïN7�îïN7îÿîUî ¡î&”î)Bî0Õî3!î6uî7àî:DîBkîEÒîáïLî$î¨î îúî!Éî$Úî'î*±î1 î2Äî7uîýïJåtî®ïJå�sî¬ïJå�îeïJåtî½ïJå�uîýïI;tî¡ïI;�sîŸïI;�îGïI;tî,ïI;�îïI;îûsî?ïI;�îïI;tî"0ïI;�î"”ïI;î(½qîïGîîkî·î‘î4î€î$sî'"î.µî1î51î8˜î:rî?µîB8îáïEésîýïD>tî…ïD>�pî ìï?DîWî&wî ìï;î ÙîÝî§î€qî ìï7Éî#îîìî(î)¼î-ãî0.î5¸îFëî ìï6"î îî&î'Žî* î,õî/& î8ˆî;4î>3î@ó î ìï4{î ¡îÈîmîÀ îXî €î"[wî ìï0Tîqî ìï-îæîîøî†î@îãîŽî 1î%rî(�î+ºî/î2ñ î8Òî:äîAŸîDLî ìï+Zrî ¹ï+Z�î„ï+Zî`qî<ï+Z�îŸï+Zî!îÅîV î&üî)÷�î+,î3=î9iî=J�î>~î ìï(Ü�î~ îîhîGîÛî!üî#±î)&î+Âî/^î1 î3Vî7¯î;¡î=xîCï(Ü�îCeï(Üqî ìï'4î îÜîÍî§î&îî!Vî#/î(È�î*1î,ðî.Èî0ïî4,î6’î8kî>îBîC¥xî ìï%qî�ï%�îçï%îòîtî(îÃî î$›î'‚î*9î,Wî.™î2>î3Ù î:¸î=Fî>¨î@CîCåîFëî ìï#æî ]îŽî5îëî”îî2�îLî ¼î#gî%?î(,î,î0kî6î9 î>ßîA î ìï">î‰î ÎîÕîqîTî˜î"Êî$fî*?î,û î3“î4÷î6”î=�î>E îF½î ìï —îaîïîîå�î#î1îÆîfî!(�rî"gï —�î#1ï —î%qî'™ï —�î(Iï —�î)[�rî*™ï —�î+dï —qî-¼ï —�î.Ãï —î0†î2kî5Dî<9î?îCmî ìïïî‘�îÆîõ îuîà î!Ìî#pî%@î'3î*<î.4î/Úî2&î ìïqî Éî0îî—îdîAîîî!‹î#+�î$[î'©î*ïî.î0Wî3¼î7sî9tî<î>• îDçîF†î ìïÊî ®îEîÚ î®îSîŸî ìïLîÒ�î" î½î!îËî%î(î+î-wî0Wî2rî4¾ïL�î5‰ïLî7|qî:nïL�î;ïLîD.îG#î ìï¤îÄî|î©îtîÕ î!ûî#î%þî(Öî*Ž�î+× î3î4Œî7²î<œî?»îBhîH#î ìïýî² î˜îi î!Pî#çî(Zî+@ î1zî3( î9õî<ÎîAWîCiîGCî ìïVîÅwî ìï/ qî ìïÜî ƒî/ îüî«î î&.î)Uî.î4Ùî7f î>rîB`îGêî ìï 5îcî¶xî›ï 5�vî)Èïö�ÿ������� á��������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.3���wî ìïaíî?qî ìï^Ÿî‰î4îÔîîî}î!sî&Ðî(|î+î-¹î3ìî7ëî:ÂîA#îB–îD¼î ìï\÷îîîwî Àî$jî)�î*¤ð!î?‡îCxîFDï\÷�pî ìïXîëxî ìïSßîîîÙîàî¥î «î'7qî ìïQdî î~xî ìïNéî¾î¹îî…î×îî"Zî&rî ìïLnqîUïLn�î¹ïLnîYî:xî ìïIóî¾î¹îî…î Xî"•î%Ûî)šqî ìïGx îkîFîÑî% î$àî-Jî.¶î0©î6…î:qî=mîB~vî)Èï�ÿ�������Õ��������TVm$�Ê������������������������������������������������������������������������������������������������������������������������������������������������������ÿ TIMESROMAN�����������þŸ����ÿ TIMESROMAN����������þY����ÿ HELVETICA������������þŸ����ÿ TIMESROMAN����������þŸ����ÿLAUREL���������������þŸ����ÿ TIMESROMAN�����������þæ����ÿ TIMESROMAN����������þæ����ÿ TIMESROMAN����������þŸ�����ÿ TIMESROMAN����������þ��������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������� �*��� � �G�����J�����������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������j/������š“ô��ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿOrderedSymbolTableRef.mesa���������������������������������������������������������17-Nov-82 10:56:52���������������������������������������������������������������������������������������������������������������������������������������������������������