PFDS Chapter #08 Examples in Oz
% Utility functions for tests
proc {QueueTest F}
A = F.empty
B = {F.snoc A 1}
C = {F.snoc B 2}
D = {F.snoc C 3}
in
{Browse D}
{Browse {F.head D}}
{Browse {F.head {F.tail D}}}
{Browse {F.head {F.tail {F.tail D}}}}
end
proc {DequeTest F}
A = F.empty
B = {F.cons 2 A}
C = {F.snoc B 1}
D = {F.cons 3 C}
in
{Browse D}
{Browse {F.head D}}
{Browse {F.head {F.tail D}}}
{Browse {F.head {F.tail {F.tail D}}}}
{Browse {F.last D}}
{Browse {F.last {F.init D}}}
{Browse {F.last {F.init {F.init D}}}}
end
% 8.2 HoodMelvilleQueue
HOODMELVILLEQUEUE =
functor
export
empty : Empty
isEmpty : IsEmpty
snoc : Snoc
head : Head
tail : Tail
define
Empty = 0#nil#idle#0#nil
fun {IsEmpty Q=LenF#F#State#LenR#R}
LenF == 0
end
fun {Exec State}
case State
of reversing(Ok X|F Fp Y|R Rp) then reversing(Ok+1 F X|Fp R Y|Rp)
[] reversing(Ok nil Fp [Y] Rp) then appending(Ok Fp Y|Rp)
[] appending(0 Fp Rp) then done(Rp)
[] appending(Ok X|Fp Rp) then appending(Ok-1 Fp X|Rp)
else State
end
end
fun {Invalidate State}
case State
of reversing(Ok F Fp R Rp) then reversing(Ok-1 F Fp R Rp)
[] appending(0 Fp X|Rp) then done(Rp)
[] appending(Ok Fp Rp) then appending(Ok-1 Fp Rp)
else State
end
end
fun {Exec2 Q=LenF#F#State#LenR#R}
case {Exec {Exec State}}
of done(NewF) then LenF#NewF#idle#LenR#R
[] NewState then LenF#F#NewState#LenR#R
end
end
fun {Check Q=LenF#F#State#LenR#R}
if LenR =< LenF then
{Exec2 Q}
else
local
NewState = reversing(0 F nil R nil)
in
{Exec2 (LenF+LenR)#F#NewState#0#nil}
end
end
end
fun {Snoc Q=LenF#F#State#LenR#R X}
{Check LenF#F#State#(LenR+1)#(X|R)}
end
fun {Head Q=LenF#F#State#LenR#R}
case F
of H|T then H
else raise empty end
end
end
fun {Tail Q=LenF#F#State#LenR#R}
case F
of H|T then {Check (LenF-1)#T#{Invalidate State}#LenR#R}
else raise empty end
end
end
end
[HoodMelvilleQueue] = {Module.apply [HOODMELVILLEQUEUE]}
{QueueTest HoodMelvilleQueue}
% 8.4 BankersDeque
BANKERSDEQUE =
functor
export
initialize : Initialize
empty : Empty
isEmpty : IsEmpty
cons : Cons
head : Head
tail : Tail
snoc : Snoc
last : Last
init : Init
define
C
proc {Initialize Cx} C = Cx end
Empty = 0#nil#0#nil
fun {IsEmpty Q=LenF#F#LenR#R}
LenF+LenR == 0
end
fun {Check Q=LenF#F#LenR#R}
if LenF > C*LenR+1 then
local
I = (LenF+LenR) div 2
J = LenF + LenR - I
Fp = {List.take F I}
Rp = {Append R {Reverse {List.drop F I}}}
in
I#Fp#J#Rp
end
elseif LenR > C*LenF + 1 then
local
J = (LenF+LenR) div 2
I = LenF + LenR - J
Rp = {List.take R J}
Fp = {Append F {Reverse {List.drop R J}}}
in
I#Fp#J#Rp
end
else
Q
end
end
fun {Cons X Q=LenF#F#LenR#R}
{Check (LenF+1)#(X|F)#LenR#R}
end
fun {Head Q=LenF#F#LenR#R}
case F#R
of nil#nil then raise empty end
[] nil#(X|_) then X
[] (X|Fp)#_ then X
end
end
fun {Tail Q=LenF#F#LenR#R}
case F#R
of nil#nil then raise empty end
[] nil#(X|_) then nil
[] (X|Fp)#_ then {Check (LenF-1)#Fp#LenR#R}
end
end
fun {Snoc Q=LenF#F#LenR#R X}
{Check LenF#F#(LenR+1)#(X|R)}
end
fun {Last Q=LenF#F#LenR#R}
case F#R
of nil#nil then raise empty end
[] (X|_)#nil then X
[] _#(X|Fp) then X
end
end
fun {Init Q=LenF#F#LenR#R}
case F#R
of nil#nil then raise empty end
[] (X|_)#nil then nil
[] _#(X|Rp) then {Check LenF#F#(LenR-1)#Rp}
end
end
end
[BankersDeque] = {Module.apply [BANKERSDEQUE]}
{BankersDeque.initialize 2}
{DequeTest BankersDeque}
% 8.4 RealTimeDeque
REALTIMEDEQUE =
functor
export
initialize : Initialize
empty : Empty
isEmpty : IsEmpty
cons : Cons
head : Head
tail : Tail
snoc : Snoc
last : Last
init : Init
define
C
proc {Initialize Cx} C = Cx end
Empty = 0#nil#nil#0#nil#nil
fun {IsEmpty Q=LenF#F#Sf#LenR#R#Sr}
LenF+LenR == 0
end
fun {Exec1 S}
case S
of H|T then T
else S
end
end
fun {Exec2 S}
{Exec1 {Exec1 S}}
end
fun {RotateRev S R A}
case S
of nil then {Append {List.reverse R} A}
[] H|T then
{fun lazy {$} H|{Append {RotateRev T {List.drop R C} {List.reverse {List.take R C}}} A} end}
end
end
fun {RotateDrop F J R}
if J < C then
{RotateRev F {List.drop R J} nil}
else
local
X|Fp = F
in
{fun lazy {$} X|{RotateDrop Fp J-C {List.drop R C}} end}
end
end
end
fun {Check Q=LenF#F#Sf#LenR#R#Sr}
if LenF > C*LenR+1 then
local
I = (LenF+LenR) div 2
J = LenF+LenR-I
Fp = {List.take F I}
Rp = {RotateDrop R I F}
in
I#Fp#Fp#J#Rp#Rp
end
elseif LenR > C*LenF+1 then
local
J = (LenF+LenR) div 2
I = LenF+LenR-J
Rp = {List.take R J}
Fp = {RotateDrop F J R}
in
I#Fp#Fp#J#Rp#Rp
end
else
Q
end
end
fun {Cons X Q=LenF#F#Sf#LenR#R#Sr}
{Check (LenF+1)#(X|F)#{Exec1 Sf}#LenR#R#{Exec1 Sr}}
end
fun {Head Q=LenF#F#Sf#LenR#R#Sr}
case F#R
of nil#nil then raise empty end
[] nil#(X|_) then X
[] (X|Fp)#_ then X
end
end
fun {Tail Q=LenF#F#Sf#LenR#R#Sr}
case F#R
of nil#nil then raise empty end
[] nil#(X|_) then nil
[] (X|Fp)#_ then {Check (LenF-1)#Fp#{Exec2 Sf}#LenR#R#{Exec2 Sr}}
end
end
fun {Snoc Q=LenF#F#Sf#LenR#R#Sr X}
{Check LenF#F#{Exec1 Sf}#(LenR+1)#(X|R)#{Exec1 Sr}}
end
fun {Last Q=LenF#F#Sf#LenR#R#Sr}
case F#R
of nil#nil then raise empty end
[] (X|_)#nil then X
[] _#(X|Rp) then X
end
end
fun {Init Q=LenF#F#Sf#LenR#R#Sr}
case F#R
of nil#nil then raise empty end
[] (X|_)#nil then nil
[] _#(X|Rp) then {Check LenF#F#{Exec2 Sf}#(LenR-1)#Rp#{Exec2 Sr}}
end
end
end
[RealTimeDeque] = {Module.apply [REALTIMEDEQUE]}
{RealTimeDeque.initialize 2}
{DequeTest RealTimeDeque}
|