type ('k, 'v) t = private
| Empty | |||||
| Node of {
} | |||||
| Leaf of {
} |
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 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
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 -> if_found:('v -> 'a -> 'b) -> if_not_found:('k -> 'a -> 'b) -> 'b
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 mem : ('k, 'v) t -> compare:('k -> 'k -> int) -> 'k -> bool
Returns true if key is present in the tree, and false otherwise.
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