A hagyományos értelemben vett verem speciális célorientált kiterjesztésekkel
és potenciálisan végtelen hosszal. A modul generikus, azaz a verem elemeinek
megszorítás nélküli típusa paraméterként szerepel.
Az elemeket kötegeljük, s az egyes kötegeket (oldalakat) ábrázoljuk
egy láncolt verem-struktúrában. A kötegek tárolását a Page Stack modul
végzi, s itt "csak" az elemek kötegeken belüli kezelése valósul meg. A
kötegelésnek tisztán hatékonysági célja van! A kötegek mérete ugyancsak
generikus paraméter.
Újdonság a virtuális verem-műveletek halmaza,
és az aktuális veremmutatók eltárolásának lehetősége.
A virtuális műveletek egy nem üres vermen
alkalmazhatók. A VReset függvény hívásával kell a virtuális műveletek végrehajtását
elkezdeni. A virtuális pop a verem tetején levő
elemet leveszi (és visszaszolgáltatja), s onnan virtuálisan törli, de fizikailag
nem. Ezzel a verem egy olyan virtuális állapotba kerül, melynek hossza
egyel kisebb a valódi hosszánál (illetve annyival, ahány virtuális Pop
műveletet csináltunk...) és elemei a tényleges verem elemeinek kezdőszeletét
képezi. A VEmtpy az üres virtuális állapotba hozza a vermet. Közvetlen
ezután a VPop nem alkalmazható eredményesen, de a VPush igen. Általánosságban
a VPush használatával a virtuális verem mérete növelhető
meg egy, a veremben ténylegesen létező, s a virtuális verem vége utáni
pozícióban levő elemmel, ezzel párhuzamosan visszaadja az adott elemet
a visszatérési érétkében. Tehát a VPush akkor használható, ha a
virtuális hossz kisebb a fizikai hossznál. A VTop ezek után már nyilvánvaló
hatást gyakorol a virtuális veremre: kiolvassa ugyanazt az elemet, mint
a VPop, de nem veszi ki onnan, sem fizikailag,
sem virtuálisan.
Könnyen meggondolható, hogy a valódi verem-műveleteket
kombinálva a virtuálisokkal egy kvázi-sorszerkezet is megvalósitható.
A verem állapotát egy futás közben dinamikusan
változó méretű tömbben tároljuk, veremszerű elérhetőséggel. Itt tehát valóban
kihasználjuk a CLU speciális tulajdonságát.
Ha a PushState művelet után bármikor meghívjuk
a RestoreState műveletet, az megpróbálja beállítani a legutoljára
elmentett értéket. Ez (ebben a verzióban) csak akkor lesz sikeres, ha az
óta több Push volt, mint Pop. Ekkor ugyanis mident kitöröl a tárolt határig
bezálólag a verem aktuális tetejétől kezdve.
(Ez ideális lesz a szimbólum-táblához, hisz ott nincs Pop). Végül
a VRestoreState egy virtuális RestoreState: nem törli ugyan a legutolsó
tárolt állapotot, de a virtuális állapotot erre állítja be.
Vigyázat! A modul jelen verziójában (Internal Version Number 1.30CLU) még rendkívűl sok veszélyforrást rejt magában a virtuális verem-műveletek nem kellően átgondolt használata, azonban kellő körültekintés mellett igen széles a lehetőségek skálája.
Megjegyzés: látható, hogy definiálhatjuk és használhatjuk a típus-implementációs modulokban is a standard outputot esetleges nyomkövetési információk kijelzésére. Ennek legkézenfekvőbb módja, ha "globális" változóként definiáljuk a stream-et. Erre a célra pedig nem más, mint az own kulcsszó alkalmas...
TStack=cluster [Elmt:type,PageSize:int] is
Create, Push, Pop, Top, Empty, IsEmpty,
VReset, VEmpty, VPush, VPop, VTop,
PushState, RestoreState, VRestoreState
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
Készítette Bodnát Imre.