Module Splay_tree0.Make_with_reduction
Parameters
Signature
include Ppx_sexp_conv_lib.Sexpable.S with type t := t
val t_of_sexp : Sexplib0.Sexp.t -> t
val sexp_of_t : t -> Sexplib0.Sexp.t
type key
= Key.t
val sexp_of_key : key -> Ppx_sexp_conv_lib.Sexp.t
val key_of_sexp : Ppx_sexp_conv_lib.Sexp.t -> key
type data
= Data.t
val sexp_of_data : data -> Ppx_sexp_conv_lib.Sexp.t
val data_of_sexp : Ppx_sexp_conv_lib.Sexp.t -> data
type accum
= R.accum
val empty : t
val of_alist : (key * data) list -> t Core_kernel.Or_error.t
val of_alist_exn : (key * data) list -> t
val to_alist : t -> (key * data) list
val is_empty : t -> bool
val length : t -> int
val accum : t -> accum
val keys : t -> key list
val data : t -> data list
val mem : t -> key -> bool
val find : t -> key -> data option
val set : t -> key:key -> data:data -> t
val remove : t -> key -> t
val remove_min : t -> (key * data * t) option
val remove_max : t -> (key * data * t) option
val remove_after : t -> key -> (key * data * t) option
val remove_before : t -> key -> (key * data * t) option
val map : t -> f:(data -> data) -> t
val map_range : t -> min_key:key -> max_key:key -> f:((key * data) list -> (key * data) list) -> t
val nth : t -> int -> (key * data) option
val rank : t -> key -> int
rank t key
is the number of nodes before wherekey
would be inserted. In other words, the length of the left subtree after asplit t key
.
val search : t -> f:(left:accum -> right:accum -> [ `Right | `Left ]) -> (key * data) option
search
implements bisection search overt
based on theaccum
values of its prefixes.Let's consider a
t
consisting of four elementsa; b; c; d
(see diagram below) (we'll refer to all of key, data, and accum ofa
as justa
; we'll also assumeR.combine = (+)
).Then there are five possible positions to evaluate
f
at (numbered 0..4 below):- | position: 0 1 2 3 4 | ------------------------- | element: | a | b | c | d | | ------------------------- | left: 0 a a+b a+b+c a+b+c+d | right: a+b+c+d b+c+d c+d d 0 | f ~left ~right: R R R L L
The function
f ~left ~right
will be called for a particular position and it takes the sum of the elements to the left and to the right of this position. This meansleft + right
will be equal toaccum t
.The return value of
f
must indicate the direction where the desired element is. In the diagram abovef ~left:(a+b) ~right:(c+d)
returns`Right
, whereasf ~left:(a+b+c) ~right:d
returns`Left
, which makesc
the desired element.Therefore,
search
will returnc
. Iff
returns the same value at all positions,search
returnsNone
.For it to make sense,
f
must be monotonic: callingf
on every possible position from left to right should produce a prefix of`Right
values followed by a suffix of`Left
values.Example:
If the values are positive integers and reduction operation is sum, then you can find the last node where the prefix sum before it is at most
x
with the followingf
:let f ~left ~right:_ = if x < left then `Left else `Right
module Partition : sig ... end
val partition : ?min_key:key -> ?max_key:key -> t -> Partition.t
val subrange : ?min_key:key -> ?max_key:key -> t -> t
subrange t ?min_key ?max_key
is equivalent to themid
inpartition
val merge : t -> t -> f:(key:key -> [ `Left of data | `Right of data | `Both of data * data ] -> data option) -> t
val split : t -> key -> t * data option * t
val join : t -> t -> t Core_kernel.Or_error.t
join t1 t2
directly concatenates the sequences described byt1
andt2
. This should be used to rejoin trees obtained by a split operation, though it can be used for other things.This operation can fail if the concatenation of the two sequences is invalid; i.e. the keys are not in order. This happens when the maximum key of
t1
is at or above the minimum key oft2
.Currently the cost of
join
is not fully amortized, so it should be considered worst-case linear time.