
<<--File: RefStackImpl.mesa>>
<<Last Edited by: CSChow, February 1, 1985 0:06:52 am PST>>

DIRECTORY
RefStack;

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.