package splay_tree

  1. Overview
  2. Docs

Module Splay_tree0.Make_without_reduction

Parameters

module Key : Key
module Data : Data

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 = unit
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.

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):

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