exception Empty_stack
class ['a] list_stack =
object
val mutable items
: 'a
list = []
method push (x : 'a) =
items <- x :: items
method pop : 'a =
match items with
| [] -> raise Empty_stack
| head :: rest ->
begin
items <- rest ;
head
end
end
class ['a] array_stack =
let grow_factor = 1.6
and init_capacity = 10 in
object (self)
val mutable items
: 'a
option array = Array.make init_capacity None
val mutable count = 0
method push (x : 'a) =
self#ensure_cap ;
Array.set items count
(Some x
) ; count <- count + 1
method pop : 'a =
if count = 0
then raise Empty_stack
else
count <- count - 1 ;
match Array.get items count
with | None
-> raise (Failure "unreachable") | Some x ->
begin
Array.set items count None
; x
end
method private ensure_cap =
if count
< Array.length items
then ()
else items <- self#grow
method private grow =
let old_cap
= Array.length items
in let dst
= Array.make new_cap None
in Array.blit items
0 dst
0 old_cap
; dst
end
type 'a stack =
; pop : 'a
>
let main
(make_stack
: unit -> 'a stack
) = let s = make_stack () in
for i = 1 to 3 do
s#push i
done ;
for i = 1 to 3 do
done ;
let _ =
main (fun () -> new list_stack) ;
main (fun () -> new array_stack)
ZXhjZXB0aW9uIEVtcHR5X3N0YWNrCgpjbGFzcyBbJ2FdIGxpc3Rfc3RhY2sgPQogIG9iamVjdAogICAgdmFsIG11dGFibGUgaXRlbXMgOiAnYSBsaXN0ID0gW10KCiAgICBtZXRob2QgcHVzaCAoeCA6ICdhKSA9CiAgICAgIGl0ZW1zIDwtIHggOjogaXRlbXMKCiAgICBtZXRob2QgcG9wIDogJ2EgPQogICAgICBtYXRjaCBpdGVtcyB3aXRoCiAgICAgIHwgW10gLT4gcmFpc2UgRW1wdHlfc3RhY2sKICAgICAgfCBoZWFkIDo6IHJlc3QgLT4KICAgICAgICBiZWdpbgogICAgICAgICAgaXRlbXMgPC0gcmVzdCA7CiAgICAgICAgICBoZWFkCiAgICAgICAgZW5kCgogIGVuZAoKY2xhc3MgWydhXSBhcnJheV9zdGFjayA9CiAgbGV0IGdyb3dfZmFjdG9yID0gMS42CiAgYW5kIGluaXRfY2FwYWNpdHkgPSAxMCBpbgoKICBvYmplY3QgKHNlbGYpCiAgICB2YWwgbXV0YWJsZSBpdGVtcyA6ICdhIG9wdGlvbiBhcnJheSA9IEFycmF5Lm1ha2UgaW5pdF9jYXBhY2l0eSBOb25lCiAgICB2YWwgbXV0YWJsZSBjb3VudCA9IDAKCiAgICBtZXRob2QgcHVzaCAoeCA6ICdhKSA9CiAgICAgIHNlbGYjZW5zdXJlX2NhcCA7CiAgICAgIEFycmF5LnNldCBpdGVtcyBjb3VudCAoU29tZSB4KSA7CiAgICAgIGNvdW50IDwtIGNvdW50ICsgMQoKICAgIG1ldGhvZCBwb3AgOiAnYSA9CiAgICAgIGlmIGNvdW50ID0gMAogICAgICB0aGVuIHJhaXNlIEVtcHR5X3N0YWNrCiAgICAgIGVsc2UKICAgICAgICBjb3VudCA8LSBjb3VudCAtIDEgOwogICAgICAgIG1hdGNoIEFycmF5LmdldCBpdGVtcyBjb3VudCB3aXRoCiAgICAgICAgfCBOb25lICAgLT4gcmFpc2UgKEZhaWx1cmUgInVucmVhY2hhYmxlIikKICAgICAgICB8IFNvbWUgeCAtPgogICAgICAgICAgYmVnaW4KICAgICAgICAgICAgQXJyYXkuc2V0IGl0ZW1zIGNvdW50IE5vbmUgOwogICAgICAgICAgICB4CiAgICAgICAgICBlbmQKCiAgICBtZXRob2QgcHJpdmF0ZSBlbnN1cmVfY2FwID0KICAgICAgaWYgY291bnQgPCBBcnJheS5sZW5ndGggaXRlbXMKICAgICAgdGhlbiAoKQogICAgICBlbHNlIGl0ZW1zIDwtIHNlbGYjZ3JvdwoKICAgIG1ldGhvZCBwcml2YXRlIGdyb3cgPQogICAgICBsZXQgb2xkX2NhcCA9IEFycmF5Lmxlbmd0aCBpdGVtcyBpbgogICAgICBsZXQgbmV3X2NhcCA9IGludF9vZl9mbG9hdCAoZ3Jvd19mYWN0b3IgKi4gZmxvYXRfb2ZfaW50IG9sZF9jYXApIGluCiAgICAgIGxldCBkc3QgPSBBcnJheS5tYWtlIG5ld19jYXAgTm9uZSBpbgogICAgICBBcnJheS5ibGl0IGl0ZW1zIDAgZHN0IDAgb2xkX2NhcCA7CiAgICAgIGRzdAoKICBlbmQKCnR5cGUgJ2Egc3RhY2sgPQogIDwgcHVzaCA6ICdhIC0+IHVuaXQKICA7IHBvcCAgOiAnYQogID4KCmxldCBtYWluIChtYWtlX3N0YWNrIDogdW5pdCAtPiAnYSBzdGFjaykgPQogIGxldCBzID0gbWFrZV9zdGFjayAoKSBpbgogIGZvciBpID0gMSB0byAzIGRvCiAgICBzI3B1c2ggaQogIGRvbmUgOwogIGZvciBpID0gMSB0byAzIGRvCiAgICBzI3BvcCB8PiBQcmludGYucHJpbnRmICIlZCAiCiAgZG9uZSA7CiAgUHJpbnRmLnByaW50ZiAiXG4iCgpsZXQgXyA9CiAgbWFpbiAoZnVuICgpIC0+IG5ldyBsaXN0X3N0YWNrKSA7CiAgbWFpbiAoZnVuICgpIC0+IG5ldyBhcnJheV9zdGFjaykK