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;
--For statistic gathering
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
--! Raise OutOfRange[at]
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.