RefStackImpl:
CEDAR
PROGRAM
EXPORTS RefStack = BEGIN OPEN RefStack;
RStackUnderflow: PUBLIC ERROR = CODE;
RStackRangeFault: PUBLIC ERROR = CODE;
Ref: TYPE = REF Rep;
Rep: PUBLIC TYPE = REF RepRec;
RepRec: TYPE = RECORD[top: NAT ← 0, items: SEQUENCE order: SeqIndex OF REF];
SeqIndex: TYPE = [0..LAST[INTEGER]]; --NB: SeqIndex starts at 0--
Create:
PUBLIC
PROC [hint: Index ← SizeHint]
RETURNS [Ref]={
RETURN [NEW[Rep ← NEW[RepRec[hint]]]]};--Create--
Push:
PUBLIC
PROC[rStack: Ref, item:
REF]={
IF rStack.top = rStack.order
THEN {
oldStack: Rep ← rStack^;
rStack^ ← NEW[RepRec[2*oldStack.order]];
rStack.top ← oldStack.top;
FOR i: SeqIndex
IN [0..oldStack.top)
DO
rStack[i] ← oldStack[i]
ENDLOOP;};
rStack[rStack.top] ← item;
rStack.top ← rStack.top.SUCC;};--Push--
Pop1:
PUBLIC
PROC[rStack: Ref]
RETURNS [item:
REF]={
IF rStack.top = 0 THEN ERROR RStackUnderflow;
item ← rStack[rStack.top ← rStack.top.PRED];
};--Pop1--
Pop:
PUBLIC
PROC[rStack: Ref, n:
NAT, p: EachItemAction]={
THROUGH [0..n)
DO
IF p[Pop1[rStack]] THEN EXIT
ENDLOOP;};--Pop--
Copy:
PUBLIC
PROC[rStack: Ref, after:
NAT]
RETURNS [items:
LIST
OF
REF ←
NIL] ={
FOR i: SeqIndex DECREASING IN [after..rStack.top) DO items ← CONS[rStack[i], items] ENDLOOP
}; --Copy--
Items:
PUBLIC
PROC[rStack: Ref, p: EachItemAction, topDown:
BOOL] ={
i: SeqIndex;
IF topDown
THEN FOR i DECREASING IN [0..rStack.top) DO IF p[rStack[i]] THEN EXIT ENDLOOP
ELSE FOR i IN [0..rStack.top) DO IF p[rStack[i]] THEN EXIT ENDLOOP}; --Items--
ItemAt:
PUBLIC
PROC[rStack: Ref, index: Index]
RETURNS [
REF] ={
IF index IN [1..rStack.top] THEN NULL ELSE ERROR RStackRangeFault;
RETURN [rStack[index.PRED]]}; --ItemAt--
Size: PUBLIC PROC[rStack: Ref] RETURNS [NAT] = {RETURN [rStack.top]}; --Size--
Reset: PUBLIC PROC[rStack: Ref] = {rStack.top ← 0}; --Reset--
Empty: PUBLIC PROC[rStack: Ref] RETURNS [BOOL] = {RETURN [rStack.top = 0]}; --Empty--
END.