base
  1. Overview
  2. Docs
package base
Legend:
Library
Module
Module type
Parameter
Class
Class type

Build_increasing can be used to construct a map incrementally from a sequence that is known to be increasing.

The total time complexity of constructing a map this way is O(n), which is more efficient than using Map.add by a logarithmic factor.

This interface can be thought of as a dual of to_sequence, but we don't have an equally neat idiom for the duals of sequences (of_sequence is much less general because it does not allow the sequence to be produced asynchronously).

type ('a, 'b, 'c) tree := ('a, 'b, 'c) t
type ('k, 'v, 'w) t
val empty : ('k, 'v, 'w) t
val add_exn : ('k, 'v, 'w) t -> comparator:('k, 'w) Comparator.t -> key:'k -> data:'v -> ('k, 'v, 'w) t

Time complexity of add_exn is amortized constant-time (if t is used linearly), with a worst-case O(log(n)) time.

val to_tree : ('k, 'v, 'w) t -> ('k, 'v, 'w) tree

Time complexity is O(log(n)).