Module `Splay_tree0.Make_without_reduction`Source

Parameters

module Key : Key

module Data : Data

Signature

Sourcetype t

include Sexplib0.Sexpable.S with type t := t

Sourceval t_of_sexp : Sexplib0.Sexp.t -> t

Sourceval sexp_of_t : t -> Sexplib0.Sexp.t

Sourcetype key = Key.t

Sourceval sexp_of_key : key -> Sexplib0.Sexp.t

Sourceval key_of_sexp : Sexplib0.Sexp.t -> key

Sourcetype data = Data.t

Sourceval sexp_of_data : data -> Sexplib0.Sexp.t

Sourceval data_of_sexp : Sexplib0.Sexp.t -> data

Sourcetype accum = unit

Sourceval empty : t

Sourceval of_alist : (key * data) list -> t Core.Or_error.t

Sourceval of_alist_exn : (key * data) list -> t

Sourceval to_alist : t -> (key * data) list

Sourceval is_empty : t -> bool

Sourceval length : t -> int

Sourceval accum : t -> accum

Sourceval keys : t -> key list

Sourceval data : t -> data list

Sourceval mem : t -> key -> bool

Sourceval find : t -> key -> data option

Sourceval set : t -> key:key -> data:data -> t

Sourceval remove : t -> key -> t

Sourceval remove_min : t -> (key * data * t) option

Sourceval remove_max : t -> (key * data * t) option

Sourceval remove_after : t -> key -> (key * data * t) option

Sourceval remove_before : t -> key -> (key * data * t) option

Sourceval map : t -> f:(data -> data) -> t

Source

val map_range : 
  t ->
  min_key:key ->
  max_key:key ->
  f:((key * data) list -> (key * data) list) ->
  t

Sourceval nth : t -> int -> (key * data) option

Sourceval 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.

Source

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

Sourcemodule Partition : sig ... end

Sourceval partition : ?min_key:key -> ?max_key:key -> t -> Partition.t

Sourceval subrange : ?min_key:key -> ?max_key:key -> t -> t

subrange t ?min_key ?max_key is equivalent to the mid in partition

Source

val merge : 
  t ->
  t ->
  f:
    (key:key ->
      [ `Left of data | `Right of data | `Both of data * data ] ->
      data option) ->
  t

Sourceval split : t -> key -> t * data option * t

Sourceval 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.

Sourceval join_exn : t -> t -> t

package splay_tree

Module Splay_tree0.Make_without_reductionSource

Parameters

Signature

Module `Splay_tree0.Make_without_reduction`Source