DIRECTORY OrderedRefArray; OrderedRefArrayImpl: CEDAR PROGRAM EXPORTS OrderedRefArray = BEGIN OPEN OrderedRefArray; OutOfRange: PUBLIC ERROR[index: Index] = CODE; PruneMethod: PUBLIC PruneMethodTypes _ lastValueIfFilled; --The initial value Ref: TYPE = REF Rep; Rep: PUBLIC TYPE = RECORD[ maxSize: Index, size: NAT _ 0, itemsHd, itemsTl: LIST OF Item _ NIL, insertCnt: INT _ 0 --For statistics gathering ]; Item: TYPE = REF ItemRec; ItemRec: TYPE = RECORD[item: REF, value: INT]; Create: PUBLIC PROC [maxSize: Index] RETURNS [Ref] ={ RETURN [NEW[Rep _ [maxSize]]] }; --Create Copy: PUBLIC PROC[oArray: Ref] RETURNS [nArray: Ref] ={ IF oArray.itemsHd = NIL THEN RETURN [NEW[Rep _ [oArray.maxSize, oArray.size]]] ELSE {itemsHd, itemsTl: LIST OF Item; itemsHd _ itemsTl _ CONS[NIL, NIL]; FOR l: LIST OF Item _ oArray.itemsHd, l.rest UNTIL l = NIL DO itemsTl _ LIST[l.first]; itemsTl _ itemsTl.rest; ENDLOOP; itemsHd _ itemsHd.rest; RETURN [NEW[Rep _ [oArray.maxSize, oArray.size, itemsHd, itemsTl]]]} }; --Copy Size: PUBLIC PROC [oArray: Ref] RETURNS [NAT] ={ RETURN [oArray.size]};--Size MaxSize: PUBLIC PROC[oArray: Ref] RETURNS [Index] ={RETURN [oArray.maxSize]}; --MaxSize Insert: PUBLIC PROC[oArray: Ref, item: REF, value: INT] ={ remLast: BOOL _ (oArray.size = oArray.maxSize); IF oArray.insertCnt = LAST[INT] THEN oArray.insertCnt _ FIRST[INT] --wrap around ELSE oArray.insertCnt _ oArray.insertCnt.SUCC; IF oArray.itemsHd = NIL THEN { oArray.size _ 1; oArray.itemsHd _ oArray.itemsTl_ LIST[NEW[ItemRec _ [item, value]]]} ELSE { IF value <= oArray.itemsHd.first.value THEN {oArray.itemsHd _ CONS[NEW[ItemRec _ [item, value]], oArray.itemsHd]; GOTO fini}; IF value > oArray.itemsTl.first.value THEN { IF remLast THEN RETURN ELSE {oArray.itemsTl.rest _ LIST[NEW[ItemRec _ [item, value]]]; oArray.itemsTl _ oArray.itemsTl.rest; GOTO fini}}; FOR l: LIST OF Item _ oArray.itemsHd, l.rest DO IF value <= l.rest.first.value THEN {l.rest _ CONS[NEW[ItemRec _ [item, value]], l.rest]; GOTO fini} ENDLOOP; EXITS fini => IF remLast THEN {FOR l: LIST OF Item _ oArray.itemsHd, l.rest DO IF l.rest.rest = NIL THEN {oArray.itemsTl _ l; l.rest _ NIL; EXIT} ENDLOOP} ELSE oArray.size _ oArray.size.SUCC; }; --endIF };--Insert InsertCheck: PUBLIC PROC[oArray: Ref, item: REF, value: INT] RETURNS [BOOL] ={ IF oArray.size < oArray.maxSize THEN RETURN [TRUE] ELSE RETURN [value <= oArray.itemsTl.first.value]; }; --InsertCheck Enumerate: PUBLIC PROC[oArray: Ref, action: EachItemAction, increasing: BOOL _ TRUE] ={ items: LIST OF Item; index: NAT; indexIncr: INT; IF increasing THEN { items _ oArray.itemsHd; index _ 1; indexIncr _ 1;} ELSE { items _ Reverse[oArray.itemsHd]; index _ oArray.size; indexIncr _ -1;}; WHILE items # NIL DO IF action[index, items.first.item, items.first.value] THEN EXIT; items _ items.rest; index _ index + indexIncr; ENDLOOP; };--Enumerate Fetch: PUBLIC PROC[oArray: Ref, at: Index] RETURNS [item: REF, value: INT] ={ IF at > oArray.size THEN ERROR OutOfRange[at] ELSE [item, value] _ NthElement[oArray.itemsHd, at]^; };--Fetch NthElement: PROC[list: LIST OF Item, n: Index] RETURNS[Item] = { UNTIL n = 1 DO list _ list.rest; n _ n.PRED; ENDLOOP; RETURN [list.first]; }; -- of NthElement GetPruneValue: PUBLIC PROC[oArray: Ref] RETURNS [INT] = { SELECT PruneMethod FROM firstValue => IF oArray.size > 0 THEN RETURN [oArray.itemsHd.first.value]; lastValue => IF oArray.size > 0 THEN RETURN [oArray.itemsTl.first.value]; firstValueIfFilled => IF oArray.size = oArray.maxSize THEN RETURN [oArray.itemsHd.first.value]; lastValueIfFilled => IF oArray.size = oArray.maxSize THEN RETURN [oArray.itemsTl.first.value]; ENDCASE => ERROR; RETURN [LAST[INT]]; }; --GetPruneValue GetInsertionCount: PUBLIC PROC[oArray: Ref] RETURNS [INT] ={ RETURN [oArray.insertCnt]}; -- GetInsertionCount Reverse: PROC [list: LIST OF Item] RETURNS[val: LIST OF Item] = { val _ NIL; UNTIL list = NIL DO val _ CONS[list.first, val]; list _ list.rest; ENDLOOP; RETURN[val]; }; -- of Reverse END. Ф--File: OrderedRefArrayImpl.mesa Last Edited by: CSChow, January 28, 1985 2:34:40 am PST --For statistic gathering --! Raise OutOfRange[at] Э╩╛ШJЩ JЩ7JШЪ╧k Ш JШЧJШЪЬЭЬЭШ"JЪЭЬЭЬЭЬШ5JШJШJЪЬЭЬЭЬЭЬШ.JШJЪЬ ЭЬ'╧cШMJШJЪЬЭЬЭЬШЪЬЭЬЭЬЭЬШJЪЬШJЪЬЭЬШJЪЬЭЬЭЬЭШ%JЪЬЭЬЮШ-JЪЬШЧJШJЪЬЭЬЭЬ ШJЪ Ь ЭЬЭЬЭЬ ЭЬШ.JЩcodeЪ╧nЬЭЬЭЬЭЬ Ш5KЪЭЬЭЬШKЪЬЮШЧKШЪЯЬЭЬЭЬЭЬШ7ЪЭЬЭЬШKЪЭЬЭЬЭЬ&Ш6ЪЭЬЭЬЭЬШ&KЪЬЭЬЭЬЭЬШ#Ъ ЭЬЭЬЭЬЭЬЭШ=KЪЬ ЭЬ ШKЪЬШKЪЭШЧKЪЬШKЪЭЬЭЬ9ШDЧЧKЪЬЮШ ЧKШЪ ЯЬЭЬЭЬЭЬЭЬШ0KЪЭЬЮШЧKШKЪЯЬЭЬЭЬЭЬЭЬЮ ШWKШЪ ЯЬЭЬЭЬЭЬ ЭЬШ:KЪЬ ЭЬ"Ш/ЪЭЬЭЬЭЬШ KЪЭЬЭЬЭЬЮ Ш0KЪЭЬ%ЭЬШ.KЩЧЪЭЬЭЬШЪЭЬШKЪЬШKЪЬ!ЭЬЭЬШDЧЪЭЬШЪЭЬ&Ш(KЪЭЬЭЬЭЬ,ЭЬШVЧЪЭЬ$ЭЬШ,KЪЭЬ ЭЬЭЬЭЬЭЬЭЬBЭЬШЙKШЧЪЭЬЭЬЭЬЭШ/ЪЭЬШKЪЭЬЭЬЭЬ$ЭЬШEЧKЪЭЬШЧKШЪЭШЪЬЭЬ ЭЬШЪЬЭЬЭЬЭЬЭШ0KЪ ЭЬЭЬЭЬЭЬЭЬШBKЪЭЬШЧKЪЭЬЭЬШ$ЧЧKЪЬЮШ KШKШЧЧKЪЬЮШ ЧKШЪЯЬЭЬЭЬЭЬ ЭЬЭЬЭЬШNЪЭЬШ KЪЭЬЭЬЭЬШKЪЭЬЭЬ(Ш3ЧKЪЬЮ ШЧKШЪ Я ЬЭЬЭЬ2ЭЬЭЬШWKЪЬЭЬЭЬШKЪЬЭЬШKЪЬЭЬШЪЭЬШЪЭЬШKЪЬШKЪЬ Ш KЪЬШЧЪЭЬШKЪЬ Ш KЪЬШKЪЬШЧЧЪЭЬ ЭЬЭШKЪЭЬ4ЭЬЭЬШ@KЪЬШKЪЬШKЪЭЬШЧKЪЬЮШ ЧKШЪЯЬЭЬЭЬЭЬЭЬ ЭЬШMЪЭЬШKЪЭЬЭЬШKЪЭЬ1Ш5ЧKЪЬЮШ KЪЬЩЧKШЪ Я ЬЭЬЭЬЭЬЭЬШAЪЭЬЭШKШKЪЬЭЬШKЪЭЬШЧKЪЭЬШJЪЬЮШЧJШЪ Я ЬЭЬЭЬЭЬЭЬШ9ЪЭЬ ЭШKЪЬЭЬЭЬЭЬШJKЪЬ ЭЬЭЬЭЬШIKЪЬЭЬЭЬЭЬШ_KЪЬЭЬЭЬЭЬШ^KЪЭЬЭЬШЧKЪЭЬЭЬЭЬШKЪЬЮШЧKШЪ ЯЬЭЬЭЬЭЬЭЬШ