splay_tree v0.15.0 · OCaml Package

Parameters

module Key : Key

module Data : Data

module R : Reduction_operation with type key = Key.t and type data = Data.t

Signature

type t

include Sexplib0.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 -> Sexplib0.Sexp.t

val key_of_sexp : Sexplib0.Sexp.t -> key

type data = Data.t

val sexp_of_data : data -> Sexplib0.Sexp.t

val data_of_sexp : Sexplib0.Sexp.t -> data

type accum = R.accum

val empty : t

val of_alist : (key * data) list -> t Core.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 where key would be inserted. In other words, the length of the left subtree after a split t key.

val search : 
  t ->
  f:(left:accum -> right:accum -> [ `Right | `Left ]) ->
  (key * data) option

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

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 means left + right will be equal to accum t.

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 `Right, whereas f ~left:(a+b+c) ~right:d returns `Left, which makes c the desired element.

Therefore, search will return c. If f returns the same value at all positions, search returns None.

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 `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 following f:

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 the mid in partition

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.Or_error.t

join t1 t2 directly concatenates the sequences described by t1 and 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 t2.

Currently the cost of join is not fully amortized, so it should be considered worst-case linear time.

val join_exn : t -> t -> t

package splay_tree

Parameters

Signature