[Header]
open K_
open K

let test_run pgm_str =
  let pgm = Parser.program Lexer.start (Lexing.from_string pgm_str) in
  K.run (K.emptyMemory, K.emptyEnv, pgm)

let test testcase_str = 
  let submission = In_channel.with_open_bin "tree.k-" In_channel.input_all in
  let start = Str.search_backward (Str.regexp "2026") submission (String.length submission) in
  let pgm_str = Str.string_before submission start ^ testcase_str ^ Str.string_after submission (start + 4) in
  test_run pgm_str

[Test]
(* 1. lTree + rTree + nodeVal *)
test "
let tr1 := leaf (2) in
let tr2 := makeLtree (3, (leaf (20))) in
let tr3 := makeRtree (5, (leaf (31))) in
let tr4 := makeTree (7, leaf (44), leaf (56)) in (
write (nodeVal (tr1) + nodeVal (tr2) + nodeVal (tr3) + nodeVal (tr4));
write (nodeVal (lTree (tr2)) + nodeVal (lTree (tr4)));
write (nodeVal (rTree (tr3)) + nodeVal (rTree (tr4)))
)
"

[Output]
17
64
87


[Test]
(* 2. isLeaf *)
test "
let tr := leaf (97) in
if isLRtree (tr) then write (0)
else if isLtree (tr) then write (1)
else if isRtree (tr) then write (2)
else if isLeaf (tr) then write (3)
else write (4)
"

[Output]
3


[Test]
(* 3. isLtree *)
test "
let tr := makeLtree (89, (leaf (83))) in
if isLRtree (tr) then write (5)
else if isLeaf (tr) then write (7)
else if isRtree (tr) then write (8)
else if isLtree (tr) then write (6)
else write (9)
"

[Output]
6


[Test]
(* 4. isRtree *)
test "
let tr := makeRtree (79, (leaf (73))) in
if isLRtree (tr) then write (10)
else if isLeaf (tr) then write (12)
else if isLtree (tr) then write (13)
else if isRtree (tr) then write (11)
else write (14)
"

[Output]
11


[Test]
(* 5. isLRtree *)
test "
let tr := makeTree (71, (leaf (67)), (leaf (61))) in
if isLeaf (tr) then write (17)
else if isLtree (tr) then write (18)
else if isRtree (tr) then write (19)
else if isLRtree (tr) then write (15)
else write (20)
"

[Output]
15


[Test]
(* 6. dft *)
test "
let t6 := leaf (7) in
let t5 := makeLtree (6, t6) in
let t2 := makeLtree (5, t5) in
let t4 := leaf (4) in
let t3 := makeRtree (2, leaf (3)) in
let t1 := makeTree (1, t3, t4) in
let t0 := makeTree (0, t1, t2) in
dft (t0)
"

[Output]
0
1
2
3
4
5
6
7


[Test]
(* 7. bft *)
test "
let t6 := leaf (7) in
let t5 := makeLtree (6, t6) in
let t2 := makeLtree (5, t5) in
let t4 := leaf (4) in
let t3 := makeRtree (2, leaf (3)) in
let t1 := makeTree (1, t3, t4) in
let t0 := makeTree (0, t1, t2) in
bft (t0)
"

[Output]
0
1
5
2
4
6
3
7

[Test]
(* 8. binary search tree *)
test "
let proc insert (x, tr) =
  let v := nodeVal (tr) in
  if isLeaf (tr) then
    if x < v then makeLtree (v, leaf (x))
    else makeRtree (v, leaf (x))
  else if isLtree (tr) then
    if x < v then makeLtree (v, insert (x, lTree (tr)))
    else makeTree (v, lTree (tr), leaf (x))
  else if isRtree (tr) then
    if x < v then makeTree (v, leaf (x), rTree (tr))
    else makeRtree (v, insert (x, rTree (tr)))
  else
    if x < v then makeTree (v, insert (x, lTree (tr)), rTree (tr))
    else makeTree (v, lTree (tr), insert (x, rTree (tr)))
in
let proc search (x, tr) =
  let v := nodeVal (tr) in
  if isLeaf (tr) then
    x = v
  else if isLtree (tr) then
    if x < v then search (x, lTree (tr))
    else x = v
  else if isRtree (tr) then
    if v < x then search (x, rTree (tr))
    else x = v
  else
    if x = v then true
    else if x < v then search (x, lTree (tr))
    else search (x, rTree (tr))
in
let tr := leaf (10) in
tr := insert (5, tr);
tr := insert (15, tr);
tr := insert (3, tr);
tr := insert (7, tr);
tr := insert (12, tr);
tr := insert (18, tr);
bft (tr);
write (if search (7, tr) then 200 else 404);
write (if search (4, tr) then 200 else 404)
"

[Output]
10
5
15
3
7
12
18
200
404