Module `Tree.Build_increasing`

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