base
-
library base
-
module Base
-
module Applicative
-
module type Applicative_infix
-
module type Applicative_infix2
-
module type Applicative_infix3
-
module type Basic
-
module type Basic2
-
module type Basic2_using_map2
-
module type Basic3
-
module type Basic3_using_map2
-
module type Basic_using_map2
-
module Compose
-
argument 1-F
-
module Applicative_infix
-
-
argument 2-G
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module type Let_syntax
-
module Let_syntax
-
module Let_syntax
-
-
module Open_on_rhs_intf
-
-
module type Let_syntax2
-
module Let_syntax
-
module Let_syntax
-
-
module Open_on_rhs_intf
-
-
module type Let_syntax3
-
module Let_syntax
-
module Let_syntax
-
-
module Open_on_rhs_intf
-
-
module Make
-
argument 1-X
-
module Applicative_infix
-
-
module Make2
-
argument 1-X
-
module Applicative_infix
-
-
module Make2_using_map2
-
argument 1-X
-
module Applicative_infix
-
-
module Make3
-
argument 1-X
-
module Applicative_infix
-
-
module Make3_using_map2
-
argument 1-X
-
module Applicative_infix
-
-
module Make_let_syntax
-
argument 1-X
-
argument 2-Intf
-
module Let_syntax
-
module Let_syntax
-
-
-
module Make_let_syntax2
-
argument 1-X
-
argument 2-Intf
-
module Let_syntax
-
module Let_syntax
-
-
-
module Make_let_syntax3
-
argument 1-X
-
argument 2-Intf
-
module Let_syntax
-
module Let_syntax
-
-
-
module Make_using_map2
-
argument 1-X
-
module Applicative_infix
-
-
module Of_monad
-
argument 1-M
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Applicative_infix
-
-
module Of_monad2
-
argument 1-M
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Applicative_infix
-
-
module Pair
-
argument 1-F
-
module Applicative_infix
-
-
argument 2-G
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module type S
-
module Applicative_infix
-
-
module type S2
-
module Applicative_infix
-
-
module S2_to_S
-
argument 1-X
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module S2_to_S3
-
argument 1-X
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module type S3
-
module Applicative_infix
-
-
module S3_to_S2
-
argument 1-X
-
module Applicative_infix
-
-
module Applicative_infix
-
-
module S_to_S2
-
argument 1-X
-
module Applicative_infix
-
-
module Applicative_infix
-
-
-
module Array
-
module Avltree
-
module Binary_search
-
module Binary_searchable
-
module type Indexable
-
module type Indexable1
-
module type S
-
module type S1
-
module Which_target_by_key
-
module Which_target_by_segment
-
-
module Blit
-
module Make
-
argument 1-Sequence
-
-
module Make1
-
argument 1-Sequence
-
-
module Make1_generic
-
argument 1-Sequence
-
-
module Make_distinct
-
module Make_to_string
-
argument 1-T
-
argument 2-To_bytes
-
-
module type S
-
module type S1
-
module type S1_distinct
-
module type S_distinct
-
module type S_to_string
-
module type Sequence
-
module type Sequence1
-
-
module Bool
-
module Non_short_circuiting
-
-
module Bytes
-
module From_string
-
module To_string
-
-
module Comparable
-
module Make_using_comparator
-
argument 1-T
-
-
module Polymorphic_compare
-
argument 1-T
-
-
module type S
-
module type With_compare
-
module Comparisons
-
module Container
-
module Continue_or_stop
-
module type Generic
-
module type Generic_phantom
-
module type S0
-
module type S0_phantom
-
module type S1
-
module type S1_phantom
-
module type S1_phantom_invariant
-
module type Summable
-
-
module Continue_or_stop
-
module Either
-
module First
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type Focused
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Second
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
-
module Error
-
module Internal_repr
-
-
module Exn
-
module Export
-
module Field
-
module Fn
-
module Formatter
-
module Hash_set
-
module Hashtbl
-
module type Accessors
-
module type Equal_m
-
module type For_deriving
-
module type Equal_m
-
module type M_of_sexp
-
module type M_sexp_grammar
-
module type Sexp_of_m
-
-
module type M_of_sexp
-
module type M_sexp_grammar
-
module Merge_into_action
-
module type Multi
-
module Poly
-
module type S_poly
-
module type S_without_submodules
-
module type Sexp_of_m
-
-
module Identifiable
-
module type Arg
-
module type Arg_with_comparator
-
module Make_using_comparator
-
argument 1-M
-
-
module type S
-
-
module Info
-
module Internal_repr
-
module type S
-
module Internal_repr
-
-
-
module Int
-
module Hex
-
module type Int_without_module_types
-
module O
-
module type Operators
-
module type Operators_unbounded
-
module type Round
-
module type S_unbounded
-
-
module Int63
-
module Hex
-
module O
-
module Overflow_exn
-
-
module Lazy
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
module T_unforcing
-
-
module Linked_queue
-
module List
-
module Assoc
-
module Cartesian_product
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
module Or_unequal_lengths
-
-
module Map
-
module type Accessors1
-
module type Accessors2
-
module type Accessors3
-
module type Accessors3_with_comparator
-
module type Accessors_generic
-
module type Compare_m
-
module Continue_or_stop
-
module type Creators1
-
module type Creators2
-
module type Creators3_with_comparator
-
module type Creators_and_accessors1
-
module type Creators_and_accessors2
-
module type Creators_and_accessors3_with_comparator
-
module type Creators_and_accessors_generic
-
module type Creators_generic
-
module type Equal_m
-
module Finished_or_unfinished
-
module type For_deriving
-
module type Compare_m
-
module type Equal_m
-
module type M_of_sexp
-
module type M_sexp_grammar
-
module type Sexp_of_m
-
-
module type M_of_sexp
-
module type M_sexp_grammar
-
module Merge_element
-
module Or_duplicate
-
module Poly
-
module type S_poly
-
module type Sexp_of_m
-
module Symmetric_diff_element
-
module Using_comparator
-
module Empty_without_value_restriction
-
argument 1-K
-
-
module Tree
-
module Build_increasing
-
-
-
module With_comparator
-
module With_first_class_module
-
module Without_comparator
-
-
module Maybe_bound
-
module Monad
-
module type Basic
-
module type Basic2
-
module type Basic3
-
module type Basic_indexed
-
module Ident
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type Infix
-
module type Infix2
-
module type Infix3
-
module type Infix_indexed
-
module Make
-
argument 1-X
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Make2
-
argument 1-X
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Make3
-
argument 1-X
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Make_indexed
-
argument 1-X
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Of_monad
-
argument 1-Monad
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
argument 2-M
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Of_monad2
-
argument 1-Monad
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
argument 2-M
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Of_monad3
-
argument 1-Monad
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
argument 2-M
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Of_monad_indexed
-
argument 1-Monad
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
argument 2-M
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S2
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S3
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S_indexed
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module type S_without_syntax
-
module Monad_infix
-
-
module type Syntax
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
-
module type Syntax2
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
-
module type Syntax3
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
-
module type Syntax_indexed
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
-
-
module Nothing
-
module Option
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Option_array
-
module Or_error
-
module Applicative_infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Ordered_collection_common
-
module Private
-
-
module Poly
-
module Popcount
-
module Pretty_printer
-
module Register_pp
-
argument 1-M
-
-
module type S
-
module Printf
-
module Result
-
module Error
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Export
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Sequence
-
module Expert
-
module Generator
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
-
module Infix
-
module Let_syntax
-
module Let_syntax
-
module Open_on_rhs
-
-
-
module Monad_infix
-
module Step
-
-
module Set
-
module type Accessors0
-
module Named
-
-
module type Accessors1
-
module Named
-
-
module type Accessors2
-
module Named
-
-
module type Accessors2_with_comparator
-
module Named
-
-
module type Accessors_generic
-
module Named
-
-
module type Compare_m
-
module type Creators0
-
module type Creators1
-
module type Creators2
-
module type Creators2_with_comparator
-
module type Creators_and_accessors0
-
module Named
-
-
module type Creators_and_accessors1
-
module Named
-
-
module type Creators_and_accessors2
-
module Named
-
-
module type Creators_and_accessors2_with_comparator
-
module Named
-
-
module type Creators_generic
-
module type Elt_plain
-
module type Equal_m
-
module type For_deriving
-
module type Compare_m
-
module type Equal_m
-
module type M_of_sexp
-
module type M_sexp_grammar
-
module type Sexp_of_m
-
-
module type M_of_sexp
-
module type M_sexp_grammar
-
module Merge_to_sequence_element
-
module Named
-
module type Sexp_of_m
-
module Using_comparator
-
module Empty_without_value_restriction
-
argument 1-Elt
-
-
module Named
-
-
module With_comparator
-
module With_first_class_module
-
module Without_comparator
-
-
module Sexpable
-
module Of_sexpable
-
argument 1-Sexpable
-
argument 2-M
-
-
module Of_sexpable1
-
argument 1-Sexpable
-
argument 2-M
-
-
module Of_sexpable2
-
argument 1-Sexpable
-
argument 2-M
-
-
module Of_sexpable3
-
argument 1-Sexpable
-
argument 2-M
-
-
module Of_stringable
-
argument 1-M
-
-
module type S
-
module type S1
-
module type S2
-
module type S3
-
-
module Sign
-
module Sign_or_nan
-
module Source_code_position
-
module Staged
-
module String
-
module Caseless
-
module Escaping
-
module Search_pattern
-
-
module Stringable
-
module type S
-
-
module Sys
-
module type T1
-
module type T2
-
module type T3
-
module Type_equal
-
module type Injective
-
module type Injective2
-
module Uchar
-
module Uniform_array
-
module Unit
-
module Variant
-
module With_return
-
module Word_size
-
-
-
library base.base_internalhash_types
-
module Base_internalhash_types
-
-
library base.caml
-
module Caml
-
module In_channel
-
module Out_channel
-
-
-
library base.md5
-
module Md5_lib
-
-
library base.shadow_stdlib
-
module Shadow_stdlib
-
module In_channel
-
module Out_channel
-
-
The type of a set. The first type parameter identifies the type of the element, and the second identifies the comparator, which determines the comparison function that is used for ordering elements in this set. Many operations (e.g., union
), require that they be passed sets with the same element type and the same comparator type.
type ('k, 'cmp) comparator = ( 'k, 'cmp ) Comparator.Module.t
val invariants : ( _, _ ) t -> bool
Tests internal invariants of the set data structure. Returns true on success.
val comparator_s : ( 'a, 'cmp ) t -> ( 'a, 'cmp ) Comparator.Module.t
Returns a first-class module that can be used to build other map/set/etc with the same notion of comparison.
val comparator : ( 'a, 'cmp ) t -> ( 'a, 'cmp ) Comparator.t
val empty : ( 'a, 'cmp ) Comparator.Module.t -> ( 'a, 'cmp ) t
Creates an empty set based on the provided comparator.
val singleton : ( 'a, 'cmp ) Comparator.Module.t -> 'a -> ( 'a, 'cmp ) t
Creates a set based on the provided comparator that contains only the provided element.
val length : ( _, _ ) t -> int
Returns the cardinality of the set. O(1)
.
val is_empty : ( _, _ ) t -> bool
is_empty t
is true
iff t
is empty. O(1)
.
val mem : ( 'a, _ ) t -> 'a -> bool
mem t a
returns true
iff a
is in t
. O(log n)
.
add t a
returns a new set with a
added to t
, or returns t
if mem t a
. O(log n)
.
remove t a
returns a new set with a
removed from t
if mem t a
, or returns t
otherwise. O(log n)
.
union t1 t2
returns the union of the two sets. O(length t1 + length t2)
.
val union_list :
( 'a, 'cmp ) Comparator.Module.t ->
( 'a, 'cmp ) t list ->
( 'a, 'cmp ) t
union c list
returns the union of all the sets in list
. The comparator
argument is required for the case where list
is empty. O(max(List.length list, n log n))
, where n
is the sum of sizes of the input sets.
inter t1 t2
computes the intersection of sets t1
and t2
. O(length t1 +
length t2)
.
diff t1 t2
computes the set difference t1 - t2
, i.e., the set containing all elements in t1
that are not in t2
. O(length t1 + length t2)
.
val symmetric_diff :
( 'a, 'cmp ) t ->
( 'a, 'cmp ) t ->
( 'a, 'a ) Either.t Sequence.t
symmetric_diff t1 t2
returns a sequence of changes between t1
and t2
. It is intended to be efficient in the case where t1
and t2
share a large amount of structure.
compare_direct t1 t2
compares the sets t1
and t2
. It returns the same result as compare
, but unlike compare, doesn't require arguments to be passed in for the type parameters of the set. O(length t1 + length t2)
.
val hash_fold_direct : 'a Hash.folder -> ( 'a, 'cmp ) t Hash.folder
Hash function: a building block to use when hashing data structures containing sets in them. hash_fold_direct hash_fold_key
is compatible with compare_direct
iff hash_fold_key
is compatible with (comparator s).compare
of the set s
being hashed.
equal t1 t2
returns true
iff the two sets have the same elements. O(length t1 +
length t2)
val exists : ( 'a, _ ) t -> f:( 'a -> bool ) -> bool
exists t ~f
returns true
iff there exists an a
in t
for which f a
. O(n)
, but returns as soon as it finds an a
for which f a
.
val for_all : ( 'a, _ ) t -> f:( 'a -> bool ) -> bool
for_all t ~f
returns true
iff for all a
in t
, f a
. O(n)
, but returns as soon as it finds an a
for which not (f a)
.
val count : ( 'a, _ ) t -> f:( 'a -> bool ) -> int
count t
returns the number of elements of t
for which f
returns true
. O(n)
.
val sum :
(module Container.Summable with type t = 'sum) ->
( 'a, _ ) t ->
f:( 'a -> 'sum ) ->
'sum
sum t
returns the sum of f t
for each t
in the set. O(n)
.
val find : ( 'a, _ ) t -> f:( 'a -> bool ) -> 'a option
find t f
returns an element of t
for which f
returns true, with no guarantee as to which element is returned. O(n)
, but returns as soon as a suitable element is found.
val find_map : ( 'a, _ ) t -> f:( 'a -> 'b option ) -> 'b option
find_map t f
returns b
for some a
in t
for which f a = Some b
. If no such a
exists, then find
returns None
. O(n)
, but returns as soon as a suitable element is found.
val find_exn : ( 'a, _ ) t -> f:( 'a -> bool ) -> 'a
Like find
, but throws an exception on failure.
val nth : ( 'a, _ ) t -> int -> 'a option
nth t i
returns the i
th smallest element of t
, in O(log n)
time. The smallest element has i = 0
. Returns None
if i < 0
or i >= length t
.
remove_index t i
returns a version of t
with the i
th smallest element removed, in O(log n)
time. The smallest element has i = 0
. Returns t
if i < 0
or i >= length t
.
is_subset t1 ~of_:t2
returns true iff t1
is a subset of t2
.
are_disjoint t1 t2
returns true
iff is_empty (inter t1 t2)
, but is more efficient.
module Named : sig ... end
Named
allows the validation of subset and equality relationships between sets. A Named.t
is a record of a set and a name, where the name is used in error messages, and Named.is_subset
and Named.equal
validate subset and equality relationships respectively.
val of_list : ( 'a, 'cmp ) Comparator.Module.t -> 'a list -> ( 'a, 'cmp ) t
The list or array given to of_list
and of_array
need not be sorted.
val of_sequence :
( 'a, 'cmp ) Comparator.Module.t ->
'a Sequence.t ->
( 'a, 'cmp ) t
val of_array : ( 'a, 'cmp ) Comparator.Module.t -> 'a array -> ( 'a, 'cmp ) t
val to_list : ( 'a, _ ) t -> 'a list
to_list
and to_array
produce sequences sorted in ascending order according to the comparator.
val to_array : ( 'a, _ ) t -> 'a array
val of_sorted_array :
( 'a, 'cmp ) Comparator.Module.t ->
'a array ->
( 'a, 'cmp ) t Or_error.t
Create set from sorted array. The input must be sorted (either in ascending or descending order as given by the comparator) and contain no duplicates, otherwise the result is an error. The complexity of this function is O(n)
.
val of_sorted_array_unchecked :
( 'a, 'cmp ) Comparator.Module.t ->
'a array ->
( 'a, 'cmp ) t
Similar to of_sorted_array
, but without checking the input array.
val of_increasing_iterator_unchecked :
( 'a, 'cmp ) Comparator.Module.t ->
len:int ->
f:( int -> 'a ) ->
( 'a, 'cmp ) t
of_increasing_iterator_unchecked c ~len ~f
behaves like of_sorted_array_unchecked c
(Array.init len ~f)
, with the additional restriction that a decreasing order is not supported. The advantage is not requiring you to allocate an intermediate array. f
will be called with 0, 1, ... len - 1
, in order.
val stable_dedup_list : ( 'a, _ ) Comparator.Module.t -> 'a list -> 'a list
stable_dedup_list
is here rather than in the List
module because the implementation relies crucially on sets, and because doing so allows one to avoid uses of polymorphic comparison by instantiating the functor at a different implementation of Comparator
and using the resulting stable_dedup_list
.
val map :
( 'b, 'cmp ) Comparator.Module.t ->
( 'a, _ ) t ->
f:( 'a -> 'b ) ->
( 'b, 'cmp ) t
map c t ~f
returns a new set created by applying f
to every element in t
. The returned set is based on the provided comparator
. O(n log n)
.
val filter_map :
( 'b, 'cmp ) Comparator.Module.t ->
( 'a, _ ) t ->
f:( 'a -> 'b option ) ->
( 'b, 'cmp ) t
Like map
, except elements for which f
returns None
will be dropped.
filter t ~f
returns the subset of t
for which f
evaluates to true. O(n log
n)
.
val fold : ( 'a, _ ) t -> init:'accum -> f:( 'accum -> 'a -> 'accum ) -> 'accum
fold t ~init ~f
folds over the elements of the set from smallest to largest.
val fold_result :
( 'a, _ ) t ->
init:'accum ->
f:( 'accum -> 'a -> ( 'accum, 'e ) Result.t ) ->
( 'accum, 'e ) Result.t
fold_result ~init ~f
folds over the elements of the set from smallest to largest, short circuiting the fold if f accum x
is an Error _
val fold_until :
( 'a, _ ) t ->
init:'accum ->
f:( 'accum -> 'a -> ( 'accum, 'final ) Container.Continue_or_stop.t ) ->
finish:( 'accum -> 'final ) ->
'final
fold_until t ~init ~f
is a short-circuiting version of fold
. If f
returns Stop _
the computation ceases and results in that value. If f
returns Continue _
, the fold will proceed.
val fold_right :
( 'a, _ ) t ->
init:'accum ->
f:( 'a -> 'accum -> 'accum ) ->
'accum
Like fold
, except that it goes from the largest to the smallest element.
val iter : ( 'a, _ ) t -> f:( 'a -> unit ) -> unit
iter t ~f
calls f
on every element of t
, going in order from the smallest to largest.
val iter2 :
( 'a, 'cmp ) t ->
( 'a, 'cmp ) t ->
f:( [ `Left of 'a | `Right of 'a | `Both of 'a * 'a ] -> unit ) ->
unit
Iterate two sets side by side. Complexity is O(m+n)
where m
and n
are the sizes of the two input sets. As an example, with the inputs 0; 1
and 1; 2
, f
will be called with `Left 0
; `Both (1, 1)
; and `Right 2
.
if a, b = partition_tf set ~f
then a
is the elements on which f
produced true
, and b
is the elements on which f
produces false
.
val min_elt : ( 'a, _ ) t -> 'a option
Returns the smallest element of the set. O(log n)
.
val max_elt : ( 'a, _ ) t -> 'a option
Returns the largest element of the set. O(log n)
.
val choose : ( 'a, _ ) t -> 'a option
returns an arbitrary element, or None
if the set is empty.
split t x
produces a triple (t1, maybe_x, t2)
where t1
is the set of elements strictly less than x
, maybe_x
is the member (if any) of t
which compares equal to x
, and t2
is the set of elements strictly larger than x
.
if equiv
is an equivalence predicate, then group_by set ~equiv
produces a list of equivalence classes (i.e., a set-theoretic quotient). E.g.,
let chars = Set.of_list ['A'; 'a'; 'b'; 'c'] in
let equiv c c' = Char.equal (Char.uppercase c) (Char.uppercase c') in
group_by chars ~equiv
produces:
[Set.of_list ['A';'a']; Set.singleton 'b'; Set.singleton 'c']
group_by
runs in O(n^2) time, so if you have a comparison function, it's usually much faster to use Set.of_list
.
val to_sequence :
?order:[ `Increasing | `Decreasing ] ->
?greater_or_equal_to:'a ->
?less_or_equal_to:'a ->
( 'a, 'cmp ) t ->
'a Sequence.t
to_sequence t
converts the set t
to a sequence of the elements between greater_or_equal_to
and less_or_equal_to
inclusive in the order indicated by order
. If greater_or_equal_to > less_or_equal_to
the sequence is empty. Cost is O(log n) up front and amortized O(1) for each element produced.
val binary_search :
( 'a, 'cmp ) t ->
compare:( 'a -> 'key -> int ) ->
[ `Last_strictly_less_than
| `Last_less_than_or_equal_to
| `Last_equal_to
| `First_equal_to
| `First_greater_than_or_equal_to
| `First_strictly_greater_than ] ->
'key ->
'a option
binary_search t ~compare which elt
returns the element in t
specified by compare
and which
, if one exists.
t
must be sorted in increasing order according to compare
, where compare
and elt
divide t
into three (possibly empty) segments:
| < elt | = elt | > elt |
binary_search
returns an element on the boundary of segments as specified by which
. See the diagram below next to the which
variants.
binary_search
does not check that compare
orders t
, and behavior is unspecified if compare
doesn't order t
. Behavior is also unspecified if compare
mutates t
.
val binary_search_segmented :
( 'a, 'cmp ) t ->
segment_of:( 'a -> [ `Left | `Right ] ) ->
[ `Last_on_left | `First_on_right ] ->
'a option
binary_search_segmented t ~segment_of which
takes a segment_of
function that divides t
into two (possibly empty) segments:
| segment_of elt = `Left | segment_of elt = `Right |
binary_search_segmented
returns the element on the boundary of the segments as specified by which
: `Last_on_left
yields the last element of the left segment, while `First_on_right
yields the first element of the right segment. It returns None
if the segment is empty.
binary_search_segmented
does not check that segment_of
segments t
as in the diagram, and behavior is unspecified if segment_of
doesn't segment t
. Behavior is also unspecified if segment_of
mutates t
.
module Merge_to_sequence_element : sig ... end
Produces the elements of the two sets between greater_or_equal_to
and less_or_equal_to
in order
, noting whether each element appears in the left set, the right set, or both. In the both case, both elements are returned, in case the caller can distinguish between elements that are equal to the sets' comparator. Runs in O(length t + length t').
val merge_to_sequence :
?order:[ `Increasing | `Decreasing ] ->
?greater_or_equal_to:'a ->
?less_or_equal_to:'a ->
( 'a, 'cmp ) t ->
( 'a, 'cmp ) t ->
( 'a, 'a ) Merge_to_sequence_element.t Sequence.t
M
is meant to be used in combination with OCaml applicative functor types:
module type Sexp_of_m = sig ... end
module type M_of_sexp = sig ... end
module type M_sexp_grammar = sig ... end
module type Compare_m = sig ... end
module type Equal_m = sig ... end
module type Hash_fold_m = Hasher.S
val m__t_of_sexp :
(module M_of_sexp with type comparator_witness = 'cmp and type t = 'elt) ->
Sexp.t ->
( 'elt, 'cmp ) t
val m__t_sexp_grammar :
(module M_sexp_grammar with type t = 'elt) ->
( 'elt, 'cmp ) t Sexplib0.Sexp_grammar.t
val hash_fold_m__t :
(module Hash_fold_m with type t = 'elt) ->
Hash.state ->
( 'elt, _ ) t ->
Hash.state
val hash_m__t : (module Hash_fold_m with type t = 'elt) -> ( 'elt, _ ) t -> int
module Poly : sig ... end
A polymorphic Set.
module Using_comparator : sig ... end
Using comparator is a similar interface as the toplevel of Set
, except the functions take a ~comparator:('elt, 'cmp) Comparator.t
where the functions at the toplevel of Set
takes a ('elt, 'cmp) comparator
.
Modules and module types for extending Set
For use in extensions of Base, like Core
.
module With_comparator : sig ... end
module With_first_class_module : sig ... end
module Without_comparator : sig ... end
module type For_deriving = sig ... end
module type S_poly = sig ... end
module type Accessors0 = sig ... end
module type Accessors1 = sig ... end
module type Accessors2 = sig ... end
module type Accessors2_with_comparator = sig ... end
module type Accessors_generic = sig ... end
module type Creators0 = sig ... end
module type Creators1 = sig ... end
module type Creators2 = sig ... end
module type Creators2_with_comparator = sig ... end
module type Creators_and_accessors0 = sig ... end
module type Creators_and_accessors1 = sig ... end
module type Creators_and_accessors2 = sig ... end
module type Creators_and_accessors2_with_comparator = sig ... end
module type Creators_generic = sig ... end
module type Elt_plain = sig ... end