PFDS Chapter #11 Examples in Oz==
proc {CatenableDequeTest F}
A = F.empty
B = {F.cons 2 A}
C = {F.snoc B 1}
D = {F.cons 3 C}
E = {F.append D {F.cons 4 F.empty}}
in
{Browse D}
{Browse {F.head E}}
{Browse {F.head {F.tail E}}}
{Browse {F.head {F.tail {F.tail E}}}}
{Browse {F.head {F.tail {F.tail {F.tail E}}}}}
{Browse {F.last E}}
{Browse {F.last {F.init E}}}
{Browse {F.last {F.init {F.init E}}}}
{Browse {F.last {F.init {F.init {F.init E}}}}}
end
% 11.1 ImplicitQueue
IMPLICITQUEUE =
functor
export
empty : Empty
isEmpty : IsEmpty
snoc : Snoc
head : Head
tail : Tail
define
Empty = shallow(zero)
fun {IsEmpty Q} Q == Empty end
fun {SnocEP Q Y}
case Q
of shallow(zero) then shallow(one(Y))
[] shallow(one(X)) then deep(two(X Y) Empty zero)
[] deep(F M zero) then deep(F M one(Y))
[] deep(F M one(X)) then deep(F {fun lazy {$} {Wait M} {SnocEP M pair(X Y)} end} zero)
end
end
fun {Snoc Q Y}
{SnocEP Q elem(Y)}
end
fun {HeadEP Q}
case Q
of shallow(zero) then raise empty end
[] shallow(one(X)) then X
[] deep(one(X) M R) then X
[] deep(two(X Y) M R) then X
end
end
fun {Head Q}
elem(X) = {HeadEP Q}
in
X
end
fun {Tail Q}
case Q
of shallow(zero) then raise empty end
[] shallow(one(X)) then Empty
[] deep(two(X Y) M R) then deep(one(Y) M R)
[] deep(one(X) Qp R) then
if {IsEmpty Qp} then
shallow(R)
else
local
pair(Y Z) = {HeadEP Qp}
in
deep(two(Y Z) {fun lazy {$} {Tail Qp} end} R)
end
end
end
end
end
[ImplicitQueue] = {Module.apply [IMPLICITQUEUE]}
{QueueTest ImplicitQueue}
% 11.2 SimpleCatenableDeque
fun {Force X} {Wait X} X end
SIMPLECATENABLEDEQUE =
functor
export
initialize : Initialize
empty : Empty
isEmpty : IsEmpty
cons : Cons
head : Head
tail : Tail
snoc : Snoc
last : Last
init : Init
append : Append
define
Deque
Empty
proc {Initialize D}
Deque = D
Empty = shallow(Deque.empty)
end
fun {IsEmpty D}
case D
of shallow(X) then {Deque.isEmpty X}
else false
end
end
fun {ConsED X D}
case D
of shallow(Y) then shallow({Deque.cons X Y})
[] deep(F M R) then deep({Deque.cons X F} M R)
end
end
fun {Cons X D}
{ConsED elem(X) D}
end
fun {TooSmall D}
{Deque.isEmpty D} orelse {Deque.isEmpty {Deque.tail D}}
end
fun {DappendL D1 D2}
if {Deque.isEmpty D1} then
D2
else
{Deque.cons {Deque.head D1} D2}
end
end
fun {DappendR D1 D2}
if {Deque.isEmpty D2} then
D1
else
{Deque.snoc D1 {Deque.head D2}}
end
end
fun {HeadED D}
case D
of shallow(X) then {Deque.head X}
[] deep(F M R) then {Deque.head F}
end
end
fun {Head D}
elem(X) = {HeadED D}
in
X
end
fun {Tail D}
case D
of shallow(X) then shallow({Deque.tail X})
[] deep(F M R) then
local
Fp = {Deque.tail F}
in
if {Not {TooSmall Fp}} then
deep(Fp M R)
elseif {IsEmpty {Force M}} then
shallow(DappendL Fp R)
else
local
deque(X) = {HeadED {Force M}}
in
deep({DappendL Fp X} {fun lazy {$} {Tail {Force M}} end} R)
end
end
end
end
end
fun {SnocED D X}
{Browse snoc#D#X}
case D
of shallow(Y) then shallow({Deque.snoc Y X})
[] deep(F M R) then deep({Deque.snoc F X} M R)
end
end
fun {Snoc D X}
{SnocED D elem(X)}
end
fun {LastED D}
case D
of shallow(X) then {Deque.last X}
[] deep(F M R) then {Deque.last F}
end
end
fun {Last D}
elem(X) = {LastED D}
in
X
end
fun {Init D}
case D
of shallow(X) then shallow({Deque.init X})
[] deep(F M R) then
local
Fp = {Deque.init F}
in
if {Not {TooSmall Fp}} then
deep(Fp M R)
elseif {IsEmpty {Force M}} then
shallow(DappendL Fp R)
else
local
deque(X) = {HeadED {Force M}}
in
deep({DappendL Fp X} {fun lazy {$} {Init {Force M}} end} R)
end
end
end
end
end
fun {Append Z1 Z2}
case Z1#Z2
of shallow(D1)#shallow(D2) then
if {TooSmall D1} then
shallow({DappendL D1 D2})
elseif {TooSmall D2} then
shallow({DappendR D1 D2})
else
deep(D1 Empty D2)
end
[] shallow(D)#deep(F M R) then
if {TooSmall D} then
deep({DappendL D F} M R)
else
deep(D {fun lazy {$} {ConsED deque(F) {Force M}} end} R)
end
[] deep(F M R)#shallow(D) then
if {TooSmall D} then
deep(F M {DappendR R D})
else
deep(F {fun lazy {$} {Snoc {Force M} deque(R)} end} D)
end
[] deep(F1 M1 R1)#deep(F2 M2 R2) then
deep(F1
{fun lazy {$}
{Append {Snoc {Force M1} deque(r1)}
{ConsED deque(F2) {Force M2}}}
end}
R2)
end
end
end
[SimpleCatenableDeque] = {Module.apply [SIMPLECATENABLEDEQUE]}
{SimpleCatenableDeque.initialize BankersDeque}
{CatenableDequeTest SimpleCatenableDeque}
% 11.2 ImplicitCatenableDeque
IMPLICITCATENABLEDEQUE =
functor
export
initialize : Initialize
empty : Empty
isEmpty : IsEmpty
cons : Cons
head : Head
tail : Tail
snoc : Snoc
last : Last
init : Init
append : Append
define
Deque
Empty
proc {Initialize D}
Deque = D
Empty = shallow(Deque.empty)
end
fun {IsEmpty D}
case D
of shallow(X) then {Deque.isEmpty X}
else false
end
end
fun {ConsCE X D}
case D
of shallow(Y) then shallow({Deque.cons X Y})
[] deep(F A M B R) then deep({Deque.cons X F} A M B R)
end
end
fun {Cons X D}
{ConsCE elem(X) D}
end
fun {HeadCE D}
case D
of shallow(X) then {Deque.head X}
[] deep(F A M B R) then {Deque.head F}
end
end
fun {Head D}
elem(X) = {HeadCE D}
in
X
end
fun {SnocCE D X}
case D
of shallow(Y) then shallow({Deque.snoc Y X})
[] deep(F A M B R) then deep({Deque.snoc F X} A M B R)
end
end
fun {Snoc D X}
{SnocCE D elem(X)}
end
fun {LastCE D}
case D
of shallow(X) then {Deque.last X}
[] deep(F A M B R) then {Deque.last F}
end
end
fun {Last D}
elem(X) = {LastCE D}
in
X
end
fun {Share F R}
M = {Deque.cons {Deque.last F} {Deque.cons {Deque.head R} {Deque.empty}}}
in
{Deque.init F}#M#{Deque.tail R}
end
fun {DappendL D1 D2}
if {Deque.isEmpty D1} then
D2
else
{DappendL {Deque.init D1} {Deque.cons {Deque.last D1} D2}}
end
end
fun {DappendR D1 D2}
if {Deque.isEmpty D2} then
D1
else
{DappendR {Deque.snoc D1 {Deque.head D2}} {Deque.tail D2}}
end
end
fun {Append Z1 Z2}
case Z1#Z2
of shallow(D1)#shallow(D2) then
if {Deque.size D1} < 4 then
shallow(DappendL D1 D2)
elseif {Deque.size D2} < 4 then
shallow(DappendR D1 D2)
else
local
F#M#R = {Share D1 D2}
in
deep(F Empty M Empty R)
end
end
[] shallow(D)#deep(F A M B R) then
if {Deque.size D} < 4 then
deep({DappendL D F} A M B R)
else
deep(D {fun lazy {$} {ConsCE simple(F) {Force A}} end} M B R)
end
[] deep(F A M B R)#shallow(D) then
if {Deque.size D} < 4 then
deep(F A M B {DappendR R D})
else
deep(F A M {fun lazy {$} {SnocCE {Force B} simple(R)} end} D)
end
[] deep(F1 A1 M1 B1 R1)#deep(F2 A2 M2 B2 R2) then
local
Rp1#M#Fp2 = {Share R1 F2}
Ap1 = {fun lazy {$} {SnocCE {Force A1} cmpd(M1 B1 Rp1)} end}
Bp2 = {fun lazy {$} {ConsCE cmpd(Fp2 A2 M2) {Force B2}} end}
in
deep(F1 Ap1 M Bp2 R2)
end
end
end
fun {ReplaceHead X D}
case D
of shallow(Y) then shallow(Deque.cons X {Deque.tail Y})
[] deep(F A M B R) then deep({Deque.cons X {Deque.tail F}} A M B R)
end
end
fun {Tail Z}
case Z
of shallow(D) then shallow({Deque.tail D})
[] deep(F A M B R) then
if {Deque.size F} > 3 then
deep({Deque.tail F} A M B R)
elseif {Not {IsEmpty {Force A}}} then
case {HeadCE {Force A}}
of simple(D) then
local
Fp = {DappendL {Deque.tail F} D}
in
deep(Fp {fun lazy {$} {Tail {Force a}} end} M B R)
end
[] cmpd(Fp Cp Rp) then
local
Fpp = {DappendL {Deque.tail F} Fp}
App = {fun lazy {$} {Append {Force Cp} {ReplaceHead simple(Rp) {Force A}}} end}
in
deep(Fpp App M B R)
end
end
elseif {Not {IsEmpty {Force B}}} then
case {HeadCE {Force B}}
of simple(D) then
local
Fp = {DappendL {Deque.tail F} M}
in
deep(Fp Empty D {fun lazy {$} {Tail {Force B}} end} R)
end
[] cmpd(Fp Cp Rp) then
local
Fpp = {DappendL {Deque.tail F} M}
App = {fun lazy {$} {ConsCE simple(Fp) {Force Cp}} end}
in
deep(Fpp App Rp {fun lazy {$} {Tail {Force B}} end} R)
end
end
else
shallow({Append {DappendL {Deque.tail F} M} shallow(R)})
end
end
end
fun {ReplaceLast X D}
case D
of shallow(Y) then shallow(Deque.snoc {Deque.init Y} X)
[] deep(F A M B R) then deep({Deque.snoc {Deque.init F} X} A M B R)
end
end
fun {Init Z}
case Z
of shallow(D) then shallow({Deque.init D})
[] deep(F A M B R) then
if {Deque.size F} > 3 then
deep({Deque.init F} A M B R)
elseif {Not {IsEmpty {Force A}}} then
case {HeadCE {Force A}}
of simple(D) then
local
Fp = {DappendL {Deque.init F} D}
in
deep(Fp {fun lazy {$} {Init {Force a}} end} M B R)
end
[] cmpd(Fp Cp Rp) then
local
Fpp = {DappendL {Deque.init F} Fp}
App = {fun lazy {$} {Append {Force Cp} {ReplaceLast simple(Rp) {Force A}}} end}
in
deep(Fpp App M B R)
end
end
elseif {Not {IsEmpty {Force B}}} then
case {HeadCE {Force B}}
of simple(D) then
local
Fp = {DappendL {Deque.init F} M}
in
deep(Fp Empty D {fun lazy {$} {Init {Force B}} end} R)
end
[] cmpd(Fp Cp Rp) then
local
Fpp = {DappendL {Deque.init F} M}
App = {fun lazy {$} {SnocCE {Force Cp} simple(Fp)} end}
in
deep(Fpp App Rp {fun lazy {$} {Init {Force B}} end} R)
end
end
else
shallow({Append {DappendL {Deque.init F} M} shallow(R)})
end
end
end
end
[ImplicitCatenableDeque] = {Module.apply [IMPLICITCATENABLEDEQUE]}
{ImplicitCatenableDeque.initialize BankersDeque}
|