% ----------------------------------
% Symbol Table  Scott (c) 1997-99
% Unbounded Stack  - Version 1.30CLU
% ----------------------------------

TStack=cluster [Elmt:type,PageSize:int] is
       Create, Push, Pop, Top, Empty, IsEmpty,
       VReset, VEmpty, VPush, VPop, VTop,
       PushState, RestoreState, VRestoreState

  % Functions:
  % Create..........Creates a new empty stack (without any page)
  % Push............Push. Appending new pages is included
  % Pop.............Pop. Destoying non-used pages is included
  % Top.............Top
  % Empty...........Clears the stack
  % IsEmpty.........Returns true, if the s
  % PushState.......Saves the current position of stack to an other stack
  % RestoreState....Restore last saved stack state.
  % VReset..........Initialize variables for beginning virtual operations
  %                 NOTES: You must use it at least at once before virtual
  %                 operations. After this, virtual top=real top.
  %                 Using VReset after Pop or RestoreState is strongly
  %                 recommended!
  % VPop............Virtual Pop. No page-destoying of course
  % VTop............Virtual Top
  % VIsPushedState..Return true, if current virtual state is the last
  %                 stored state

  % Exceptions:
  % ST_NullStack......Pop from a null stack
  % ST_NoMoreState....More RestoreState than PushState
  % ST_VPushOverflow..Virtual Push Overflow

  TStackState=record
    [ Element:int,
      CurrentPage:int,
      CurrentIndex:int ]

  TSymbolStack=record
    [ Element:int,              % Number of element
      DefElement:Elmt,
      Pages:TStackPage[Elmt,PageSize],
      CurrentPage:int,
      CurrentIndex:int,
      Virtual:TStackState,
      States:array[TStackState] ]

  rep=variant[Stack:TSymbolStack, Empty:null]

  % own out:stream := stream$primary_output() %for debug reasons

  % ---------------------[ Create ]----------------------------
  Create = proc (E:Elmt) returns (cvt)
           return(rep$make_Stack(TSymbolStack${
                                 Element:0,
                                 DefElement:E,
                                 Pages:TStackPage[Elmt,PageSize]$Create(),
                                 CurrentPage:-1,
                                 CurrentIndex:PageSize-1,
                                 Virtual:TStackState${Element:0,
                                                      CurrentPage:-1,
                                                      CurrentIndex:PageSize-1 },
                                 States:array[TStackState]$Create(0)}))
  end Create

   % ---------------------[ Push ]-----------------------------
   Push = proc (Stack:cvt,e:Elmt) returns (Elmt)
          St:TSymbolStack:=rep$value_Stack(Stack)
          if (St.CurrentIndex=PageSize-1) then
            % stream$puts(out,"Calling AddPage by Push...\n") %for debug
            St.Pages:=TStackPage[Elmt,PageSize]$AddPage(St.Pages)
            St.CurrentPage:=St.CurrentPage+1
            St.CurrentIndex:=0
          else
            St.CurrentIndex:=St.CurrentIndex+1
          end
          TStackPage[Elmt,PageSize]$PutIntoLast(St.Pages,St.CurrentIndex,e)
          St.Element:=St.Element+1
          return (e)
   end Push

   % ---------------------[ Pop ]------------------------
   Pop = proc (Stack:cvt) returns (Elmt) signals (ST_NullStack)
         St:TSymbolStack:=rep$value_Stack(Stack)
         ret:Elmt
         if (St.Element=0) then
           signal ST_NullStack
         end
         ret:=TStackPage[Elmt,PageSize]$GetFromLast(St.Pages,St.CurrentIndex)
         St.Element:=St.Element-1
         if (St.CurrentIndex=0) then
           St.Pages:=TStackPage[Elmt,PageSize]$DelPage(St.Pages)
           St.CurrentPage:=St.CurrentPage-1
           St.CurrentIndex:=PageSize-1
         else
           St.CurrentIndex:=St.CurrentIndex-1
         end
         return (ret)
   end Pop

   % ---------------------[ Top ]------------------------------
   Top = proc (Stack:cvt) returns (Elmt) signals (ST_NullStack)
         St:TSymbolStack:=rep$value_Stack(Stack)
         ret:Elmt
         if (St.Element=0) then
           signal ST_NullStack
         end
         ret:=TStackPage[Elmt,PageSize]$GetFromLast(St.Pages,St.CurrentIndex)
         return (ret)
    end Top

    % -----------------------[ Empty ]-------------------------
    Empty = proc (Stack:cvt)
            St:TSymbolStack:=rep$value_Stack(Stack)
            while bool$not(TStackPage[Elmt,PageSize]$IsEmpty(St.Pages)) do
              St.Pages:=TStackPage[Elmt,PageSize]$DelPage(St.Pages)
            end
            St.Element:=0
            St.Pages:=TStackPage[Elmt,PageSize]$Create()
            St.CurrentPage:=-1
            St.CurrentIndex:=PageSize-1
    end Empty

    % -----------------------[ IsEmpty ]-----------------------
    IsEmpty = proc (Stack:cvt) returns (bool)
              return (rep$value_Stack(Stack).Element=0)
    end IsEmpty

    % ----------------------[ PushState ]----------------------
    PushState = proc (Stack:cvt)
                St:TSymbolStack:=rep$value_Stack(Stack)
                State:TStackState
                State:=TStackState${Element:St.Element,
                                    CurrentPage:St.CurrentPage,
                                    CurrentIndex:St.CurrentIndex}
                Array[TStackState]$addh(St.States,State)
    end PushState

    % -------------------[ RestoreState ]----------------------
    RestoreState = proc (Stack:cvt) signals (ST_NoMoreState)
                   St:TSymbolStack:=rep$value_Stack(Stack)
                   State:TStackState
                   State:=Array[TStackState]$remh(St.States)
                   while State.CurrentPage<St.CurrentPage do
                      St.Pages:=TStackPage[Elmt,PageSize]$DelPage(St.Pages)
                      St.CurrentPage:=St.CurrentPage-1
                   end
                   St.CurrentIndex:=State.CurrentIndex
                   St.Element:=State.Element
    end RestoreState

    % -------------------[ VRestoreState ]---------------------
    VRestoreState = proc (Stack:cvt) signals (ST_NoMoreState)
                   St:TSymbolStack:=rep$value_Stack(Stack)
                   State:TStackState:=Array[TStackState]$top(St.States)
                   St.Virtual.CurrentIndex:=State.CurrentIndex
                   St.Virtual.CurrentPage:=State.CurrentPage
                   St.Virtual.Element:=State.Element
    end VRestoreState

    % ----------------------[ VReset ]-------------------------
    VReset = proc (Stack:cvt)
             St:TSymbolStack:=rep$value_Stack(Stack)
             St.Virtual.Element:=St.Element
             St.Virtual.CurrentIndex:=St.CurrentIndex
             St.Virtual.CurrentPage:=St.CurrentPage
    end VReset

    % -----------------------[ VEmpty ]------------------------
    VEmpty = proc (Stack:cvt)
             St:TSymbolStack:=rep$value_Stack(Stack)
             St.Virtual.Element:=0
             St.Virtual.CurrentPage:=-1
             St.Virtual.CurrentIndex:=PageSize-1
    end VEmpty

   % ------------------------[ VPush ]-------------------------
   VPush = proc (Stack:cvt) returns (Elmt) signals (ST_VPushOverFlow)
           St:TSymbolStack:=rep$value_Stack(Stack)
           if (St.CurrentIndex=St.Virtual.CurrentIndex) &
              (St.CurrentPage=St.Virtual.CurrentPage) then
              signal ST_VPushOverflow
           end
           if (St.Virtual.CurrentPage=-1) then           % after VEmpty !
             St.Virtual.CurrentPage:=0
             St.Virtual.CurrentIndex:=0
           else
             if (St.Virtual.CurrentIndex=PageSize-1) then
               St.Virtual.CurrentPage:=St.Virtual.CurrentPage+1
               St.Virtual.CurrentIndex:=0
             else
               St.Virtual.CurrentIndex:=St.Virtual.CurrentIndex+1
             end
           end
           St.Virtual.Element:=St.Virtual.Element+1
           return (TStackPage[Elmt,PageSize]$GetFrom(St.Pages,St.Virtual.CurrentPage,St.Virtual.CurrentIndex))
   end VPush

    % -----------------------[ VPop ]--------------------------
    VPop = proc (Stack:cvt) returns (Elmt) signals (ST_NullVStack)
           St:TSymbolStack:=rep$value_Stack(Stack)
           ret:Elmt
           if (St.Virtual.Element=0) then
             signal ST_NullVStack
           end
           ret:=TStackPage[Elmt,PageSize]$GetFrom(St.Pages,St.Virtual.CurrentPage,St.Virtual.CurrentIndex)
           St.Virtual.Element:=St.Virtual.Element-1
           if (St.Virtual.CurrentIndex=0) then
             St.Virtual.CurrentPage:=St.Virtual.CurrentPage-1
             St.Virtual.CurrentIndex:=PageSize-1
           else
             St.Virtual.CurrentIndex:=St.Virtual.CurrentIndex-1
           end
           return (ret)
      end VPop

    % -----------------------[ VTop ]--------------------------
    VTop = proc (Stack:cvt) returns (Elmt) signals (ST_NullVStack)
           St:TSymbolStack:=rep$value_Stack(Stack)
           ret:Elmt
           if (St.Virtual.Element=0) then
             signal ST_NullVStack
           end
           ret:=TStackPage[Elmt,PageSize]$GetFrom(St.Pages,St.Virtual.CurrentPage,St.Virtual.CurrentIndex)
           return (ret)
    end VTop

end TStack