type key = Key.t
type data = Data.t
type accum = R.accum
val empty : t
val is_empty : t -> bool
val length : t -> int
rank t key is the number of nodes before where
key would be inserted. In other words, the length of the left subtree after a
split t key.
search implements bisection search over
t based on the
accum values of its prefixes.
Let's consider a
t consisting of four elements
a; b; c; d (see diagram below) (we'll refer to all of key, data, and accum of
a as just
a; we'll also assume
R.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
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 means
left + right will be equal to
The return value of
f must indicate the direction where the desired element is. In the diagram above
f ~left:(a+b) ~right:(c+d) returns
f ~left:(a+b+c) ~right:d returns
`Left, which makes
c the desired element.
search will return
f returns the same value at all positions,
For it to make sense,
f must be monotonic: calling
f on every possible position from left to right should produce a prefix of
`Right values followed by a suffix of
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 following
let f ~left ~right:_ = if x < left then `Left else `Right
module Partition : sig ... end
subrange t ?min_key ?max_key is equivalent to the
join t1 t2 directly concatenates the sequences described by
t2. 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 of
Currently the cost of
join is not fully amortized, so it should be considered worst-case linear time.