Module CCWBTree.Make
Parameters
Signature
type key
= X.t
type +'a t
val empty : 'a t
val is_empty : _ t -> bool
val singleton : key -> 'a -> 'a t
val mem : key -> _ t -> bool
val get : key -> 'a t -> 'a option
val get_exn : key -> 'a t -> 'a
- raises Not_found
if the key is not present.
val nth : int -> 'a t -> (key * 'a) option
nth i m
returns thei
-thkey, value
in the ascending order. Complexity isO(log (cardinal m))
.
val get_rank : key -> 'a t -> [ `At of int | `After of int | `First ]
get_rank k m
looks for the rank ofk
inm
, i.e. the index ofk
in the sorted list of bindings ofm
.let (`At n) = get_rank k m in nth_exn n m = get m k
should hold.- since
- 1.4
val add : key -> 'a -> 'a t -> 'a t
val remove : key -> 'a t -> 'a t
val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
update k f m
callsf (Some v)
ifget k m = Some v
,f None
otherwise. Then, iff
returnsSome v'
it bindsk
tov'
, iff
returnsNone
it removesk
.
val cardinal : _ t -> int
val weight : _ t -> int
val fold : f:('b -> key -> 'a -> 'b) -> x:'b -> 'a t -> 'b
val mapi : f:(key -> 'a -> 'b) -> 'a t -> 'b t
Map values, giving both key and value. Will use
WORD
.of_list to rebuild keys.- since
- 0.17
val iter : f:(key -> 'a -> unit) -> 'a t -> unit
val split : key -> 'a t -> 'a t * 'a option * 'a t
split k t
returnsl, o, r
wherel
is the part of the map with keys smaller thank
,r
has keys bigger thank
, ando = Some v
ifk, v
belonged to the map.
val extract_min : 'a t -> key * 'a * 'a t
extract_min m
returnsk, v, m'
wherek,v
is the pair with the smallest key inm
, andm'
does not containk
.- raises Not_found
if the map is empty.
val extract_max : 'a t -> key * 'a * 'a t
extract_max m
returnsk, v, m'
wherek,v
is the pair with the highest key inm
, andm'
does not containk
.- raises Not_found
if the map is empty.
val choose : 'a t -> (key * 'a) option
val choose_exn : 'a t -> key * 'a
- raises Not_found
if the tree is empty.
val random_choose : Stdlib.Random.State.t -> 'a t -> key * 'a
Randomly choose a (key,value) pair within the tree, using weights as probability weights.
- raises Not_found
if the tree is empty.
val add_list : 'a t -> (key * 'a) list -> 'a t
val of_list : (key * 'a) list -> 'a t
val to_list : 'a t -> (key * 'a) list
val add_seq : 'a t -> (key * 'a) sequence -> 'a t
val of_seq : (key * 'a) sequence -> 'a t
val to_seq : 'a t -> (key * 'a) sequence
val add_gen : 'a t -> (key * 'a) gen -> 'a t
val of_gen : (key * 'a) gen -> 'a t
val to_gen : 'a t -> (key * 'a) gen
val pp : key printer -> 'a printer -> 'a t printer
Renamed from
val print
.- since
- 2.0