Module `Tree.Build_increasing`Source

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) Base.Map.Using_comparator.Tree.t

Sourcetype ('k, 'v, 'w) t

Sourceval empty : ('k, 'v, 'w) Base.Map.Using_comparator.Tree.Build_increasing.t

Source

val add_exn : 
  ('k, 'v, 'w) Base.Map.Using_comparator.Tree.Build_increasing.t ->
  comparator:('k, 'w) Base.Comparator.t ->
  key:'k ->
  data:'v ->
  ('k, 'v, 'w) Base.Map.Using_comparator.Tree.Build_increasing.t

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

Source

val to_tree : 
  ('k, 'v, 'w) Base.Map.Using_comparator.Tree.Build_increasing.t ->
  ('k, 'v, 'w) Base.Map.Using_comparator.Tree.Build_increasing.tree

Time complexity is O(log(n)).

Module Tree.Build_increasingSource

Module `Tree.Build_increasing`Source