1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
|
module Make
:
sig
type 'a tree = 'a node option
and 'a node = {
mutable left : 'a tree;
mutable right : 'a tree;
mutable item : 'a;
}
val empty : 'a tree
val is_empty: 'a tree -> bool
val singleton: 'a -> 'a tree
val copy: 'a tree -> 'a tree
val diff: 'a tree -> int -> int
val length: 'a tree -> int
val map: ('a -> 'b) -> 'a tree -> 'b tree
val add: 'a -> 'a tree -> 'a tree
val insert: 'a -> 'a tree -> 'a tree
val combine: 'a tree -> 'a tree -> 'a tree
val case: 'a tree -> ('a * 'a tree) option
val uncons: 'a tree -> 'a * 'a tree
val lookup: int -> 'a tree -> 'a option
val find: int -> 'a tree -> 'a
val update: int -> 'a -> 'a tree -> 'a tree
val assign: int -> 'a -> 'a tree -> 'a tree
val append: 'a tree -> 'a tree -> 'a tree
end
=
struct
type 'a tree =
'a node option
and 'a node =
{
mutable left: 'a tree; mutable right: 'a tree; mutable item: 'a;
}
let empty =
None
let is_empty t = (t = empty)
let singleton x =
Some {left = None; right = None; item = x}
let rec copy = function
| None -> None
| Some n -> Some {n with left = copy n.left; right = copy n.right}
let rec diff t m =
match t with
| None -> 0
| Some n when m = 0 -> 1
| Some n ->
if m land 1 = 1 then diff n.left ((m - 1) / 2)
else diff n.right ((m - 2) / 2)
let rec length = function
| None -> 0
| Some n -> let m = length n.right in 1 + m + m + diff n.left m
let rec map f = function
| None -> None
| Some n -> Some
{left = map f n.left; right = map f n.right; item = f n.item}
let rec add x = function
| None ->
Some {left = None; right = None; item = x}
| Some n ->
Some {left = add n.item n.right; right = n.left; item = x}
let rec insert x t =
match t with
| None ->
Some {left = None; right = None; item = x}
| Some n ->
let l = n.left in
n.left <- insert n.item n.right; n.right <- l;
n.item <- x; t
let rec combine t c =
match t with
| None -> None
| Some n ->
Some {left = c; right = combine n.left n.right; item = n.item}
let case = function
| None -> None
| Some n -> Some (n.item,combine n.left n.right)
let uncons = function
| None -> failwith "uncons"
| Some n -> (n.item,combine n.left n.right)
let rec lookup i = function
| None -> None
| Some n ->
if i = 0 then Some (n.item) else
if i land 1 = 1 then lookup (i / 2) n.left
else lookup (i / 2 - 1) n.right
let rec find i = function
| None -> raise Not_found
| Some n ->
if i = 0 then n.item else
if i land 1 = 1 then find (i / 2) n.left
else find (i / 2 - 1) n.right
let rec update i x = function
| None -> raise Not_found
| Some n ->
if i = 0 then Some {n with item = x} else
if i land 1 = 1 then Some {n with left = update (i / 2) x n.left}
else Some {n with right = update (i / 2 - 1) x n.right}
let rec assign i x t =
match t with
| None -> raise Not_found
| Some n ->
if i = 0 then n.item <- x else
if i land 1 = 1 then n.left <- assign (i / 2) x n.left
else n.right <- assign (i / 2 - 1) x n.right;
t
let rec append n ta tb =
if n = 0 then tb else
match ta,tb with
| _,None -> ta
| None,_ -> assert false
| Some a,Some b ->
let m = n / 2 in
if n land 1 = 1 then Some
{item = a.item;
left = append m a.left (add b.item b.right);
right = append m a.right b.left}
else Some
{item = a.item;
left = append m a.left b.left;
right = append (m-1) a.right (add b.item b.right)}
let append ta tb =
if tb = None then ta
else append (length ta) ta tb
end |
Partager