Up
### Signature

type
('k, 'v)
t
= private

We expose `t`

to allow an optimization in Hashtbl that makes iter and fold more than
twice as fast.

It is however private so that `'k`

and `'v`

are invariant. This avoids the following
segfault. The segfault works by creating a tree containing `[`A of string]`

keys,
mutating it to contain `[`A of string | `B of int]`

keys, and then pattern matching
against keys at the first type.

```
let added = ref false in
let tree =
Avltree.add Avltree.empty ~key:0 ~data:(`A "Hello, world!") ~compare
~added ~replace:true
in
let x : (int, [ `A of string ]) Avltree.t = tree in
ignore (Avltree.add tree ~key:0 ~data:(`B 0) ~compare
~added ~replace:true : (_, _) Avltree.t);
match Avltree.find x 0 ~compare:compare with
| None -> assert false
| Some (`A str) -> print_string str (* BOOM! *)
```

val
empty : ('k, 'v) t

val
invariant : ('k, 'v) t -> compare:('k -> 'k -> int) -> unit

check invariants, raise an exception if any invariants fail

val
add : ('k, 'v) t -> replace:bool -> compare:('k -> 'k -> int) -> added:bool Pervasives.ref -> key:'k -> data:'v -> ('k, 'v) t

adds the specified key and data to the tree destructively (previous t's are no longer
valid) using the specified comparison function. O(log(N)) time, O(1) space. The
returned t is the new root node of the tree, and should be used on all further calls
to any other function in this module. The bool ref, added, will be set to true if a
new node is added to the tree, or false if an existing node is replaced (in the case
that the key already exists). If `replace`

(default true) is true then add will
overwrite any existing mapping for `key`

. If `replace`

is false, and there is an
existing mapping for key then add has no effect.

val
first : ('k, 'v) t -> ('k
* 'v) option

Returns the first (leftmost) or last (rightmost) element in the tree

val
last : ('k, 'v) t -> ('k
* 'v) option

val
find : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> 'v option

if the specified key exists in the tree, return the corresponding value. O(log(N)) time and O(1) space.

val
find_and_call : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> if_found:('v -> 'a) -> if_not_found:('k -> 'a) -> 'a

`find_and_call t ~compare k ~if_found ~if_not_found`

is equivalent to:

`match find t ~compare k with Some v -> if_found v | None -> if_not_found k`

except that it doesn't allocate the option.

val
mem : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> bool

return true if key is present in the tree, otherwise return false.

val
remove : ('k, 'v) t -> removed:bool Pervasives.ref -> compare:('k -> 'k -> int) -> 'k -> ('k, 'v) t

remove key destructively from the tree if it exists, return the new root node. Previous root nodes are not usable anymore, do so at your peril. the removed ref will be set to true if a node was actually removed, or false otherwise.

val
fold : ('k, 'v) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a

fold over the tree

val
iter : ('k, 'v) t -> f:(key:'k -> data:'v -> unit) -> unit

iterate over the tree