IPStackImpl.mesa
Last edited by:
Doug Wyatt, July 7, 1983 11:49 am
DIRECTORY
IPBasic USING [Any, Identifier, Integer, Marker, nullMarker, Number, Operator, Vector],
IPConvert USING [AnyToIdentifier, AnyToInteger, AnyToNumber, AnyToOperator, AnyToReal, AnyToVector, IdentifierToAny, NumberToInteger, NumberToReal, OperatorToAny, VectorToAny],
IPErrors USING [Bug, MasterError],
IPStack USING [],
IPState USING [MarkItem, MarkItemRep, Stack, StackRep, State, StateRep];
IPStackImpl:
CEDAR
PROGRAM
IMPORTS IPConvert, IPErrors
EXPORTS IPStack, IPBasic
= BEGIN OPEN IPState, IPBasic;
State: TYPE = IPState.State;
StateRep: PUBLIC TYPE = IPState.StateRep; -- export to IPBasic
maxStackSize: NAT = (LAST[NAT]-SIZE[StackRep[0]])/SIZE[Any];
Init:
PUBLIC
PROC[self: State, max: Integer] = {
IF max>maxStackSize THEN ERROR IPErrors.MasterError[LimitExceeded]
ELSE self.stack ← NEW[StackRep[max] ← [mark: NIL, bot: 0, top: 0, elements: ]];
};
Push:
PROC[self: State, x: Any] =
INLINE {
stack: Stack = self.stack;
i: NAT = stack.top;
IF i<stack.max
THEN {
stack[i].type ← x.type; TRUSTED {stack[i].number ← x.number};
IF x.ref#NIL THEN stack[i].ref ← x.ref;
stack.top ← i+1 }
ELSE ERROR IPErrors.MasterError[StackOverflow];
};
Pop:
PROC[self: State]
RETURNS[x: Any] =
INLINE {
stack: Stack = self.stack;
top: NAT = stack.top;
IF top>stack.bot
THEN { i:
NAT = top-1; x: Any = stack[i];
stack.top ← i; IF x.ref#NIL THEN stack[i].ref ← NIL; RETURN[x] }
ELSE ERROR IPErrors.MasterError[StackUnderflow];
};
InlineAnyToNumber:
PROC[x: Any]
RETURNS[Number] =
INLINE {
RETURN[
IF x.type=number
THEN x.number
ELSE IPConvert.AnyToNumber[x]]
};
InlineAnyToReal:
PROC[x: Any]
RETURNS[
REAL] =
INLINE {
RETURN[
IF x.type=number
THEN IPConvert.NumberToReal[x.number]
ELSE IPConvert.AnyToReal[x]]
};
InlineAnyToInteger:
PROC[x: Any]
RETURNS[Integer] =
INLINE {
RETURN[
IF x.type=number
THEN IPConvert.NumberToInteger[x.number]
ELSE IPConvert.AnyToInteger[x]]
};
InlineNumberToAny:
PROC[x: Number]
RETURNS[Any] =
INLINE {
RETURN[[type: number, number: x]];
};
InlineRealToAny:
PROC[x:
REAL]
RETURNS[Any] =
INLINE {
RETURN[[type: number, number: [real[x]]]];
};
InlineIntegerToAny:
PROC[x: Integer]
RETURNS[Any] =
INLINE {
RETURN[[type: number, number: [int[x]]]];
};
PushAny:
PUBLIC
PROC[self: State, x: Any] = {
Push[self, x]
};
PushBool:
PUBLIC
PROC[self: State, x:
BOOL] = {
Push[self, InlineIntegerToAny[IF x THEN 1 ELSE 0]]
};
PushInteger:
PUBLIC
PROC[self: State, x: Integer] = {
Push[self, InlineIntegerToAny[x]]
};
PushReal:
PUBLIC
PROC[self: State, x:
REAL] = {
Push[self, InlineRealToAny[x]]
};
PushNumber:
PUBLIC
PROC[self: State, x: Number] = {
Push[self, InlineNumberToAny[x]]
};
PushIdentifier:
PUBLIC
PROC[self: State, x: Identifier] = {
Push[self, IPConvert.IdentifierToAny[x]]
};
PushVector:
PUBLIC
PROC[self: State, x: Vector] = {
Push[self, IPConvert.VectorToAny[x]]
};
PushOperator:
PUBLIC
PROC[self: State, x: Operator] = {
Push[self, IPConvert.OperatorToAny[x]]
};
PopAny:
PUBLIC
PROC[self: State]
RETURNS[Any] = {
RETURN[Pop[self]];
};
PopBool:
PUBLIC
PROC[self: State]
RETURNS[
BOOL] = {
RETURN[IF InlineAnyToInteger[Pop[self]]=0 THEN FALSE ELSE TRUE];
};
PopInteger:
PUBLIC
PROC[self: State]
RETURNS[Integer] = {
RETURN[InlineAnyToInteger[Pop[self]]];
};
PopReal:
PUBLIC
PROC[self: State]
RETURNS[
REAL] = {
RETURN[InlineAnyToReal[Pop[self]]];
};
PopNumber:
PUBLIC
PROC[self: State]
RETURNS[Number] = {
RETURN[InlineAnyToNumber[Pop[self]]];
};
PopIdentifier:
PUBLIC
PROC[self: State]
RETURNS[Identifier] = {
RETURN[IPConvert.AnyToIdentifier[Pop[self]]];
};
PopVector:
PUBLIC
PROC[self: State]
RETURNS[Vector] = {
RETURN[IPConvert.AnyToVector[Pop[self]]];
};
PopOperator:
PUBLIC
PROC[self: State]
RETURNS[Operator] = {
RETURN[IPConvert.AnyToOperator[Pop[self]]];
};
Copy:
PUBLIC
PROC[self: State, n: Integer] = {
Copy the top n entries on the stack.
stack: Stack = self.stack;
top: NAT = stack.top;
IF (top-stack.bot)<n THEN ERROR IPErrors.MasterError[StackUnderflow]
ELSE IF (stack.max-top)<n THEN ERROR IPErrors.MasterError[StackOverflow]
ELSE {
count: NAT = n;
newTop: NAT = top+count;
FOR i: NAT IN[top..newTop) DO stack[i] ← stack[i-count] ENDLOOP;
stack.top ← newTop;
};
};
Roll:
PUBLIC
PROC[self: State, depth, moveFirst: Integer] = {
Roll the top depth stack elements as a circular queue, where moveFirst<=depth, the first (i.e., bottommost) moveFirst of the depth argument values are the last (i.e., topmost) moveFirst of the depth result values, and order is otherwise preserved.
stack: Stack = self.stack;
IF moveFirst>depth THEN ERROR IPErrors.MasterError[InvalidArgs]
ELSE IF depth>(stack.top-stack.bot) THEN ERROR IPErrors.MasterError[StackUnderflow]
ELSE {
k: NAT = moveFirst;
n: NAT = depth;
top: NAT = stack.top;
bot: NAT = top-n; -- [bot..top) is the part to be rolled
count: NAT ← 0;
IF k=0 OR k=n THEN RETURN;
FOR f:
NAT ← bot, f+1
DO
-- for each cycle of the permutation
x: Any = stack[f]; -- first element of cycle
i: NAT ← f;
next:
PROC[t:
NAT]
RETURNS[
NAT] =
INLINE {
RETURN[
IF t<(top-k) THEN t+k ELSE t-(n-k)] }; -- index of next element in the cycle
FOR j:
NAT ← next[i], next[j]
DO
count ← count+1;
IF j=f THEN { stack[i] ← x; EXIT }
ELSE { stack[i] ← stack[j]; i ← j };
ENDLOOP;
IF count=n THEN EXIT;
ENDLOOP;
};
};
CurrentMark:
PROC[self: State]
RETURNS[Marker] =
INLINE {
RETURN[IF self.context=NIL THEN nullMarker ELSE self.context.mark] };
Mark:
PUBLIC
PROC[self: State, n: Integer] = {
Place a mark n elements down in the stack.
stack: Stack = self.stack;
marker: Marker = CurrentMark[self];
IF n>(stack.top-stack.bot) THEN ERROR IPErrors.MasterError[StackUnderflow]
ELSE {
mark: MarkItem = NEW[MarkItemRep ← [next: stack.mark, marker: marker, bot: stack.bot]];
stack.mark ← mark; stack.bot ← stack.top-n;
};
};
Unmark:
PUBLIC
PROC[self: State, n: Integer] = {
Remove a mark n elements down in the stack.
stack: Stack = self.stack;
marker: Marker = CurrentMark[self];
IF n>(stack.top-stack.bot) THEN ERROR IPErrors.MasterError[StackUnderflow]
ELSE IF n<(stack.top-stack.bot) THEN ERROR IPErrors.MasterError[WrongType]
ELSE {
mark: MarkItem = stack.mark;
IF mark=NIL THEN ERROR IPErrors.Bug
ELSE IF mark.marker#marker THEN ERROR IPErrors.MasterError[MarkMismatch]
ELSE { stack.bot ← mark.bot; stack.mark ← mark.next };
};
};
TopMark:
PROC[stack: Stack]
RETURNS[Marker] =
INLINE {
Return the value of the topmost mark.
mark: MarkItem = stack.mark;
RETURN[IF mark=NIL THEN nullMarker ELSE mark.marker]
};
Count:
PUBLIC
PROC[self: State]
RETURNS[Integer] = {
Count the stack elements above the top mark.
stack: Stack = self.stack;
marker: Marker = CurrentMark[self];
IF TopMark[stack]=marker THEN RETURN[stack.top-stack.bot]
ELSE ERROR IPErrors.MasterError[MarkMismatch];
};
PopToMark:
PUBLIC
PROC[self: State]
RETURNS[Marker] = {
stack: Stack = self.stack;
WHILE stack.top>stack.bot DO [] ← PopAny[self] ENDLOOP;
RETURN[TopMark[stack]];
};
PopMark:
PUBLIC
PROC[self: State] = {
stack: Stack = self.stack;
IF stack.top#stack.bot THEN ERROR IPErrors.Bug
ELSE {
mark: MarkItem = stack.mark;
IF mark#NIL THEN { stack.bot ← mark.bot; stack.mark ← mark.next };
};
};
END.