type ('k, 'v) t = private
| Empty
| Node of {
mutable left : ('k, 'v) t;
key : 'k;
mutable value : 'v;
mutable height : int;
mutable right : ('k, 'v) t;
}
| Leaf of {
key : 'k;
mutable value : 'v;
}
We expose
t
to allow an optimization in Hashtbl that makes iter and fold more than twice as fast. We keep the type private to reduce opportunities for external code to violate avltree invariants.
val empty : ('k, 'v) t
val is_empty : (_, _) t -> bool
val invariant : ('k, 'v) t -> compare:('k -> 'k -> int) -> unit
Checks invariants, raising an exception if any invariants fail.
val add : ('k, 'v) t -> replace:bool -> compare:('k -> 'k -> int) -> added:bool Caml.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 boolref
, added, will be set totrue
if a new node is added to the tree, orfalse
if an existing node is replaced (in the case that the key already exists).If
replace
(default true) is true thenadd
will overwrite any existing mapping forkey
. Ifreplace
is false, and there is an existing mapping for key, thenadd
has no effect.
val first : ('k, 'v) t -> ('k * 'v) option
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, returns 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 find_and_call1 : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> a:'a -> if_found:('v -> 'a -> 'b) -> if_not_found:('k -> 'a -> 'b) -> 'b
val find_and_call2 : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> a:'a -> b:'b -> if_found:('v -> 'a -> 'b -> 'c) -> if_not_found:('k -> 'a -> 'b -> 'c) -> 'c
val findi_and_call : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> if_found:(key:'k -> data:'v -> 'a) -> if_not_found:('k -> 'a) -> 'a
val findi_and_call1 : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> a:'a -> if_found:(key:'k -> data:'v -> 'a -> 'b) -> if_not_found:('k -> 'a -> 'b) -> 'b
val findi_and_call2 : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> a:'a -> b:'b -> if_found:(key:'k -> data:'v -> 'a -> 'b -> 'c) -> if_not_found:('k -> 'a -> 'b -> 'c) -> 'c
val mem : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> bool
Returns true if key is present in the tree, and false otherwise.
val remove : ('k, 'v) t -> removed:bool Caml.ref -> compare:('k -> 'k -> int) -> 'k -> ('k, 'v) t
Removes key destructively from the tree if it exists, returning 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, and false otherwise.
val fold : ('k, 'v) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a
Folds over the tree.
val iter : ('k, 'v) t -> f:(key:'k -> data:'v -> unit) -> unit
Iterates over the tree.
val mapi_inplace : ('k, 'v) t -> f:(key:'k -> data:'v -> 'v) -> unit
Map over the the tree, changing the data in place.
val choose_exn : ('k, 'v) t -> 'k * 'v