Commit | Line | Data |
---|---|---|
f76c63f8 SK |
1 | module Array = ArrayLabels |
2 | ||
3 | module type TREE = sig | |
8dd28238 | 4 | type ('k, 'v) t |
f76c63f8 | 5 | |
8dd28238 | 6 | val empty : ('k, 'v) t |
f76c63f8 | 7 | |
8dd28238 | 8 | val set : ('k, 'v) t -> k:'k -> v:'v -> ('k, 'v) t |
f76c63f8 | 9 | |
8dd28238 SK |
10 | val get : ('k, 'v) t -> k:'k -> 'v option |
11 | ||
12 | val member : ('k, 'v) t -> k:'k -> bool | |
f76c63f8 SK |
13 | end |
14 | ||
15 | module BinaryTree : TREE = struct | |
8dd28238 SK |
16 | type ('k, 'v) t = |
17 | | Node of 'k * 'v * ('k, 'v) t * ('k, 'v) t | |
f76c63f8 SK |
18 | | Leaf |
19 | ||
20 | let empty = Leaf | |
21 | ||
8dd28238 SK |
22 | let rec set t ~k ~v = |
23 | match t with | |
24 | | Leaf -> Node (k, v, Leaf, Leaf) | |
25 | | Node (k', v', l, r) when k < k' -> Node (k', v', set l ~k ~v, r) | |
26 | | Node (k', v', l, r) when k > k' -> Node (k', v', l, set r ~k ~v) | |
27 | | Node (k, _, l, r) -> Node (k, v, l, r) | |
28 | ||
29 | let rec get t ~k = | |
f76c63f8 | 30 | match t with |
8dd28238 SK |
31 | | Leaf -> None |
32 | | Node (k', _, l, _) when k < k' -> get l ~k | |
33 | | Node (k', _, _, r) when k > k' -> get r ~k | |
34 | | Node (_, v, _, _) -> Some v | |
f76c63f8 | 35 | |
8dd28238 | 36 | let rec member t ~k = |
f76c63f8 SK |
37 | match t with |
38 | | Leaf -> false | |
8dd28238 SK |
39 | | Node (k', _, l, _) when k < k' -> member l ~k |
40 | | Node (k', _, _, r) when k > k' -> member r ~k | |
f76c63f8 SK |
41 | | Node _ -> true |
42 | end | |
43 | ||
44 | let () = | |
8dd28238 SK |
45 | let tree_a = BinaryTree.empty in |
46 | let tree_a = BinaryTree.set tree_a ~k:"k1" ~v:"v1" in | |
47 | let tree_a = BinaryTree.set tree_a ~k:"k2" ~v:"v2" in | |
48 | assert (BinaryTree.member tree_a ~k:"k1"); | |
49 | assert (BinaryTree.member tree_a ~k:"k2"); | |
50 | assert (Some "v1" = BinaryTree.get tree_a ~k:"k1"); | |
51 | assert (Some "v2" = BinaryTree.get tree_a ~k:"k2"); | |
52 | let tree_b = | |
f76c63f8 SK |
53 | Array.fold_left |
54 | (Sys.argv) | |
55 | ~init:BinaryTree.empty | |
8dd28238 | 56 | ~f:(fun t k -> BinaryTree.set t ~k ~v:()) |
f76c63f8 | 57 | in |
8dd28238 | 58 | Printf.printf "%B\n" (BinaryTree.member tree_b ~k:"a") |